首页|Heuristic Expanding Disconnected Graph:A Rapid Path Planning Method for Mobile Robots
Heuristic Expanding Disconnected Graph:A Rapid Path Planning Method for Mobile Robots
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NETL
NSTL
万方数据
Existing mobile robots mostly use graph search algorithms for path planning,which suffer from relatively low plan-ning efficiency owing to high redundancy and large computational complexity.Due to the limitations of the neigh-borhood 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 J PS,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 planningMobile robotExpanding disconnected graphEdge nodeOffset
Yong Tao、Lian Duan、He Gao、Yufan Zhang、Yian Song、Tianmiao Wang
展开 >
School of Mechanical Engineering & Automation,Beihang University,Beijing 100191,China
Aero-Engine Research Institute,Beihang University,Beijing 102206,China
School of Large Aircraft Engineering,Beihang University,Beijing 100191,China
NETL
NSTL
万方数据
