一种基于环境栅格地图的多机器人路径规划方法

　　全覆盖路径规划[1]的目的是让移动机器人合理而高效地走遍一个区域内除障碍物以外的全部地方;全覆盖路径规划问题也就是完全遍历的路径规划问题,即要求机器人遍历环境中的所有可达区域。全覆盖路径规划分为无障子区域分解、子区域内部行走路径、子区域衔接顺序等3个问题的研究。国内外对此问题已经提出了多种算法。目前应用较多的是分块算法。主要的分块算法有:Trapezoidal分块算法[2]、Boustrophe-don分块算法[3]和矩形分解法[4]。

　　分块算法是将环境根据障碍物的情况分解为多个分块,而后在此基础上实现遍历的算法。在设计出对分块进行局部遍历算法的基础上,完全遍历规划就是简化为对各个分块进行依次遍历的问题。Trapezoidal分块算法是将环境分解为梯形块,在单个分块中机器人通过往返移动来进行遍历。Bous-trophedon分块算法是Trapezoidal分块算法的改进,

　　其目的是即是减少由于分块过多而造成的重复遍历。矩形分解法是将环境中任意形状障碍物进行矩形建模,构建分块环境拓扑图,在拓扑图中求解出一条Hamilton路径,机器人沿着分块的Hamilton路径遍历每个分块来实现对整个环境的完全遍历。

　　机器人在分块间移动时,分块算法所产生重复遍历路径将使机器人降低运行效率。对于应用浇灌、播撒、监控、警戒、探测等任务的机器人,利用分块算法的基本思想,我们提出了应用多机器人系统的分区算法来实现已知环境区域的全覆盖路径规划,以及机器人路径的优化,使得提高机器人的运行效率,高效快速地完成任务。在每个分区内应用广义VORONOI图法建立规划机器人的全覆盖探测运行路径,在此基础上构建路径拓扑图,利用加权值的深度优先搜索算法和Dijkstra算法优化机器人运行路径,即得出了一条机器人运行路径序列。

　　1　栅格地图的分区建模

　　1·1　矩形栅格地图建模

　　栅格地图是对已知的环境信息进行栅格处理后得到的信息地图。对得到的环境信息进行矩形化建模,以球形机器人的最大外径作为栅格的单元长度,从而把给定的环境信息转化为矩形化的栅格地图。

　　每个栅格格点以其格点中心节点来表示,把整个栅格地图对应到坐标系中,每个节点对应坐标系上的坐标,即用(x,y)来表示,x表示节点所在的列数,y表示节点所在的行数;而整个坐标系的坐标单位长度为栅格的单元长度,即每个机器人占据一个坐标单元格。于是定义,左上角节点为(1,1),右下角节点为(Xmax,Ymax)。其中,含有障碍物信息的节点标注为1,不含有障碍物信息的节点标注为0;并且我们称含有障碍物的栅格为‘占有’栅格,把不含有障碍物的栅格称为‘空闲’栅格。所以,整个栅格地图就由‘占有’栅格和‘空闲’栅格组成,如图1和图2所示