A Reusable Generalized Voronoi Diagram-Based Feature Tree for Fast Robot Motion Planning in Trapped Environments

The sampling-based partial motion planning algorithm has been widely applied in real-time mobile robot navigation for its computational savings and its flexibility in avoiding obstacles. However, in some complex environments, partial planning algorithms are prone to fall into traps, resulting in the failure of motion planning. This paper proposes a feature tree algorithm based on Generalized Voronoi Diagram (GVD) to generate heuristic paths to guide partial motion planning. A GVD feature extraction algorithm is proposed to reduce the redundancy in the representation of obstacle-free regions and improve the searching efficiency in heuristic planning process. The feature node set guarantees that any node from obstacle-free regions can be connected to at least one feature node without any collision. For one map, the feature nodes only need to be extracted once and then can be reused in different scenarios on the same map. Thus, the feature extraction can be executed off-line. Based on GVD feature nodes, a feature tree is reported to generate a heuristic path and the nodes on the heuristic path are utilized sequentially as sub-goals to guide the partial motion planning. When the target changes, the feature tree can quickly replan a new heuristic path. The experimental studies reveal that our proposed method can significantly improve the robot motion planning efficiency and the navigation success rate in trapped environments.