Incorporation of Potential Fields and Motion Primitives for the Collision Avoidance of Unmanned Aircraft

Abstract

Collision avoidance (CA) using the artificial potential field (APF) usually faces several known issues such as local minima and dynamically infeasible problems, so unmanned aerial vehicles’ (UAVs) paths planned based on the APF are safe only in a certain environment. This research proposes a CA approach that combines the APF and motion primitives (MPs) to tackle the known problems associated with the APF. Since MPs solve for a locally optimal trajectory with respect to allocated time, the trajectory obtained by the MPs is verified as dynamically feasible. When a collision checker based on the k-d tree search algorithm detects collision risk on extracted sample points from the planned trajectory, generating re-planned path candidates to avoid obstacles is performed. After rejecting unsafe route candidates, one applies the APF to select the best route among the remaining safe-path candidates. To validate the proposed approach, we simulated two meaningful scenario cases—the presence of static obstacles situation with local minima and dynamic environments with multiple UAVs present. The simulation results show that the proposed approach provides smooth, efficient, and dynamically feasible pathing compared to the APF.

1. Introduction

A number of studies for collision avoidance (CA) have been conducted [1,2]. Among several CA approaches, the graph search algorithms are widely used because they are known to provide successful results in general. Sanchez-Lopez et al. [3] proposed A* graph search algorithm-based approach to find a collision-free path. However, using the graph search algorithm takes a long search time in a complex and large environment [4], and it requires a sufficient number of nodes before starting the algorithm [3]. Piece-wise Bezier curves are applied to the CA during multi-robot operations [5], which offers smooth trajectories for avoiding collisions. However, dynamic constraints such as position, velocity, and acceleration changes are not bounded in some circumstances. Zhang et al. [6] utilizes an optimization technique to find a collision-free trajectory that minimizes a vehicle’s total travel distance. However, this problem is sensitive to initial guesses and requires a high computational burden. One of the widely used technologies for CA is an artificial potential field (APF) [7]. Based on the straightforward principle of the APF, it generates a smooth trajectory efficiently. In addition, the APF enables one to consider motion uncertainty due to disturbance [8]. In fact, numerous researchers have investigated the APF to develop path planning algorithms that avoid obstacles [9,10,11,12].

Despite the advantages of the APF, CA using the APF usually faces two major problems as follows: the local minima problem [13] and the problem of goal non-reachable with obstacles nearby (GNRON) [14]. The local minima problem occurs when an agent does not go further in front of an obstacle since the attractive and repulsive potential field makes a balance. In the GNRON problem, an agent does not reach the goal location because an obstacle is too close to the goal location; that is, the goal is located within a certain area influenced by the repulsive potential field. To solve those problems, some scholars proposed the modified attractive and/or repulsive potential functions. As an illustration, Azzabi and Nouri [15] added extra fractional equations to the attractive and repulsive potential functions. To resolve the APF’s two major drawbacks, the only repulsive potential function was modified in the following three approaches: Triharminto et al. [16] added fractional equations to the repulsive potential function; Sudhakara et al. [17] multiplied the repulsive potential function by an exponential function; Guo et al. [14] multiplied the navigation potential function into the repulsive potential function. Although they tried to solve the two major problems of the conventional APF, planned paths based on the above modified potential functions are safe only in a certain static environment [18]. In other words, prior mapping is meaningless in dynamic environments [19,20]. To avoid dynamic obstacles, the potential functions with polynomial equations were replaced with exponential functions [21] or the Gaussian function [22]. Furthermore, Choi et al. [12] enhanced the potential field, applying the concept of the curl-free vector field [23] in the aspect of the local minima and dynamic obstacles. However, these approaches did not consider the GNRON problem. Also, they are only applicable for 2-dimensional (2D) dynamic environments. Furthermore, to resolve the GNRON issue, Sun et al. [24] proposed the optimized APF (OAPF) algorithm, which multiplies the repulsive potential function with the distance between an agent and the goal. Even though the OAPF approach avoids dynamic and static obstacles in a 3D environment, it simulated only a scenario in which all unmanned aerial vehicles (UAVs) as relative dynamic obstacles go toward the same goal location, so it does not assure the CA’s robustness for dynamic obstacles flying to other directions.

Applying the conventional APF to the CA systems is not feasible for six degrees-of-freedom (DOF) UAVs since its formula does not consider the dynamics of vehicles [19,20,24]. To illustrate vehicles’ dynamics in the APF, the fuzzy inference system models the repulsive potential field is used [25,26]. Moreover, Ahmed et al. [27] provided a new repulsive potential function by multiplying the relative distance between an agent’s current position and its goal location while the agent’s motion is controlled by a PID controller based on the particle swarm optimization algorithm. Li et al. [28] used the same potential function formula as the one used by Ahmed et al., while they controlled a mobile robot via the model predictive control approach. In addition, Yan et al. [29] and Iswanto et al. [30] handled the dynamics of a quadcopter with the APF, but their maneuvering is limited to horizontal avoidance at a constant altitude. Although these references generated dynamically feasible trajectories, their available environment is only a 2D space with static obstacles.

Motion primitives (MPs) [31,32] are a widely used trajectory generation method for controlling a quadcopter in a 3D space, so the planned trajectory is dynamically feasible. In fact, the MPs create a smooth and optimal path by minimizing the jerk when given a UAV’s current state information, the desired end conditions, and duration period. It results in a time-parameterized polynomial to make capable a fast update when re-planning is required, but the standard MPs themselves do not contain the CA functionality.

To tackle all of the known issues related to the APF, this paper proposes a CA approach that combines the APF and the MPs. First, an autonomous UAV rapidly propagates an optimal trajectory using the MPs. Next, once point cloud data are ready, the UAV checks collision risk on the extracted sample points along the path using the k-d tree search. If a collision risk point is detected, one re-plans path candidates connecting intermediate waypoints to avoid the nearest obstacle point. After removing unsafe ones, one selects the best path candidate using the APF. Although mathematical theory and technical fundamentals related to the MP and k-d tree search are already known, the authors emphasize that generating path candidates and re-planning by the APF are our major contributions. Furthermore, the integration of individually known theories to an overall CA process and validation of it in realistic simulations are original and valuable results.

Table 1. A comparison of the collision avoidance (CA) approaches using the artificial potential field (APF) (O: Solved, X: Unsolved, and $\Delta$: Limited case only).

Approach	Local Minima	GNRON	Dynamic Obstacles	3D Space	Dynamically Feasible
Azzabi & Nouri [15]	O	O	X	X	X
Triharminto et al. [16]	O	O	X	X	X
Sudhakara et al. [17]	O	O	X	X	X
Geu et al. [14]	O	O	X	X	X
Weerakoon et al. [21]	O	O	O	X	X
Cho et al. [22]	O	O	O	X	X
Chang et al. [23]	O	O	X	O	O
Rezaee & Abdollahi [18]	O	X	X	O	O
Choi et al. [12]	O	X	O	X	X
Park et al. [25]	O	X	X	X	O
Elkilany et al. [26]	O	X	X	X	O
Ahmed & Abed [27]	O	O	X	X	O
Li et al. [28]	O	O	X	X	O
Yan et al. [29]	O	O	X	X	O
Iswanto & Ma’arif [30]	O	O	X	X	O
Apoorva et al. [19]	O	O	X	X	X
Azmi et al. [20]	O	O	X	X	X
Sun et al. [24]	O	O	$\Delta$	O	X
Ours	O	O	O	O	O

summarizes the literature review of the CA approaches using the APF, including the proposed approach. Compared to other relevant articles, the proposed approach enables UAVs to avoid static and moving obstacles in a 3D space along dynamically feasible trajectories without the local minima and GNRON problems. The authors’ previous research [33] focused on conceptual validation so that it tested with artificially generated obstacles and did not consider the sensor’s specifications when calculating the CA algorithm. However, this study adopts realistic obstacles representing an urban environment for validating practicability. In addition, to efficiently generate path candidates beneficial to avoidance, this paper adds perturbation for asymmetry. In case all path candidates are unsafe, the ability to set additional route candidates has also been proposed so that a UAV avoids a larger detour.

The remainder of this paper contains the following sections. Section 2 presents our methodology; that is, path propagation using the MPs, collision checking based on the k-d tree search algorithm [34], and re-planning using the APF when potential collision risks are detected. Section 3 shows the simulation results for various scenarios in realistic environments. The last section concludes and plans future work.

2. Methodology

Figure 1 depicts a flowchart of the overall CA process proposed in this study. The following subsections explain each process and the interactions among them.

2.1. Path Propagation Using Motion Primitives

To control differentially flat dynamical systems, such as quadcopters [35], a widely used trajectory planning method is the MPs [31,32]. The MPs are defined by a UAV’s initial state, the desired motion duration, and any combination of components of its position, velocity, and acceleration at the motion’s end. Given those states and conditions, the MPs generate smooth trajectories by minimizing a cost function ${\mathcal{J}}_{\Sigma }=\frac{1}{T}{\int }_0^T{\parallel \mathbf{j}\left(t\right)\parallel }^{2}dt$, where $\mathbf{j}\left(t\right)$ and T denote the jerk and a terminal time, respectively. Indeed, the dynamics into three orthogonal inertial axes are assumed to be decoupled, so the generated MPs minimize the cost value for each axis independent of the other axes. In other words,

$${\mathcal{J}}_{\Sigma }=\sum _{q=1}^3{\mathcal{J}}_q=\sum _{q=1}^3\frac{1}{T}{\int }_0^T{j}_q^2\left(t\right)dt,$$

(1)

where ${\mathcal{J}}_q$ represents a per-axis cost. For each axis q, let the state ${\mathbf{s}}_{\mathbf{q}}\left(t\right)={[p_q\left(t\right),v_q\left(t\right),a_q\left(t\right)]}^{\mathrm{T}}$ be the scalar components of position, velocity, and acceleration. The control input is the jerk $j_q\left(t\right)$ such that

$${\dot{\mathbf{s}}}_{\mathbf{q}}\left(t\right)=f_s({\mathbf{s}}_{\mathbf{q}}\left(t\right),j_q\left(t\right))={[v_q\left(t\right),a_q\left(t\right),j_q\left(t\right)]}^{\mathrm{T}}.$$

(2)

For shorthand notations, it neglects axis subscript q when only a single axis is considered and time argument $\left(t\right)$, when it is not ambiguous.

The control input jerk is chosen $\forall t\in [0,T]$ to minimize objective functional in Equation (1). Hamiltonian function $\mathcal{H}$ is constructed by introducing the time-varying Lagrange multiplier vector $\mathsf{\lambda }={[{\lambda }_1,{\lambda }_2,{\lambda }_3]}^{\mathrm{T}}$, whose elements are called the costates of the system as follows:

$$\mathcal{H}(\mathbf{s},j,\lambda )={\mathsf{\lambda }}^{\mathrm{T}}{f}_s(\mathbf{s},j)+\frac{1}{T}{j}^2={\lambda }_{1}v+{\lambda }_{2}a+{\lambda }_{3}j+\frac{1}{T}{j}^2.$$

(3)

The Pontryagin’s minimum principle [36] states that optimal state trajectory ${\mathbf{s}}^{*}$, optimal control $j^{*}$, and corresponding Lagrange multiplier vector ${\mathsf{\lambda }}^{*}$ minimize $\mathcal{H}$ so that the following costate equation must be satisfied:

$$-\dot{\mathsf{\lambda }}={\nabla }_{\mathbf{s}}\mathcal{H}({\mathbf{s}}^{*},j^{*},\mathsf{\lambda })={[0,{\lambda }_1,{\lambda }_2]}^{\mathrm{T}},$$

(4)

where ${\nabla }_{\mathbf{s}}\mathcal{H}({\mathbf{s}}^{*},j^{*},\mathsf{\lambda })$ represent the gradient of $\mathcal{H}$ with respect to $\mathbf{s}$. Integrating the costate differential equation in Equation (4) with constants $\alpha ,\beta$, and $\gamma$ yields

$$\mathsf{\lambda }\left(t\right)=\frac{1}{T}\left[\begin{array}{c}-2\alpha \\ 2\alpha t+2\beta \\ -\alpha t^2-2\beta t-2\gamma \end{array}\right].$$

(5)

From Equation (3), $j^{*}$ is solved by

$$\begin{array}{cc}\hfill j^{*}\left(t\right)& =\underset{j\left(t\right)}{error}\mathcal{H}({\mathbf{s}}^{*}\left(t\right),j\left(t\right),\lambda \left(t\right))=-\frac{T}{2}{\lambda }_3\left(t\right)\hfill \\ & =\frac{1}{2}\alpha t^2+\beta t+\gamma ,\hfill \end{array}$$

(6)

and ${\mathbf{s}}^{*}$ is obtained by integrating Equation (2) given the initial condition $\mathbf{s}\left(0\right)={[p\left(0\right),v\left(0\right),a\left(0\right)]}^{\mathrm{T}}={[p_0,v_0,a_0]}^{\mathrm{T}}$ as follows:

$${\mathbf{s}}^{*}\left(t\right)=\left[\begin{array}{c}{p}^{*}\left(t\right)\\ v^{*}\left(t\right)\\ a^{*}\left(t\right)\end{array}\right]=\left[\begin{array}{c}\frac{\alpha }{120}{t}^5+\frac{\beta }{24}{t}^4+\frac{\gamma }{6}{t}^3+\frac{a_0}{2}{t}^2+v_{0}t+p_0\\ \frac{\alpha }{24}{t}^4+\frac{\beta }{6}{t}^3+\frac{\gamma }{2}{t}^2+a_{0}t+v_0\\ \frac{\alpha }{6}{t}^3+\frac{\beta }{2}{t}^2+\gamma t+a_0\end{array}\right].$$

(7)

One solves remaining unknowns $\alpha ,\beta ,$ and $\gamma$ depending on the given components of the desired end translational state. As an illustration, when fully defined end translational state is given, let end condition be ${\mathbf{s}}^{*}\left(T\right)={[p\left(T\right),v\left(T\right),a\left(T\right)]}^{\mathrm{T}}={[p_f,v_f,a_f]}^{\mathrm{T}}$ along an axis. Substituting ${\mathbf{s}}^{*}\left(T\right)$ into Equation (7) and reordering the equation yields

$$\begin{array}{cc}\hfill \left[\begin{array}{c}\Delta p\\ \Delta v\\ \Delta a\end{array}\right]& =\left[\begin{array}{c}{p}_f-p_0-v_{0}T-\frac{1}{2}{a}_0{T}^2\\ v_f-v_0-a_{0}T\\ a_f-a_0\end{array}\right]\hfill \\ \hfill & =\left[\begin{array}{ccc}\frac{1}{120}{T}^5& \frac{1}{24}{T}^4& \frac{1}{6}{T}^3\\ \frac{1}{24}{T}^4& \frac{1}{6}{T}^3& \frac{1}{2}{T}^2\\ \frac{1}{6}{T}^3& \frac{1}{2}{T}^2& T\end{array}\right]\left[\begin{array}{c}\alpha \\ \beta \\ \gamma \end{array}\right].\hfill \end{array}$$

(8)

Then, the unknown coefficients $\alpha ,\beta ,$ and $\gamma$ are solved by the inverse of Equation (8) as follows:

$$\left[\begin{array}{c}\alpha \\ \beta \\ \gamma \end{array}\right]=\frac{1}{T^5}\left[\begin{array}{ccc}720& -360T& 60T^2\\ -360T& 168T^2& -24T^3\\ 60T^2& -24T^3& 3T^4\end{array}\right]\left[\begin{array}{c}\Delta p\\ \Delta v\\ \Delta a\end{array}\right].$$

(9)

Hence, generating the MPs requires only evaluating the matrix multiplication for each axis from Equation (9), and then the state trajectory along the MPs is obtained by Equation (7). In implementation, T in Equation (9) is computed with the desired average speed $\overline{V}$ as follows:

$$T=\frac{\parallel {\mathbf{p}}_{\mathbf{f}}-{\mathbf{p}}_{\mathbf{0}}\parallel }{\overline{V}},$$

(10)

where ${\mathbf{p}}_0$ and ${\mathbf{p}}_f$ represent the initial and target position vector, respectively. For the details of other end conditions, see the Reference [32].

Since the MPs solve for a locally optimal trajectory with respect to allocated time, the trajectory represents time-parameterized polynomials. That is, the closed-form solution of the MPs converts the trajectory generation problem to a problem of finding polynomial coefficients. Thus, the MPs make it possible for the rapid generation and the frequent updates of paths.

2.2. Collision Check Using k-d Tree Search

To navigate in unknown environments, one requirement is real-time sensing of surroundings by remote sensors such as 3D scanners, light detection and ranging (LiDAR) sensors, time-of-flight cameras, and depth sensors. Such sensors measure many points on the external surfaces of objects around them, and the set of those data points is called a point cloud. In other words, since the sensor observes the relative distances between the outer surfaces of the objects and the sensor, the point cloud includes all distance vectors with respect to the center of the sensor, expressed in the sensor reference frame. In fact, depending on computational availability, downsampling the point cloud is sometimes beneficial. In addition, when navigating in dynamic environments, prior mapping is meaningless. Although graph-search algorithms like A* that require map information beforehand need an additional technique or process to deal with dynamic obstacles [37], the proposed approach does not need any additional mapping process, and the updated point cloud, whenever new information becomes available, is useful to represent real-time obstacles.

When the MPs-based motion planning in Section 2.1 are ready for collision checking, an autonomous UAV first extracts sample points from the planned path within the observable area (e.g., sensing range and limited field-of-view (FOV)), shown in Figure 2. Indeed, the maximum distance between two consecutive samples does not exceed the resolution of the point cloud.

Next, the k-d tree search algorithm [34] aims to find the nearest obstacle point to each extracted sample-path point. If all closest obstacle points exist outside a certain margin (e.g., collision risk sphere) of the corresponding sample points, then the planned path is assumed to be safe, so the vehicle continues to follow the trajectory. In other words, if the nearest obstacle point exists within the collision risk sphere centered at the corresponding point on the path, re-planning to avoid that path point, called ${\mathbf{p}}_{\mathrm{col}}$, is performed at the next step in Section 2.3. As a corner case, if ${\mathbf{p}}_{\mathrm{col}}$ is the current location (e.g., when an obstacle moves towards the UAV), then the UAV stops the mission and lands autonomously.

2.3. Re-Planned Path Using Potential Fields

2.3.1. Path Candidates

From the collision checking process, a possible collision risk point ${\mathbf{p}}_{\mathrm{col}}$ along the path is determined. For re-planning on it, one first imagines a tunnel or corridor with a certain radius the UAV has to avoid, centered around ${\mathbf{p}}_{\mathrm{col}}$. Around that point, the autonomous UAV lists the intermediate waypoint candidates ${\mathbf{p}}_{\mathrm{int},l}(l=1,2,\cdots ,m)$ onto the tunnel surface as follows:

$$\begin{array}{cc}\hfill {\mathbf{p}}_{\mathrm{int},l}& ={\mathbf{p}}_{\mathrm{col}}+(cos{\theta }_l)\mathbf{y}+(sin{\theta }_l)\mathbf{z},\hfill \end{array}$$

(11)

where ${\theta }_l=2\pi l/m+$ perturbation for asymmetry. The origin of the perpendicular plane is ${\mathbf{p}}_{\mathrm{col}}$ and the normal vector of the plane is the desired velocity at the origin $\mathbf{x}={\mathbf{v}}_{\mathrm{col}}/\parallel {\mathbf{v}}_{\mathrm{col}}\parallel$. The vertical vector is a unit vector direction to z-axis $\mathbf{z}={[0,0,1]}^{\mathrm{T}}$ in the body frame and the y-axis unit vector follows the right-hand rule $\mathbf{y}=\mathbf{z}\times \mathbf{x}$, shown in Figure 3. Here, the number of intermediate destinations (i.e., m) enable variability depending on the availability of computing power.

Next, the MPs create two distinct path segments with a midpoint candidate: one connects from the current position to the intermediate point and the other from the intermediate point to the final location. To smoothly connect the two path segments at that midpoint, in implementation, the following full states ${\mathbf{s}}_{\mathrm{int},l}$ at the l-th intermediate point are commonly used as each end condition:

$$\begin{array}{c}\hfill {\mathbf{s}}_{\mathrm{int},l}={[{\mathbf{p}}_{\mathrm{int},l},{\mathbf{v}}_{\mathrm{int},l},{\mathbf{a}}_{\mathrm{int},l}]}^{\mathrm{T}},\end{array}$$

(12)

where ${\mathbf{a}}_{\mathrm{int},l}={[0,0,0]}^{\mathrm{T}}$ and

$${\mathbf{v}}_{\mathrm{int},l}=\overline{V}\frac{{\mathbf{p}}_f-{\mathbf{p}}_{\mathrm{int},l}}{\parallel {\mathbf{p}}_f-{\mathbf{p}}_{\mathrm{int},l}\parallel }.$$

(13)

Among m route candidates, unsafe intermediate waypoints are rejected by performing the collision checking process again. If all of the path candidates are unsafe, the UAV sets additional route candidates on the surface of another tunnel with a larger radius at the same sample point for bigger detouring and performs the collision checking of new ones.

2.3.2. Selection of Re-Planned Path Candidates

After rejecting unsafe route candidates, one applies the APF for selecting the best route among the remaining safe-path candidates. In other words, the APF is used for a decision-making purpose here. The APF artificially generates the attractive and repulsive potential fields based on the potential functions by considering the goal, which is the target position, and obstacles. While a UAV is attracted by a goal in the attractive potential field, the UAV is repelled by obstacles in the repulsive potential field. Then, the UAV in a given space travels in a direction where the total potential function value has the minimum value. The total potential function for the safe-path candidates is defined as follows [7]:

$$\begin{array}{c}\hfill U_{\mathrm{tot}}\left({\mathbf{p}}_{\mathrm{int},l}\right)=U_{\mathrm{att}}\left({\mathbf{p}}_{\mathrm{int},l}\right)+\sum _i{U}_{\mathrm{rep}}({\mathbf{p}}_{\mathrm{int},l},{\mathbf{p}}_{\mathrm{obs},i}),\end{array}$$

(14)

where $U_{\mathrm{att}}$ and $U_{\mathrm{rep}}$ are the attractive and repulsive potential functions that are defined as

$$\begin{array}{}\mathrm{(15)}& U_{\mathrm{att}}\left({\mathbf{p}}_{\mathrm{int},l}\right)& =\frac{1}{2}{k}_{\mathrm{att}}D{({\mathbf{p}}_{\mathrm{int},l},{\mathbf{p}}_f)}^2,\hfill \mathrm{(16)}& U_{\mathrm{rep}}({\mathbf{p}}_{\mathrm{int},l},{\mathbf{p}}_{\mathrm{obs},i})& =\left\{\begin{array}{cc}\frac{1}{2}{k}_{\mathrm{rep}}{\left(\frac{1}{D\left({\mathbf{p}}_{\mathrm{int},l},{\mathbf{p}}_{\mathrm{obs},i}\right)}-\frac{1}{d_{\mathrm{thd}}}\right)}^2,\hfill & \mathrm{if}D({\mathbf{p}}_{\mathrm{int},l},{\mathbf{p}}_{\mathrm{obs},i})\le d_{\mathrm{thd}},\hfill \\ 0,\hfill & \mathrm{if}D({\mathbf{p}}_{\mathrm{int},l},{\mathbf{p}}_{\mathrm{obs},i})>d_{\mathrm{thd}},\hfill \end{array}\right.\end{array}$$

where $k_{\mathrm{att}}$ and $k_{\mathrm{rep}}$ are scaling factors for the attractive and repulsive potential functions, $D(\mathbf{a},\mathbf{b})$ is the relative distance between arbitrary two vectors $\mathbf{a}$ and $\mathbf{b}$, ${\mathbf{p}}_{\mathrm{obs},i}$ is the position vector of measured i-th obstacle, and $d_{\mathrm{thd}}$ is the threshold distance influenced by the repulsive potential function. With the the concept of the APF, the $l^{*}$-th path that has the smallest total potential function value among the computed values for each path candidate is finally selected as follows:

$$l^{*}=\underset{l}{\mathrm{arg min}}{U}_{\mathrm{tot}}\left({\mathbf{p}}_{\mathrm{int},l}\right).$$

(17)

At the next time step, the above processes are repeated until the UAV arrives at the final goal position.

3. Results

3.1. Urban Modeling

To test CA algorithms in more realistic simulation environments, unlike Lee et al. [33], one models an urban environment with real datasets. In other words, one processes the following steps to generate static obstacles using a city model [38]. The first step is collecting urban data from airborne LiDAR sensors and down-selecting the collected data. The open-source urban information is available at numerous sources. Here, a “.las” file downloaded from Open-Topography (https://opentopography.org/, accessed on 30 March 2021) is utilized, and San Diego downtown is selected as an example of urban environments. Next, one classifies data in the file as the x, y, and z components of a point cloud and filters out only data with a height of z between 200 and 400 ft. For visualization, its scatter plot is depicted in Figure 4. The density of the point cloud is quite similar to the resolution of real-time measurements, so they are sufficient static obstacles in simulations to test CA approaches.

3.2. Simulation Cases and Results

For validating the performance of the proposed approach, one simulates five meaningful scenarios in realistic environments as follows: (i) local minima problem, (ii) GNRON problem, (iii) only static obstacles, (iv) only dynamic obstacles, and (v) complex environment. The first and second cases describe the well-known two major issues of the path planning problems including the APF. The third case tests a 3D environment that contains urban structures as static obstacles, demonstrated in Section 3.1. In the fourth case, a UAV senses other non-cooperative UAVs that are considered as dynamic obstacles. The last challenging case is a complex environment with multiple UAVs (i.e., moving obstacles) in the presence of static obstacles. All of these scenarios are popular in the field of path planning.

In this work, for simulating practical sensing, a range sensor mounted a UAV obtains a point cloud within the measurable space (Figure 2) based on the sensor’s specification. The point cloud includes relative distance information between the UAV and obstacles. In addition, for navigating safely, it assumes that collision occurs when obstacles are inside the risk sphere with a radius of 5 m, centered at the UAV. Here, one assumes no collision at the initial state and no existence of estimation errors and sensing errors. In the processes of the proposed approach, the number of intermediate waypoint candidates is multiples of 8 so that each one is distributed about every 45 deg on the perpendicular plane of the UAV’s path direction.

Table 2. Simulation parameters.

Variable	Value
$\overline{V}$	2 m/s
Discrete-time Interval	0.1 s
Sensor’s Sensing Range	20 m
Sensor’s Horizontal FOV	220 deg
Sensor’s Vertical FOV	70 deg
Radius of the Collision Risk Sphere	5 m
Number of Intermediate Waypoints	8×
Maximum Number of Intermediate Waypoints	1000
Maximum Iterations for the APF	1000
Resolution of Extracted Path-Sample Points	0.3 s
$k_{\mathrm{att}}$	0.01
$k_{\mathrm{rep}}$	$5\times {10}^3$
$d_{\mathrm{thd}}$	10 m

lists simulation parameters, and the start and goal positions for each case are tabulated in

Table 3. Start and goal positions of unmanned aerial vehicles (UAVs) for each case.

	Description	Start Position (m)	Goal Position (m)
Case 1	Local Minima	${(350,270,60)}^{\mathrm{T}}$	${(200,270,60)}^{\mathrm{T}}$
Case 2	GNRON	${(250,170,60)}^{\mathrm{T}}$	${(330,207,65)}^{\mathrm{T}}$
Case 3	Static Obstacles Only	${(300,210,70)}^{\mathrm{T}}$	${(355,110,70)}^{\mathrm{T}}$
Case 4	Dynamic Obstacles Only	${(0,0,20)}^{\mathrm{T}}$	${(90,30,30)}^{\mathrm{T}}$
		${(100,0,30)}^{\mathrm{T}}$	${(0,50,20)}^{\mathrm{T}}$
		${(50,70,30)}^{\mathrm{T}}$	${(50,0,20)}^{\mathrm{T}}$
Case 5	Complex Environment	${(350,260,60)}^{\mathrm{T}}$	${(250,150,60)}^{\mathrm{T}}$
		${(215,200,60)}^{\mathrm{T}}$	${(380,210,60)}^{\mathrm{T}}$

. Note that each component of the column vectors represents x, y, and z (altitude), respectively. The following results from the proposed approach are compared to those from the existing APF method.

In case 1, a point of the static obstacle is exactly on the line connecting the start and goal positions. In that environment, the APF yields the UAV gets stuck in the local minima, so the UAV cannot go further avoiding the obstacle as shown in the blue dotted line of Figure 5. In the bird’s eye view, green and pink dots represent the start and goal locations, respectively. Figure 6 depicts the fact that the APF-based UAV (i.e., blue line) stays near the obstacle while maneuvering back and forth around $d_{\mathrm{thd}}$. In the figure, relative distances to the nearest obstacle are measured only within the sensor range (i.e., black dotted line), and both paths do not collide since they are no closer than the collision risk distance (i.e., pink dotted line). In addition, since the heading direction (i.e., sign of the APF’s velocity vector) changes instantaneously as shown in the middle one of Figure 7b, the planned path is dynamically infeasible. However, the proposed approach generates the collision-free path resolving the local minima problem. That is, the proposed method completes the mission within around 82 seconds but the APF cannot since it stays in the local minima area forever (see Figure 7). The red stars illustrated in Figure 5 represent obstacle points that influence re-planning in the approach proposed. With minimal obstacle points (i.e., red stars), a smooth and dynamically feasible trajectory is created, shown in the position vector of Figure 7a.

In case 2, the goal location is set close to 6 m from the static obstacle (pink dot in Figure 8). Like the local minima problem in case 1, such a GNRON environment produces similar results. The APF prevents the UAV from reaching the goal position under the influence of the repulsive potential field. Whereas the APF method keeps the UAV near the region where the repulsive force is affected (see the blue and green lines of Figure 9), the proposed approach enables the UAV to arrive at the destination successfully and safely as exhibited in Figure 8 and Figure 10. Moreover, in the proposed method combining the MPs and APF, the relative distance to the nearest obstacle continues to decrease rapidly, shown in the red line of Figure 9. That is, the UAV based on the proposed approach reaches smoothly the goal location near the obstacle so that the simulation is done within about 45 seconds. However, the UAV based on the APF keeps moving back and forth around the GNRON region, so its final location does not change much (Figure 9 and Figure 10).

The next case is static obstacles only. Figure 11 and Figure 12 highlight the performance of the proposed approach, which provides smooth and continuous position and velocity trajectories. Both methods reach their destination without invading the 5 m collision risk radius as shown in Figure 13, but the APF method is shown to be inefficient since it is affected by more obstacle points and required re-plans more often (i.e., the number of blue squares in Figure 11) than the proposed method experienced (i.e., the number of red stars in Figure 11). Moreover, the APF plans the dynamically impracticable velocity profile enough to require infinite acceleration as shown in the middle one of Figure 12b. In other words, like the proposed approach, the continuous change of the velocity profile is possible dynamically, but like the APF, the relatively discrete variation of the velocity profile is not dynamically executable.

In case 4, three UAVs’ starting points (green dots) and destinations (pink dots) are set as if they meet each other around the middle area in the open space (see Figure 14). Here, each UAV is a decentralized agent without any communication like automatic dependent surveillance-broadcast. That is, one UAV does not know the location of the other two UAVs via communication in advance, and like moving obstacles, it can instead predict their rough locations only through real-time measurements of the point cloud. For arrival to the destinations, the APF method becomes inefficient and more dangerous next time since all UAVs are required to do CA too frequently (i.e., the number of blue squares in Figure 14), which results in the repeats of infeasible movement forward and backward (i.e., blue dashed lines in Figure 15, subfigures at the middle row of Figure 16, and blue lines in Figure 17). However, in the proposed method, while UAV2 and UAV3 remain along the initially planned optimal route, only UAV1 efficiently maneuvers a single avoidance whenever the other agents are detected (i.e., red lines in Figure 14 and Figure 15).

The last scenario is a complex case formed with two moving UAVs and multiple static obstacles. Although both approaches allow all UAVs to reach their goal positions without any collision, similar to case 4, only the proposed method plans optimal (i.e., shorter) and practicable smooth trajectories, shown in Figure 18 and Figure 19. In fact, the proposed method’s UAV2 avoids dynamic (i.e., UAV1) and static obstacles safely during its mission while the proposed method’s UAV1 continues to go along its initially planned path without any collisions. In other words, Figure 18 and Figure 20 show that the APF’s UAV1 has a longer history since it is hindered by UAV2. At similar times, the APF-based UAVs try to avoid each other, so their paths are not planned to be dynamically feasible (i.e., subfigures at the middle row of Figure 21).

4. Conclusions

This paper proposes a collision-avoidance approach that combines the artificial potential field (APF) and motion primitives (MPs). Initially, the MPs generate a dynamically feasible and locally optimal trajectory with respect to the allocated time and given states. When collision risk in the planned trajectory is detected by a collision checker, several path candidates around the possible collision risk point are generated for re-planning. After unsafe candidates are rejected, the best route among the remaining safe-path candidates is selected by utilizing the APF. The performance of the proposed approach is validated by numerical simulations with several different scenarios. The unmanned aerial vehicles (UAVs) using the proposed approach reach the goal position along a dynamically feasible trajectory while avoiding collision and the local minima. A practical application of the proposed approach would be the smart mobility corridor for the air traffic management of multiple UAVs’ flights within a complex urban area in the future.