激光数据聚类和Morphin算法下的机器人避障研究①

, ,

(安徽工程大学 安徽省电气传动与控制重点实验室,安徽 芜湖 241000)

0 引 言

在机器人导航中，障碍物是不可避免的、随机出现且形状不可预知的[1-3]。目前，在避障问题上常使用激光传感器，其探测距离远，测量精度高。

黄如林等[6]提出一种基于动态障碍物几何特征和障碍物回波脉冲宽度特征融合的动态障碍物检测与跟踪方法。虽然较好的实现对障碍物的检测，但缺乏对障碍物运动轨迹的预测和避撞策略的描述。刘杰等[7]利用静态障碍物和目标点之间的位置关系，提出一种通过调节自适应阈值的改进矢量场直方图避障算法，但该方法缺乏对动态障碍物检测和预测的阐述。杨月全等[8]针对一类圆形动态障碍物，采用最小二乘法对障碍物边缘进行拟合，实现避障规划，但该方案受限于动态障碍物的形状。

目前，利用激光传感进行避障的相关研究大多数是针对避障问题中某个过程的研究，但是关于整个避障体系的阐述很少且存在部分局限性,对激光数据采集，进行障碍物检测、预测及避撞研究，阐述一套完整的避障体系。

1 障碍物检测

利用激光传感器在不同时刻的扫描数据区分环境中存在的动态和静态障碍物，并求解出动态障碍物的运动状态。在障碍物检测过程中，以机器人为中心设定圆形窗口，在窗口内进行利用激光传感器进行数据采集，对所获得的激光数据进行聚类、匹配和分类操作区分出动静障碍物，对动态障碍物进行分析确定障碍物的运动速度和方向角度。记录障碍物和机器人运动信息，绘制当前窗口内的动态地图，动态地图随着圆形窗口不断更新。

1.1 激光传感器数据采集

栅格地图[9]具有易于构建和维护的特点且不需要其他参数，因此采用栅格地图建立环境模型。现规定机器人携带的激光传感器和机器人本身采用同一坐标系以及机器人的出发点与世界坐标系的原点重合。同时，通过激光传感器对周围障碍物的扫描获取环境信息。

采用德国SICK公司生产的二维激光传感器，根据激射出的脉冲红外激光束碰到物体发生反射，由接收器接接收，通过时间间隔来计算出目标距离。它的角度分辨率为0.5°，在180°的扫描范围内可获得361个障碍物距离数据点。障碍物的位置信息可以表示为(ρo,θo)(o=1,2,...361)，其中：ρo、θo分别表示机器人到障碍物的距离及角度。障碍物位置(xo,yo)在机器人世界坐标系中的表示如式(1)所示。

(1)

再通过式(2)映射到栅格地图中的位置。

(2)

1.2 障碍点聚类

机器人在圆形窗口运动，利用激光传感器扫描障碍物获得的是一些孤立的点集，为了确定这些点集所属的目标障碍物，提出一种自适应阈值的最近邻聚类方法。

规定圆形窗口内获得的激光数据为有效数据，对其进行聚类。采样时刻t时，通过比较连续障碍点的距离和预先设定阈值的关系判断是否属于同一障碍物：当两点间的距离小于阈值，则认为两个点属于同一障碍物；若两点间的距离大于阈值，则认为两点不属于同一障碍物，即表示有新障碍物出现，依次将每个数据点与它前一个点进行比较完成聚类。自适应阈值的设定如式(3)、(4)所示。

d≈r·sin(0.5°)

(3)

d'=λ·d

(4)

d表示相邻两激光反射点之间的距离，r表示激光束的长度，λ表示自适应参数。

聚类后可以得到若干个障碍聚类子集Ok(t)构成的障碍物链Ob_list(t)，如式(5)、(6)所示。

Ob_list(t)={O1(t),O2(t),···,OK(t)}

(5)

Ok(t)={IDk(t),Zk(t),Sk(t),Vk(t)}

(6)

IDk(t)表示障碍物的状态量；Zk(t)表示质心；Sk(t)表示区域面积；Vk(t)表示动态障碍物的速度。

对先前聚类的障碍数据进行时间关联性分析来确定获得的障碍物类型及运动障碍物的运动信息，评估函数如式(7)所示。

(7)

(8)

其中，F表示障碍子集质心间的距离；G表示两障碍子集不重合面积占总面积的比重；λF，λG表示系数。

根据评估函数的大小得到的障碍物类型如图1所示。

图1 障碍物聚类结果

如图1(a)所示，在相邻时刻，C值最大，可认定障碍物为静态障碍物。

如图1(b)所示，在相邻时刻，C值最小，可认定障碍物为两个不同的障碍物。

如图1(c)所示，在相邻时刻，C值处于最大最小值之间，可认定障碍物为动态障碍物。

1.3 匹 配

机器人不断地运动，激光传感器时刻采集障碍物数据，为了确定不同时刻得到的障碍物是否来自同一个障碍物，需要对当前时刻障碍物链表Ob_list(t)中的障碍物和上一时刻障碍物链表Ob_list(t-1)中的障碍物进行配对操作。配对的障碍物是同一个障碍物的条件是两个障碍物数据关联评估函数的取值大于预先设定的阈值c。具体实现过程如图2所示 。

图2 障碍物匹配流程图

1.4 分 类

完成配对的同一个障碍物，需要进行分类来区分是静态障碍物还是动态障碍物。具体实现过程如图3所示。其中ηk表示障碍子集合的点重合度。

图3 障碍物分类流程图

1.5 运动障碍物运动信息

对聚类后获得的动态障碍物进一步分析计算出其运动的速度以及角度。

图4 障碍物运动过程

(9)

(10)

(11)

(12)

其中，γ表示机器人的航向角；vO、αO分分别表示障碍物运动的速度和方向角度。

2 障碍物预测

障碍物预测是根据障碍物的运行轨迹来预测移动机器人和运动障碍物的碰撞关系。机器人在行走过程中，会遇到突发的障碍物，机器人根据自身携带的激光传感器对运动障碍物进行检测，获得运动信息并结合自身的运行信息绘制出圆形窗口内的动态地图来预测碰撞情况。这里针对以下可能发生碰撞的几种情况进行讨论。

图5 预测情况1

如图5所示，当机器人缓慢行走时，探测前方有障碍物以较快速度运动，得出障碍物的运动方向和速度，预测不会与障碍物相撞。

图6 预测情况2

如图6所示，机器人探测到前方有动态障碍物以较慢速度运动，得出障碍物的运动方向和速度，预测两者发生碰撞的位置。

如图7所示，机器人探测到对向而来的动态障碍物，两者相撞不可避免，预测发生碰撞的位置。

图7 预测情况3

3 障碍物避撞

这个过程主要是决策规划出合理的行走路径来进行静态或动态障碍物避让，利用Morphin算法进行实现。

Morphin算法是一种基于地面分析以及对先验栅格地图进行可行性统计分析的局部路径避障算法。如图8所示，机器人探测到障碍物时会在位置前设置数条避开障碍物的备选路径，再根据机器人当前状态以及备选路径的评价函数选出一条最优避障路径。

图8 Morphin算法备选路径

以机器人当前位置和障碍物的连线作为Morphin算法的中心线，其方向始终朝向障碍物，在中心线左右两侧各画若干条弧线，并采用式(13)对每条弧线进行评价。

(13)

其中，D表示每条弧线路径的长度；M表示每条弧线路径的拐点参数；ΔL表示弧线所经过的每个栅格点到子目标点距离的平均值；W表示弧线终点与子目标点连线与障碍物栅格相交的次数；ε1、ε2、ε3、ε4表示各个参数的权值。当障碍物位于弧线上时，评价函数y的值为无穷大，y值最小的那条弧线表示局部最优路径。

图9 总体流程图

图10 仿真结果图

机器人行走过程中，遇到静态障碍物和各种动态障碍物，采取不同的避障策略。

当检测到静态障碍物时，直接调用Morphin算法；当遇到图5所示的情况，机器人不采取任何措施，继续运行；当遇到图6所示的情况，机器人将停止运行直到障碍物离开预测的碰撞点；当遇到图7所示的情况，机器人在到达碰撞点之前调用Morphin算法。

4 仿真实验

为了说明上述所提的算法对移动机器人在未知环境中避障的有效性，在Matlab进行仿真验证。算法总体流程图如图9所示。

仿真结果如图10所示。V1、V2、V3、V4表示圆形窗口；S1、S2、S3、S4表示检测到的静态障碍物；D1、D2、D3-1、D3-2、D4表示检测到的动态障碍物；B、C、E表示机器人检测到动态障碍物位置；A、D、F表示机器人避障发生的位置。窗口内其他黑色圆形表示检测到的其他障碍物；窗口外灰色圆形表示无效区域内的障碍物，不参与任何避障操作。

表1 障碍物运动速度和角度

从图10和表1看出，机器人在V1窗口内运动，构建出动态窗口地图，在该地图内，机器人在A点检测到障碍物S1调用Morphin算法进行避障，在A到B段，检测到动态障碍物D1的运行速度为450mm/s，角度为80.83°；一旦机器人超出V1的有效区域，立即构建V2的圆形窗口，在C到D段检测到动态障碍物D2的运动运行速度为760mm/s，角度为62.47°，并在D处检测到障碍物S3立即调用Morphin算法。同样地，超出V2有效区域，构建V3的圆形窗口，当运行到E点时，检测到障碍物D3-1运行速度为510mm/s，角度为91.05°，在O1处发生碰撞，此时机器人将采取暂停运行操作，但检测到障碍物D3-2远离碰撞点时，则开始运行；当在V4窗口内运行到F点时，检测到对向而来的障碍物，其运行速度为805mm/s，角度为180.09°，预测碰撞不可避免，并预测到碰撞位置发生在O2处，此时机器人提前做出避障措施调用Morphin算法避开障碍物。

5 结 语

针对未知环境中移动机器人避障问题，提出一种基于激光传感器的障碍物检测、预测及避障方法。首先，设定圆形窗口作为机器人有效扫描区域，根据采用自适应阈值的最近邻聚类方法对激光数据进行聚类，通过匹配和分类算法确定障碍物类型，完成运动障碍物速度和方向角的检测；再通过实时绘制窗口内的动态局部地图来预测移动机器人和障碍物碰撞的关系，结合Morphin算法做出相应避障措施。仿真实验表明，移动机器人能够有效地检测出障碍物，进行碰撞预测，并做出合理地避障措施。下一步，将该算法用于实验室机器人上进行验证，并考虑与其他传感器的融合，进一步提高避障性能。