应急场景通信机器人布放路径规划

孙 弋，雷锦航

(西安科技大学 通信与信息工程学院， 西安 710600)

0 引言

通信基站布放在应急场景下的机器人通信系统搭建过程中具有十分重要的作用[1]。采用具有通信能力的通信机器人进行通信站点布放就是在一定环境下寻找一条连接起始点到目标点的可行路径的过程[2]。该过程即路径规划，是机器人技术的重要研究方向[3]。

路径规划可表示为：在已知范围内，机器人自动搜寻一条连接起始点到目标点的最优可通行路径[4]。目前主要路径规划算法有人工势场法[5]、A*算法[6]、Dijkstra 算法[7]、可视图法[8]和快速扩展随机树(RRT)算法等。其中，RRT算法因更适合移动机器人自主路径规划而被广泛应用及改进[9]。RRT算法优点在于无需对所需场景进行建模，仅通过随机树扩展就可以找到一条通往目标点的可行路径，但正是因为随机树扩展的随机性导致最终产生的路径随机性过强、冗余节点过多且寻路运算过程耗时，增加了计算机内存负担[10]。

为弥补经典RRT算法的不足，研究学者提出了以目标点为导向[11]的采样方法，以大于p的概率将目标点采样为随机点，提高了RRT算法的目标导向性，但是依旧存在路径节点数过多和冗余支路的问题。刘恩海等[12]引入目标点吸引力思想，改变了RRT扩展无方向性的问题，但算法寻路效率依然较低。Wan等[13]将RRT算法与人工势场法结合，减小了RRT算法的采样个数，但其算法搜索时间加长。杨洪涛[14]在RRT中引入至目标点的初始方向向量，加强了随机树扩展的方向性问题，但其方向性过强，导致RRT扩展极易陷入随机树扩展失败的局面。闫明亮等[15]提出了双采样点的RRT改进方法，也在一定程度上加强了RRT扩展的导向性，但其在路径长度上并未有明显改善。赵惠等[16]结合目标偏置和双采样点原则对RRT进行总体改进，其在路经长度、寻路时间上均有所改进，但易陷入RRT节点扩展不易的局面。

针对以上RRT算法中的不足，引入目标偏置采样策略，减少RRT算法的采样盲目性；引入剪枝采样方法，通过计算新节点位置对下一采样位置进行约束，减少冗余支路的产生；引入目标点引力、随机点引力及权重距离系数，实时调整新节点生成方向和步长，提高路径生成效率；结合三次B样条对路径进行平缓，增强通信机器人行驶的稳定性。

1 问题模型建立

近年来，各地受灾情况时有发生，导致环境原有形态遭到破坏且通信网络瘫痪。针对这种情况，采用机器人代替人类进入受灾现场实现临时通信网的建立。现有的机器人一般都具有导航定位、地形探测、无线通信等众多功能[17]。因此，采用多个具备无线通信和传感器等设备的通信机器人来充当应急场景下的临时通信基站。

临时通信网组建过程中，需要将具备通信功能的通信机器人布放到合适的基站位置。布放过程即找到一条连接基站通信机器人和基站站点的无障碍路径。由于最终路径仅在非障碍区出现，将三维空间的应急场景简化为平面的俯视二维图。图1为应急场景下的通信基站布放俯视图，黑色部分代表障碍物区域，白色空白区域代表非障碍区域，左上角为中心通信机器人位置和基站通信机器人起始位置，即为中心站点，右下角为基站通信机器人布放位置，即为基站站点。通信机器人通信半径均为R，弧线L1为中心通信机器人可通信的通信边界位置，弧线L2为基站通信机器人布放成功后可通信的通信边界位置，各通信机器人构成临时通信网络。针对基站通信机器人到达指定基站站点的路径规划过程进行研究。

图1 通信基站布放示意图

2 基站通信机器人布放路径规划

2.1 基于RRT的机器人路径规划

将中心站点、基站站点质点化，中心基站置为坐标原点，规定以中心站点为RRT算法的根节点qinit，基站站点为RRT算法的目标点qgoal，初始化随机树，并在应急场景内以随机采样的方式向非障碍区生成一随机点qrand。遍历树上现有节点，找到距随机点qrand最近的树节点qnear，以树节点qnear为起始点，向随机点qrand方向生长λ，得到新节点qnew。判断新节点qnew与树节点qnear之间是否存在障碍物，若存在障碍物，则此次生长作废，重新进行随机采样过程，否则将新节点qnew加入树中，成为树节点。判断新加入的树节点是否进入目标点qgoal的阈值Thre范围内，若进入，停止树的扩展，并从目标点qgoal回溯，找到一条连通目标点qgoal和根节点qinit的可通行路径；否则，重新进入随机采样过程，直到找到最终路径。RRT通信机器人布放路径规划过程如图2所示。

图2 基于RRT通信机器人布放路径规划过程示意图

2.2 存在问题

依据基站通信机器人布放路径规划过程，基站通信机器人初始布放路径如图3所示，黑色加粗线条为基站通信机器人最终布放路径，蓝色线条代表废弃路径，蓝色小点代表废弃路径节点。可以看出，运用传统RRT进行基站布放存在一些不足之处。

图3 基站通信机器人初始布放路径示意图

1) RRT算法进行寻路是随机的，在相同场景中多次进行路径规划，得出的路径结果并不相同，甚至与最优路径相差甚远。

2) 寻路过程中随机点位置选取在整个范围内进行，导致最终寻路成功后产生多余的冗余路径节点被储存，产生冗余支路，且容易出现规划路径时间过长的情况。

3) RRT算法最终生成路径由各个路径节点连接而成，并不是一条适合机器人行走的光滑曲线。

3 机器人代价评估函数

为便于对比改进算法和未改进算法，对模型中的机器人消耗代价做如下定义：

1) RRT算法规划出的路径由目标点回溯得到，最终路径长度为路径上两相邻节点间距离之和。机器人速度恒定，单位距离内机器人能量消耗一定，因此规定行驶这段距离所产生的的能耗代价由起始点到目标点的欧几里得距离确定。

(1)

式中：qk表示路径节点的位置；qk-1表示路径前一节点的位置；dis(qk,qk-1)表示机器人从qk-1行驶到qk的能量消耗。

2) RRT算法寻路过程中会产生寻路节点和路径节点，其中寻路节点为不可用节点，路径节点为可用节点，两类节点皆占用机器人内存，规定路径节点与寻路节点比例为机器人内存利用率。

(2)

式中：r(t)表示寻路时间内产生的路径节点数；f(t)表示寻路时间内产生的寻路节点数。

3) RRT算法寻路时间为寻路开始与寻路完毕的时间差，规定该时间差为机器人寻路时间代价。

T(t)=T(qgoal)-T(qinit)

(3)

式中：T(qgoal)代表寻路结束时间；T(qinit)代表寻路开始时间。

4) 路径转折度依据路径节点之间的夹角来判断路径是否平滑，规定路径转折度为机器人行驶过程中的稳定代价。

(4)

式中：A(qk-1,qk)表示路径qk-1qk与路径qkqk+1的夹角。

4 改进基站通信机器人布放路径规划

针对传统RRT算法规划路径存在的问题，分别采用目标概率采样、剪枝采样和引力场思想来对RRT算法进行改进，提升整体规划效率。其扩展流程如下：

Step1定义中心通信机器人位置为起始点qinit，以该位置为起点进行随机树扩展，基站通信机器人布放位置为目标点qgoal，目标阈值thre，目标偏置采样概率pa，剪枝采样半径new_dis，扩展步长λ，最大迭代次数iter；

Step2以偏向概率pa进行采样点qrand的选择；

Step3计算dis(qrand,qgoal)，并与剪枝采样半径进行比较，若小于该半径，则进入Step 4，否则进入Step 2；

Step4寻找距qrand最近的树节点qnear。

Step5引入目标点引力、随机点引力、权重距离系数共同引导qnew生成；

Step6检测qnear与qnew之间是否存在障碍物，若存在，则废除此次扩展，重新进入Step 2；否则，将qnew添加到树上；

Step7判断qnew是否进入目标阈值thre范围内，若进入，进入Step 8；否则，进入Step 2；

Step8对生成的路径节点进行采集，利用3次B样条对路径进行平滑，得到最终路径。

图4为改进的基站通信机器人布放流程框图。

图4 改进的基站通信机器人布放流程框图

4.1 目标偏置采样

基本RRT算法采样在整个空间X内进行，算法采样过程的随机性强，致使随机树扩展存在一定盲目性，导致最终获取的路径冗余节点过多，且算法迭代时间过长。为提高采样的方向性，结合偏置概率采样的思想，预设采样概率pa，通过函数均匀生成概率p，p∈(0,1)；以大于pa的概率将目标点qgoal作为采样点，其余采样点依然在采样空间X内随机选取。如式(5)所示，目标偏置采样式为：

(5)

式中X(q)为采样空间X内的随机采样点。

4.2 剪枝采样

以一定偏置概率进行采样后，除开最终需要的可通行路径外，存在一系列的分叉路径，导致寻路成功后依然存在冗余采样点形成的冗余路径，消耗机器人内存空间。为避免这些多余路径的形成，对导致多余路径形成的随机采样点采样位置进行约束，其约束思想为：每迭代产生1个新节点qnew，即对新节点qnew位置进行判断，并计算新节点qnew与目标点qgoal之间的直线距离，以目标点qgoal为圆心，该距离为半径，对下次迭代的采样点位置进行约束。若下一采样点在约束范围内采样，则采样成功；否则，重新进行采样过程，直到采样点出现在约束范围内。规定初始采样半径由起始点和目标点的位置决定，之后根据每次新节点位置更新采样范围。图5所示为剪枝采样示意图。

图5 剪枝采样示意图

采样部分伪代码如下：

T.init

new_dis=sqrt(qinit,qgoal)；

fori=count

随机生成一个采样概率p；

if 0

进行随机采样，得到预备采样点qrand；

else

qrand=qgoal；

end

计算rand_dis=sqrt(qrand,qgoal)；

ifrand_dis

采样节点生成qrand；

else

continue；

end

end

依据生成新节点qnew；

重置new_dis=sqrt(qnew,qgoal)，进行下一次迭代

4.3 变步长扩展

基本RRT算法在新节点扩展中采用恒定步长进行扩展，其扩展方向均由采样点决定，致使寻路方向随机且寻路时间过长。为进一步减小规划时间和优化节点扩展方向，结合引力场思想和权重距离系数，在生成新节点时，引入随机点引力和目标点引力两力合一来引导新节点生长，并依据权重距离系数对两者比例进行自适应调控，使得随机树在远离障碍物时获得偏向目标点生长的引力，加快随机树在非障碍区域的蔓延过程，减小寻路时间。在靠近障碍物时，获得偏向随机点生长的引力，避免随机树因遇到连续障碍物而停止扩展。

具体生成过程：在生成随机点qrand后，寻找到距该点最近的树节点qnear，借用引力场思想对该节点施加2个力，分别为随机点引力r(q)和目标点引力g(q)，并利用权重距离系数，根据树节点qnear位置实时分配目标点引力大小和随机点引力大小；在障碍物附近时，由随机点引力为主要导向，反之，以目标点为主要导向，引导树节点向不同方向扩展，而其实时的合力大小也作为新节点的生长步长生成新节点qnew；检测新节点qnew树节点qnear之间是否存在障碍物，若存在，废除此次扩展，若不存在，将其加入随机树中。新节点扩展表达式为：

qnew=qnear+p*r(q)*nr(q)+

(1-p)*g(q)*ng(q)

(6)

(7)

(8)

(9)

式(6)—(9)中:p为权重距离系数；r(q)代表随机点引力系数；g(q)代表为目标点引力系数；nr(q)代表随机点引力方向；ng(q)代表目标点引力方向；dis(qrand,qnear)代表随机点qrand与最近树节点qnear的直线距离；dis(qgoal,qnear)代表目标点qgoal与扩展节点qnear的直线距离；dis代表障碍物影响最近距离；qnear_ob表示最近树节点qnear与最近障碍物边界点的距离。

新节点扩展方向如图6所示。

图6 新节点扩展方向示意图

4.4 路径平滑

RRT算法得到的可行路径由树节点组成，为一系列离散位置点，而并非一条平滑曲线。机器人按此路径行驶时，突发转折情况时有发生，并不符合机器人运动学规律，减慢机器人行驶速度，因此在此基础上，对路线进行平缓处理，B样条曲线能够对离散路径节点进行平缓而不影响整体形态，被广泛应用于路径运动学处理[18]。考虑到该函数的这些特点，采用三次B样条对改进RRT生成的路径节点进行平缓处理。

三次B样条曲线数学表达式为：

(10)

三次B样条基函数表达式为：

(11)

5 仿真实验

在 Matlab R2018a 实施，实验环境配置：Window10，Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz，RAM 8.00GB。

仿真地图为800 mm×800 mm，节点扩展步长为35 mm，目标点阈值为20 mm，障碍物影响距离为12 mm。基站通信机器人起始点坐标为(0,0)，基站站点坐标为(750,750)。最终目标是得到从基站通信机器人位置到基站站点的机器人布放路径。图7分别为3种算法的仿真示意图和改进算法路径平滑示意图。设置黑色方块代表障碍物，蓝线条为搜索形成的随机树，黑色加粗线条为规划成功的路径。由于算法采样随机进行，每次产生的结果不同，故分别对RRT算法、文献[11]改进算法、本文改进算法在通信基站布放俯视图上各进行500次仿真实验，取各项结果的平均值。对不同算法的内存占用情况、能量消耗情况和寻路时间代价进行分析。

图7 机器人布放路径示意图

图7(a)为基于传统RRT算法进行机器人布放所得路径，可以看出，路径转折点较多，冗余节点和冗余支路杂乱，进行机器人布放效果不是很理想；图7(b)为文献[11]改进算法进行机器人布放所得路径，相比于传统RRT算法，其冗余路径节点和冗余支路明显减少，路径质量明显提高；图7(c)为本文改进RRT算法进行机器人布放所得路径，改进算法在路径质量、冗余节点、冗余支路上相比于前2种具有明显改进；图7(d)为最终的平滑布放路径图，可以看出，红色线条相比于黑色线条更加平缓，且路径转折点更少。

3种算法在500次路径规划情况下对基站通信机器人的能量消耗、内存占用情况、寻路时间代价如表1所示。

表1 3种算法机器人代价情况

改进RRT算法在进行基站布放时能量消耗比传统RRT算法减少了14.2%，相比于文献[11]改进算法减少了7.0%；在机器人内存利用率上，改进算法比基本RRT算法提高了72.2%，比文献[11]改进算法提高了47.4%；在寻路时间代价上，改进算法相比基本RRT算法降低了77.6%，比文献[11]改进算法降低了31.5%。

6 结论

针对应急场景的基站通信机器人布放路径规划问题，提出了一种改进 RRT的基站通信机器人布放路径规划算法。利用目标偏置采样、剪枝采样和节点引力，提高基站通信机器人寻路效率，令机器人快速找到一条无碰撞的可行路径进行站点通信机器人布放，及时搭建应急场景下的内部局域网。改进算法在内存占用率、能量消耗和寻路代价方面均有明显改进，减少了机器人能耗；通过平滑后的路径转折点明显减少，使机器人行驶更加平稳。但本文中仅对单站点布放做了路径规划，而实际应急场景区域范围不定，站点布放问题不单为单通信机器人路径规划问题，因此后续研究将考虑多通信机器人布放的路径规划问题。