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

An efficient complete coverage path planning in known environments

作　　者：刘淑华[1] 夏菁[1] 孙学敏[1] 张友[1] 

机构地区：[1]东北师范大学计算机科学与信息技术学院,吉林长春130117

出　　处：《东北师大学报（自然科学版）》2011年第4期39-43,共5页Journal of Northeast Normal University(Natural Science Edition)

基　　金：吉林省科技发展计划重点项目(20100305)

摘　　要：提出一种基于栅格表示的非结构化环境下移动机器人的高效全覆盖路径规划算法.移动机器人采取内螺旋算法从起始点进行覆盖,当陷入覆盖死角时,采用野火法搜索周边离它最近的未覆盖点,找到后按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.

关 键 词：全覆盖路径规划 内螺旋算法 野火法 A＊算法 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]