应急场景通信机器人布放路径规划 孙弋.pdf

该【应急场景通信机器人布放路径规划 孙弋 】是由【夸客客】上传分享，文档一共【7】页，该文档可以免费在线阅读，需要了解更多关于【应急场景通信机器人布放路径规划 孙弋 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。重庆理工大学学报(自然科学)
JournalofChongqingUniversityofTechnology(NaturalScience)
ISSN1674-8425,CN50-1205/T
《重庆理工大学学报(自然科学)》网络首发论文
题目:应急场景通信机器人布放路径规划
作者:孙弋,雷锦航
收稿日期:2022-01-09
网络首发日期:2022-10-06
引用格式:孙弋,[J/OL].重庆理工大学学报
(自然科学)..
网络首发:在编辑部工作流程中,稿件从录用到出版要经历录用定稿、排版定稿、整期汇编定稿等阶
段。录用定稿指内容已经确定,且通过同行评议、主编终审同意刊用的稿件。排版定稿指录用定稿按照期
刊特定版式(包括网络呈现版式)排版后的稿件,可暂不确定出版年、卷、期和页码。整期汇编定稿指出
版年、卷、期、页码均已确定的印刷或数字出版的整期汇编稿件。录用定稿网络首发稿件内容必须符合《出
版管理条例》和《期刊出版管理规定》的有关规定;学术研究成果具有创新性、科学性和先进性,符合编
辑部对刊文的录用要求,不存在学术不端行为及其他侵权行为;稿件内容应基本符合国家有关书刊编辑、
出版的技术标准,正确使用和统一规范语言文字、符号、数字、外文字母、法定计量单位及地图标注等。
为确保录用定稿网络首发的严肃性,录用定稿一经发布,不得修改论文题目、作者、机构名称和学术内容,
只可基于编辑规范进行少量文字的修改。
出版确认:纸质期刊编辑部通过与《中国学术期刊(光盘版)》电子杂志社有限公司签约,在《中台上创办与纸质期刊内容一致的网络版,以单篇或整期出版形式,在印刷
出版之前刊发论文的录用定稿、排版定稿、整期汇编定稿。因为《中国学术期刊(网络版)》是国家新闻出
版广电总局批准的网络连续型出版物(ISSN2096-4188,CN11-6037/Z),所以签约期刊的网络版上网络首
发论文视为正式出版。
网络首发时间:2022-10-0611:29:04
网络首发地址:.
收稿日期:2022-01-09
作者简介:孙弋,男,博士,教授,主要从事嵌入式系统、信号与信息处理研究,E-mail:******@;通讯作者雷
锦航,女,硕士,主要从事机器人路径规划、多智能体研究,E-mail:******@。
应急场景通信机器人布放路径规划
孙弋,雷锦航
(西安科技大学通信与信息工程学院,西安710600)
摘要:针对应急场景通信基站站点布放的路径规划问题,提出了一种改进RRT的基站通信机器人布放路径规划算法。采用
目标偏置采样结合剪枝采样的新采样方法,以一定概率将目标点作为采样点进行随机采样,并结合新节点位置约束采样范围。
在此基础上引入随机点引力和目标点引力思想来改变局部节点扩展方向,利用权重距离系数实时调整扩展步长。对生成路径
进行3次B样条拟合。驱使基站通信机器人安全、高效、稳定地抵达预先规划好的基站位置。与其他几种算法的Matlab仿真
对比结果表明:所提方法具有可行性,且改进后的RRT算法在进行基站布放时内存占用率更低,能耗更少,寻路代价更短。
关键词:改进RRT;通信机器人;剪枝采样;局部节点扩展;权重距离系数
中图分类号::A
LayoutPathPlanningforEmergencyDisaster-strickenCommunication
RobotBaseStation
SUNYi,LEIJinhang
(CollegeofCommunicationandInformationEngineering,Xi’anUniversityofScienceandTechnology,Xi’an710600,China)
Abstract:Aimingatthepathplanningproblemofbasestationdeploymentinemergencyscenariocommunication,apathplanning


samplingwithacertainprobability,,theideaof
randompointgravityandtargetpointgravityisintroducedtochangetheexpansiondirectionoflocalnodes,andtheexpansionstep
sizeisadjustedinreal--splinecurve.
Drivethebasestationcommunicationrobottoarrivesafely,efficiently,andstablyatthepre-,the
algorithmisverifiedbasedontheMatlabplatform,whichiscomparedwiththetraditionalRRTalgorithmandanexistingimproved
algorithm,andtheresultsshowthattheproposedmethodisfeasible,andtheimprovedRRTalgorithmhaslowermemoryoccupation,
lessenergyconsumption,andshorterpathfindingcostwhenthebasestationisdeployed.
Keywords:ImprovedRRT;communicationrobot;pruningsampling;localnodeexpansion;weighteddistancecoefficient
0引言
通信基站布放在应急场景下的机器人通信系统(RRT)因更适合移动机器人自主路径规划而被广
搭建过程中具有十分重要的作用[1]。采用具有通信泛应用及改进[9]。RRT算法优点在于无需对所需场
能力的通信机器人进行通信站点布放就是在一定环景进行建模,仅通过随机树扩展就可以找到一条通
境下寻找一条连接起始点到目标点的可行路径的过往目标点的可行路径,但正是因为随机树扩展的随
程[2]。该过程即路径规划,是机器人技术的重要研机性导致最终产生的路径随机性过强、冗余节点过
究方向[3]。多且寻路运算过程耗时,增加了计算机内存负担[10]。
路径规划可表示为:在已知范围内,机器人自为弥补经典RRT算法的不足,研究学者提出了
动搜寻一条连接起始点到目标点的最优可通行路径以目标点为导向[11]的采样方法,以大于p的概率将
[4]。目前主要路径规划算法有人工势场法[5]、A*算目标点采样为随机点,提高了RRT算法的目标导向
法[6]、Dijkstra算法[7]、可视图法[8]、和快速扩展随性,但是依旧存在路径节点数过多和冗余支路的问
机树算法(RRT)等。其中,快速搜索随机树算法题。刘恩海等[12]引入目标点吸引力思想,改变了RRT
2
扩展无方向性的问题,但算法寻路效率依然较低。
L
宋宇等[13]将RRT算法与人工势场法结合,减小了2
RRT算法的采样个数,但其算法搜索时间加长。代中心站点
彦辉等[14]在RRT中引入至目标点的初始方向向量,
加强了随机树扩展的方向性问题,但其方向性过强,
导致RRT扩展极易陷入随机树扩展失败的局面。闫
明亮等[15]提出了双采样点的RRT改进方法,也在一
定程度上加强了RRT扩展的导向性,但其在路径长R
度上并未有明显改善。赵惠等[16]结合目标偏置和双
采样点原则对RRT进行总体改进,其在路经长度、
寻路时间上均有所改进,但也易陷入RRT节点扩展
不易的局面。L1
针对以上RRT算法中的不足,引入目标偏置采基站站点
样策略,减少RRT算法的采样盲目性;引入剪枝采
样方法,通过计算新节点位置对下一采样位置进行图1通信基站布放图
约束,减少冗余支路的产生;引入目标点引力、随
机点引力及权重距离系数,实时调整新节点生成方2基站通信机器人布放路径规划
向和步长,提高路径生成效率;结合三次B样条对
路径进行平缓,增加通信机器人行驶的稳定性。
将中心站点、基站站点质点化,中心基站置为
1问题模型建立坐标原点,规定以中心站点为RRT算法的根节点
近年来,各地受灾情况时有发生,导致环境原qinit,基站站点为RRT算法的目标点qgoal,初始化
有形态遭到破坏且通信网络瘫痪。针对这种情况,随机树,并在应急场景内以随机采样的方式向非障
采用机器人代替人类进入受灾现场实现临时通信网碍区生成一随机点q,遍历树上现有节点,找到
的建立。现有的机器人一般都具有导航定位、地形rand
探测、无线通信等众多功能[17]。因此,采用多个具距随机点qrand最近的树节点qnear,以树节点qnear为
备无线通信和传感器等设备的通信机器人来充当该
起始点,向随机点qrand方向生长,得到新节点
应急场景下的临时通信基站。
q。判断新节点q与树节点q之间是否存在
临时通信网组建过程中,需要将具备通信功能newnewnear
的通信机器人布放到合适的基站位置。布放过程即障碍物,若存在障碍物,则此次生长作废,重新进
找到一条连接基站通信机器人和基站站点的无障碍行随机采样过程,否则将新节点qnew加入树中,成
路径。由于最终路径仅在非障碍区出现,将三维空为树节点。判断新加入的树节点是否进入目标点
间的应急场景简化为平面的俯视二维图。图1为应
qgoal阈值Thre范围内,若进入,停止树的扩展,并
急场景下的通信基站布放俯视图,黑色部分代表障
从目标点q回溯,找到一条连通目标点q和根
碍物区域,白色空白区域代表非障碍区域,左上角goalgoal
为中心通信机器人位置和基站通信机器人起始位节点qinit的可通行路径,否则,重新进入随机采样
置,即为中心站点,右下角为基站通信机器人布放过程,直到找到最终路径。RRT扩展如图2所示。
位置,即为基站站点。通信机器人通信半径均为R,
中心站点(qinit)
弧线L1为中心通信机器人可通信的通信边界位置,
弧线为基站通信机器人布放成功后可通信的通
L2qnear基站站点(qgoal)
信边界位置,各通信机器人构成临时通信网络。本
λThre
文针对基站通信机器人到达指定基站站点的路径规
q
划过程进行研究。new
qrand
图2基于RRT通信机器人布放路径规划过程

依据基站通信机器人布放路径规划过程,基站
通信机器人初始布放路径如图3所示,黑色加粗线
条为基站通信机器人最终布放路径,蓝色线条代表
3
废弃路径,蓝色小点代表废弃路径节点。可以看出的时间差,规定该时间差为机器人寻路时间代价。
运用传统RRT进行基站布放有以下不足之处。
T(t)T(qgoal)T(qinit)(3)
式中:Tq()goal代表寻路结束时间;Tq()init代表寻
路开始时间。
4)路径转折度依据路径节点之间的夹角来判断
路径是否平滑,规定路径转折度为机器人行驶过程
中的稳定代价。
n
htAqq()(,)kk1(4)
k1
式中:A(q,q)kk1表示路径qqkk1与路径qqkk1的
夹角。
4改进基站通信机器人布放路径规划
图3基站通信机器人初始布放路径针对传统RRT算法规划路径存在的问题,分别
采用目标概率采样、剪枝采样和引力场思想来对
1)RRT算法进行寻路是随机的,在相同场景中RRT算法进行改进,提升整体规划效率。其扩展流
多次进行路径规划,得出的路径结果并不相同,甚程如下:
至与最优路径相差甚远。Step1定义中心通信机器人位置为起始点
)寻路过程中随机点位置选取在整个范围内进
2q,以该位置为起点进行随机树扩展,基站通信
行,导致最终寻路成功后产生多余的冗余路径节点init
被储存,产生冗余支路,且容易出现规划路径时间机器人布放位置为目标点qgoal,目标阈值thre,目
过长的情况。
标偏置采样概率pa,剪枝采样半径new_dis,扩
3)RRT算法最终生成路径由各个路径节点连接
展步长,最大迭代次数iter;
而成,并不是一条适合机器人行走的光滑曲线。
Step2以偏向概率p进行采样点q的选
3机器人代价评估函数arand
择;
为对比改进算法和未改进算法方便,现对模型
Step3计算disqq(,),并与剪枝采样半
中的机器人消耗代价做如下定义:randgoal
径进行比较,若小于该半径,则进入,否则
1)RRT算法规划出的路径由目标点回溯得到,Step4
最终路径长度为路径上两相邻节点间距离之和。机进入Step2;
器人速度恒定,单位距离内机器人能量消耗一定,Step4寻找距qrand最近的树节点qnear。
因此规定行驶这段距离所产生的的能耗代价由起始Step5引入目标点引力、随机点引力、权重距
点到目标点的欧几里得距离确定。
离系数共同引导qnew生成;
n
Step6检测q与q之间是否存在障碍物,
Ptdisqq()(,)kk1(1)nearnew
k1若存在,则废除此次扩展,重新进入Step2,否则,
式中:q表示路径节点的位置;q表示路径前一
kk-1将qnew添加到树上;
节点的位置;disqq(,)表示机器人从q行驶到
kk1k-1Step7判断qnew是否进入目标阈值thre范围
qk的能量消耗。内,若进入,进行Step8,否则,进行Step2;
2)RRT算法寻路过程中会产生寻路节点和路Step8对生成的路径节点进行采集,利用3次
径节点,其中寻路节点为不可用节点,路径节点为B样条对路径进行平滑,得到最终路径。
可用节点,两类节点皆占用机器人内存,规定路径图4为改进的基站通信机器人布放流程示意
节点与寻路节点比例为机器人内存利用率。图。
rt()
Rt()(2)
ft()
式中:rt()表示寻路时间内产生的路径节点数;
ft()表示寻路时间内产生的寻路节点数。
3)RRT算法寻路时间为寻路开始与寻路完毕
4
开始结束约束。若下一采样点在约束范围内采样,则采样成
功;否则,重新进行采样过程,直到采样点出现在
约束范围内。规定初始采样半径由起始点和目标点
初始化随机数、、平滑处理
qinit的位置决定,之后根据每次新节点位置更新采样范
qgoal、目标阈值thre、
pa、剪枝采样半径围。图5所示为剪枝采样示意图。
new_dis、扩展步长生成路径节
点中心站点(qinit)
随机采样生成计算并重置
Yqnear
一点p(0<p<1)new_dis=dis(qne基站站点(q)
,q)goal
wgoalλ
YN
qnewNew_dis
0<p<paN
判断与
qnear图5剪枝采样示意图
随机生成qnew中间是否
q=q采样部分伪代码如下:
随机点qrandgoal存在障碍物

newdissqrtqq_(,)initgoal;
引入随机点引力和
计算目标点引力及权重fori=count
距离系数共同扩展随机生成一个采样概率;
dis(qrand,qgoal)p
新节点qnew
if0ppa
比较找出距离该进行随机采样,得到预备采样点;
Nqrand
Y采样点最近
dis(qrand,qgoal)else
<new_dis的树节点qnear
qq;
图4改进的基站通信机器人布放流程框图randgoal
end
计算rand_dis=sqrt(q,q);

ifrand_dis<new_disthen
基本RRT算法采样在整个空间X内进行,算法
采样过程的随机性强,致使随机树扩展存在一定盲采样节点生成qrand;
目性,导致最终获取的路径冗余节点过多,且算法else
迭代时间过长。为提高采样的方向性,结合偏置概continue;
end
率采样的思想,预设采样概率,通过函数均匀生
paend
成概率p,p(0,1);以大于p的概率将目标点
a依据生成新节点qnew;
q作为采样点,其余采样点依然在采样空间X内
goal重置newdissqrtqq_(,)newgoal,进行下一次迭代;
随机选取。如式(5)所示,目标偏置采样式为:

Xqpp(),(0)
a基本RRT算法在新节点扩展中采用恒定步长进
qrand(5)
qppgoala,(1)行扩展,其扩展方向均由采样点决定,致使寻路方
式中Xq()为采样空间X内的随机采样点。向随机且寻路时间过长。为进一步减小规划时间和
优化节点扩展方向,结合引力场思想和权重距离系
,在生成新节点时,引入随机点引力和目标点引
以一定偏置概率进行采样后,除开最终需要的力两力合一来引导新节点生长,并依据权重距离系
可通行路径外,存在一系列的分叉路径,导致寻路数对两者比例进行自适应调控,使得随机树在远离
成功后依然存在冗余采样点形成的冗余路径,消耗障碍物时,获得偏向目标点生长的引力,加快随机
机器人内存空间。为避免这些多余路径的形成,对树在非障碍区域的蔓延过程,减小寻路时间。在靠
导致多余路径形成的随机采样点采样位置进行约近障碍物时,获得偏向随机点生长的引力,避免随
机树因遇到连续障碍物而停止扩展。
束,其约束思想为:每迭代产生1个新节点qnew,
具体生成过程:在生成随机点qrand后,寻找到
即对新节点qnew位置进行判断,并计算新节点qnew
距该点最近的树节点qnear,借用引力场思想对该节
与目标点qgoal之间的直线距离,以目标点qgoal为圆
心,该距离为半径,对下次迭代的采样点位置进行点施加两个力,分别为随机点引力rq()和目标点引
5
三次B样条曲线数学表达式为为:
力gq(),并利用权重距离系数,根据树节点qnear位
置实时分配目标点引力大小和随机点引力大小,在PtFtpFtpiii()()*()*0,31,31
(10)
障碍物附近时,由随机点引力为主要导向,反之,
FtpFtp2,323,33()*()*ii
以目标点为主要导向,引导树节点向不同方向扩展,
三次B样条基函数表达式为:
而其实时的合力大小也作为新节点的生长步长生成
1
新节点q,检测新节点q树节点q之间是否Ftttt()(331)32
newnewnear0,36
存在障碍物,若存在,废除此次扩展,若不存在,
将其加入随机树中。新节点扩展公式为:132
Fttt1,3()(364)
qqprqn*()*6
newnearrq()(11)
(6)1
(1)*()*pgqnFtttt()(3631)32
gq()2,36
qqrandnear
nrq()(7)13
disqq(,)Ftt3,3()
randnear6
qq
goalnear(8)
ngq()5仿真实验
disqq(,)goalnear
实验在MatlabR2018a实施,实验环境配置:
disqdisq/,nearobnearob__
p(9)Window10,Intel(R)Core(TM)i7-7500UCPU@
1,,。
式(6)—(9)中,p为权重距离系数,rq()仿真地图为800mm×800mm,节点扩展步长为
代表随机点引力系数,gq()代表为目标点引力系35mm,目标点阈值为20mm,障碍物影响距离为12
mm。基站通信机器人起始点坐标为(0,0),基站站
数,代表随机点引力方向,代表目标点
nrq()ngq()点坐标为(750,750)。最终目标是得到从基站通信
引力方向,disqq(,)randnear代表随机点qrand与最近机器人位置到基站站点的机器人布放路径。图7分
树节点q的直线距离,disqq(,)代表目标别为3种算法的仿真示意图和本文改进算法路径平
neargoalnear滑图。设置黑色方块代表障碍物,蓝线条为搜索形
点qgoal与扩展节点qnear的直线距离,dis代表障碍成的随机树,黑色加粗线条为规划成功的路径。由
于算法采样随机进行,每次产生的结果不同,故分
物影响最近距离,qnear_ob表示最近树节点qnear与最
别对RRT算法、文献[11]改进算法、本文改进算法
近障碍物边界点的距离。
在通信基站布放俯视图上各进行500次仿真实验,
新节点扩展方向示意如图6所示。
取各项结果的平均值。对不同算法的内存占用情况、
中心站点(qinit)能量消耗情况和寻路时间代价进行分析。
qnearg(q)
r(q)基站站点
qnew
(qgoal)
q
rand
图6新节点扩展示意图
(a)RRT算法(b)文献11改进
RRT算法得到的可行路径是由树节点组成,为
一系列离散位置点,而并非一条平滑曲线。机器人
按此路径行驶时,突发转折情况时有发生,其并不
符合机器人运动学规律,减慢机器人行驶速度,因
此在此基础上,对路线进行平缓处理,B样条曲线
能够对离散路径节点进行平缓而不影响整体形态,
被广泛应用于路径运动学处理[18]。考虑到该函数的
这些特点,采用三次B样条对改进RRT生成的路径
节点进行平缓处理。(c)本文改进RRT(d)路径平滑
6
图7机器人布放路径示意图[3]陈侠,刘奎武,-RRT算法的无人机航迹
规划[J/OL].电光与控制:1-7[2022-03-20]..
图7(a)为基于传统RRT算法进行机器人布放所net/kcms/detail/
得路径,可以看出,路径转折点较多,且冗余节点[4]江洪,[J].重庆理
和冗余支路杂乱,进行机器人布放效果不是很理想;工大学学报(自然科学),2021,35(7):10-16,124.
[5]CHENYB,LUOGC,MEIYS,
图7(b)为文献11改进算法进行机器人布放所得路usingartificialpotentialfieldmethodupdatedbyoptimal
径,相比于传统RRT算法,其冗余路径节点和冗余controltheory[J].InternationalJournalofSystemsScience,
支路明显减少,且路径质量明显提高;图7(c)为本2016,47(6):1407-1420.
[6]王洪斌,尹鹏衡,郑维,~*算法与动态窗口
文改进RRT算法进行机器人布放所得路径,改进算
法的移动机器人路径规划[J].机器
法在路径质量、冗余节点、冗余支路上相比于前两人,2020,42(3):346-:..
种具有明显改进;图7(d)为最终的平滑布放路径图,[7]ZOUZ,XIAOY,
可以看出,红色线条相比于黑色线条更加平缓,且transitnetworkbasedoncomplexnetworkstheory[J].
路径转折点更少。Kybernetes,2013,42(3):383-399.
[8]徐可,陈宗海,张陈斌,
3种算法在500次路径规划情况下对基站通信机的滚动轴承故障诊断[J].控制理论与应
机器人的能量消耗、内存占用情况、寻路时间代价用,2019,36(6):915-922.
如表1所示。[9]李金良,舒翰儒,刘德建,
表13种算法机器人代价情况[J].组合机床与自动化加工技术,2021(2):22-24,29.
[10]李伟,
路径规划内存利用率寻路时间代收敛方法[J].计算机应用,2021,41(10):2912-2918.
能量消耗/mm
500次/%价/s[11]URMSONC,-ally
[C]//IEEE/RSJInternational
:
,2003:1178-1183.
改进RRT算法在进行基站布放时能量消耗比传[12]刘恩海,高文斌,孔瑞平,
计算机工程与设计
%,相比于文献[11]改进算[J].,2019,40(8):2253-2258.
[13]WANJ,ZHANGX,
法减少了;在机器人内存利用率上,改进算法
%de-noisingmethodbasedonwaveletthreshold[C]//
%,比文献[11]改进算Interna-tionalConferenceonInformationEngineering&
%;在寻路时间代价上,:IEEE,2010:1-4.
%,比文献[11]改进算[14][J].
%。组合机床与自动化加工技术,2020(1):79-82,88.
[15]闫明亮,
6结论法[J].计算机与网络,2019,45(15):55-58.
[16]赵惠,李庆党,
针对应急场景的基站通信机器人布放路径规划规划方法[J].电子测量技术,2021,44(16):45-49.
问题,提出了一种改进RRT的基站通信机器人布放[17]
路径规划算法。利用目标偏置采样、剪枝采样和节[D].长沙:国防科技大学,2017.
陈秋莲蒋环宇郑以君机器人路径规划的快速扩展随
点引力,提高基站通信机器人寻路效率,令机器人[18],,.
机树算法综述[J].计算机工程与应用,2019,55(16):10-17.
快速找到一条无碰撞的可行路径进行站点通信机器
人布放,及时搭建应急场景下的内部局域网。改进
算法在内存占用率、能量消耗和寻路代价方面均有
明显改进,减少了机器人能耗,通过平滑后的路径
转折点明显减少,使机器人行驶更加平