HLT*: Real-time and Any-angle Path Planning in 3D Environment
Xiaoxue Zhang, Sunan Huang, Wenyu Liang, Zilong Cheng, Kok Kiong Tan, Tong Heng Lee · 2019
Even though path planning is a well-studied problem in 2D environment, finding an optimal or near-optimal path in a complex and unknown 3D environment has great prospect, but it is hard to find the optimal path quickly. In this paper, we propose a new algorithm called Hierarchical Lazy Theta* (HLT*), which can plan the near-optimal path efficiently for real-time operation based on the heuristic-based path-finding algorithm Lazy Theta* with a hierarchical path planning approach. Path refinement, smoothing, and polishing are used to refine the path to ensure the feasibility of computed path. Its computation time and path quality are dependent on parameters, such as map size, environment complexity, sensor detection range, refinement range, computation time limits, and any restriction on planning time. Simulation experiments are used to assess the performance, and the simulation results show that HLT* algorithm is capable of planning a high-quality path in a shorter time.