李淑霞,杨俊成,2

(1.河南工业职业技术学院电子信息工程学院，河南 南阳 473000; 2.武汉大学计算机学院，湖北 武汉 430072)

0 引 言

路径规划算法[1]实现从起始点到目标点的无碰撞路径，但该算法并不能覆盖环境的全部区域。而现实生活中全区域路径规划[2-3](即全覆盖路径规划)的应用还是比较多的，比如排雷机器人[4]、日常家家户户用得比较多的室内清扫机器人[5-6]、智能时代用得比较多的播撒机器人、搜救机器人[7]……，这些机器人要想完成任务就避不开路径问题，并且该路径需要覆盖所给区域的所有坐标，即为全覆盖路径规划[8]问题。所以全覆盖路径规划具有一定的研究意义，其路径规划算法是核心技术，受到专家学者的关注。

全覆盖路径规划[8]是指在短时间内以低重复率走遍除障碍物外的所有自由空间。根据环境状态的不同，全覆盖路径规划可分为已知环境下的路径规划和未知环境下的路径规划[9]。在已知环境中，机器人根据当前的环境信息规划出一条重复路径最少的路径走遍环境中的所有自由点，其规划方法比较成熟[7]；在未知环境中，机器人需利用自身的传感器认知环境信息，再规划出全覆盖路径规划[10]。根据移动策略的不同，全覆盖路径规划可以分为随机移动策略和非随机移动策略。随机移动策略是清扫机器人无法直行时随机旋转一个角度，该方法简单，工作效率不高；非随机移动策略采用某种性能评价函数来控制机器人运动路径，性能评价函数是清洁效率的关键。