第40卷第lo期机械工程学报v01．40No．102004年l0月CHINESEJOURNALOFM匿CHANICALENGINEERINGOct2O04基于栅格地图的移动机器人完全遍历算法——矩形分解法田春颖刘瑜冯申坤朱世强f浙江大学流体传动及控制国家重点实验室杭州310027)摘要：提出移动机器人的一种新的完全遍历算法：矩形分解算法。首先通过机器人环境学习建立栅格地图，对环境中的障碍物实行矩形化建模。而后应用矩形化模型中的关键点将环境分解成为矩形块．最后在这个分块环境的拓扑图中寻找到一条Han】i№n路径，机器人沿此路径即可实现对环境的完全遍历。为处理复杂的局部情况，又提出基于模板的局部环境处理算法。矩形算法的优点在于机器人可以实现完全自主的复杂环境遍历，并且可以处理未知障碍，从而使算法适合于任意非结构化的工作环境。关键词：矩形分解算法HaIIlilton路径完全遍历栅格地图移动机器人中图分类号：TP240前言完全遍历的路径规划问题要求机器人遍历环境中的所有可达区域。在这个问题上已经提出了多种算法。目前常用的算法有模板算法和分块算法两类。模板算法是一种利用模板进行遍历的算法，该算法首先见于参考文献【1]，但该文章中提出的模板算法不能应用于有障碍的环境中，只对于该文中列举的一些环境具有实用性。参考文献[2]对前面提出的模板算法进行改进，可以应用于基于地图的有障碍环境并且对环境中出现的未知障碍有相应的处理策略。但是在一些特殊情况比如遇到存在凹陷的障碍物时，机器人便会进入无法处理的死循环状态。这种情况出现的主要原因是由于对整个环境缺乏整体的规划。分块算法是将环境根据障碍物的情况分解为多个分块，而后在此基础上实现遍历的算法。在设计出对分块进行局部遍历算法的基础上，完全遍历规划就简化为对各个分块进行依次遍历的问题。目前有两种主要的分块算法：Trapezoidal分块算法”1和Bous仃0phedon分块算法14】0Trapezoidal算法将环境分解为梯形块，在单个分块中机器人通过往返移动来进行遍历。Bous仃ophedon算法是Tr印ezoidal算法的改进，其目的即是减少由于分块过多而造成的重复遍历。但是Bous仃oDhedon算法只减少了机器人在相邻梯形分块之间进行移动时所产生的重复遍历，机20031108收到初稿，20040520收到修改稿器人在不相邻分块之间移动时所产生的重复遍历并没有减少。choset详细介绍了机器人在不同分块间移动的算法口】。由此算法可知，如果一个分块有很多个未被遍历的相邻分块，那么必定会有一个或几个分块被留在后面，等待机器人遍历其他的分块后再回来将其遍历。在机器人返回的过程中，必然会有大量的重复遍历产生。针对重复遍历问题提出矩形分解算法，利用分块算法的基本思想，将任意形状障碍进行矩形化建模，在此基础上构建分块环境拓扑图。此拓扑图中必然存在使各个分块间无重复遍历的Hmilton回路。如图1，Bous仃Dphedon算法将环境分为4个分块，矩形分解算法将环境分为3个分块，这样不仅进一步减少了分块数目，而且在分块后的环境拓扑图中可以寻找到一条Hmilton路径，这在Bous仃Dphedon算法的环境拓扑图中是不一定能实现的。(a)Ba岫们phedon算法(b)矩形算法图1两种算法的分块情况对比1基于栅格地图的分块建模1．1栅格地图栅格地图是由机器人自主学习得到的。每当机万方数据2004年10月田春颖等：基于栅格地图的移动机器人完全遍历算法——矩形分解法57器人被应用于一个新的环境时，机器人对环境进行一次自主学习并建立栅格地图。在工作中如果发现地图中未标注的未知障碍即调用模板进行处理并且根据新障碍的情况更新地图。机器人建立栅格地图的具体算法如图2所示。机器人首先从环境原点D沿x方向进行移动，发现障碍即绕过障碍物，此后继续沿原方向运动，到达边界后沿y增大方向移动一个车距返回。重复这个过程，直到环境学习完毕。当机器人遇到障碍物时，记录该格点为有障碍，否则记录为无障碍，根据机器人的记录情况即可以建立该环境的栅格地图。图2栅格地图建模过程1．2矩形化建模图3是对矩形房间遍历学习后建立的栅格地图，每个格点可以用∽们来表示，x表示格点所在列数，y表示格点所在行数。于是，左上角格点fl，1)，右下角格点(20，10)。其中，含有障...
