刘淑华，夏 菁，孙学敏，张 友

（东北师范大学计算机科学与信息技术学院，吉林 长春 130117）

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

刘淑华，夏 菁，孙学敏，张 友

（东北师范大学计算机科学与信息技术学院，吉林 长春 130117）

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

全覆盖路径规划；内螺旋算法；野火法；A＊算法

0 引言

随着智能服务型机器人的迅速发展，全覆盖路径规划技术的研究越来越受到研究者的重视.全覆盖路径规划是指机器人以尽可能低的重复率遍历环境中的全部无障碍区.因此，它包含两个方面的技术指标，即覆盖率和重复率.全覆盖路径规划技术有着广泛的应用背景，它对清洁机器人、草坪修剪机器人、矿藏探测机器人以及扫雷机器人等都具有重要意义.

已有的全覆盖路径规划算法主要包括随机方法，最大面积优先算法，ISC（内螺旋覆盖算法），基于模板的完全覆盖方法，Boustrophedon往复前进法等［1－5］.随机方法让机器人随机选择一个方向前进，遇到障碍物后转向再继续前进［6］.该算法简单易行，但无法保证完全覆盖.最大面积优先算法将待覆盖的区域划分成许多栅格，机器人在行走过程中随时计算当前位置的前边、左边和右边三个方向上未覆盖栅格的数目，若前方有未覆盖栅格，则继续前进，否则朝未覆盖栅格较多的方向转弯.基于模板的完全覆盖方法则是利用已知的环境地图和一系列模板规划出覆盖路径，对不同的地形应用不同的模板.该方法能实现完全覆盖，但要求事先知道环境地图.Boustrophedon往复前进的方法分为简单的往复式策略和改进的往复式策略.简单的策略会留有由障碍物引起的未覆盖区域，而且障碍物越多，未覆盖的区域就越多.改进的策略是进行与第一次行进方向相垂直的第二次覆盖，进而提高覆盖率.因此，上述方法在覆盖效率方面都有待于提高.

1 问题描述

由于栅格地图易于计算是否实现完全覆盖，因此本文研究栅格环境下移动机器人的全覆盖路径规划技术.环境中存在任意形状的障碍物，机器人先按一定的算法进行自主覆盖，只有当机器人陷入死角（周边的所有栅格都已经覆盖完）时才“拿”出地图进行搜索，搜索到下一个未覆盖的区域后移动到新的区域继续进行自主覆盖，直到全部完成为止.因此，本文研究的是已知非结构化环境下的半自主全覆盖路径算法.

2 算法描述

本文首先采用内螺旋算法进行覆盖，当机器人陷入局部死锁点时，用野火法搜索离机器人当前点最近的未覆盖点，找到以后用A＊算法规划出从当前点到未覆盖点的最短路径，再开始新区域的覆盖，直到全部覆盖完成为止.

2.1 内螺旋法

内螺旋算法的基本思想是机器人按一定的方向（如顺时针或逆时针）进行覆盖，当前方有未覆盖的栅格时，机器人就向前运动，如果前方有障碍物或者已经覆盖过，则向右转90°，如图1.

2.2 野火法

野火法又称广义的宽度优先搜索法，是一种在固定尺寸的单元阵列中有效且易于实现的寻找路径技术.算法采用从目标位置向外的前波扩展，直到找到所需要的单元格为止.本文对该算法进行了扩展，即采用全方位的扩展波，当机器人陷入死角时，算法向机器人的8个方向一起扩展，直到找到一个空闲的单元为止.如图2-A.当机器人陷入死角时，首先按图2-B查找机器人周围的8个栅格，如果没有找到空闲的栅格，则继续扩大搜索范围，查找距离机器人为3的栅格，如图2-C.按此方法依次扩大查找的范围，直到找到一个空闲的栅格为止.

图1 内螺旋算法示意图

图2 野火法示意图

2.3 高效的全覆盖路径算法

结合内螺旋算法、野火法以及A＊算法，本文提出了一种高效的全覆盖路径规划算法.算法的具体步骤如下.

Step 1按内螺旋算法进行全覆盖.

Step 2如果前方栅格有障碍或已经被覆盖，则向右旋转90°.

Step 3如果机器人陷入死角，转Step 4；否则转Step 1.

Step 4用野火法搜索离机器人最近的未覆盖栅格，如果没找到，说明地图已经被全覆盖，转Step 7；否则转Step 5.

Step 5用A＊算法规划出从机器人当前位置到搜索到的未覆盖点之间的最短路径，然后机器人按该路径到达未覆盖的栅格，此时会出现一定数量的重复覆盖，但由于A＊算法得到的是最短路径，所以尽可能保证较低的重复率.

Step 6机器人从新的起点继续执行覆盖任务，转Step 1.

Step 7算法结束.

2.4 算法的有效性证明

如果环境中存在多个待覆盖的区域B，C，D和E，当前机器人在A点陷入死角，如图3所示.内螺旋算法的特点是由区域的四周向中间覆盖，所以每个未覆盖区域可近似地抽象为它的中心点.因此，图3可以抽象为图4.

图3 地图中存在多个待覆盖的区域

图4 抽象后的连通图

此时，要使重复覆盖最少就转变成了旅游商问题（TSP），即求从某一顶点出发，遍历完图中全部的顶点且要求路径最短.其中，最近邻点法（Nearest Neighbor Procedure）是求解旅游商问题的解法之一，即开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到最后.该方法与本文用到的野火法寻找下一个结点，然后用A＊算法求到下一个结点的最短路径是完全吻合的，因此，本文的方法从理论上能证明是最优的.

3 仿真结果

本文提出的算法在自行开发的机器人仿真平台GA上进行多次仿真实验，并与其他的算法进行了对比.

首先，以文献［7］中的地图为例，用本文提出的算法进行了仿真.图5是一个家庭的结构图，图6是对应的栅格地图，大小为40＊50.图7是用本文提出的算法覆盖后的效果，深灰色代表的是障碍，浅灰色代表清扫过的栅格，黑色代表重复的栅格.

图5 房间的平面图

图6 房间的栅格地图

4 算法性能分析和改进

上述算法的性能已经实现，重复率很低，但还存在一定的问题，即对于凹陷形的障碍物或有较长的障碍物阻挡时适应性有所下降.原因在于用野火法寻找下一个未被覆盖点时，没有考虑被障碍物阻挡的问题.如图8.

图7 重复率为3.3%的效果图

图8 凹陷形障碍的野火法扩展

如果机器人陷入了“死角”A点，此时按野火法扩展时，找到离A点最近的未覆盖点是C，但实际情况是B点离A点最近.为此，对上述算法的Step 5进行改进，具体改进方法如下：

假设机器人当前处于“死角”A点，用野火法搜到离A点欧式距离最近的点为C.机器人先用A＊算法规划出从A到C的路径，然后在沿该路径从A到C运动的过程中，增加机器人的视距，视距的大小依赖于视机器人的传感器，本文分别对机器人的视距为1，2，4的情况进行了仿真.机器人在行进的过程中，如果发现视距范围内有未覆盖的栅格，则停止向C点前进，而是从视距内发现的空闲栅格开始进行新一轮的内螺旋覆盖.

用改进后的算法对图6所示的环境再次进行仿真，将机器人的视距分别设为2和4，得到的仿真结果如图9和图10.

图9 机器人的视距为2，重复率为3.05%的仿真结果

10 机器人的视距为4，重复率为2.05%的仿真结果

接下来本文还做了其他仿真，包括不同起始点测试、障碍物的形状和复杂度测试，以及与其他算法的对比.

图11 起点在（0，0），重复率为4.2%的仿真结果

图12 起点在（35，5），重复率为4.6%的仿真结果

表1 全覆盖算法性能比较%

由图9和图11可以看出，障碍物的形状越不规则、障碍物越多，覆盖的重复率就越大；由图11和图12可以看出，本文的算法性能基本不受起始点的影响.

最后，用文献［8］的地图进行对比实验，地图的大小为30＊55栅格.仿真结果如图13.

图13 仿真对比

5 结论与未来的工作

本文提出了一种结合内螺旋算法、野火法和A＊算法的全覆盖路径规划算法，仿真结果表明，该算法适用于存在任意形状障碍物的环境，对清扫的起点没有依赖，清扫效率很高.另外，我们从理论上证明了该算法的有效性，理想情况下，该算法的效果与旅游商问题的求解相吻合，但当有较大长度的障碍物阻挡时，算法的性能会有所下降.未来的工作是让机器人加强对环境的理解，尤其是室内房间结构的学习和理解，然后再结合门栅格技术，使算法的效率得到进一步的提高.

［1］ CARVALHO R N，VIDAL H，HIEIRA P.Complete coverage path planning and guidance for cleaning robots［C］／／Proceedings of the IEEE International Symposium on Industrial Electronics，Guimarães，Portugal：Institute of Electrical and Electronics Enginee，1997：677-682.

［2］ ITAIA，PAPADIMITRIO C，SZWARCFITER L.Hamilton paths in grid graphs［J］.S IAM Journal on Computing，1982，11（4）：676-686.

［3］ GAGE D.Randomized search strategies with imperfect sensors［C］／／Proc of SPIE Mobile RobotsⅧ.Boston，1993：270-279.

［4］ BALCH T.The case for randomized search［C］／／Proc of IEEE Inter-national Conference on Robotics and Automation.San Francisco，CA，2000：264-275.

［5］ CHOSETH，PIGNON P.Coverage of known spaces：the Boustrophedon cellular decomposition［J］.Autonomous Robotics，2000，9（3）：247-253.

［6］ LATOME J-C，BARRAQUAND J.Robot motion planning：a distributed presentation approach［J］.International Journal of Robotics Research，1991，10：628-649.

［7］ 林宗德.居家清洁机器人之全域覆盖路径规划与实现［D］.台南：国立成功大学工程科学系，2005.

［8］ 田春颖，刘瑜，冯申珅，等.基于栅格地图的移动机器人完全遍历算法——矩形分解法［J］.机械工程学报，2004，40（10）：56-61.

An efficient complete coverage path planning in known environments

LIU Shu-hua，XIA Jing，SUN Xue-min，ZHANG You
（College of Computer Science and Information Technology，Northeast Normal University，Changchun 130117，China）

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.

complete coverage path planning；internal spiral coverage；grassfire；A＊algorithm

TP 242

520·20

A

1000-1832（2011）04-0039-05

2010-12-08

吉林省科技发展计划重点项目（20100305）.

刘淑华（1970—），女，博士，副教授，主要从事移动机器人研究.

陶 理）