Heuristic Expanding Disconnected Graph:A Rapid Path Planning Method for Mobile Robots  

作　　者：Yong Tao Lian Duan He Gao Yufan Zhang Yian Song Tianmiao Wang 

机构地区：[1]School of Mechanical Engineering&Automation,Beihang University,Beijing 100191,China [2]Aero-Engine Research Institute,Beihang University,Beijing 102206,China [3]School of Large Aircraft Engineering,Beihang University,Beijing 100191,China

出　　处：《Chinese Journal of Mechanical Engineering》2024年第2期68-82,共15页中国机械工程学报（英文版）

基　　金：Supported by National Key Research and Development Program of China(Grant No.2022YFB4700402).

摘　　要：Existing mobile robots mostly use graph search algorithms for path planning,which suffer from relatively low planning efficiency owing to high redundancy and large computational complexity.Due to the limitations of the neighborhood search strategy,the robots could hardly obtain the most optimal global path.A global path planning algorithm,denoted as EDG*,is proposed by expanding nodes using a well-designed expanding disconnected graph operator(EDG)in this paper.Firstly,all obstacles are marked and their corners are located through the map pre-processing.Then,the EDG operator is designed to find points in non-obstruction areas to complete the rapid expansion of disconnected nodes.Finally,the EDG*heuristic iterative algorithm is proposed.It selects the candidate node through a specific valuation function and realizes the node expansion while avoiding collision with a minimum offset.Path planning experiments were conducted in a typical indoor environment and on the public dataset CSM.The result shows that the proposed EDG*reduced the planning time by more than 90%and total length of paths reduced by more than 4.6%.Compared to A*,Dijkstra and JPS,EDG*does not show an exponential explosion effect in map size.The EDG*showed better performance in terms of path smoothness,and collision avoidance.This shows that the EDG*algorithm proposed in this paper can improve the efficiency of path planning and enhance path quality.

关 键 词：Global path planning Mobile robot Expanding disconnected graph Edge node OFFSET 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置] TP391.41[自动化与计算机技术—控制科学与工程]