Improved lazy theta∗ algorithm based on octree map for path planning of UAV

Abstract

This paper investigates the path planning method of unmanned aerial vehicle (UAV) in three-dimensional map. Firstly, in order to keep a safe distance between UAV and obstacles, the obstacle grid in the map is expanded. By using the data structure of octree, the octree map is constructed, and the search nodes is significantly reduced. Then, the lazy theta∗ algorithm, including neighbor node search, line-of-sight algorithm and heuristics weight adjustment is improved. In the process of node search, UAV constraint conditions are considered to ensure the planned path is actually flyable. The redundant nodes are reduced by the line-of-sight algorithm through judging whether visible between two nodes. Heuristic weight adjustment strategy is employed to control the precision and speed of search. Finally, the simulation results show that the improved lazy theta∗ algorithm is suitable for path planning of UAV in complex environment with multi-constraints. The effectiveness and flight ability of the algorithm are verified by comparing experiments and real flight.

Keywords

• Unmanned aerial vehicle
• Path planning
• Lazy theta∗ algorithm
• Octree map
• Line-of-sight algorithm