基于单元分解的改进D*lite路径规划算法

Improved D*lite path planning algorithm based on cell decomposition

障碍物分隔搜索空间会隐藏D*lite算法正确的搜索方向,增加算法的计算次数,进而影响搜索效率,针对这一问题提出一种基于单元分解的改进D*lite路径规划算法。在原有Boustrophedon单元分解法的基础上加入了新的分解规则,对环境地图进行单元分解并构建了以单元为节点的图。设计了双向图搜索算法,能够快速计算出最短路径需要依次经过哪些单元。在这些单元中设置核心网格并依照顺序构建搜索链表,引导正确的搜索方向,使规划速度提高。在仿真平台上将算法与其他路径规划算法进行对比实验,实验结果表明,算法规划出的路径长度与其他算法几乎没有差别,并且减少了计算次数、降低了规划时间,验证了算法提高路径规划效率的有效性。

When obstacles separate the search space,the correct search direction of D*lite algorithm is hidden,the calculation times of the algorithm are increased,and the search efficiency is affected.To solve this problem,an improved D*lite path planning algorithm based on cell decomposition is proposed.New decomposition rules are added to Boustrophedon cellular decomposition.This new method decomposes the environment map into multiple units and a graph with these units as nodes is constructed.A bidirectional graph search algorithm is designed to quickly calculate which units the shortest path needs to pass in turn.The main grids are set up in these units and form a linked list in order.This linked list guides the right search direction and makes planning faster.The algorithm in this paper is compared with other path planning algorithms on the simulation platform.The experimental results show that the length of the path planned by this algorithm is almost the same as that of other algorithms,and the calculation times and the planning time are reduced.This result verifies the effectiveness of this algorithm to improve the efficiency of path planning.