移动机器人混合式全遍历覆盖路径规划算法
2013-12-18李彩虹
陈 鹏， 李彩虹
(山东理工大学 计算机科学与技术学院， 山东 淄博 255091)
全遍历覆盖路径规划[1]是指在满足某种性能评价指标最优或准优的前提下，寻找一条从起始点开始，且经过工作区域内所有可达点的路径规划.全遍历覆盖路径规划是一类特殊的路径规划，在许多领域都有着广阔的应用前景，特别是很多家用场合，都要求移动机器人具备全区域覆盖的能力.
按照对环境知识的了解，全遍历覆盖路径规划可分为环境已知和环境未知的路径规划.已知环境下的路径规划，多采用单元分解法[2-3]和模板模型法[4].单元分解法是将环境分解为梯形单元，机器人在梯形单元中做往返运动，并通过邻接图来表示从一个单元到另一个单元的转移.缺点是单元分解过多致使重复率较高.模板模型法是根据覆盖区域获取的环境信息，与各个模板进行匹配来完成遍历.缺点是对环境缺乏整体规划，要求事先定义环境模型和模板记忆，对变化的环境很难处理.
对于环境未知情形下的路径规划，郝宗波[5]等提出了基于传感器和栅格地图的路径规划方法，适合简单环境.Hsu[6]等采用离线规划和在线避障方式来完成全遍历，实现过程较为复杂.邱雪娜[7]等提出了基于生物激励与滚动启发式规则的路径规划，适合简单环境，在复杂环境下出现了较多转弯和重复.郭小勤[8]提出了可动态调节启发式规则的滚动路径规划算法，有效减少转弯次数，并解决了U型障碍物区域的连续遍历问题.禹建丽[9]等在犁田式路径规划的基础上，运用回溯法来解决遍历过程中的盲区问题.
环境已知的路径规划方法不适用于环境未知的情形，而未知环境下的路径规划方法存在着重复率较高、系统开销大等缺点.为提高工作效率，采用混合式的全遍历覆盖路径规划算法.利用滚动规划把未知区域转化为已知区域.于是，未知环境下的路径规划转化为在已知区域内的路径规划，从而有效地提高工作效率.
1 实时环境信息
在未知环境下，移动机器人利用声纳传感器探测环境信息，如障碍物位置等.在研究中所使用的移动机器人是利曼科技有限公司生产的先锋机器人Pioneer3，先锋机器人Pioneer3装配有两个声纳阵，前方、后方各有一个，每个声纳阵由8个声纳环组成，用于物体检测、距离检测和自动避障等.其声纳环分布如图1所示.
图1 声纳环结构
移动机器人装载的声纳传感器，可探测机器人位置360°范围内的障碍物信息.此外，利用定位系统感知任意时刻的机器人位置Probot、目标栅格位置Pgoal(xg,yg)和障碍物位置Pobstacle(i)(i=1，…，n)等信息.
机器人的视野域Ssense定义为以机器人位置Probot为中心，以rsense为半径的圆内.假定移动机器人的行进速度恒定，运动步长为ε，ε 1)障碍属性Flag(x,y) (1) 2)覆盖属性Visited(x,y) Visited(x,y)= (2) 3)关联属性Related(x,y) Related(x,y)表示与栅格(x,y)相邻的自由栅格的个数. 4)可选属性Enabled(x,y) Enabled(x,y)= (3) 此外，还约定在栅格地图中，用机器人位置Probot所在的栅格来标识机器人，用障碍物位置Pobstacle(i)(i=1，…，n)对应的栅格来标识障碍物.如图2所示. 图2 视野域示意图 视野总域Ssensor定义为机器人在遍历过程中，探测到的区域总和.机器人在路径规划时，可依据具体情形，选择遍历视野总域Ssensor内的任意自由栅格.机器人每行进一步，须实时探测、记录视野域Ssense内的环境信息,并将新探测到的区域归入视野总域Ssensor内. 机器人在初始遍历时，执行二叉树搜索策略，直至相邻栅格被全部遍历.此时，由于没有达到全遍历覆盖的要求，随即执行目标栅格选取策略.待目标栅格确定后，执行两点法搜索策略.机器人逐步移动至目标栅格位置，并重新执行二叉树搜索策略，此后重复这个过程.在机器人移动过程中，一旦达到全遍历覆盖要求，路径规划立即终止.整个过程，就形成了有限状态机(Finite State Machine,FSM)[10]的设计思路.下面就FSM实现、策略设计、评价指标做具体阐述. 移动机器人的全遍历覆盖路径规划可通过FSM来实现，图3是规划算法的五状态FSM实现图.FSM包括五种状态，还需要设计三种策略进行状态之间的转换，分别是二叉树搜索策略、目标栅格选取策略和两点法搜索策略. 当机器人周围的相邻栅格中，不存在还未被遍历的自由栅格时，机器人须在视野总域Ssensor内，选取离当前机器人位置最近的、还未被遍历的自由栅格，作为下一遍历区域的起始栅格，我们称该起始栅格为目标栅格. 五种状态、三种策略作如下定义. S1：初始状态 S2：在机器人周围的相邻栅格中，还存在未被遍历的自由栅格. S3：在机器人周围的相邻栅格中，不存在还未被遍历的自由栅格. S4：目标栅格已确定时. S5：结束状态 F1：二叉树搜索策略 F2：目标栅格选取策略 F3：两点法搜索策略 移动机器人的全遍历覆盖过程何时结束，需依据具体环境和实际工作要求来决定.这里为了仿真实验的需要，假定遍历覆盖率达到99%，全遍历覆盖过程结束. 全遍历覆盖路径规划的FSM实现如图3所示. 图3 全遍历覆盖路径规划的FSM实现 2.2.1 二叉树搜索策略F1 机器人处于S2时，执行F1.该状态的目标是搜索与机器人相邻的自由栅格，找出其中关联栅格数最大的栅格，并遍历该栅格.值得指出的是，机器人每前进一步，须实时更新环境信息，并检测在机器人的相邻栅格中是否还存在未被访问的自由栅格.若存在，则重复F1.若不存在，机器人随即跳转至S3. 为满足二叉树搜索策略的需要，为所有栅格赋予四种属性：障碍属性Flag(x,y)、遍历属性Visited(x,y)、关联属性Related(x,y)、可选属性Enabled(x,y).这样，二叉树搜索策略选取栅格须符合：障碍属性值Flag(x,y)为1、遍历属性值Visited(x,y)为0、关联属性值Related(x,y)最大、可选属性值Enabled(x,y)为1. 二叉树搜索策略，涉及到了关联栅格数的计算问题.根据待研究栅格在栅格区域的位置不同，栅格区域可划分为三种模型：四格型、六格型和九格型.通过转化，任意栅格区域均符合三种模型，如图4所示.为此，本文仅对三种模型进行研究. (a)四格型 (b)六格型 (c)九格型图4 栅格区域模型示意图 1)若采用数组结构存储各栅格的关联栅格信息，假定数组名为A.以栅格i为例，则有： (1)当栅格i为自由栅格时 a)四格型 A{i}.Related=A{1}.Flag+A{2}.Flag +A{3}.Flag (4) b)六格型 A{i}.Related=A{1}.Flag+ A{2}.Flag+ A{3}.Flag+ A{4}.Flag+ A{5}.Flag (5) c)九格型 A{i}.Related=A{1}.Flag+ A{2}.Flag+ A{3}.Flag+ A{4}.Flag+ A{5}.Flag+ A{6}.Flag+ A{7}.Flag+ A{8}.Flag (6) 此处，若栅格i的相邻栅格中有障碍物栅格，则障碍物栅格的障碍属性值Flag为0，因此，栅格i的关联属性值不受影响，A{i}.Related能够真实反映栅格i关联栅格的实际个数. (2)当栅格i为障碍栅格时 A{i}.Related=0 (7) 2)若栅格i为机器人栅格，求所有相邻栅格的最大关联栅格数，则有： a)四格型 A{i}.maxrelated= max(A{1}.Related, A{2}.Related, A{3}.Related) (8) b)六格型 A{i}.maxrelated= max(A{1}.Related, A{2}.Related, A{3}.Related, A{4}.Related, A{5}.Related) (9) c)九格型 A{i}.maxrelated= max(A{1}.Related, A{2}.Related, A{3}.Related, A{4}.Related, A{5}.Related, A{6}.Related, A{7}.Related, A{8}.Related) (10) 通过比较，得到栅格i的最大关联栅格数A{i}.maxrelated，记录最大关联栅格数对应的栅格编号j.紧接着，移动机器人前进至栅格j，并实时更新环境信息. 2.2.2 目标栅格选取策略F2 机器人处于S3时，为使机器人离开已遍历完区域，到未遍历区域继续遍历，需选取一个目标栅格，即在视野总域Ssensor内，选取离机器人栅格最近的可选栅格，并且要求该栅格还未被遍历过.待目标栅格确定后，机器人随即跳转至S4. 假设任意栅格与机器人位置Probot(xr,yr)之间的距离用Distance表示，则目标栅格须符合：障碍属性值Flag(x,y)为1、遍历属性值Visited(x,y)为0、可选属性值Enabled(x,y)为1、Distance值最小. 若用栅格的中心点坐标来标识栅格位置，则待选栅格Pi(xi,yi)(i=1，…，m，m为符合目标栅格选取条件的栅格总数)与机器人位置Probot(xr,yr)之间的距离Distance(i)可表示为 (i=1，…，m) (11) 求Distance(i)的最小值： Distance=min(Distance(i)) i=1,…,m (12) 通过比较，得到待选栅格与机器人位置之间的距离最小值Distance，并记录该最小值对应的栅格编号k、栅格中心点坐标Pk(xk,yk). 2.2.3 两点法搜索策略F3 目标栅格确定后，机器人立即从当前位置，移动到目标栅格位置.在向目标栅格移动过程中，若已达到全遍历覆盖要求，则终止整个遍历过程.若到达目标栅格后，还未达到全遍历覆盖要求，机器人随即跳转至S2. 两点法搜索策略简述为移动机器人向目标栅格直线移动时，若遇到障碍物，就改变方向、移动到没有障碍物的位置，并再次确定目标栅格的方向、感知障碍物信息.如此反复，直至到达目标栅格[11].两点法搜索策略示意图如图5所示. 图5 两点法搜索过程示意图 由图5可知，A为起始点，B为目标栅格，起始点A与目标栅格B之间的线段AB上有障碍物.此时，首先向上偏转角度θ，得到的线段AB1上仍有障碍物，再以线段AB为基准，向下偏转角度θ，得到的线段AB2上也有障碍物，再从线段AB1开始向上偏转角度θ….如此反复，当偏转到线段ABi时，ABi上没有障碍物，得到一点C，以此类推得到另一点D，直至到达目标栅格B，整个搜索过程停止. 遍历结束后，须引入“评价指标”对遍历结果进行评价.本文采用遍历覆盖率和遍历重叠率作为评价指标.假设S表示整个工作空间，SΩ表示可达区域的面积，Shc表示已遍历的面积，Scc表示重复遍历的面积. 1)遍历覆盖率：遍历完成后，已遍历面积与可达区域面积的百分比. Jhc=(Shc/SΩ)×100% (13) 2)遍历重叠率：所有重复遍历面积之和与可达区域面积的百分比. Jcc=(Scc/SΩ)×100% (14) 为了尽可能地减少遍历盲区，不可避免地就会产生一定程度的重叠.显然，重叠率越小越好，但受系统误差、控制精度以及环境等诸多因素的影响，重叠区域不可能太小.但若机器人的性能较高，则遍历重叠率可控制在较小的范围内，遍历效率大幅提高，遍历效果趋于理想. 利用以上设计的全遍历覆盖路径规划算法，对移动机器人在障碍物稀疏程度不同的环境下进行仿真.程序运行前，设定覆盖率达到99%时，遍历结束.仿真结果如图6所示. 仿真结果表明，移动机器人在无障碍环境、障碍稀疏环境、障碍密集环境下，都能有效地躲避障碍物，高效地完成全遍历覆盖任务，遍历重复率也被控制在可接受的范围内. (a)无障碍环境 (b)障碍稀疏环境 (c) 障碍密集环境 图6 遍历效果图 本文针对移动机器人在未知环境下的全遍历覆盖任务，提出了滚动规划与搜索策略相结合的一种混合式全遍历覆盖路径规划算法，并进行仿真实验.结果表明，算法具有以下特点：能在无障碍环境、障碍稀疏环境、障碍密集环境下，完成全遍历覆盖路径规划任务；能覆盖工作区域的几乎全部区域，遍历覆盖率高；移动机器人重复遍历的栅格较少，重复率较低.从整体来看，遍历覆盖率较高，遍历重复率较低，因此遍历效率较高. 移动机器人根据全遍历覆盖路径规划算法，能够高效地完成全遍历覆盖任务，但也存在一些不足之处，如尚不能保证遍历路径长度绝对最短等，这些问题将是今后研究的课题. [1]邱燕，仪垂杰.小麦精播机器人路径规划研究[D].青岛:青岛理工大学，2011. [2]徐美清,孙晨亮.移动机器人路径规划方法研究[J].科教信息，2012(35):60-61. [3]顾国昌,张巧荣.移动机器人分层路径规划方法研究[J].哈尔滨工程大学学报，2011,22(5):31-32. [4]田春颖,刘瑜,冯申坤,等.基于栅格地图的移动机器人完全遍历算法—矩形分解法[J].机械工程学报，2004,40(10):56-61. [5]郝宗波,洪柄榕,黄庆成.基于栅格地图的机器人覆盖路径规划研究[J].计算机应用研究，2007,24(10):56-58. [6]Hsu S M,Lin C L,Yang M Y.On the complete coverage path planning for mobile robots[J].Intelligent and Robotic System，2013，7(1):1-19. [7]邱雪娜,刘士荣,宋加涛.不确定动态环境下移动机器人的完全遍历路径规划[J].机器人，2006,28(6):586-592. [8]郭小勤.未知环境下移动机器人遍历路径规划[J].计算机工程与设计，2010,31(1):172-174. [9]禹建丽,徐亮.室内自主机器人的路径规划[J].中原工学院学报，2010,21(3):1-3. [10]张峥炜.基于生物启发的群机器人系统群体搭建机制研究[D].济南：山东大学,2012. [11]李彩虹,张子间.基于两点法的机器人路径规划[J].山东理工大学学报:自然科学报，2005,19(1):17-20.
2 全遍历覆盖路径规划算法
2.1 全遍历覆盖路径规划的FSM实现
2.2 全遍历覆盖路径规划的策略设计
2.3 评价指标
3 仿真实验
4 结束语
