Real-Time 3D LiDAR-Based Obstacle Avoidance for UAV Using Sector-Filtering Algorithm

1. Introduction

Thanks to their flexibility and high mobility, unmanned aerial vehicles (UAVs) have gained enormous popularity in recent years for real-world applications, i.e., military missions, search-and-rescue, and delivery^[1-5]. In line with the growth of its popularity, the autonomous navigation of UAVs has rapidly been under development and urging the system to be more applicable and efficient over time^[6-9]. Obstacle avoidance is one of the main challenges in UAV autonomous navigation. Therefore, providing the best possible solutions for efficient obstacle detection is needed since it is inseparable from obstacle avoidance.

Based on the type of sensors, generally, obstacle detection techniques can be divided into two categories: two-dimensional (2D) perception and three-dimensional (3D) perception. Some existing works proposed obstacle detection and avoidance techniques employing 2D-perception sensors^[10-12]. In [10], a real- time obstacle avoidance in dynamic environments where the mobile robot and the obstacle are moving was proposed by utilizing 2D LiDAR. In [11], a 2D LiDAR was employed to detect obstacles and translate online the essential geometric information of the obstacle- dense environments. In [12], a combination of mono-camera and 2D LiDAR was proposed for predicting the velocities and positions of surrounding obstacles through optical flow estimation, object detection, and sensor fusion. Although the techniques above that utilized 2D-perception sensors offered low computational complexity, which directly affects a short computational time, it has a significantly limited perspective that is only in 2D planes and thus results in one-sided field-of-view (FoV)^[13,14]. Unfortunately, the real environment is in 3D, which makes 2D-perception solutions insufficient, thus forcing solutions for obstacle detection from a 3D perspective to be provided.

Several works have proposed obstacle detection and avoidance employing depth cameras as 3D-perception sensors^[15-19]. In [15], a stereo frame-based camera was employed to avoid obstacles and safely navigate through an unknown cluttered environment. In [16], an active-sensing-based obstacle avoidance paradigm was proposed utilizing a stereo camera with an independent rotational degree of freedom to sense the obstacles actively. In [17], the ZED depth camera was utilized to detect and extract obstacles for robot navigation. In [18], a stereo camera system provided a point cloud of the environment to detect obstacles through time. In [19], a convex optimization framework was proposed utilizing a depth camera for obstacle detection that is vital for real-time autonomous vehicle operations. However, existing works that utilized depth cameras have limited detection range, limited FoV with less than 360 degrees, and environmental constraints, i.e., illumination, wind, temperature, atmospheric condition, environmental, and density. The limitations above notably contribute to lowering the detection accuracy. Dissimilar to depth camera characteristics, 3D LiDAR enables a broader range and FoV with its 360-degree view coverage^[25]. Moreover, the 3D LiDAR is keenly robust to environmental obstructions that improve detection accuracy due to the advantage of laser light compared to an image frame^[26]. By considering such conditions, employing 3D LiDAR can be one of the best solutions to improve the accuracy and FoV of obstacle avoidance in the real environment.

Some of the existing works employed 3D LiDAR for obstacle avoidance^[20-24]. In [20], a 3D LiDAR was employed to detect dynamic obstacles using an end-to-end sparse tensor-based deep neural network. In [21], a fully autonomous UAV system was proposed that enables flying safely in cluttered environments while avoiding dynamic obstacles using 3D LiDAR. In [22], a real point cloud from 3D LiDAR was augmented with synthetic obstacles for autonomous navigation. In [23], the utilization of 3D LiDAR for high-accuracy and high-efficiency 3D sensing was investigated and applied to intelligent transportation systems. In [24], an obstacle detection that addressed a partial scanning data availability issue was proposed employing 3D LiDAR. However, processing high-resolution and massive point cloud data from 3D LiDAR contributes to exponentially escalating computational burden.In consequence, computational time also rises exponentially. Considering the conditions above, those techniques can be challenging to apply in the UAV obstacle avoidance system where low computational time is required because of its high mobility^[27].

This study introduces a sector-filtering algorithm to reduce processing point clouds for obstacle detection using 3D LiDAR. To summarize the contribution of current study, Table 1 illustrated a comparison between existing 3D LiDAR literature. To be specified, the point clouds in three-dimensional space from 3D LiDAR are sectorized into eight zones. In this manner, all the point clouds in the 3D space can be mapped into the eight zones according to their location in degrees. Subsequently, an angular filter and intensity filter are employed in each sector to reduce the dimension of point clouds from 3D to 2D points.

Thus, smaller data dimensions that affect lower computational complexity and computational time can be achieved.

Fig. 1.

Estimated LiDAR orientation (red arrow) and 3D point cloud (colored dots)

1.1 Contributions

To the best of the authors’ knowledge, few works employ 3D LiDAR and reduce its computational complexity for real-time UAV obstacle avoidance. Table 1 shows that current proposed system includes avoidance system with [TeX:] $$360^{\circ}$$ degree LiDAR. In comparison with existing reference, the current approach does not require any training method in order to detect an object. Therefore, the main contributions are specified as follows:

· To highlight our contribution, this study considers a summary of existing algorithms with proximity- based UAV avoidance in Table 2. Based on the table, this study proposed sector filtering algorithm for 3D LiDAR because existing avoidance systems are limited to 2D point cloud. Moreover, 3D LiDAR serves a higher resolution and accuracy in terms of detecting object (up to 100 meters).

· Due to the large number of 3D point clouds compared to the 2D ones, this study proposed sector filtering algorithm^[28]. In comparison with related works of 3D LiDAR, the proposed algorithm could reduce computational time because of less number of point cloud. However, the tradeoff is that the trajectory will be longer than 3D-based SLAM because there is no mapping process. In exchange, UAV could react faster to avoid incoming obstacle.

· The proposed algorithm is integrated with 3D trajectory planning for UAVs.

· Performance of the proposed algorithm is validated through experiments in the real environment.

1.2 Paper Organization

The rest of this paper is organized as follows. The idea of the sector-filtering algorithm for real-time obstacle detection is introduced and described in Section II. Section III presents obstacle detection and avoidance using 3D LiDAR for UAVs. The proposed algorithm’s experimental results and performance analysis are discussed in Section IV. Finally, this paper is concluded in Section V.

1.3 Notations

Matrices and vectors are denoted by upper-case and lower-case bold letters, respectively. The notations [TeX:] $$(\mathbf{B})^{\mathrm{T}} \text { and }(\mathbf{B})^{-1}$$ denote transpose and matrix inversion of [TeX:] $$\mathbf{B}$$, respectively. The notation [TeX:] $$\mathbb{R}$$ denotes a real number.

Ⅱ. Sector-filtering Algorithm for Real-time Obstacle Detection

This section presents the proposed sector-filtering algorithm for real-time obstacle detection. The objective of the algorithm is to reduce the computational complexity of processing massive and high-resolution point cloud data from 3D LiDAR. The algorithm consists of data acquisition, point cloud conversion, point cloud filtering, and obstacle mapping.

2.1 Data Acquisition

The initial phase of the proposed scheme involves collecting detailed point cloud information of the environment employing the Velodyne VLP-16 3D LiDAR sensor, which is affixed to the UAV. This sensor scans the surroundings in a full 360-degree range, capturing a multitude of points every second. The amassed point cloud offers an intricate depiction of the UAV’s surroundings, encompassing potential obstacles.

Without loss of generality, this study consider a similar approach with [25], where each LiDAR points is repre-sented as 3-Dimensional Cartesian coordinates (x, y, z). Then, the overall coordinates of point k is expressed as follows

where [TeX:] $$\kappa, \theta, \text { and } \phi$$ denote distance of a point from the origin, elevation angle, and azimuth angle of the 3D LiDAR, respectively.

Let us consider an object detected, where every part of the detected object is marked as a point cloud. Moreover, all the point clouds of the detected object can be denoted as [TeX:] $$\mathbf{P} \in \mathbb{R}^3.$$ Assumed K point clouds formed as detected objects, a single point cloud [TeX:] $$P_k \in \mathbf{P},$$ where [TeX:] $$k=\{1, \ldots, K\},$$ is located at [TeX:] $$x_k, y_k, z_k$$ in a 3D environment [TeX:] $$\mathbf{W} \in \mathbb{R}^3 .$$ Due to the limitation of LiDAR based detection to laser misalignment, some of the laser points did not bounce back from environment, resulting in zero value of k-th point cloud^[24]. Let [TeX:] $$P_k$$ be the variable to store a cartesian value whether an object is successfully detected or not^[29]. A point cloud is considered to be filled as a representative of the detected object when the [TeX:] $$P_k=1, \forall k \in K$$ and considered to be empty when the [TeX:] $$P_k=0, \forall k \in K$$, which can be expressed as

The generated point clouds [TeX:] $$\mathbf{P}$$ from the detected object in the environment [TeX:] $$\mathbf{W}$$ at time t can be expressed as

where [TeX:] $$x_K, y_K, \text { and } z_K$$ denote the length, width, and height of the detected object, respectively. The data format of each returned LiDAR point is a 4-tuple formed by its coordinate with respect to the LiDAR coordinate frame [TeX:] $$\mathbf{P}(x, y, z)$$ as well as its intensity denoted by ρ.

Fig. 2.

Diagram flow of 3D LiDAR avoidance.

2.2 Point Cloud Conversion

The raw point cloud data, denoted by [TeX:] $$\mathbf{P}(x, y, z)$$, collected from the 3D LiDAR sensor, as mentioned in the previous subsection, is in a binary file format. Unfortunately, data formed in binary format is not compatible with the Ardupilot robot operating system (ROS) message. Since this study employs ROS as a bridge for software control systems and hardware actuators, directly utilizing raw 3D point cloud data is unfeasible. Consequently, the raw point cloud data is required to be converted to a format compatible with the ROS message. In practice, the Point Cloud Library (PCL) software is employed in the conversion process to convert the raw Point Cloud data that is in binary format into a Point Cloud Data ROS format^[30]. At each time step, the raw point cloud data [TeX:] $$\mathbf{P}(x, y, z)$$ are published in the format of PCL ROS message as pcl∶∶Point XYZ^[29]

2.3 Obstacles Mapping

After the point cloud data have been successfully converted, all the detected obstacles are mapped and unified to acknowledge the location of the detected obstacles in the environment [TeX:] $$\mathbf{W}$$. First, all the detected obstacles at time t are mapped and gathered in the environment, denoted by [TeX:] $$\mathbf{C}$$. Assume the 3D LiDAR has successfully detected N obstacles; the obstacles map then can be expressed as

where [TeX:] $$\mathbf{P}_{n,} n=1,2, \ldots, N$$ denotes the generated point clouds [TeX:] $$\mathbf{P}$$ of each detected obstacle at time t. The generated point clouds of a single detected obstacle [TeX:] $$\mathbf{P}_n$$ are formed by K point clouds, which can be expressed as

where [TeX:] $$P_{k,} k=1,2, \ldots, K$$ denotes the k-th point cloud of the single detected obstacle. All the generated point clouds can then be represented as unified point clouds from the detected obstacles. It is important to note that each generated point clouds [TeX:] $$\mathbf{P}_n$$ is not overlapped with other point clouds [TeX:] $$\mathbf{P}_{j \neq n}$$ which can be expressed as

Finally, all detected obstacles in the environment at time t can be expressed

where N denotes the number of detected obstacles at time t.

2.4 Point Cloud Filtering

In order to improve the detection accuracy, noise, and unwanted point clouds that are irrelevant to the detected obstacles must be removed through the point cloud filtering process. The filtration procedure includes utilizing statistical filters like outlier elimination and voxel grid down-sampling. These filters aid in eliminating undesired data points and diminishing the overall size of the point cloud data, simplifying the processing task. The filtering process generally consists of an angular filter and an intensity filter. However, a pre-processing filter is introduced to sharply reduce the noise in horizontal and vertical planes of the point clouds [TeX:] $$\mathbf{P}.$$ The pre-processing for the horizontal plane is done by setting a threshold based on the distance from each point to the origin, which can be expressed as follows

where [TeX:] $$\delta_{\mathrm{h}}$$ denotes the threshold distance in horizontal. Moreover, the pre-processing for the vertical plane can be done by setting a threshold based on the vertical location of each point, which can be expressed as follows

where [TeX:] $$\delta_{\mathrm{v}}$$ denotes the maximum vertical distance between the origin and each point. In addition, the noises and data outliers can be removed by employing a median filter, which can be expressed as follows

where [TeX:] $$\hat{z}\left(x_j, z_j\right)$$ denotes new vertical coordinate of the point at [TeX:] $$\left(x_j, y_j\right)$$, the [TeX:] $$\mathbf{Med}\{\cdot\}$$ operator is employed to calculate the median of a set of data, [TeX:] $$z\left(x_i, y_i\right)$$ represents the vertical point at coordinate [TeX:] $$\left(x_j, y_j\right)$$ coordinate, and Γ denotes the neighbourhood centered on the point at coordinate [TeX:] $$\left(x_j, y_j\right)$$.

Angular Filter : The angular filter is designed to remove the noises and data outliers concerning the elevation angle [TeX:] $$(\theta)$$ and azimuth angle [TeX:] $$(\phi)$$ of the 3D LiDAR. Specifically, the minimum elevation angle is filtered by setting a threshold on the azimuth angle, which should be in the range of minimum and maximum azimuth angle, which can be expressed as follows

where [TeX:] $$\theta_{\min }, \Phi_{\min }, \Phi_{\max } \text { and } \mu$$ denote the minimum elevation angle, minimum azimuth angle, maximum azimuth angle, and constant parameter, respectively, similarly, the maximum elevation angle is filtered by setting a threshold on the azimuth angle, which should be in the range of minimum and maximum azimuth angle, which can be expressed as follows

where [TeX:] $$\theta_{\max }$$ denotes maximum elevation angle and μ is the constant parameter.

Intensity Filter : The intensity filter is designed to remove the noises and data outliers based on distance from each point to the intensity of the point clouds that should be in the range of minimum and maximum intensity, which can be expressed as follows

where the term [TeX:] $$\left(x^2+y^2+z^2\right)^{1 / 2}$$ refers to distance from each point, [TeX:] $$\delta_{\mathrm{h}}$$ is the threshold distance in horizontal, μ is the constant parameter, Ψ denotes the intensity of point clouds [TeX:] $$\mathbf{P}, \Lambda_{\min }$$ is the minimum intensity threshold for point clouds, and [TeX:] $$\Lambda_{\max }$$ is the maximum intensity threshold for point clouds. Furthermore, the intensity of point clouds in the vertical location can be filtered by setting a threshold with minimum and maximum intensity, which can be expressed as follows

where [TeX:] $$|z|$$ refers to the vertical location of each point, [TeX:] $$\delta \mathrm{v}$$ denotes the vertical distance threshold, and μ is the constant parameter.

2.5 Remapping based on Point Cloud Filtering

The filtered point cloud data is subsequently utilized as inputs of a sectoring process, each delineating a distinct section of the environment. The sector is generated by applying a threshold to the point cloud data, where points falling within the threshold are assigned a value of 1, while those outside it are assigned a value of 0. The classified obstacle maps are combined to create a single map representing the entire environment.

2.6 Sectorization of Obstacles

Following the filtering stage, all the detected obstacles [TeX:] $$\mathbf{C}$$ are sectorized in order to classify their locations in the environment [TeX:] $$\mathbf{W}$$ from the FoV of UAV at time t. As previously mentioned in Section I, the leverage of employing 3D LiDAR is the 360o FoV that enables wider detection for the UAV. By utilizing the benefits mentioned earlier of the 3D LiDAR, the information about the detected obstacles can be more specified. In this study, the FoV of 3D LiDAR is sectorized into 8 sectors, which implies Sector 1 can be determined as [TeX:] $$S_1 \in\left[0^{\circ}, 45^{\circ}\right],$$ Sector 2 as [TeX:] $$S_2 \in\left[46^{\circ}, 90^{\circ}\right],$$ Sector 3 as [TeX:] $$S_3 \in\left[91^{\circ}, 135^{\circ}\right],$$ Sector 4 as [TeX:] $$S_4 \in\left[136^{\circ}, 180^{\circ}\right],$$ Sector 5 as [TeX:] $$S_5 \in\left[181^{\circ}, 225^{\circ}\right],$$ Sector 6 as [TeX:] $$S_6 \in\left[226^{\circ}, 270^{\circ}\right],$$ Sector 7 as [TeX:] $$S_7 \in\left[271^{\circ}, 315^{\circ}\right],$$ and Sector 8 as [TeX:] $$S_8 \in\left[316^{\circ}, 360^{\circ}\right].$$

A single obstacle [TeX:] $$\mathbf{P}_n(x, y, z)$$ can be categorized as located in Sector 1,2,3,4,5,6,7, or 8 if its azimuth angle [TeX:] $$(\phi),$$ from the spherical coordinates [TeX:] $$(\kappa, \theta, \phi)$$ which can be obtained by converting its cartesian coordinates (x, y, z), that is the angle in the x-y plane with respect to the positive direction of the x-axis, is in the range of [TeX:] $$\left[0^{\circ}, 45^{\circ}\right],\left[46^{\circ}, 90^{\circ}\right],\left[91^{\circ}, 135^{\circ}\right],\left[136^{\circ}, 180^{\circ}\right],\left[181^{\circ}, 225^{\circ}\right],\left[226^{\circ}, 270^{\circ}\right],\left[271^{\circ}, 315^{\circ}\right], \text { or }\left[316^{\circ},360^{\circ}],\right.$$ respectively. Moreover, the location of obstacles can be detected, whether in the upper or below of the UAV, based on the elevation angle [TeX:] $$(\theta),$$ which is the angle to the positive direction of the z-axis.

Fig. 3.

Hardware configuration of the proposed 3D LiDAR UAV avoidance.

Ⅲ. Real-time Obstacle Avoidance and Navigation for UAV using 3D LiDAR

Following the obstacle detection employing the proposed sector-filtering algorithm with the 3D LiDAR, the UAV executes an avoidance maneuver in real time and continues navigating toward a target location. In order for the UAV to successfully navigate to the target location while avoiding obstacles along the way, the UAV navigation is divided into an obstacle avoidance stage and a navigation stage, which can be described as follows

3.1 UAV Real-time Obstacle Avoidance

Let us consider a scenario where a UAV equipped with a 3D LiDAR flies to a target location and meets obstacles along the way. The UAV detects the obstacles employing the proposed sector-filtering algorithm with the 3D LiDAR mentioned in Section II and avoids the detected obstacles in real time by employing a Kalman filter algorithm. The Kalman filter is employed because of its well-known ability to predict position accurately by minimizing error measurement from the noises, thus increasing navigation accuracy. In the Kalman filter algorithm, there are two phases which can be referred to as a prediction phase and an update phase.

Pr ediction Phase: In the prediction phase, the Kalman filter assists the UAV in predicting its next position in the environment while acknowledging the surrounding obstacles at time t. In other words, the prediction phase is to estimate the avoidance maneuver for the UAV at each time t. The next position of UAV at time t can be predicted by

where [TeX:] $$\bar{s}^{(t)}$$ denotes a predicted state at t-th time, [TeX:] $$s^{(t-1)}$$ denotes the estimated state at t - 1-th time, [TeX:] $$\mathrm{F}_{\mathrm{UAV}}$$ denotes state transition matrix representing motion model of the UAV, [TeX:] $$v_{\mathrm{UAV}}^{(t)}$$ denotes velocity of the UAV at t-th time, and [TeX:] $$\mathrm{C}_{\mathrm{ctr}}$$ denotes control-input matrix i.e., velocity or acceleration command input. Moreover, the prediction of state covariance matrix at t-th time, denoted by [TeX:] $$\overline{\mathbf{P}}_s^{(t)},$$ can be expressed as

where [TeX:] $$\mathbf{P}_s^{(t-1)}$$ is the predicted state covariance matrix at t - 1-th time and [TeX:] $$\mathbf{W}_{\text {noise }}$$ denotes the process noise covariance matrix.

Update Phase: Following the prediction phase, the update phase is designated to update the position of the UAV at each time t after the avoidance maneuver. The position of the UAV at time t can be updated by

where [TeX:] $$s^{(t)}$$ denotes estimated update state at t-th time. [TeX:] $$\bar{\Lambda}^{(t)}$$ is the estimation of avoidance variable at t-th time, which can be expressed as

where [TeX:] $$Q^{(t)}$$ represents the 3D LiDAR measurement at t-th time and [TeX:] $$\mathbf{M}$$ denotes the predicted measurement matrix of the generated 3D map from 3D LiDAR. [TeX:] $$K^{(t)}$$ represents the Kalman gain at t-th time, which can be formulated as

where [TeX:] $$L^{(t)}$$ denotes residual covariance, which can be expressed as

where [TeX:] $$\mathbf{Z}_{\text {noise }}$$ is the measurement of noise covariance matrix. Finally, the state covariance at t-th time can be updated by

where [TeX:] $$\mathbf{I}$$ denotes an identity matrix.

3.2 UAV Navigation

Let us assume the location of the UAV, which is denoted by g in the [TeX:] $$\mathbf{W}$$ environment, is estimated using the aforementioned Kalman filter algorithm. The UAV is located at [TeX:] $$(x, y, z) \in \mathbf{W}$$ at time t, and can be expressed as

At the initial time t = 0, the location of the UAV in an unknown environment [TeX:] $$\mathbf{W}$$ is initialized at (0, 0, 0) which can be expressed as

In the navigation process, the UAV moves from the initial point [TeX:] $$X_0$$ to the goal point [TeX:] $$X_F.$$ The displacement of the UAV generates a trajectory. The trajectory of the UAV in the map of environment [TeX:] $$\mathbf{W}$$ can be expressed as

Meanwhile, the motion of the UAV [TeX:] $$r_t$$ during the flight maneuver at time t is given by

As the environment condition [TeX:] $$\mathbf{W}$$ and location [TeX:] $$g_t$$ of the UAV are updated over time, the environment W is observed from the initial time [TeX:] $$t_0$$ to time T. It can be expressed as

Subsequently, the trajectory of the UAV and map are estimated by

where p denotes the probability distribution of the trajectory of the UAV [TeX:] $$\mathrm{G}_t, \forall t \in[0, T]$$ and the environment [TeX:] $$\mathbf{W}$$ based on the motion control [TeX:] $$\left(o_1, r_1\right)$$ at the next time step t + 1.

The UAV moves from the initial point [TeX:] $$X_0$$ to a goal point [TeX:] $$X_F$$ through an obstacle in environment [TeX:] $$\mathbf{W}$$. The path planning for navigation is generated based on the estimated map environment [TeX:] $$\mathbf{W}$$ and location [TeX:] $$g_t$$ of the UAV.

Fig. 4.

Hardware implementation of UAV 3D LiDAR avoidance.

To generate a path, the environmental condition [TeX:] $$\mathbf{W} \subset \mathbb{R}^3$$ should acknowledge the free and occupied space in the map. A point in the 3D space [TeX:] $$f_k\left(x_k, y_k, z_k) \in \mathbb{R}^3\right.$$ is defined as occupied if the point is filled with a point cloud [TeX:] $$\mathbf{P}_k\left(x_k, y_{k,}, z_k\right) \in C .$$ Otherwise, it is defined as an accessible point. This can be expressed as

A set of occupied and free points [TeX:] $$f_k, \forall k \in K$$ is called an occupied and accessible space, respectively. An occupied space implies that an obstacle is located in that area, whereas a free space indicates that the area is free from obstacles. The occupied and free spaces are presented as occupancy grids.

Ⅳ. Experimental Results and Analysis

The performance of the proposed algorithm is validated through experiments conducted in real environments. The experimental setup can be seen in Fig. 3, where an Nvidia Jetson NX was utilized as an onboard PC to process the point cloud data from the Velodyne 3D LiDAR in real time. In order to minimize delay during data transmission, the onboard PC and the 3D LiDAR were connected using ethernet. The 3D LiDAR point cloud data processing and real- time generated UAV trajectory on the onboard PC were monitored using a laptop on the ground. This study employs a WiFi router connection to maintain a stable connection between ROS in the onboard PC and the ground control station. Fig. 4 depicts a configuration of sensors, onboard PC, and the UAV setup. A hexacopter tarot X6 was employed to enable carrying the loads. The 3D LiDAR, GPS sensor, onboard PC, and Pixhawk flight controller unit were loaded on the UAV. The proposed algorithm was implemented in Python. To be specified, the whole proposed algorithm was built and implemented in the Ardupilot and robot operating system (ROS) Melodic environment.

Figure 5(a) depicts an average detection time in milliseconds (ms) obtained from real time 3D LiDAR mapping from [31], current proposed system, and existing 2D LiDAR avoidance in [32]. The experiment was conducted by deploying an obstacle at random different angle of 8 sector and 20 meters distance with 10 times repetition. Based on obtained result, the proposed system is outperformed^[31] in term of average detection rate, since the proposed sector filtering algorithm reduces the total number of PCL. However, the trade-off of using the 3D LiDAR caused a higher detection time compared with existing 2D LiDAR avoidance in [32]. This is due to the lower resolution of 2D LiDAR scan; thus, the existing 2D based avoidance requires a lower computational complexity.

Fig. 5.

(a) Average detection time obtained from 10 trials for different scheme. (b) Average accuracy obtained from 20 trials for each trial distance.

Figure 5(b) presents the obstacle detection employing a sector-filtering algorithm and the results are compared with the real distance measurement. The experimental setup is described as follows:

· Consider low altitude UAV to calculate the error between measured and real distance;

· The experiment conducted by moving an obstacle at a fixed distance from one sector to another sector generated by proposed algorithm, therefore, the time elapsed for one distance and varying sector is 10 seconds;

· To validate the observation, this study consider 10 trials (random 8 sectors selection) for each fixed distance and approximate measurement by taking mean value;

· This experiment considers 9 variable distances which are [100, 98, 97, 96, 92, 90, 82, 80, 77] meters away from LiDAR.

As shown in the figure, the maximum error of obstacle detection employing the sector-filtering algorithm is below 4% in all the cases. The results show that the proposed sector-filtering algorithm could detect obstacles correctly in real-time.

Fig. 6(a) depicts the real-world experiment of filtered 3D LiDAR point cloud. It can be seen that the red dot indicates a laser scan ROS message that is obtained from the proposed algorithm. In contrast with Fig. 1, the obtained laser scan is less populated with a 3D point cloud. Therefore, it can reduce the computational burden of UAV while estimating the path that has to be taken to reach the destination. Fig. 6(b) depicts an experiment visualization of obstacle detection through the proposed algorithm. It can be seen that the algorithm will filter the 3D point cloud and divide it into 8 sectors. The red curve indicates the drone’s distance from the closest point cloud, and every sector will move dynamically according to the filtered point cloud. Moreover, for ease of use, the obtained distance is measured in meters and the sector angle in degrees. Fig. 6(c) shows that the maximum distance of a detected obstacle can go up to 100 meters. Therefore, UAVs can efficiently estimate and calculate the path from start to destination. In addition, with the real-time 8-sector estimation, the UAV can easily evade an incoming obstacle due to its long-range detection capability.

Fig. 6.

(a) Detected object/obstacle from 8 sectors of point cloud. (b) RVIZ visualization of 360° of 2D laser scan ROS message. (c) The detection range of the proposed system can work up to 100 meters.

Fig. 7 shows the real-world implementation of the proposed system in the hexacopter UAV. As can be seen from the figure, the UAV detects an obstacle after flying from the initial location, successfully avoids the obstacle, and then continues heading toward the target location. For ease of understanding, Fig. 7(a) shows the UAV successfully detects an obstacle after flying from the initial location marked as an orange dot. In addition, a red curve that appears in this follows Fig. 6(b) behavior, where each red curve represents generated sector filtering and distance from UAV to obstacle. Fig. 7(b) shows the UAV changed its flight directions to avoid the detected obstacle marked by a red triangle and red path as the trajectory of the UAV. Moreover, as shown in the figure, the UAV continuously senses obstacles around its position. Furthermore, Fig. 7(c) shows the UAV flies toward the target location marked as a green dot after successfully avoiding the obstacle while sensing the other obstacles.

Fig. 7.

The real-world implementation of the proposed system. The experimental results of UAV trajectory which (a) avoiding an obstacle, (b) finding a new path, (c) and continuing path to the end waypoint.

Ⅴ. Conclusion

This paper employed a sector-filtering algorithm to improve real-time obstacle avoidance of UAV using 3D LiDAR. The sector-filtering algorithm mitigated the high-computational complexity issue of processing high-resolution and massive point cloud data from 3D LiDAR at a time by employing sectoring and filtering processes. Therefore, the computational time for dynamic obstacle detection in the 360-degree FoV was significantly reduced, and real-time obstacle avoidance was performed. The proposed algorithm was validated through experiments conducted in a real environment. The results show that the obstacles have been successfully detected within the 100-meter range, and the UAV avoidance maneuver is performed in real time. The future research directions are described as follows:

· Due to the limitation of the current system that there is no mapping process, it will be difficult for the UAV to maneuver in complex environments. The integration of mapping and optimized pathplanning is considered as an appealing future research direction.

· A larger number of UAVs with a cooperative scheme such as multi-cooperative UAVs has potentially integrated with the proposed sector-filtering algorithm in each UAV.