TY - JOUR
T1 - Skeleton Extraction and Greedy-Algorithm-Based Path Planning and its Application in UAV Trajectory Tracking
AU - Chang, Jianfang
AU - Dong, Na
AU - Li, Donghui
AU - Ip, Wai Hung
AU - Yung, Kai Leung
N1 - Funding:
This work was supported by the National Natural Science Foundation of China under Grant 61773282.
ACKNOWLEDGMENT:
The authors would sincerely like to thank the anonymous reviewers for their valuable comments.
PY - 2022/12
Y1 - 2022/12
N2 - Space research is of great significance to increasingly decentralized and distributed space systems, and path planning in space systems has become a research hotspot for maintaining their safety, security, and reliability. To explore the passable path connecting the starting point and the target point, and optimize a smooth trajectory that can be tracked by unmanned aerial vehicles (UAVs) in 3-D space, a skeleton-extraction- and greedy-algorithm-based path planning has been proposed to guide the flight of UAVs. First, the rapidly exploring random tree (RRT) has been introduced for path search. To speed up the path search process, the spatial skeleton extraction method has been introduced to calculate the skeleton of free space The greedy algorithm has been utilized to increase the RRT expansion and reduce unnecessary bends in the path. The skeleton extraction and greedy-algorithm-based Lazy RRT and RRT-Connect have been proposed to build compared experiments. Second, the minimum snap has been applied to generate a smooth flight trajectory, and the flight time is allocated according to the distance between the waypoints. Third, the UAV Simulink model has been established, and the spatial position of the optimized trajectory is tracked. The experimental results prove that the skeleton extraction can significantly speed up the search process, and greedy algorithm can shorten the path length effectively. The minimum snap combined with the time allocation strategy can produce a smooth and feasible path. The UAV Simulink model also proves that the classic proportion-differentiation controller can accurately track the generated trajectory. The greedy algorithm and skeleton extraction reduce the average path length of RRT by 9.780 and 8.251%, respectively. The greedy algorithm and skeleton extraction reduce the average path length of RRT, Lazy RRT, and RRT-Connect by about 10–13%. The greedy algorithm and skeleton extraction reduce the time consumption of RRT by 62.781 and 36.276%, respectively.
AB - Space research is of great significance to increasingly decentralized and distributed space systems, and path planning in space systems has become a research hotspot for maintaining their safety, security, and reliability. To explore the passable path connecting the starting point and the target point, and optimize a smooth trajectory that can be tracked by unmanned aerial vehicles (UAVs) in 3-D space, a skeleton-extraction- and greedy-algorithm-based path planning has been proposed to guide the flight of UAVs. First, the rapidly exploring random tree (RRT) has been introduced for path search. To speed up the path search process, the spatial skeleton extraction method has been introduced to calculate the skeleton of free space The greedy algorithm has been utilized to increase the RRT expansion and reduce unnecessary bends in the path. The skeleton extraction and greedy-algorithm-based Lazy RRT and RRT-Connect have been proposed to build compared experiments. Second, the minimum snap has been applied to generate a smooth flight trajectory, and the flight time is allocated according to the distance between the waypoints. Third, the UAV Simulink model has been established, and the spatial position of the optimized trajectory is tracked. The experimental results prove that the skeleton extraction can significantly speed up the search process, and greedy algorithm can shorten the path length effectively. The minimum snap combined with the time allocation strategy can produce a smooth and feasible path. The UAV Simulink model also proves that the classic proportion-differentiation controller can accurately track the generated trajectory. The greedy algorithm and skeleton extraction reduce the average path length of RRT by 9.780 and 8.251%, respectively. The greedy algorithm and skeleton extraction reduce the average path length of RRT, Lazy RRT, and RRT-Connect by about 10–13%. The greedy algorithm and skeleton extraction reduce the time consumption of RRT by 62.781 and 36.276%, respectively.
KW - Greedy algorithm
KW - Rapidly exploring random tree (RRT)
KW - Skeleton extraction
KW - Space research
KW - Tracking
KW - Trajectory optimization
U2 - 10.1109/TAES.2022.3198925
DO - 10.1109/TAES.2022.3198925
M3 - Journal article
VL - 58
SP - 4953
EP - 4964
JO - IEEE Transactions on Aerospace and Electronic Systems
JF - IEEE Transactions on Aerospace and Electronic Systems
IS - 6
ER -