基于改进A^(*)算法的机器人全覆盖衔接路径规划

Improved A^(*) algorithm for robot full coverage connection path planning

为解决A*算法在规划衔接路径时转角多、路径不平滑、深度优先搜索(DFS)算法规划衔接顺序的随机性和距离较大的问题,提出改进邻域扩展A*算法和经预处理的DFS算法结合的衔接路径规划方法。首先,对A*算法搜索范围扩展至24邻域,经二次数量优化后得到最终邻域搜索节点。其次,设计具有双层位置导向信息的评价函数,对DFS添加节点预处理的步骤。实验结果表明:所提改进A*算法在路径长度、搜索节点数量、规划时间上均优于传统A*算法,且与改进DFS算法结合所得衔接路径表现更优。

To solve the problems of Aalgorithm in planning the connection path,such as many corners,uneven path,great randomness and large distance of depth-first-search(DFS)planning connection sequence,an improved neighbor expansion Aalgorithm combined with preprocessed DFS connection path planning method is proposed.Firstly,the search range of the Aalgorithm is extended to 24—neighborhood,and the final neighbor search nodes are obtained after secondary optimization in terms of quantity.Then,evaluation function having double-layer position of the guide information is designed.And node pre-processing step is added to DFS algorithm.The experimental results show that the proposed improved Aalgorithm is better than traditional Aalgorithm in terms of path length,number of search nodes,planning time,and the connection path obtained by combining with the improved DFS algorithm performs better.