一种基于新的单元分解法的全覆盖路径规划算法

李燊

（沈阳新松机器人自动化股份有限公司，辽宁 沈阳 100169）

0 引言

全覆盖路径规划算法是指在一个有限且有界的区域内，获得一条能够覆盖除了障碍物外所有区域的路径[1-2]。一个好的全覆盖路径规划算法，应满足覆盖率高、重复率尽量低。

目前，已有全覆盖路径规划算法主要有随机法、模板法、单元分解法、栅格法等[3-4]。其中随机法让机器人随机选择一个方向前进，遇到障碍物后转向再继续前进。这种方法简单，但无法保证全覆盖[4]，一般用于未知环境中。模板法采用预先设定的模板与当前环境信息比较，进而选择下一步路径，但模板法缺乏对整个环境的规划，效率较低。

单元分解法是将含有障碍物的整个区域，分解成若干无障碍的子区域，子区域之间采用某种算法进行遍历。常用单元分解法有Trapeziodal分解法[5]和Boustrophedon分解法[6]。Trapeziodal分解法是将一条直线扫过目标区域，当直线遇到多边形障碍物的顶点时，产生IN,OUT,MIDDLE三种情形，依据不同情形将环境分成若干梯形子区域。为了减少相邻子区域边界处的重复覆盖，Boustrophedon单元分解法在Trapeziodal分解法基础上进一步合并MIDDLE操作产生的子区域，减少子区域个数，进而减少重复的覆盖，提高效率，但相邻子区域边界仍有重复覆盖问题。以上单元分解法，障碍物需为为多边形。为了解决非多边形的障碍物问题，morse分解法[7]以morse函数的等值线与障碍物的切点作为关键点,以关键点为顶点，障碍物的边界和等值线为边，对地图进行分区，同时选择不同的morse函数可以划分成不同的子区域，生成不同的规划路线。……