1、基于搜索规则和交叉熵优化的无人机路径规划方法胡 磊 赵 辉 南 熠 伊国兴*王 昊 曹志慧(哈尔滨工业大学航天学院 哈尔滨 150000)摘 要：针对快速扩展随机树(RRP)算法计算效率低、不具备渐进最优性等问题，该文提出一种基于搜索规则和交叉熵优化的改进RRT(IRRT)算法。在路径搜索过程中根据当前节点位置及搜索规则，调整搜索步长及搜索方向，实现高效、快速的初始路径规划。然后，利用交叉熵理论优化初始路径，使得路径具备渐进最优性。仿真实验1结果表明所提方法的有效性和收敛性，仿真实验2将该文所提算法与多种变体RRT算法进行比较，结果表明所提算法能够保证计算效率，同时使得路径具备渐进最优性。关键
2、词：无人机；路径规划；改进快速扩展随机树；路径优化；交叉熵中图分类号：TP242文献标识码：A文章编号：1009-5896(2023)06-2144-09DOI:10.11999/JEIT220579Unmanned Aerial Vehicle Path Planning Method Based onSearch Rule And Cross Entropy OptimizationHU Lei ZHAO Hui NAN Yi YI Guoxing WANG Hao CAO Zhihui(School of Astronautics,Harbin Institute of Technolo
3、gy,Harbin 150000,China)Abstract:The Rapidly-exploring Random Tree(RRT)algorithm has some shortcomings,including lowcomputation efficiency and non-asymptotic optimality.An Improved RRT(IRRT)algorithm based on searchrules and cross entropy optimization is presented in this paper.In the path search pro
4、cess,according to thecurrent node position and search rules,the search step size and search direction are adjusted to achieve efficientand rapid initial path planning.Then,the cross entropy theory is applied to optimize the initial path,so thatthe path has the characteristic of asymptotic optimality
5、.The simulation results of experiment 1 show theeffectiveness and convergence of the proposed method,in the second simulation experiment,the proposedalgorithm is compared with several variant RRT algorithms,and the results show that the proposed algorithmcan ensure the computational efficiency and m
6、ake the path has the characteristic of asymptotic optimality.Key words:Unmanned Aerial Vehicle(UAV);Path planning;Improved Rapidly-exploring Random Tree(IRRT);Path optimization;Cross entropy 1 引言无人机(Unmanned Aerial Vehicle,UAV)是一种可扩展、可回收、并能够携带有效载荷的无人飞行平台1，具有成本低、体积小、零伤亡、适应能力强等优点2,3，在民用及军用领域具有广泛的应用。利用
7、无人机执行各种任务的基本保障是为其规划出安全可靠的飞行路径，近年来国内外学者在路径规划领域进行了大量的研究，主流的路径规划算法包括A*算法4,5、D*算法6、快速扩展随机树(Rapidly-exploring Random Tree,RRT)算法7,8，及遗传算法9,10、粒子群算法11、人工蜂群12等。A*算法的搜索空间增长是指数级别的，当存在多个极值时不能保证搜索到最优路径。遗传算法具有灵活性强、适用范围广的特点，但是存在模型精度不够、时效性不足等问题10。尽管粒子群算法结构简单、容易实现，但存在早熟收敛、容易陷入局部最优等问题。利用上述方法开展路径规划问题研究时，往往需要对算法进行改进9
8、,10。快速扩展随机树算法是一种基于节点采样的路径搜索方法13，该算法具有结构简单、容易实现等优点，因此被国内外学者广泛使用。对于密集障碍物任务场景，RRT算法存在计算效率低、收敛速度慢、路径不具备渐进最优等问题，因此，许多学者提出了相应的改进算法。Kuffner等人14提出了双向RRT(Bidirectional Extended RRT,BERRT)算法，该算法从起点和目标点出生成两颗随机树，在计算资源充足时能够有效的提升搜索速度。王乐 收稿日期：2022-05-10；改回日期：2022-10-26；网络出版：2022-11-03*通信作者：伊国兴第45卷第6期电 子 与 信 息 学 报V
9、ol.45No.62023年6月Journal of Electronics&Information TechnologyJun.2023乐等人15提出了一种改进RRT(Improved RRT,IRRT)算法，优点在于可扩展，能够为不同数量机器人构成的编队规划路径，但是路径中明显存在大量冗余路径，导致机器人编队的路径成本较大。李洋等人16提出了一种自适应步长的RRT(Self-Ada-ptive Step-size RRT,SAS-RRT)算法，在为机器人规划路径时，无需多次调试就能确定步长，提高了路径规划效率。Jeong等人17提出了Quick-RRT*算法，该算法通过三角不等式定理优化R
10、RT*算法扩展范围，获得了更优的路径和收敛速度。上述方法都能有效地解决机器人或无人机路径规划问题，但是仍然存在以下不足：(1)RRT13,BERRT14,IRRT15,SAS-RRT16等算法为无人机规划出的路径不具备渐进最优特性，对于执行物流快递、搜索救援等路径规划任务是不适用的。(2)Quick-RRT*17算法能够保证搜索路径具备渐进最优特性，但是算法计算效率不高，收敛较慢，尤其是在密集障碍物情形下难以快速高效地规划出最短路径。针对以上存在的问题，本文提出一种基于搜索规则和交叉熵的改进RRT算法，通过设计搜索规则以实现快速高效的无人机路径规划，通过交叉熵理论优化路径使其具备渐进最优特性。
11、2 RRT基础理论RRT是一种基于随机采样的路径搜索方法，其基本思路是通过对已知地图的空白区域进行随机采样生成随机树，并通过对树进行回溯生成相对最优的路径。该方法具有搜索速度快、无需对环境建模、易于实现等特点，被广泛地应用与无人机、无人车、无人船、机器人等的路径规划问题1012。qsqeqnearqrandqnearqrandstpqnewqnewqestp如图1展示了RRT算法搜索过程中各个节点的扩展过程，和分别表示起点和目标点，表示现有扩展节点中距离当前随机点最近的点，在点和点的连线上，以为步长扩展出新节点。当新扩展点距离目标点 的距离小于步长时，完成搜索过程。根据搜索树，从目标点出发反向
12、回溯到起点，能够获得一条从起点到目标点的折线段路径。qs具体而言，搜索树从起点 出发，在空间中随qrandqrand机生成一个点，的生成规则可以表述为式(1)qrand=G (rand,rand)(1)G=mL,mWT R2mLmWrand其中，表示任务场景大小，和分别表示长度和宽度，为01的随机数。qrandqnear现有扩展节点中距离当前随机点最近的节点根据式(2)确定dist(qrand,qnear)dist(qrand,qi),i=1,2,.,Tol(2)Toldist其中，表示当前扩展树中所有节点，表示距离函数，定义如式(3)dist(qi,qj)=qi qj(3)qnearqnea
13、rqrandstpqnew在找到节点之后，沿着点到点的方向，以步长拓展获得新的节点，如式(4)所示qnew=qnearqrandqnear qrand stp(4)GHqnew假设场景的二值灰度矩阵为，其中0表示障碍物、禁飞区所在区域，1表示可飞区域，若点满足式(5)，则表明该点可行H(qnew(1),qnew(2)=1(5)qnearqnewqnearqnew节点到节点路径段是否可行，需要进一步判断，基本思路是将该路径段用等间距的k个路径点分割，得到k+1段路径，若这k个路径点均可行，表明k+1段路径亦可行，即节点到节点的路径段可行，数学描述如式(6)F(qnear,qnew)=1,ki=1
14、H(qi(1),qi(2)=k0,其他(6)3 SRBERRT-CE算法设计 3.1 SRBERRT算法qsqeqsqeGHqnearqnearstpqnear双向扩展RRT算法的基本思路是同时从起点和目标点 开始进行搜索，并将从起点 出发的搜索树称为始树，从目标点 出发的搜索树称为终树，两树的搜索过程与单树的搜索过程相同，包括扩展和查询。在此基础上，提出了基于搜索规则的双向扩展RRT(Search Rules-based Bidirectional Ex-tended RRT,SRBERRT)算法，搜索规则包括搜索步长规则、搜索角度规则和搜索方向规则。为提升搜索速度，设计了搜索步长规则，该规
15、则如图2所示，给定地图能够得到其灰度矩阵，以节点为圆心，以半径R为大小的区域C内，节点处的步长如式(7)图 1 RRT算法搜索树第6期胡 磊等：基于搜索规则和交叉熵优化的无人机路径规划方法2145stpqnear=1+iCjCH(i,j)iCjCI(i,j)stp0(7)stp0IH(i,j)qnear其中，为给定步长，矩阵中所有元素均为1，为灰度矩阵，该式表明节点处周围可行区域越多，则搜索步长越长。对于任意的任务规划场景，搜索过程中不用额外资源来计算该节点处的步长，这是因为任意节点处的搜索步长是事先确定的。qnear,rootqnearqnew为使得生成路径的可航性更好，在搜索树扩展过程中引
16、入搜索角度规则，如图3所示。从节点出发到节点，若最大转弯角为，则为使得生成的路径点可行，则新节点为需满足式(8)。只有满足最大转弯角约束以及续航约束的新节点方能加入到搜索树中，并进行下一次随机采样，这使得在采样过程中能够减少生成需要进行较大机动的节点，提高路径的可航性cos=cosqnear qnear,root,qnew qnear cos(8)p 0,1psp psqeqs,randqs,randqeqe,rand搜索方向规则是指在生成采样点的过程中按照一定的规则进行，具体而言，始树的搜索方向如式(9)，首先生成一个随机数，为给定的朝着目标点搜索的概率，若，选取为随机采样点，否则采样点随机在空间内随机生成。终树的扩展从目标点 开始，采样点的扩展方向如式(10)。在实现过程中，始树和终树的扩展过程交替进行，逐步向对方扩展，直到两树相连。qs,rand=qe,p psqrand,其他(9)qe,randqs,p psqrand,其他(10)dist(qs,new,qe,new)当两颗树之间的距离满足式(11)时，停止扩展,并从两树连接的节点开始查询过程，对于始树，从连接点向起点进行回溯
