Abstract
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.
NETL
NSTL
万方数据