基于分段随机和角度随机算法的无人机三维航路规划_郑波.pdf

引用格式:郑波，高峰，马昕，等 基于分段随机和角度随机算法的无人机三维航路规划J 电光与控制，2023，30(7):82-90 ZHENG B,GAOF,MA X,et al UAV three-dimensional route planning based on segment random and angle random algorithmJ Electronics Optics Control,2023,30(7):82-90基于分段随机和角度随机算法的无人机三维航路规划郑波a，高峰a，马昕b，朱新宇a(中国民用航空飞行学院，a 航空电子电气学院;b 空中交通管理学院，四川 广汉618000)摘要:提出了一种分段随机和角度随机(SA)的算法，用于复杂空间、多约束条件下的无人机三维航路规划。SA 算法利用随机分段和随机角度确定航路点。同时，对有向线段角度进行规定，设计圆形障碍区避障方法、航路平滑方法以及多航路规划方法，提升航路规划质量，满足航路规划多样性要求。还提出了求解变长解的非关联迭代更新方法，实现对 SA 算法在多约束条件下的求变长解。通过对复杂空间下的航路规划质量验证，以及分别与蚁群算法、遗传算法和粒子群优化算法的比较，证明了 SA 算法的无人机航路规划的稳健性、高效性和通用性。关键词:分段随机和角度随机;避障方法;航路平滑;多航路规划;非关联迭代更新中图分类号:TP18文献标志码:Adoi:10 3969/j issn 1671 637X 2023 07 015UAV Three-Dimensional oute Planning Based onSegment andom and Angle andom AlgorithmZHENG Boa,GAO Fenga,MA Xinb,ZHU Xinyua(Civil Aviation Flight University of China,a Institute of Electronic and Electrical Engineering;b College of Air Traffic Management,Guanghan 618000,China)Abstract:This paper proposes a Segment andom and Angle andom(SA)algorithm for UAV sthree-dimensional route planning under complex space and multiple constraints SA algorithm uses ran-dom segments and random angles to determine the way points Meanwhile,the angle of directional line seg-ment is specified,and the circular obstacle avoidance method,route smoothing method and multi-route plan-ning method are designed to improve the quality of route planning,and meet the diversity requirements ofroute planning This paper also proposes an unassociated iterative updating method to solve the variable-length solution,which can obtain the variable-length solution under multiple constraints By verifying theroute quality in complex space,and comparing with ant colony algorithm,genetic algorithm and particleswarm optimization algorithm,the results can effectively prove that the SA algorithm is robust,efficientand universal for UAV s route planningKey words:Segment andom and Angle andom;obstacle avoidance;route smoothing;multi-routeplanning;unassociated iterative updating0引言无人机(Unmanned Aerial Vehicle，UAV)的航路规划是指在给定的规划空间内，寻找从起始位置到达目标位置，且满足给定约束条件和性能指标的最优或可行航路，以满足无人机安全、适时地抵达目标区域的需收稿日期:2022-06-03修回日期:2022-07-03基金项目:民航重点实验室自主研究项目(FZ2021ZZ04);民航教育人才类项目(14002600100018J034)作者简介:郑波(1984)，男，四川邛崃人，博士，副教授。求1。随着无线通信、智能控制、传感器探测等技术的快速发展，无人机按规划航路自主飞行的能力不断增强，而通过地面人员远程遥控飞行的功能需求逐渐降低，更加凸显了无人机航路规划的重要性2。无人机航路规划是一个 NP(Non-deterministic Poly-nomial)问题3。研究者在单无人机航路规划方面开展了深入研究，取得了大量成果，最优控制法4、人工势场法5、启发式 A*搜索法 6、动态规划法7 等传统数值方法被广泛应用于航路规划。随着智能算法的发展，特别是群体智能算法的快速发展，粒子群优化算法(ParticleSwarm Optimization，PSO)8、蚁群算法(Ant Colony Opti-Vol 30No 7July 2023第 30 卷第 7 期2023 年 7 月电光与控制Electronics Optics Control郑波等:基于分段随机和角度随机算法的无人机三维航路规划mization，ACO)9、遗传算法(Genetic Algorithm，GA)10、模拟退火(Simulated Annealing，SA)11 算法等也被广泛应用于航路规划。文献 12 提出一种量子 PSO(Quan-tum PSO，QPSO)算法，用于无人机三维航路规划，但该算法对于复杂障碍环境的避障能力有限，且航路规划的平滑性较差;文献 13 提出一种基于 ACO 算法的三维航路规划方法，该方法以地形的网格化为航路规划单元，但对航路首端点(Start Point，StP)和末端点(EndPoint，EnP)位置较为敏感，且对航路及高度规划的平滑性较差;文献 14 利用 GA 算法对三维航路进行规划，由于仅通过交叉、变异等机制改变航路点位置坐标，缺乏各航路点位置的主动调节机制，因此对种群初始化质量要求高，避障能力较差。在面对复杂地形地貌及障碍区的航路规划时，当前基于群体智能的航路规划一般难以取得较优结果，因为该类型算法多是以不断调整航路点(Way Point，WP)的位置坐标来实现航路规划的，容易存在规划的航路点间距不均匀，难以避免产生航路平滑性差、避障能力不足等问题。一些算法采用栅格方法对飞行空间进行网格化等分处理，沿着某一坐标轴依次递进，在垂直于该轴的平面进行规划 15。但在一些复杂飞行空间的航路规划中，通常会出现在坐标轴正负方向均移动的情况。单一航路规划难以满足特定任务的备份性、隐蔽性需求，因此多航路规划研究更具有应用价值。针对上述存在的航路点间距不均匀、平滑性差、避障能力不足、对航路的首端点和末端点位置敏感、航路规划单一等关键问题，本文提出一种分段随机和角度随机(Segment andom and Angle andom，SA)算法用于三维航路规划。同时，对航路进行避障、平滑等处理，进行多航路规划，以克服上述存在的问题，提升无人机航路规划质量，保障无人机执行任务的安全性和高效性。1无人机航路规划中常见问题1 1对航路首末端位置敏感的问题在水平投影面上，一些算法只能处理第一象限的首末端位置类型13，16，即末端点坐标在 x 轴和 y 轴上均不小于首端点坐标。但在实际规划中，通常还存在其他象限的首末端位置类型。1 2航路点间距不均匀、平滑性差的问题基于群体智能的算法，因航路点坐标调整是通过随机移动实现的12 14，17，易导致航路点间距不均匀、平滑性差等问题。间距不均匀会影响避障性能，平滑性差不但增加航程，还难以满足无人机的机动性能。1 3栅格方法移动方向的问题栅格方法要求航路在规定的坐标轴方向上递进 13，15。但在对复杂飞行空间进行航路规划时，通常是不会只朝一个规定方向递进的，栅格方法难以满足这种航路规划需求。1 4避障能力弱的问题基于群体智能的算法，通常采用惩罚系数法或航路点位置调整法进行避障。由于在复杂高维空间寻优能力的限制，很难做到完全避开复杂障碍区，因此不能有效应对复杂飞行空间的航路规划。2SA 算法的规划过程2 1有向线段的角度计算在航路规划时，航路是有向的，因此对于两条有向线段，一条规定为起始轴(Starting Axis，SA)，另一条为旋转轴(otation Axis，A)，旋转轴是以起始轴首端点为旋转点，以起始轴为初始位置，顺时针或逆时针旋转得到的。表 1 显示了起始轴和旋转轴在不同象限时，两条有向线段间夹角 的算式，其中，S为 x 轴与起始轴的夹角，为 x 轴与旋转轴的夹角。表 1有向线段夹角算式表Table 1Calculation formulas of included anglesbetween directed line segments起始轴旋转轴在，象限旋转轴在，象限在象限=S=180+S在象限=(180+S)=S在象限=180+S=S在象限=S=(180+S)180 时 =360;180 时 =+3602 2SA 算法的初始化方法图1 显示了 SA 算法的航路初始化原理及过程。x 轴与航路首末端连线的夹角为，若随机将首末端连线等分为 S 段，每段长度为 l，产生 S 1 个分段点(Seg-ment Point，SeP)，有 S 1 条直线过分段点且垂直于首末端连线。设分段点集合(Segment-Point Set，SPS)为 StP，SeP1，SePi，SePS 1，EnP，包含首末端点。除开分段点集合中的 SePS 1，EnP 两点外，依次以分段点集合中的点为旋转点，以首末端连线为起始轴，随机顺时针或逆时针产生一个角度 A，从旋转点沿着角度 A 与垂线的连接点，就构成一个构造航路点(Constructed Way Point，CWP)，则依次可构成 S 1 个构造航路点。首末端点和各构造航路点可形成一个构造航路点集合(ConstructedWay-Point Set，CWPS)StP，CWP1，CWPi，CWPS 1，EnP。为保证后续避障算法的实现，在构造航路点集合中各点间均匀填充点，形成填充航路点(Filled Way Point，FWP)。首末端点、构造航路点和填充航路点共同构成了一条完整的初始航路(Initial oute，I)。38第 7 期图 1SA 算法航路初始化示意图Fig 1oute initialization diagrambased on SA algorithm如图1 所示，假设首末端连线长度为 L，每段长度为l=L/S，首端点 StP 的坐标为(Sx，Sy)，末端点 EnP 的坐标为(Ex，Ey)，则第 i 个分段点 SePi的坐标可表示为Six=Sx+(Ex Sx)iSSiy=Sy+(Ey Sy)iSi=1，S 1(1)实际上，式(1)所求的分段点坐标即是在首末端点间均匀填充获得的。第 i 个构造航路点 CWPi坐标可通过计算得到，即Cix=S(i 1)x+lcos Aicos(+Ai)sgn(Ex Sx)Ciy=S(i 1)y+lcos Aisin(+Ai)sgn(Ex Sx)(2)式中:i=1，S 1，若 i 1=0，则 S(i 1)x=Sx，S(i 1)y=Sy;sgn(*)是符号函数，当 Ex Sx0 时，sgn(Ex Sx)=1，否则 sgn(ExSx)=1。构造航路点坐标确定后，再按照式(1)的方式在构造航段点集合的各相邻点间均匀插入填充航路点。设航路点总数均为 D，且含首末端点，则填充航路点的个数是 D S 1，共有 S 段，各段填充航路点个数 Di为Di=round(D S 1)(S(i1)x Six)2+(S(i1)y Siy)2S1i=1(S(i1)x Six)2+(S(i1)y Siy)2DS=D S 1 S1i=1Di(3)式中:i=1，S 1，若 i 1=0，则 S(i 1)x=Sx，S(i 1)y=Sy;round(*)是四舍五入函数。2 3SA 算法的避障方法障碍区(Obstacle Area，OA)是指对飞行安全有威胁的区域，可包括击落威胁、超高威胁、气象威胁、禁止飞行等区域，将障碍区等效为圆形区域进行处理，便于通过比较到圆心(Center Point，CP)距离来判断航路点是否在障碍区内。SA 算法的避障原理如图 2 所示。过 OA 内的航路点 WP2，WP3作垂线，以 WP1为旋转点，以 WP1到 WP4的线段为起始轴，逆时针旋转角度，旋转线与过 WP2垂线相交可得在 OA 外的移动航路点(Moved WP，MWP)MWP1。同理，可得到 WP3在OA 外的 MWP2，连接 WP1，MWP1，MWP2，WP4，使初始航路成为避障航路(Obstacle Avoidance oute，OA)。图 2SA 算法的避障原理示意图Fig 2Obstacle avoidance principle diagrambased on SA algorithm为避开障碍区，关键是要确定旋转角度，借助向量法进行求解。如图 2 所示，作坐标变换，以 WP1到WP4的连线作为横轴，WP1为圆点，则可形成 3 个向量，分别为v?1，v?2，v?3，按照向量运算法则，v?1 v?2=v?3。可计算出 WP1到 WP4连线与 WP1到 CP 连线间夹角为，同时计算出 WP1和 WP2间的距离为 lm，WP1和 CP间的距离为 lc。因此，v?1的模为 lc，复角为，v?2的模为lm/cos，复角为。则可求出 的表达式为(lccos lm)2+lcsin lmcos sin()2r+(4)式中:r 是障碍区的半径;为安全裕度，主要是平衡弧形障碍区对 MPW 的影响，保证航路规划能完全避开障碍区。整理式(4)后可得l2mtan2 2lclmsin tan +l2c2lclmcos +l2m(r+)20。(5)按照几何关系，和 是正负号相反的角度，且 是使得式(5)成立的最小角度，据此求解一元二次方程，得出 的唯一解。当 的值确定后，按照式(2)求出 MWP1和 MWP2的坐标。2 4SA 算法的平滑方法SA 算法的平滑处理是在寻优结束后，对输出的优化解进行的，包含位置平滑(Position Smoothing)和超48第 30 卷电光与控制郑波等:基于分段随机和角度随机算法的无人机三维航路规划高处置(Over Height Disposal)。2 4 1SA 算法的位置平滑方法图 3 显示了位置平滑的意义，位置平滑的原则就是尽量减小转角，缩短航程。图 3位置平滑示意图Fig 3Position smoothing diagram如图3 所示，从 StP 到 EnP 规划航路，假设依次避开 n 个 OA，避开第 i 个 OA 形成的移动航路点，构成第 i个移动航路点集合(MWP Set，MWPS)，MWPi1，MWPi2，MWPin(i)，n(i)表示第 i 个移动航路点集合中的元素个数。位置平滑的步骤如下。1)依次为 MWPi1和 MWPin(i)分配构造航路点集合中的距离最近点(Nearest Segment Point，NSP)，分别记为 NSPi1和 NSPin(i)。在第 i 个 MWPS 中，若 n(i)为偶数，选择编号为 n(i)/2 和(n(i)+1)/2 的两个移动航路点 作为优化连接 点(Optimized Connection Point，OCP)OCPi1，OCPi2;若 n(i)为奇数，选择编号为(n(i)+1)/2 的移动航路点作为优化连接点 OCPi1，OCPi2，此时，OCPi1=OCPi2。同时，要将 OCP 按序插入构造航路点集合中。2)对于第1 个 MWPS，则在 OCP11到 StP 间重新均匀填充航路点，并判断是否有新生成航路点在 OA 内。若无，则利用 OCP11到 StP 间新均匀填充航路点代替原来两点间航路点。若有，则利用 OCP11到 NSP11间新均匀填充航路点代替原来两点间的航路点。3)对于第 n 个 MWPS，则在 OCPn2到 EnP 间重新均匀填充航路点，并判断是否有新生成航路点在 OA内。若无，则利用 OCPn2到 EnP 间新均匀填充航路点代替原来两点间的航路点。若有，则利用 OCPn2到NSPnn(i)间新均匀填充航路点代替原来两点间的航路点。4)对于第2 到第 n 1 个 MWPS，设 j=2，n 2，依次在 OCPj2到 OCP(j+1)1间重新均匀填充航路点，并判断是否有新生成的航路点在 OA 内。若无，则利用OCPj2到 OCP(j+1)1间新均匀填充航路点代替原来两点间的航路点。若有，则求出 OCPj2到 OCP(j+1)1间的 MWPS，嵌入执行步骤 1)4)，直至 OCPj2到 OCP(j+1)1间新均匀填充的航路点不经过 OA 为止。2 4 2SA 算法的超高处置方法对航路进行位置平滑处理后，存在新均匀填充的航路点在高度上不满足约束的可能，出现超高航路点，因此需要对超高航路点进行处理，使其满足高度约束。具体处置步骤如下。1)若位置平滑后，有航路点不满足高度约束条件，则将超高航路点对应替换的原航路点作为一个MWPS，设 MWPS 共有 n 个元素。2)确定 MWPS 的 NSP 和 OCP。在构造航路点集合中确定 NSP1和 NSPn;将 MWPS 中的 MWP1和 MWPn作为 OCP1和 OCP2。3)在 NSP1和 OCP1，NSPn和 OCP2间重新均匀填充航路点，并判断是否有新生成的航路点在 OA 内。若无，则利用 NSP1到 OCP1，NSPn到 OCP2间新均匀填充航路点代替原来两段间的航路点。若有，则计算出所有 MWPS，包含因超高产生的 MWPS，将 NSP1作为StP，NSPn作为 EnP，按照 2 4 1 节的步骤进行位置平滑。此时，所获得的航路必然满足高度约束的要求。2 5SA 算法的多航路规划方法多航路规划可提升航路的备份性和多样性，图 4为多航路规划方法的示意图。图 4多航路规划方法示意图Fig 4Multi-route planning diagram2 5 1指定途中目标点的方法设定某一点为途中目标点(Midway Target Point，MTP)，其坐标为(Mx，My)，航路规划时必须经过该点。如图4 所示，此时，把 MTP 作为第一个构造航路点 CWP1。58第 7 期再按22 节方法随机确定余下的构造航路点和填充航路点。2 5 2指定航向及距离的方法该方法本质上和指定途中目标点方法是一致的。如图 4 所示，指定途中目标点方法是先确定 MTP 坐标。而该方法是先确定航向和距离(即 A1和 l)，再来确定第一个 CWP1。2 5 3指定航路点及角度的方法如图 4 所示，设航路点总数为 D，按要求选择第 i个航路点作为选择航路点(Selected Way Point，SWP)，按表 1 方法求出夹角。此时再求出第 i 个航路点夹角不小于 的最短规划航路。因此，该方法需要指定SWP 和。2 5 4混合方法混合方法是将指定途中目标点和指定航路点及角度点相结合，先指定途中目标点 MTP，再确定 SWP 和，最终求出符合要求的最短航路。3SA 算法的更新过程3 1SA 算法的适应度函数适应度函数 fit(*)包含了优化目标，以及约束条件，是定量评价解优劣的标准 18。SA 算法的fit(*)设计主要考虑无人机的飞行性能特点，以及障碍区威胁等。本文对固定翼无人机进行研究，适应度函数主要有以下约束条件。3 1 1水平转角的约束水平转角 限制了无人机转入下一航段时，航向角的变化范围。水平转角 是按照表 1 所示方法，计算出 WPi到 WPi+1间航段与 WPi+1到 WPi+2间航段的夹角，则该约束可表示为|max。3 1 2俯仰角的约束俯仰角 限制了所规划航路在高度方向爬升或下滑的最大角度，该约束是由无人机性能决定的。设相邻 WPi，WPi+1的位置分别为(xi，yi，zi)和(xi+1，yi+1，zi+1)，则 max，该约束可表示为arctanzi+1 zixi+1 x()i2+yi+1 y()i()2max。(6)3 1 3航段长度的约束航段长度 lLi反映了无人机在开始改变飞行状态前必须保持直飞的最短距离。该约束可表示为 lLilLmin，则 WPi和 WPi+1间航段约束为(xi+1 xi)2+(yi+1 yi)2+(zi+1 zi)2lLmin。(7)3 1 4航路点高度的约束航路点高度 zi限制了无人机在所规划航路上的最大飞行高度。设 Zi为第 i 个航路点水平坐标对应的地形高度，最大飞行高度为 Zmax，最佳飞行高度是 Zbest，飞行高度与地形高度应不低于相对高度 Zrel。航路点高度的约束为 ziZmax。为满足无人机执行任务的需要，则各航路点的规划高度为zi=Zii=1，DZi+Zrel2i=2，D 1Zi+Zreli=3，D 2ZbestZi+Zrel Zbest，i 3，i D 2Zi+Zrel其他。(8)3 1 5障碍区的约束当航路规划穿越障碍区时，以 n(i)表示第 i 个移动航路点集合中的元素个数，n 为初始规划时，穿越的障碍区数。该约束是为了保障无人机完全避开障碍区，可表示为ni=1n(i)=0。本文采用规划航路航程最小的优化目标，则整个优化模型表示为minD1i=1l()Li(9)s t max，max，lLi lLminzi Zmax，ni=1n(i)=0。最终，适应度函数 fit(*)可表示为fit(S)=min(D1i=1lLi)+nstPst(10)式中:S=S，A1，Ai，AS 1，S 是随机确定的，表示算法的可行解集向量;表示规划的航路点坐标;S表示由 S 所确定的避障航路中各航路点坐标集合;nst表示不满足的约束条件数;Pst表示当任一约束条件不满足时的惩罚系数，因为优化问题是最小化优化问题，Pst通常取较大的数，本文令 Pst=1000。3 2非关联迭代更新方式传统群体智能算法一般是基于定长解的迭代过程。而 SA 算法的可行解 S 中元素个数取决于随机确定的 S，所以是变长解问题。本文提出一种非关联迭代更新方式求解变长解。非关联是指第 i 次迭代求的解 Si，不依赖第 i 1 次迭代求出的 Si 1、极值等计算结果，第 i 次迭代的解 Si依然靠随机产生。迭代过程中，假设迭代最大次数为 Imax，种群为Ns，Sopt表示优化解，Sij为第 i 次迭代的第 j 个可行解，则iImax，jNs，若 min(fit(Sijij)fit(Soptopt)，则令 Sopt=Sij，opt=ij，直至满足迭代终止条件 i=Imax为止。图 5 显示了 SA 算法的航路规划68第 30 卷电光与控制郑波等:基于分段随机和角度随机算法的无人机三维航路规划流程。图 5SA 算法流程图Fig 5Flow chart of SA algorithm4SA 算法的性能验证为验证 SA 算法的无人机航路规划性能，生成一幅 100 km 100 km 复杂地形图，该地图三维坐标(xi，yi，Zi)间关系可表示为Zi=01+50i=1a(i)expxi b(i)c(i()2yi d(i)e(i()2(11)式中，a，b，c，d，e 均是1 50 维的系数向量。生成的地形图见图 6。图 6复杂三维地形图Fig 6Complex 3D topographic map图6 中，红色圆圈表示障碍区，共24 个，远超其他文献中的障碍区数量 14，17，19。障碍区密度较大，相互交错，形成复杂障碍区分布，能对算法造成耦合影响，可有效检验算法的航路规划质量。下文中坐标单位均为千米。4 1对不同首末端类型规划的性能验证在地形图上设置 4 对首末端点，如图 7 所示，坐标分别为:StP1=(50，50)，EnP1=(6，9);StP2=(50，50)，EnP2=(10，88);StP3=(50，50)，EnP3=(96，89);StP4=(50，50)，EnP4=(98，4)，代表 4 种首末端类型。按照SA 算法进行航路规划，设 2S4，A 40，40，Imax=50，N=50，D=40，max=80，max=25，=0 5 km，lLmin=1 km，Zmax=2 8 km，Zbest=1 km，Zrel=0 5 km，则 4 条航路规划如图 7 所示。为显示方便，且高度规划符合约束要求，因此略去地形信息，仅在二维平面上显示规划航路。图 7对不同首末端类型的验证图Fig 7Verification for different start-end points图 7 表明，SA 算法能够应对任意的首末端位置类型，可以规划从任意位置到任意位置的航路，这符合航路规划的实际需求。4 2对超高识别的性能验证为验证 SA 算法在航路规划时的超高识别性能，将图 6 中两个最高峰的障碍区去掉，按照 4 1 节的算法设置，当 Zmax分别为 2 8 km 和 3 8 km 时，验证从StP1=(32，95)到 EnP1=(84，69)，以及从 StP2=(6，9)到 EnP2=(70，47)之间规划航路的超高识别性能。如图 8 所示，航路 1 和航路 3 在 2 8 km 高度限制下，航路最高高度分别为2 789 km 和2 792 km，航程分别为6209 km 和7750 km。而航路2 和航路4 在38 km高度限制下，航路最高高度分别为 3 408 km 和 3057km，航程分别为5978 km 和7475 km。显然，在不同高度约束下，SA 算法会自动寻找合适的航路，满足高度约束要求，输出最优航路。图 8对超高识别的验证图Fig 8Verification for over height recognition78第 7 期4 3航路平滑效果的性能验证为验证 SA 算法的航路平滑效果，按照 4 1 节的算法设置，选择从 StP=(44，2)到 EnP=(63，49)之间规划航路。如图 9 所示，航路 1 是寻优后未经任何平滑处理直接输出的航路，航程为5697 km;航路2 是对航路 1 进行位置平滑和超高处置后输出的航路，航程为 55 50 km，航路 2 比航路 1 平滑;航路 3 是对航路1 仅经过位置平滑后输出的航路，航程为5489 km，尽管航程最短，但不满足高度约束条件。图 9 证明了进行航路平滑的必要性，但在平滑处理时，必须同时考虑位置和高度的约束条件，进行位置平滑和超高处置。图 9对航路平滑效果的验证图Fig 9Verification for route smoothing effect4 4对复杂障碍区避障能力以及寻优性能的验证在复杂障碍区的条件下，验证非关联迭代方式的寻优性能，将 SA 算法连续运行 50 次，分别统计适应度值的最小值(min)、均值(mean)、最大值(max)、标准差(Standard Deviation，StD)，以衡量算法的寻优性能。如图10 所示，按照41 节的算法设置，选择从 StP1=(53，3)到 EnP1=(32，95)，从 StP2=(44，87)到 EnP2=(18，11)，从 StP3=(78，86)到 EnP3=(85，5)，以及从 StP4=(44，2)到 EnP4=(67，87)，分别规划航路 1，2，3，4。图10 显示了50 次计算中适应度值最小的规划航路。图 10对算法避障能力的验证Fig 10Verification for obstacle avoidance capability表 2 所示为 4 条航路规划 50 次的统计量，同时给出了最小和最大航程时对应的解。表 2 表明，在面对复杂障碍区规划时，SA 算法规划的所有航路均满足全部约束条件，且航程变化幅度很小，输出的航路具有较强的鲁棒性和稳定性。表 2SA 算法寻优能力验证表Table 2Verification table for optimization capability of SA algorithm航路最小航程时航程/km解mean/km最大航程时航程/km解StD/km航路 1995552 3，2 3936，2 39369985151001014 4，33556，33556，11070201310航路 2839370 3，86916，98369841367844421 3，78914，7 830501136航路 3844060 4，80554，102113，64873845774850021 4，59806，154207，15420701396航路 4914963 4，19 1967，264959，18 4335917653919335 3，17 3761，138525010994 5对多航路规划的性能验证为验证 SA 算法的多航路规划能力，如图 11 所示，按照 4 1 节的算法设置，选择从 StP=(7，40)到EnP=(95，40)之间规划航路。航路 1 按照指定中途目标点方法进行规划，MTP=(18，77);航路2 和航路3按照指定航向及距离方式进行规划，航向和距离分别为(60，25)和(40，15);航路 4 和航路 5 按照指定航路点及角度的方式进行规划，SWP 为 21，角度分别为 20，20;航路 6 和航路 7 按照混合方式进行规划，MTP=(38，5)，SWP 为 25，角度分别为 5，5。图 11对多航路规划的性能验证Fig 11Verification for multi-routeplanning performance88第 30 卷电光与控制郑波等:基于分段随机和角度随机算法的无人机三维航路规划图 11 显示了 4 种多航路规划方法规划的 7 条航路。当 SA 算法进行多航路规划时，航程最短是在满足航路规划方式的前提下实现的，能增加航路规划的多样性和备份性，满足特定任务条件下的规划需求。5与其他航路规划算法的性能比较将 SA 算法与同样是基于群体智能的其他航路规划算法进行比较，分别与文献 12，19 20 所提出的基于 QPSO 算法、GA 算法、ACO 算法进行比较，既比较连续计算 50 次的寻优性能，又比较应对不同障碍区的航路规划质量。分别规划 4 条航路，从 StP1=(2，40)到 EnP1=(57，30)，从 StP2=(63，98)到 EnP2=(98，4)，从 StP3=(34，34)到 EnP3=(45，76)，从 StP4=(32，95)到 EnP4=(53，3)之间，分别规划航路 1，2，3，4。其中:航路 1 是简单航路，不需避开任何障碍区;航路 2 是一般航路，航程较长，容易避开航路上的障碍区;航路 3 和航路 4 属于复杂航路，对避障能力要求较高，区别在于航程长短。航路规划的各约束条件如 31 节所示，SA 算法参数设置如 4 1 节所示。QPSO 算法、AC 算法和 GA算法的 Imax=100，Ns=200。3 种算法相应的适应度函数以及参数设置请分别参见文献 12，19 20。QPSO和 GA 算法的航路点个数固定，设 D=40，而 ACO 算法采用栅格法，航路点个数取决于对固定坐标轴的等分数量。各算法航路规划质量比较如表 3 所示，包含各算法在相同运行条件下，计算一次的平均时间消耗(Elapse Time，ET);需要寻优的参数个数(Number ofParameters，NP);50 次计算中航程的最小值(min)、均值(mean)、最大值(max)、标准差(Standard Deviation，StD);50 次计算中违反约束条件(Constraint Violations，CV)的次数;对违反各约束条件的次数进行统计，用1 6维向量 CCV表示，CCV中的元素依次对应违反 3 1节约束条件的次数。如表 3 中的(0 0 0 6 0)，表示6 次违反第 4 个约束条件，即违反高度约束。表 34 种算法航路规划性能比较Table 3Comparison for route planning performance of four algorithms航路算法ET/sNPmin/kmmean/kmmax/kmStD/kmCVCCV航路 1ACO56843456 3443594944614278115686(0 0 0 6 0)GA142537656 44495693455731710180450(0 0 50 0 0)QPSO85787668 21357575358659104360750(50 0 23 7 0)SA33 67456128856 13135613167 0799 10100(0 0 0 0 0)航路 2ACO141 27921168013122040612997212272440(34 0 0 0 6)GA153 51761035106105060811007211138250(0 0 45 0 50)QPSO99 39761039003111625212776695416743(42 0 8 1 0)SA36 8941009230100 96271012291006480(0 0 0 0 0)航路 3ACO45044052 1253649051745555484170(0 0 0 0 0)GA134427645 61444798305133301335850(2 2 50 0 50)QPSO100517668 76681093888153036718691550(50 2 17 0 4)SA43 94447951248 1653482794005530(0 0 0 0 0)航路 4ACO7115601062445123611415536821022437(0 0 0 0 7)GA14424769592269676159748830347950(0 0 50 0 50)QPSO114857610266311204629159282812960950(49 0 18 1 50)SA39 61499378199 70891000872013020(0 0 0 0 0)表 3 表明:在不同的航路规划中，面对多约束条件，SA 算法时间消耗最小、寻优参数最少、性能最稳定、鲁棒性最强、航路规划质量最高，有力证明了SA 算法设计的合理有效(加粗数值凸显本文所提SA 算法的优势)。造成其他 3 种算法规划质量低的原因是:除了算法自身的寻优性能外，主要是因为在对复杂的、多约束航路进行规划时，通过调整航路点坐标位置很难保证所有航路点间的坐标都获得协调一致的恰当位置。而 SA 算法巧妙地通过选择角度来确定坐标，因此避开了因直接调整航路点坐标而造成的普遍性问题，保障了航路规章质量。6结束语本文设计 SA 算法，用于规划复杂空间、多约束条件下的无人机三维航路规划，对首末端连线随机进行分段，通过随机角度确定构造航路点，再连接构造航 路点和填充航路点的方式确定初始航路。同时设计了障