复杂环境下无人机全覆盖三维路径规划算法.pdf

第2 9卷第8期计算机集成制造系统V o l.2 9N o.82023年8月C o m p u t e r I n t e g r a t e dM a n u f a c t u r i n gS y s t e m sA u g.2 0 2 3D O I:1 0.1 3 1 9 6/j.c i m s.2 0 2 3.0 8.0 0 5收稿日期:2 0 2 2-0 3-2 9;修订日期:2 0 2 2-0 5-2 2。R e c e i v e d2 9M a r.2 0 2 2;a c c e p t e d2 2M a y2 0 2 2.复杂环境下无人机全覆盖三维路径规划算法陈 艺1,于纪言1,2+(南京理工大学 机械工程学院,江苏 南京 2 1 0 0 9 4)摘 要:针对复杂实际环境下无人机进行快速三维全覆盖路径规划的问题,提出了无人机全覆盖三维路径规划算法。首先,二维全覆盖路径规划由全局运动策略、局部运动策略和摆脱死区策略组成,在全局运动策略中改进标记函数和提出次层起点动态搜寻策略,摆脱死区策略由A*算法和改进环形搜索算法构成;三维全覆盖路径规划由分层规划策略、地图重构策略和层间连接策略组成,分层规划策略将三维分为不同间隔高度的二维环境,地图重构策略对二维进行动态地图构建,层间连接策略由头一层的遍历终点确定下一层的遍历起点。仿真结果表明:所提算法在二维全覆盖路径规划时,相较于传统的单环搜索方式摆脱死区策略,路径长度缩短2.7%,路径重复率减小3%;相较于无局部运动策略,路径长度缩短1 4.2%,总死点数目和路径重复率降低3 2.9%和4.4%,且运行时间减少6.7s;在三维全覆盖路径规划时,相较于无地图重构策略,路径长度缩短2 7.3 3%,死点数目减少1 6.8 2%,运行时间减少7 0.8s,路径重复率减小7%;最后进行参数分析,得出本算法性能最优时参数取值。综上,该算法能够适应复杂环境,且能有效降低死点数目和路径重复率,快速规划全覆盖路径,具有较好的鲁棒性。关键词:无人机;三维全覆盖路径规划;复杂环境;摆脱死区策略;地图重构策略中图分类号:V 2 7 9.2 文献标识码:AF u l l c o v e r a g e3 Dp a t hp l a n n i n ga l g o r i t h mf o rU A Vi nc o m p l e xe n v i r o n m e n tCHENY i1,Y UJ i y a n1,2+(S c h o o l o fM e c h a n i c a lE n g i n e e r i n g,N a n j i n gU n i v e r s i t yo fT e c h n o l o g y,N a n j i n g2 1 0 0 9 4,C h i n a)A b s t r a c t:T os o l v e t h ep r o b l e mo fr a p i dt h r e e-d i m e n s i o n a l f u l l c o v e r a g ep a t hp l a n n i n go fU n m a n n e dA e r i a lV e h i c l e(UAV)i nc o m p l e xp r a c t i c a l e n v i r o n m e n t,at h r e e-d i m e n s i o n a l f u l lc o v e r a g ep a t hp l a n n i n ga l g o r i t h mo fUAV w a sp r o p o s e d.T h e t w o-d i m e n s i o n a l f u l lc o v e r a g ep a t hp l a n n i n gw a sc o m p o s e do fg l o b a lm o t i o ns t r a t e g y,l o c a lm o t i o ns t r a t e g ya n dg e t t i n gr i do f d e a dz o n e s t r a t e g y.I n t h eg l o b a lm o t i o ns t r a t e g y,t h em a r k i n g f u n c t i o nw a s i m p r o v e da n dt h es u bl a y e rs t a r t i n gp o i n td y n a m i cs e a r c hs t r a t e g yw a sp r o p o s e d.T h eg e t t i n gr i do fd e a dz o n es t r a t e g yw a sc o m-p o s e do fA*a l g o r i t h ma n d i m p r o v e dr i n gs e a r c ha l g o r i t h m.T h e t h r e e-d i m e n s i o n a l f u l l c o v e r a g ep a t hp l a n n i n gc o n-s i s t e do fh i e r a r c h i c a l p l a n n i n gs t r a t e g y,m a pr e c o n s t r u c t i o ns t r a t e g ya n d i n t e r l a y e r c o n n e c t i o ns t r a t e g y,a n dt h eh i-e r a r c h i c a l p l a n n i n gs t r a t e g yd i v i d e dt h e t h r e e-d i m e n s i o n a l i n t ot w o-d i m e n s i o n a l e n v i r o n m e n t sw i t hd i f f e r e n t i n t e r v a lh e i g h t s.T h em a pr e c o n s t r u c t i o ns t r a t e g yc o n s t r u c t e d t h e t w o-d i m e n s i o n a l d y n a m i cm a p,a n d t h e i n t e r l a y e r c o n n e c-t i o ns t r a t e g yd e t e r m i n e dt h e t r a v e r s a l s t a r t i n gp o i n to f t h en e x t l a y e r f r o mt h e t r a v e r s a l e n dp o i n to f t h e f i r s t l a y e r.T h es i m u l a t i o nr e s u l t ss h o w e dt h a t c o m p a r e dw i t ht h et r a d i t i o n a l s i n g l e l o o ps e a r c hm e t h o dt og e tr i do f t h ed e a dz o n es t r a t e g y,t h ep a t hl e n g t hw a ss h o r t e n e db y2.7%a n dt h ep a t hr e p e t i t i o nr a t ew a sr e d u c e db y3%.C o m p a r e dw i t hn o l o c a lm o t i o ns t r a t e g y,t h ep a t hl e n g t hw a ss h o r t e n e db y1 4.2%,t h et o t a ln u m b e ro fd e a dp o i n t sa n dp a t hr e p e t i t i o nr a t ew e r er e d u c e db y3 2.9%a n d4.4%,a n dt h er u n n i n gt i m ew a sr e d u c e db y6.7 s.I nt h r e e-d i m e n s i o n a lf u l l c o v e r a g ep a t hp l a n n i n g,c o m p a r e dw i t hn om a pr e c o n s t r u c t i o ns t r a t e g y,t h ep a t hl e n g t hw a ss h o r t e n e db y2 7.3 3%,t h en u m b e r o f d e a dp o i n t sw a s r e d u c e db y1 6.8 2%,t h e r u n n i n g t i m ew a s r e d u c e db y7 0.8 s,a n d t h ep a t hr e p-e t i t i o nr a t ew a s r e d u c e db y7%.T h ep a r a m e t e r a n a l y s i sw a s c a r r i e do u t t oo b t a i n t h ep a r a m e t e r v a l u ew h e n t h e a l g o-r i t h mh a dt h eb e s tp e r f o r m a n c e.T h ep r o p o s e da l g o r i t h mc o u l da d a p t t oc o m p l e xe n v i r o n m e n t,e f f e c t i v e l yr e d u c e d计算机集成制造系统第2 9卷t h en u m b e ro fd e a dp o i n t s,q u i c k l yp l a n e d t h e f u l l c o v e r a g ep a t h,r e d u c e d t h ep a t hr e p e t i t i o nr a t e,a n dh a dg o o dr o-b u s t n e s s.K e y w o r d s:u n m a n n e da e r i a lv e h i c l e;t h r e ed i m e n s i o n a l f u l lc o v e r a g ep a t hp l a n n i n g;c o m p l e xd i s a s t e re n v i r o n m e n t;s t r a t e g yo fg e t t i n gr i do fd e a dz o n e;m a pr e c o n s t r u c t i o ns t r a t e g y0 引言近年来,无人机空中辅助进行协同工作已经成为趋势1,S HE N等2将无人机和地面机器人相结合,实现对地面目标的搜索。无人机飞行的复杂三维环境多种多样,主要有城市环境和自然环境等。其中城市环境相对简单,障碍物较规整,而自然环境则由许多非规则障碍物组成,因此构建一种能够适应各种环境的全覆盖三维算法十分重要。无人机协同路径规划一直以来都是研究热点,如何让无人机在覆盖全部区域的路径规划过程中尽量减小能量的消耗并提高覆盖效率,是无人机全覆盖路径规划中的重点。在覆盖过程中尽量减小重覆盖率、缩短全覆盖路径长度和减少无人机转弯能量消耗等策略是确保无人机全覆盖路径最优的有效方式3。经典覆盖路径规划策略由兴趣区域分解、覆盖区域路径点生成、覆盖路径路线规划和覆盖路径执行组成4,经典区域分解算法有牛耕式分解法5、梯形分解法6等,再生成路径点及其路径,并最终实现无人机飞行。L E等7将四边形机器人作为可重构清洁机器人,目标函数基于旅行商问题(T r a v e l i n gS a l e s m a nP r o b l e m,T S P)的遗传算法(G e n e t i c A l g o r i t h m,GA)和 蚁 群 优 化(A n tC o l o n yO p t i m i z a t i o n,A C O)等进化算法进行优化,并估计连接所有航点的最短路径函数,对待清洁区域进行工作全覆盖,但其对区域拼贴图案考虑过于简单;P L E S S E N等8提出一种轻量型的覆盖路径规划算法,与常见的两步式路径规划算法(A B模式算法)相比较,其能够更有效地用于单次运行的现场覆盖;黄迎港等9采用多种运动方式约束对二维路径进行全覆盖,在二维层面上取得了不错的效果,但在三维路径规划上只是简单地将二维路径进行堆叠,对全局的优化不够;J UNG等1 0开发出基于模型的路径规划器,用于使用先验图进行结构检查,通过于非基于模型的探索对比,验证了其方法的有效性,但其在规划前需要先制作出体积图,这将会限制复杂场景适用;L I等1 1提出一种能量最优的覆盖路径规划算法,利用由张量积B e z i e r曲面构建3 D地形并进行网格划分,得到能耗图后通过遗传算法遍历地图得到能量最优路径,但整个算法过于复杂,不能用于实时路径规划;B I R CHE R等1 2利用空中机器人自主进行结构检查,并通过两步优化算法计算出最短路径,且同时用于固定翼和旋翼飞行器配置,最终在基于网格和占用图的环境上运行,通过实验验证其算法的有效性。传统的路径规划算法可以分为基于采样的路径规划、基于搜索的路径规划和智能算法,其中经典基于采样的路径规划算法有R R T(r a p i d l y-e x p l o r i n gr a n d o mt r e e)、P RM(p r o b a b i l i s t i cr o a d m a p s)和I n-f o r m e dR R T S t a r等;基于搜索的路径规划算法有A*和D i j k s t r a;智能算法有遗传算法、粒子群算法和蚁群算法等。基于搜索的算法一定能找出从起始点到终点的最优路径,但是效率低下,算法消耗时间长;基于采样的路径规划算法随着迭代会将渐近最优路径逐渐更新为全局最优路径,具有耗时少、效率高的特点;智能算法短时间也能找到路径,并且随着迭代次数的不断增加,也能够找到最优路径,但是容易陷入局部最优。王彬等1 3将A*算法和动态窗口法相结合,针对A*算法冗余点多和动态窗口法路线冗长的缺点进行改进,最终验证了其融合算法的有效性,并提高了效率;YAN等1 4将P RM和A*算法应用到无人机实时路径规划中,通过在边界框阵列中随机采样,并引入改进的概率路线图方法(P RM),以确保路线图节点在三维空间中的分布更均匀,最终通过A*算法规划路径;郭一聪等1 5对传统的人工势场法的目标不可达、易陷入局部最小、局部路径震荡等问题进行改进解决,同时也将其扩展到三维空间;李扬等1 6针对R R T算法随机性强,导向性差的缺点进行改进,设立偏置阈值限制R R T进行有效扩展,同时在平滑时采样三次B样条函数拟合,实验表明平滑性提升,搜索时间相应减小;李文广等1 7采用动态分段优化R R T算法对突发威胁作出路径改变,具有较低的路径代价;鲁建厦等1 8提出基于射频识别库存管理的三维路径规划算法,通过构造目标适应度函数,用混合蝙蝠算法进行求解获得全局最优路径,该算法搜索能力较强,但过于4652第8期陈 艺 等:复杂环境下无人机全覆盖三维路径规划算法复杂,实时性不强。针对传统全覆盖算法的适应性不强的缺点,同时提高算法的强健性,本文提出一种复杂环境下无人机全覆盖三维路径规划算法,在二维固定高度区域内,在当前节点未陷入死区时,采用全局运动策略和局部运动策略;反之则采用摆脱死区策略寻找下一节点;将二维扩展到三维,需要采用分层规划策略对不同高度值进行划分进行二维规划,地图重构策略对不同高度的障碍物区域进行重新构造,显著缩短了全覆盖的路径长度和重复率,层间连接策略将不同层之间的子节点和父节点关联起来,从而能够进行最终的路径追溯。同时,在三维路径规划层面上还需要对二维的全局运动策略进行扩展,使其能够适应多高度层节点搜寻,最终得到完整三维路径。在城市三维环境中实验此算法并进行参数分析,验证了该算法的适应性。1 算法描述本文算法首先要建立环境模型,将模型所有数据输入到该算法中,先进行全覆盖三维路径规划的预处理阶段,由分层规划策略划分不同的高度层进行二维路径规划,同时对当前层的地图进行重构,包含障碍物的位置信息和地图边界信息的更新;再对当前层的重构地图进行全覆盖路径规划,死点通过摆脱死区策略寻找到下一个最短距离的未覆盖点,靠近障碍物和边缘节点通过局部运动策略找到下一个未覆盖点,其他剩余节点通过全局运动策略找到下一个未覆盖点;随后进入后处理阶段,应用层间连接策略,将相邻层的子夫节点相关联;再判断是否所有层都已经完成全覆盖,直到所有层的重构地图中未覆盖点全部被覆盖为止;最终进行路径追溯,利用节点信息找出完整的三维路径并输出,整体算法流程如图1所示。1.1 二维全覆盖路径规划算法二维层面的路径规划算法部分参考了文献9中的综合运动函数、死区逃离策略和运动优先级策略,同时对此三部分分别进行了相应的改进。针对综合运动函数不能适用于动态分层的缺点,在不同层的过渡时,通过分区域进行下一层初始节点的寻找,改进后的算法即为本文的全局运动策略算法;对运动优先级策略运算冗余的缺点,本文通过序号索引判断方式能快速寻找到下一未覆盖节点,即本文的局部运动策略算法;对死区逃离策略中环形搜索方式进行分阶段化对比搜索,能够找到符合死点逃离路径最短的下一节点,提高全覆盖效率,同时对死点环形搜索过程中的超出重构地图的环形节点进行错误点过滤,减少了非有效点的多余计算,即本文的摆脱死区策略算法。1.1.1 全局运动策略全局运动策略主要是由转向置信函数、标记函数和次层起点动态搜寻策略组成,其中转向置信函数见参考文献9。转向置信函数主要是为了寻找无人机飞行过程中的能量消耗最小的方向,让无人机能够覆盖更大的区域;标记函数是为了让无人机搜寻下一节点时更趋于寻找下一未覆盖节点;次层起点动态搜寻策略则是在当前高度层搜寻结束后,若下一层的初始起点由全局运动策略寻找下一节点,因为此时父节点是上一层的终点,不能进行转向置信函数求解,所以将由此函数确定下一未覆盖节点。地图是无人机路径规划的前提,典型的地图构建方法包括栅格法、拓扑法和单元分解法等。本文采用栅格法,考虑到与实际环境的契合,选用1m1m大小的栅格对二维地图进行建模。(1)转向置信函数为了使无人机沿着能量消耗最小的方向运动,设置转向置信函数D,D=1-。(1)式中0,为无人机转向角。如图2所示为转向角变化示意图。5652计算机集成制造系统第2 9卷由图2可得出转向角计算表达式:=a r c t a nyPn-yPcxPn-xPc-a r c t a nyPc-yPfxPc-xPf。(2)式中pn(xpn,ypn)、pc(xpc,ypc)和pf(xpf,ypf)分别为下一未覆盖节点、当前节点和当前节点的父节点。由该转向置信函数可知,当D=1时,无人机能量消耗最小;反之,当D=0时,无人机能量消耗最大,沿反方向飞行,故转向角应该越小越有利于无人机飞行。(2)标记函数为了将无人机在选择下一节点时,只选取其中的未覆盖节点,需要对未覆盖和覆盖节点进行标记,如下式:F=1 当前节点为未覆盖节点0当前节点为已覆盖节点。(3)式(3)主要是为了区分开当前节点周围邻域内的已覆盖节点和未覆盖节点,从而在后文式(4)计算最终结果时,使未覆盖节点的函数值更大,进而使得下一节点为未覆盖节点。(3)次层起点动态搜寻策略式(2)和式(3)只考虑了二维单层情况,即当前点有父节点的时侯。而在跨层时,下一层的起点没有父节点,故需要依靠此函数动态搜寻到下一未覆盖节点。如图3所示,1,2,3,6,7代表已覆盖节点,中间方块代表当前节点,4,5,8块代表未覆盖节点,其中已覆盖节点索引为1,2,3,6,7,未覆盖节点索引为4,5,8。在这种情况下,按照先水平后竖直的“弓”字搜索方式,能够保证由行到列的全覆盖遍历,即按照4,5,2,7,1,3,6,8的先后优先级顺序寻找下一节点,以图3为例,选择正左方向(索引4方向)的节点作为下一节点。(4)全局运动函数综合上面的转向置信函数、标记函数和次层起点动态搜寻策略,如下得到全局运动函数:Ci=Fi+Di,0,1 非层起点次层起点动态搜寻策略层起点。(4)如式(4)所示,若当前节点不是层起点,则通过Ci=Fi+Di计算出当前节点相邻的8个节点中Ci值最大的点作为下一个节点,其中为Di的权重值;若当前节点是层起点,则需要通过次层起点动态搜寻策略选出下一节点。1.1.2 局部运动策略由式(4)可知,当无人机靠近障碍物和地图边界时,若还是按照上面的全局运动函数,则有很大机会陷入死区中,从而增加重复路径,因此这里需要由局部运动算法选出下一节点,减小算法的运行时间和路径长度。由图4可知,当前节点中心方块,1,2,3为障碍物节点,4,6,7为已覆盖点,5,8为未覆盖点,其中障碍物节点索引为1,2,3,已覆盖节点索引为4,6,7,未覆盖节点索引为5,8。在邻域的8个节点索引中剔除障碍物节点和已覆盖节点的索引,从而得到未覆盖节点索引,在未覆盖节点索引中按照4,5,2,7,1,3,6,8的先后优先级进行寻找下一节点。即也是采用先水平后竖直的“弓”字遍历方式,与次层起点动态搜寻策略一致,由图4的情况可以判断,下一节点为节点5。1.1.3 摆脱死区策略在搜寻下一节点时,若当前节点周围邻域8个节点都是障碍物节点和已覆盖节点,则此时当前点陷入死区,需要依靠摆脱死区策略寻找下一个未覆6652第8期陈 艺 等:复杂环境下无人机全覆盖三维路径规划算法盖节点,这里采用环形分阶段化对比搜索方式,即在前n个环形搜索时,需要同时搜索相邻两个环,对此两个相邻环的未覆盖点使用A*算法找出路径及其长度,先将所选环中超出重构地图的错误节点剔除后,再通过对比这两个相邻环中所有的未覆盖点的路径长度,找出其中最短长度的未覆盖节点,并将其作为下一节点,否则继续往外遍历;若在遍历到第n+1个环及其之后时,则找到一个有未覆盖点的环即可(即此环有未覆盖点存在),先将所选环中超出重构地图的错误节点剔除后,再找到此环中未覆盖点的最短路径节点作为下一节点,否则,继续往外遍历,直到全覆盖完成。摆脱死区策略整体流程如图5所示。如图6所示,正中心方块节点为当前节点,其外面第一层8个领域节点都不满足条件(领域有未覆盖节点存在),其中1,2,6,7,8为障碍物,3,4,5为已覆盖点,所以需要继续往外进行扩展搜寻;第二层中由A*算法计算出的最近距离节点为9、2 0和2 4,且路径长度都约为3.4m(准确计算为2+2),以节点9为例,规划出的路径为:中心点41 49;这时需要再往外扩展一层,由A*算法找到路径最短节点为3 6,长度为3m,故综合两最短路径长度,选择3 6作为下一未覆盖节点。1.2 三维全覆盖路径规划算法无人机进行三维全覆盖路径规划时,需要先进行预处理,由分层规划策略对不同高度层分别划分层间间隔,同时采用地图重构策略对不同高度层的地图进行重新动态构建,经过这两步后便可以对当前高度层进行二维全覆盖路径规划,当该层二维全覆盖路径规划结束后,需要再进行后处理,即运用层间连接策略选出次层的起点,以便次层继续进行全覆盖路径规划。在一次寻找路径结束后,判断是否已经将所有层都遍历完成,若未完成,则需要对下一层进行遍历路径规划,直到所有层全部遍历完成为止。1.2.1 分层规划策略将所有高度依据实际环境状况进行划分,同时考虑到无人机的巡航能力限制,可以根据当前区域内的障碍物高度值作出粗略划分,以便无人机能够高效地一次遍历完成。H=1 h1,t12ht1+1,t23ht2+1。(5)7652计算机集成制造系统第2 9卷式(5)中判断当前区域内的障碍物高度值h,当h1,t1 时,无人机以1m作为不同层的间隔距离;若ht1+1,t2 时,以2m作为间隔距离;若ht2+1,考虑到实际空间建筑特点(如城市实际房屋的层高都在2.8m左右),则以3m作为最大的间隔距离。1.2.2 地图重构策略经过上面的分层后,再对当前层进行地图重构,即构建在当前层高度中只包含障碍物和未覆盖点的地图,这样会减少在空间中不必要的路径消耗;同时在重构地图时,要为最外层障碍物多留一个遍历节点环,从而保证无人机在全覆盖时能够将最外层的障碍物的四周全部都搜寻到。地图重构策略如图7所示。图7中共有4个高度区间,右侧排列方块由上至下依次分别代表高度为1m、5m、1 0m和1 5m的建筑,最外层的紫色矩形边框、左侧黑色矩形线条边框、中间白色矩形线条边框和右侧灰色矩形线条边框分别代表U1,U2,U3,U4,即为区间1,h1、h1+1,h2、h2+1,h3 和h3+1,h4 重构出的地图。地图中包含的障碍物判断计算表达式如下;Ok=Oko(xy),(xy)U1,p1,u,k0,hu,Ho(xy)k。(6)式(6)中,Ok为重构地图障碍物节点集合,p1,u 表示当前层是属于哪个高度区间,(xy)U1表示初始层所属高度区间障碍物集合中的坐标点(因为地图是从初始高度逐渐往上重构),k表示当前层的高度值,以图7为例,当k=6时,u=4(因为有四个高度区间),p=3(表示当前层高度属于第3个高度区间),Ho(xy)表示为障碍物坐标点o(xy)的高度值,如果此障碍点高度值大于当前层高度,则将其并入Ok中;反之,则舍弃。具体地图的边界位置计算表达式如下:ym a x=oym a x+2,xm a x=oxm a x+2,ym i n=oym i n-2,xm i n=oxm i n-2。(7)式中:ym a x,xm a x,ym i n,xm i n分别为重构地图的上下左右边界坐标位置大小;oym a x,oxm a x,oym i n,oxm i n分别为当前层所有障碍物中的横纵坐标最大和最小值。1.2.3 层间连接策略如图8所示,重构地图区域最外层深色框为地图边界,次层浅色框为未覆盖点(重构地图过程中会多留出此层,为了将靠近边界的障碍物四周全部覆盖到),若下一层的初始节点在1、2、3和4区域内,则按照类似图示1区域中的方块节点选择方式,直向选择下一个未覆盖点作为下一层的起点;若在5、6、7和8区域,则按照类似图示5区域中的方块节点选择方式,斜向选择角落上的未覆盖点作为下一层的起点。2 实验结果验证为验证本算法的有效性和鲁棒性,算法中的关键参数的取值如表1所示。表1 实验参数设置参数取值参数取值n3t16m0.4t21 2m全覆盖路径规划的算法有效性分析可以应用以下的指标评价。2.1 区域覆盖率区域覆盖率的计算表达式如下:8652第8期陈 艺 等:复杂环境下无人机全覆盖三维路径规划算法Cc=NcN1 0 0%。(8)式中:Cc表示区域覆盖率;Nc表示无人机已经覆盖的节点数目,N表示总共待覆盖节点数目。在对区域进行覆盖搜寻时,需要算法的覆盖率达到1 0 0%,才能保证搜索的有效性。2.2 路径重复率路径重复率的计算表达式如下:Rr=Nl-NN1 0 0%。(9)式中:Rr表示为路径重复率;Nl表示无人机完成全覆盖所需要走过的路径长度值,在栅格地图中可以以节点的数目来进行计算。在覆盖率达到1 0 0%的前提下,必须使得Nl值尽量趋近于N,可以使得无人机在巡航能力有限的情况下,提高全覆盖路径规划的效率。2.3 二维环境算法验证实验的二维环境为11m的栅格地图,其中的黑色方块代表障碍物栅格节点,空白区域为待覆盖区域,最左 下 角 空 心 圆 点 代 表 起 点,坐 标 为(1,1),地图面积大小为3 03 0 m。地图总计有9 0 0个栅格节点,障碍物栅格节点数目有1 7 3个(不考虑外边界框),待覆盖栅格节点有7 2 7个,如图9所示。与文献9 中陷入死区的摆脱策略不同,本文提出的环形分阶段化对比搜索方式能够更好避免搜索摆脱的下一节点不是最优节点的缺点(即最优节点未找到)。在实际仿真的过程中,发现文献9 的死区逃离策略有缺陷,即其必须要求所搜索的环最小路径距离小于或者等于欧氏距离,首先这一点本身不成立(即最小路径距离只可能等于或者大于欧氏距离),而且若当前搜索环中不存在一个未覆盖节点满足文献9 的死区逃离策略的条件,则会彻底陷入死区,找不到下一个未覆盖节点,故本文将对比摆脱死区策略的环形分阶段化对比搜索方式和单环搜素方式(即一个一个环进行遍历,找到未覆盖点即可)的实验结果,如图1 0和图1 1所示;再对比是否加入局部运动策略对于全覆盖路径规划的影响,实验结果如图1 0和图1 2所示。9652计算机集成制造系统第2 9卷图1 0和图1 1中空心正方形框标记节点代表死点,五角星代表除死点外的其他未覆盖节点,最左下角圆形节点代表起始点,坐标为(1,1)。由表2实验结果对比可知,环形分阶段化对比搜索方式在摆脱死区时能够取得更短的路径长度,相较于单环搜素方式摆脱死区的9 3 0.4 3m,路径长度缩短2.7%;死点数目相对减少,这样可以大大减小路径重复率,两者路径重复率相比较,由1 7.2%降低至1 4.5%,并且通过实际多次实验,随着地图愈加复杂化,环形分阶段化对比搜索方式在摆脱死区时优势更加明显,在都满足全覆盖条件下,前者能够在路径长度、总死点数目和路径重复率有着显著的降低,选取其中具有代表性数据(如表2),环形分阶段化对比搜索方式相较于单环搜素方式而言,因为在初始n个相邻环需要对比找出最优节点,所以其运行时间相对更长,但在实际复杂环境下,前者更适用于无人机全覆盖三维路径规划应用。表2 分阶段对比搜索和单环搜索方式实验结果对比摆脱死区策略算法环形分阶段化对比搜索方式单环搜素方式覆盖率/%1 0 01 0 0路径长度/m9 0 5.9 19 3 0.4 3总死点数目4 74 9路径重复率/%1 4.51 7.5算法运行时间/s2 0.7 21 7.4 6由图1 0和图1 2对比可见,无局部运动策略进行路径规划时,死点数目明显多余有局部运动策略时,同时由表3可知,有局部运动策略能够显著降低整体路径长度,相 较 于 无 局 部 运 动 策 略 时,降 低1 4.2%;同时后者的总死点数目和路径重复率降低3 2.9%和4.4%,且时间缩短6.7s,故在实际复杂空间环境路径搜索时,有局部运动策略能更好的提升整体算法的效率。表3 有无局部运动策略实验结果对比算法有局部运动策略无局部运动策略覆盖率/%1 0 01 0 0路径长度/m9 0 5.9 110 5 6.1 3总死点数目4 77 0路径重复率/%1 4.51 8.9算法运行时间/s2 0.7 22 7.4 22.4 三维环境算法验证针对实际复杂三维环境,本文建立的三维仿真模型选作城市环境,对城市中不同高度的建筑物,对于目标区域进行三维全覆盖路径搜索,即对所有建筑物的所有层都要实现覆盖。城市三维环境建模如图1 3所示。无人机主要的工作任务是从底层开始往上进行层层搜索遍历,通过其上搭载的摄像头等辅助设备进行识别搜索,覆盖的主要区域是所有建筑的四周环境。本文三维全覆盖路径规划主要是由分层规划策略、地图重构策略和层间连接策略组成,无人机实际工作时,需要按照分层规划策略划分出的层间间隔以及由地图重构策略和层间连接策略联合所规划出的三维路径进行巡航。利用分层规划策略计算出不同高度层的层间间隔;其中的地图重构策略起到了显著缩短路径长度的关键作用,故本文将对是否采用地图重构策略的实验结果进行对比分析,如图1 4和图1 5所示,实验数据结果如表4所示。0752第8期陈 艺 等:复杂环境下无人机全覆盖三维路径规划算法表4 有无地图重构策略实验结果对比算法有地图重构策略无地图重构策略覆盖率/%1 0 01 0 0路径长度/m78 5 5.5 31 07 9 4.3 3总死点数目3 6 64 4 0路径重复率/%1 1.31 8.3算法运行时间/s1 3 0.6 52 0 1.4 5 三维路径规划图中,起点为(1,1,1),即初始层选择为1m(考虑到无人机实际飞行时,需要和地面保持相应距离,以保证无人机的飞行安全),同时三维环境中由3种不同高度的建筑,分别为3m、1 2m和1 8m,且分布在不同的区域中。由图1 4可见,在无重构地图策略三维全覆盖路径规划时,地图中无障碍物节点区域都是采用“弓”字形搜索策略,这部分区域也是无效区域,从而增加了无效路径长度。由图1 5可见,在有重构地图策略三维全覆盖路径规划时,可依据不同层动态重构相应的地图,从而显著提高了算法的效率。由表4实验结果可知,有重构地图策略相较于无重构地图策略在路径长度上缩短2 7.2 3%,死点数目减少1 6.8 2%,时间减少了7 0.8s,路径重复率减小7%,所以在实际复杂环境中进行无人机全覆盖路径搜索时,采取地图重构策略能够全面提高算法的效率。4 参数分析为了分析不同的参数对实验结果的影响,对实验过程中的主要参数进行实验,对参数进行二维路径规划实验分析,得到实验结果如图1 6所示。由式(4)分析参数可知,此权重参数起着驱使当前节点朝着下一未覆盖节点运动的作用,此权重部分乘积后的值域为0,1,且未覆盖节点本身标记函数为1,因此在全局运动函数中,通过将取值在0,1,间隔0.1,对实验结果进行4项指标(运行时间、路径长度、死点数目和路径重复率)分析。由图1 6 a可知,当=0.4时,运行时间最短,整体上,运行时间随着参数的增加,逐渐缩短;由图1 6 b、图1 6 c和图1 6 d可知,参数对此3项指标都影响不大,这也符合对式(4)的分析。综上,将 参数取 值为1752计算机集成制造系统第2 9卷0.4,将会在实际三维路径规划中,显著缩短算法运行时间,提高效率。5 结束语本文提出一种复杂环境下无人机全覆盖三维路径规划算法,整体算法是由不同高度层的二维地图扩展到整个三维环境,先进行预处理阶段,即由分层规划策略确定层间间隔,由地图重构策略重建出当前高度层的地图;再进入每一层进行全覆盖路径规划(二维地图层面),先判断当前节点属于哪个区域,然后分别由对应的策略选择下一个未覆盖节点,即当前节点处于死区时,采用摆脱死区策略搜寻到下一个节点,当前节点靠近障碍物和边界时,采用局部运动策略寻找下一节点,反之,则采用全局运动策略搜寻下一节点;再进入后处理阶段,由层间连接策略找出下一高度层初始节点,为下一高度层路径规划做好准备,重复迭代路径规划,直到所有高度层全部规划完成;最后经过参数分析后,得到对于本文算法效果较好的参数取值。本文主要针对复杂三维环境下全覆盖路径规划,算法具有良好的可扩展性和适应性,同时考虑无人机的巡航能力,加入动态地图重构策略,能够显著提升无人机的搜寻效率,避免无效区域搜寻造成无人机能量损耗,能够较好地适应不同的场景,但本文算法在宏观上将无人机视作一个质点,实际飞行中还有很多因素需要考虑,未来将进一步研究在非规则建筑物空间中进行精细化三维全覆盖规划。参考文献:1 M I CHA E LN,S HE NS,MOHT A K,e ta l.C o l l a b o r a t i v em a p-p i n go fa ne a r t h q u a k e-d a m a g e db u i l d i n gv i ag r o u n da n d