救援机器人搜索目标路径环境快速建模仿真
2021-11-17包琳，高巍
包 琳，高 巍
(大连海洋大学，辽宁 大连 116023)
1 引言
灾害发生时，事故现场的危险指数、复杂指数都是极高的，救援的紧迫性给救援工作带来了严峻的考验。灾害发生后的黄金救援时间为72小时，而这段时间事故现场因为有害气体较多、高温缺氧以及二次灾害的影响，使得救援工作难度大大增加，如果救援人员此时贸然进入事故现场进行救援，对自身的生命安全也会构成极大的威胁。救援机器人以其体积小、灵活性高等诸多优点在事故救援中被广泛应用，使紧迫的救援工作效率得以提高，并且有效防止了二次灾害事故对人员的伤害。
通过对事故现场障碍物距离[1]的感知，为机器人的导航、避碍等功能提供依据，这就需要对事故发生后的非结构化环境[2]进行环境建模，即在未知环境中准确判断障碍物位置信息，实现安全无碍的行走。对于救援机器人来说，环境建模的方法有很多，大多都是复杂且繁琐的，通过将实际的救援现场环境转换为图的表达形式，进而可以抽象的对救援现场的骨架进行描述和分析。对于非结构化环境建模的描述方法，主要有可视图法、自由空间法等对救援环境建模描述。
文献[3]提出一种可视图法，对于规划的机器人必须能等效地看成一个可活动的点，保证起始点、目标点以及障碍物的各个顶点可以连接在一起，同时还要保证连接的线不会触碰到障碍物，这就构成了一张无向图，即可视图。该方法在计算最短路径方面较为简便，但同时也伴随着一个很明显的缺点：当环境空间改变了，如障碍物个数的改变、障碍物位置信息发生变化等，则需要再重新构建一张新的图，缺乏灵活性，并且在路径规划方面误差较大，无法实现机器人在未知环境中安全无碰的行驶。
文献[4]提出基于自由空间法的救援机器人搜索目标路径方法，将环境空间中的障碍物信息通过二维平面内的多种凸多边形表现出来，在二维平面内实现连通图，完成对环境空间的建模。优势很明显，无论环境空间怎样变化，也不需要重新构图，具有极大的灵活性。但是缺点也很明显：障碍物的密集度越大程序越复杂，计算起来非常麻烦，所以自由空间法只能做到粗略的估计路程情况，无法做到精确计算。
本文综合考虑救援现场非结构化环境的特点，提出了在未知的事故环境中构建栅格地图，采用拓扑方法对地图进行处理，将救援机器人搜索到的障碍物信息点自动生成栅格Voronoi图，得到准确的障碍物位置信息，对机器人的行驶路径进行分析，准确判断出障碍物位置，减少路径规划误差，为机器人提供有效的路径分析，保证机器人安全无碰行驶。
2 栅格地图算法占有率计算
由于栅格地图简单易懂，能直观的表达环境空间信息和信息数据易存储等特点，被广泛应用于机器人搜索目标路径导航、安全无碍行驶、位姿估计等方面[5]，尤其是处理激光雷达采集到的数据方面，更起着不可或缺的作用。栅格地图，顾名思义，是把整个全局环境空间划分为若干个大小相等的小栅格，并对每个小栅格的占有概率赋予概率值。当机器人的位姿发生变化时，已经保存在系统中的局部环境地图也会随之发生变化。虽然环境空间过大或者对机器人位姿准确度要求过高，栅格地图自身在运算时占用了大量的存储空间和计算时间，但是对于救援现场这种非结构化环境来说，采用栅格地图算法环境建模也是可取的[6]。
栅格地图创建算法采用贝叶斯滤波器计算每一个小栅格占用的后验概率，若机器人所在栅格的坐标为(x，y)，mx，y为该栅格的占有概率，每个栅格有空闲或占用两种状态。假设事件x拥有的概率p(x)的概率定义为p(x)/[1-p(x)]，在已知位姿s′、观测点z′的前提下，利用二元贝叶斯滤波器可得静态地图的工作原理公式如下：
(1)
加法运算计算起来比乘法运算更简单便捷，还可以避免乘法运算的不稳定性，所以通常会采用对数的形式
(2)
占有栅格地图只有接收到传感器传来允许更新栅格单元状态时才可以对数据进行更新，否则不更新。占有栅格地图在创建时要有2个概率密度：p(mx，y|zt，st)和p(mx，y)。p(mx，y)表示占有栅格的后验概率，p(mx，y|zt，st)表示逆向传感器模型在采集障碍物数据信息zt时，指定位姿st在栅格元素mx，y的占有概率。表1为地图静态时逆向传感器采集到的占有概率，表2为地图在动态状态下逆向传感器采集到的占有概率，为获取救援现场环境信息提供依据。
表1 静态地图逆向传感器
表2 动态地图逆向传感器
3 栅格地图下目标路径环境快速建模
3.1 救援现场环境信息获取
现场环境信息采集设备选用URG-04LX机器人专用暗光条件激光雷达，它可采集240°内69个方向上的不同障碍物的距离数据，筛选出有效信息。通过对比雷达所探测到的最大距离信息与机器人可通过的最窄宽度，可知角度分辨率为3.64°。如图1所示，以机器人为中心，可获得由不同方向上障碍物的位置信息构成的扇形平面。
图1 救援机器人建立栅格地图
救援机器人在全局现场中的位置坐标为(x，y)，航向角为γ，可以得到当前某一方向上障碍物的位置坐标为(Xo，Yo)，在局部环境空间中可用式(2)来表示，其中，φ=3.64°n，表示救援机器人的行走方向与第n个方向之间所形成的夹角。
3.2 障碍物地图拓扑分析
便于救援机器人更好的了解救援现场环境，还需要对机器人下达指令，分析在当前环境中基于全局搜索目标的可行驶路径[7]。
1)在对可形式路径分析之前首先需要对地图上的障碍物信息值进行膨胀运算。这样做的优势在于一方面可以使机器人在遇到障碍物时减速运行，产生一段缓冲距离，避免机器人碰撞到障碍物；另一方面使离散的障碍物信息随着膨胀的过程形成连接在一起的一体障碍物，减少离散数据[8]在栅格地图上对障碍物的表达准确率误差。
2)然后需要对膨胀后的栅格地图上的障碍物图块进行分割运算并赋值。依据在栅格地图上搜索到的障碍物图块的先后顺序对障碍物赋值，赋值为m，m∈N。
3)最后对分割好并赋值的地图采用基于栅格主动生长Voronoi图做可行驶路径规划。连接各邻点之间的直线构成一个多边形，得到传统Voronoi图，然后与没有连接在一起的栅格单元相结合，障碍物栅格主动生长，最后得到栅格地图的Voronoi边。只要救援机器人在Voronoi边上行走，那么与障碍物发生碰撞的几率几乎为0。
栅格主动生长是将救援机器人搜索到的栅格地图上的所有障碍物信息点看成原始的核，在向周围栅格等速扩大的同时，占领空白栅格，称为胚，在遇到非自由栅格时停止运行。这时栅格地图中不存在空白栅格，已全部被占领，自动生成栅格Voronoi图，生长原理如图2所示。
图2 栅格Voronoi图原理
通过以上对障碍物地图拓扑分析，可知基于主动生长的Voronoi图生成过程如下：
步骤1：建立空集胚元素表D、核元素表S。
步骤2：添加核元素，将搜索到的所有值为0的邻接栅格全部放入表S中。
步骤3：检索障碍栅格，将所有值为0的邻接栅格全部放入表D中，即为胚。
步骤4：将表D中所有胚的邻接栅格值全部设置为原始胚值，并将表D置入表S中。
步骤5：全面检查新生长的邻接栅格值，将在生长过程中发生改变的邻接栅格值放入表D中，同时更新表D中的胚值，将原胚元素删除。
步骤6：如果表S中存在空位栅格，重复步骤3操作，如果没有空位栅格，即可输出。
步骤7：分析全部邻接栅格值，获取需要的Voronoi边和节点。
3.3 建立地图模型
对于事故现场这种规模比较大的环境来说，在使用栅格地图进行环境建模时，应充分控制好栅格地图规模不易较大。在机器人进行救援工作之前，还要分析自身位置与事故现场中障碍物位置，那么就需要对栅格地图做预处理、明确障碍物位置信息、提取出可行驶路径。采用拓扑方法对地图进行预处理，对全局环境信息[9]做更全面的描述，减少离散数据，保证整个环境空间的连续性。
构建栅格地图首先需要构建度量信息。每个栅格单元的大小，即栅格地图的分辨率定义为g×g(g>0)，g代表事故现场环境与栅格地图单元所对应的度量值。局部范围内栅格地图的大小可定义为w×l，w，l∈N，其中，w表示栅格地图横坐标最大值，l表示栅格地图纵坐标最大值。已知救援机器人所在栅格坐标为(x，y)，其中0
d(p1，p2)=|x1-x2|+|y1-y2|
(3)
其中，p1坐标为(x1，y1)，p2坐标为(x2，y2)。定义栅格地图上2个栅格(p1，p2)之间的拓扑关系，有相邻和相离两种。
相邻的栅格拓扑关系从度量的角度可定义为
[(x1=x2)∧(y1=y2)]∨[(x1≠x2)∧(y1≠y2)]
(4)
相离的栅格拓扑关系可定义为
(x1≠x2)∧(y1≠y2)
(5)
通过定义栅格之间的拓扑关系，即可对膨胀、腐蚀两种栅格拓扑运算作出定义。
膨胀运算：设定栅格p膨胀后的值为z，经过膨胀运算后可使该栅格单元的4-邻接栅格值全部替换为z，即
{p(x-1，y)，p(x+1，y)，p(x，y+1)，p(x，y-1)}=z
(6)
腐蚀运算：与膨胀运算恰恰相反，运算过程为膨胀运算的反过程，最终结果可使该栅格的4-邻接栅格值全部不等于z，即
{p(x-1，y)，p(x+1，y)，p(x，y+1)，p(x，y-1)}=0
(7)
(8)
随着机器人在工作区域内行走获取环境信息的同时，栅格地图也会随之不断扩展，这样下去势必会出现计算资源不足的情况。这就需要人为干预[10]栅格地图的规模。设定一个矩形范围，只允许机器人在此范围内行走，超出部分将不会被记录。具体设定范围大小应根据实际救援现场区域的宽窄而定。
4 仿真研究
为了验证所提方法的可行性，进行仿真测试。实验环境为6m×9m的环境空间，如图3所示。机器人采用频率2.4GHz的CPU及Windows2000系统。机器人在实验环境空间中行走，通过分析障碍物位置信息，可得出一条在当前环境中安全无碍的可行驶路径。实验中栅格拓扑地图模型用60×90的栅格元素来表现，分辨率设为0.1m。
对实验环境空间进行膨胀运算，可得出当前实验环境的栅格地图，如图3(a)所示。图3(b)表示经过分割运算后，用不同的灰度值表示不同的障碍物位置信息；如图3(c)表示障碍物栅格Voronoi图。将图3(c)进行障碍物位置信息提取，可以得到机器人行走过的环境空间内的可行驶路径网络，如图3(d)所示。
图3 实验环境建模与分析
在此实验测试中，环境地图的更新及Voronoi图分析时间较迅速，能够通过提取障碍物位置信息得到障碍物栅格Voronoi图，由此规划机器人行走过的环境空间内的可行驶路径准确避开了障碍物位置，有效提高了救援机器人搜索目标路径环境规划的准确率及效率。
5 结论
本文提出了一种救援机器人在搜索目标过程中路径环境快速建模方法。通过分析栅格拓扑地图上的Voronoi方法，对事故现场这种非结构化环境进行环境建模，可以得出救援机器人在环境空间内安全无碍的可行驶路径网络。通过仿真测试得到结论如下：
1)所提方法能够迅速得出环境地图的更新及Voronoi图分析结果，有效提升了救援机器人搜索目标路径效率。
2)通过障碍物栅格Voronoi图得到的机器人可行驶路径准确避开了障碍物位置，救援机器人搜索目标路径环境规划准确率较高。
本文所提环境建模方法对救援机器人在救援现场工作提供了精确的地图环境模型，并具有极高的适应能力和较好的路径规划效率。但是本文方法在建立模型地图规模方面还存在一定的局限性，以后将扩大地图规模作为主要的研究重点。
