Survey of Safety Management Approaches to Unmanned Aerial Vehicles and Enabling Technologies
3
In recent years, various path-planning algorithms for UAV
have been extensively investigated. Exhaustive reviews about
path-planning algorithm are studied in previous works. Com-
monly, the existing path-planning algorithms can be divided
into three classes of deterministic algorithm, probabilistic al-
gorithm and heuristic algorithm based on their specific calcu-
lation features.
A. Deterministic Algorithm
The deterministic algorithm group usually has a certain
search mechanism and fixed cost equations. For a given sce-
nario, it always generates the same results and attempt to find
the shortest or feasible path, which may not be the optimal
solution. There are three commonly studied deterministic
algorithms for path-planning in previous works, namely, A-
star search algorithm, potential field method and mathemati-
cal programming method.
1) A-Star Search Algorithm: A-star search algorithm is
one of the popular deterministic graph search techniques. It
improves the intensive search of Dijkstra’s algorithm, which
calculates the distance of passing a node and every node sur-
rounding the current position, by adding the global informa-
tion of estimated distance between the current node and desti-
nation that directs the search only towards nodes in the direc-
tion of the goal position. The A-star search algorithm plays
an important role in path-planning of UAV.
Hwangbo et al.
[9]
proposed an efficient two-phase approach
to path-planning for small fixed-wing UAVs in complex 3D
environments. An A-star search algorithm is used first to
generate a feasible collision-free path in a discretized 3D
workspace under the consideration of both kinematics and dy-
namics of the UAV for global planning. Afterwards, a best
first search is performed to compute a more detailed trajec-
tory for the UAV. Moreover, Meng et al.
[10]
investigated the
bidirectional sparse A-star search algorithm (BSAS) for UAV
path-planning. It starts the A-star search process from both
the start and goal point and calculates whether there is a line
of sight between two different expansion nodes of different
search processes. This algorithm shows better planning result
and stronger robustness.
Although A-star search algorithm is a classical algorithm
and widely used in UAV path-planning, it has high compu-
tational complexity and requires huge computing memory.
Meanwhile, whether there is a feasible flight path or not de-
pends on the resolution of search space grid. A-star search
algorithm may not find a feasible path if the resolution of grid
is low.
2) Potential Field Method: Potential field method is based
on the idea of particle movement under force in potential field.
In this method, the UAV is modeled as moving under the influ-
ence of a potential field. The specific potential field function
is designed first according to the destination and obstacles in
the search space. In a potential field function, the attraction
part pulls the UAV towards the destination, whereas the repul-
sive part pushed the UAV away to avoid collision with obsta-
cles. The resultant force determines the direction of moving
ahead of UAV. The potential field method has been studied
widespread in path-planning of UAV recently.
Chuang et al.
[11]
designed an analytically tractable poten-
tial field model of free space and applied the Newtonian po-
tential function to guarantee the collision avoidance between
object and obstacles in path-planning problem. Masoud
[12]
investigated the Gamma-Harmonic Potential Fields approach
for path planning in environments with inherent uncertainty
that cannot be segmented into geometrical sub-regions. Cetin
et al.
[13]
designed an obstacle aware communication relay ap-
proach to detect position of UAVs and obstacles. And path
planning for collision avoidance between UAVs and obstacles
are generated by using artificial potential fields.
The potential field method for path-planning is fast and ef-
ficient. And it is easy to handle new obstacles in the envi-
ronment. However, this method has its inherent drawbacks.
There may be no feasible flight path to destination when the
UAV is trapped in a local minimum. In addition, it is com-
plicated to design specific potential field function for different
scenarios and difficult for large obstacle-laden environment.
3) Mathematical Programming Method: The path-
planning problem can be modeled as a numerical opti-
mization problem with mathematical programming method,
which aims at finding the accurate optimal flight path under
specific objective function and constraints in solution space.
The mathematical programming methods to path-planning
are mainly concentrated on mixed integer linear program-
ming (MILP), nonlinear programming (NP) and dynamic
programming (DP).
Campbell et al.
[14]
applied MILP within receding horizon
framework to generate flight path with a minimum fuel so-
lution to mitigate persistent contrail formation and proposed
a novel path-planning approach with a penalty. Raghunathan
et al.
[15]
investigated path-planning in conflict resolution of
multi-aircrafts in 3D environment and solved this problem by
NP method. Jorris et al.
[16]
applied DP method to obtain min-
imum flight time path with avoiding collision to no-fly zone,
passing intermediate waypoints and satisfying specified con-
trol limitations.
B. Probabilistic Algorithm
The probabilistic algorithm group commonly has random-
ized search process to obtain feasible or near-optimal solu-
tions. It usually generates different results of randomized
search in many times for a specific problem. Recent research
on path-planning of UAV by probabilistic algorithm has been