基于回溯法的全覆盖路径规划算法

A full coverage path planning algorithm based on backtracking method

随着扫地机器人的快速发展,作为其核心技术的全覆盖路径规划技术也变得日益重要。目前已经提出的许多算法,如人工势场法、模板法、单元分解法等,都存在一些问题,如覆盖率低、重复率高、运行效率低等等。针对目前已有算法存在的问题,提出了一种基于回溯法的全覆盖路径规划算法。首先利用West-MoveFirst算法实现局部区域覆盖,然后为了解决扫地机器人局部区域覆盖过程中存在遗漏区域未覆盖的问题,建立了完善的回溯机制,并采用改进的A*算法规划出一条从死点到回溯点的光滑无障碍路径。通过与BA*算法进行仿真对比分析,表明了该算法具有更高的运行效率和更低的重叠率。

With the rapid development of sweeping robots,as the core technology,full coverage path planning technology has become increasingly important.Many algorithms have been proposed so far,such as the artificial potential field method,template method and unit decomposition method,however,they have problems such as low coverage,high repetition rate and low operating efficiency.In order to solve the problems existing in the proposed algorithms,we propose a full coverage path planning algorithm based on backtracking method.The algorithm firstly uses the west-move first algorithm to achieve local area coverage.Then,in order to solve the problem that the missing area is not covered in the process of local area coverage,we establish a perfect backtracking mechanism.And the improved A^*algorithm is used to plan a smooth unobstructed path from dead points to backtracking points.Simulation results show that compared with the BA^*algorithm,the proposed algorithm has higher operating efficiency and lower overlap rate.