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

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

作者机构：School of Mechanical Engineering&AutomationBeihang UniversityBeijing 100191China Aero-Engine Research InstituteBeihang UniversityBeijing 102206China School of Large Aircraft EngineeringBeihang UniversityBeijing 100191China 

出 版 物：《Chinese Journal of Mechanical Engineering》 (中国机械工程学报（英文版）)

年 卷 期：2024年第37卷第2期

页      面：68-82页

核心收录：

学科分类：080202[工学-机械电子工程] 08[工学] 080203[工学-机械设计及理论] 0804[工学-仪器科学与技术] 0802[工学-机械工程] 

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

主　　题：Global path planning Mobile robot Expanding disconnected graph Edge node Offset 

摘      要：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 *** 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 ***,all obstacles are marked and their corners are located through the map ***,the EDG operator is designed to find points in non-obstruction areas to complete the rapid expansion of disconnected ***,the EDG*heuristic iterative algorithm is *** selects the candidate node through a specific valuation function and realizes the node expansion while avoiding collision with a minimum *** planning experiments were conducted in a typical indoor environment and on the public dataset *** 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 *** EDG*showed better performance in terms of path smoothness,and collision *** shows that the EDG*algorithm proposed in this paper can improve the efficiency of path planning and enhance path quality.