已知环境下一种高效全覆盖路径规划算法

An efficient complete coverage path planning in known environments

提出一种基于栅格表示的非结构化环境下移动机器人的高效全覆盖路径规划算法.移动机器人采取内螺旋算法从起始点进行覆盖,当陷入覆盖死角时,采用野火法搜索周边离它最近的未覆盖点,找到后按A*算法规划出一条路径到达新的覆盖起点,直到全部覆盖为止.仿真结果表明该算法的覆盖率达到100%,重复率较其他算法低.而且从理论上进一步证明了该算法的有效性.

This paper proposed a near-optimal complete coverage path planning algorithm based on unstructured grid environments.Initially,the robot adopts internal spiral coverage.Only when the robot enters into ＂deadlock＂,namely,the grids around it either covered or occupied by obstacles,the grass fire algorithm is adopted to search a vacant grid that is nearest to the robot＇s current position.Then the robot performs A＊ algorithm to plan a path to the new vacant grid and continues its coverage.Simulation results show the proposed algorithm can cover completely and the number of duplicated grids is relatively low.Finally,this paper testified the efficiency by the graph theory.