HPO-RRT*: a sampling-based algorithm for UAV real-time path planning in a dynamic environment

Abstract

Abstract The real-time path planning of unmanned aerial vehicles (UAVs) in dynamic environments with moving threats is a difficult problem. To solve this problem, this paper proposes a time-based rapidly exploring random tree (time-based RRT*) algorithm, called the hierarchical rapidly exploring random tree algorithm based on potential function lazy planning and low-cost optimization (HPO-RRT*). The HPO-RRT* algorithm can guarantee path homotopy optimality and high planning efficiency. This algorithm uses a hierarchical architecture comprising a UAV perception system, path planner, and path optimizer. After the UAV perception system predicts moving threats and updates world information, the path planner obtains the heuristic path. First, the path planner uses the bias sampling method based on the artificial potential field function proposed in this paper to guide sampling to improve the efficiency and quality of sampling. Then, the tree is efficiently extended by the improved time-based lazy collision checking RRT* algorithm to obtain the heuristic path. Finally, a low-cost path optimizer quickly optimizes the heuristic path directly to optimize the path while avoiding additional calculations. Simulation results show that the proposed algorithm outperforms the three existing advanced algorithms in terms of addressing the real-time path-planning problem of UAVs in a dynamic environment.

Keywords

• Sampling-based path planning
• Dynamic path planning
• Time-based rapidly exploring random tree (RRT)
• Unmanned aerial vehicles (UAVs)