1、2023 年第 36 卷第 7 期Electronic Sci.Tech./Jul.15，2023https:/收稿日期:2022-01-07基金项目:国家自然科学基金(62003207)National Natural Science Foundation of China(62003207)作者简介:王杨斌(1994 )，男，硕士研究生。研究方向:机器人路径规划。章伟(1977 )，男，博士，教授。研究方向:非线性控制与观测、多智能体协调控制。基于队形变化的多无人机航迹规划算法王杨斌，章伟，胡陟(上海工程技术大学 机器人智能控制实验室，上海 201620)摘要针对多无人机在复杂环境下的航迹
2、规划问题，文中提出基于队形变化的多无人机航迹规划算法。利用领航 跟随的无人机拓扑结构，设计了一种以时间与航程作为衡量指标的代价函数，求解出最优的编队集结点。采用改进的 Informed T*算法求解出领航者的渐近最优航迹，结合队形变化策略实现了跟随者的航迹规划与避障。在定义队形变化量、路径长度比、航向稳定性性能指标的基础上，文中进行了仿真实验并对生成航迹进行评价与对比。仿真结果表明，无人机编队实现了在复杂环境下航迹规划与避障，同时为跟随者规划出最优航迹，与领航者最优航迹长度相差不到 1%，验证了该算法的实用性与有效性。关键词无人机编队;领航 跟随法;Informed T*;编队集结;航迹规划;
3、队形变化;最优航迹;避障中图分类号TP242文献标识码A文章编号1007 7820(2023)07 039 09doi:10.16180/ki.issn1007 7820.2023.07.006Multi UAV Path Planning Algorithm Based on Formation ChangeWANG Yangbin，ZHANG Wei，HU Zhi(Laboratory of Intelligent Control and obotics，Shanghai University of Engineering Science，Shanghai 201620，China)Abs
4、tractIn view of the problem of trajectory planning of multiple UAVs in complex environments，a multi UAV trajectory planning algorithm based on formation changes is proposed Based on the topology of pilot followingUAV，a cost function with time and range as the metrics is designed to solve the optimal
5、 formation rendezvous pointThe improved Informed T*algorithm is used to solve the asymptotic optimal track of the leader，and the trackplanning and obstacle avoidance of the follower is realized by combining the formation change strategy On the basisof defining formation variation，path length ratio，a
6、nd heading stability performance indicators，simulation experi-ments are carried out and the generated tracks are evaluated and compared The simulation results show that the UAVformation can achieve trajectory planning and obstacle avoidance in complex environments，and at the same time planthe optima
7、l trajectory planning for the follower，which is less than 1%away from the optimal trajectory length of theleader，which improves the practicality and effectiveness of the algorithmKeywordsUAV formation;leader following method;informed T*;formation assembly;path planning;formation change;optimal track
8、;obstacle avoidance近年来，随着无人机自主能力不断完善、环境感知能力不断提高，其在军事打击、灾害救援、物流等诸多领域1 5 发挥着愈加重要的作用。由于单无人机作业受到多种限制，多无人机航迹规划已成为提升协同作业效率的关键。无人机航迹规划算法主要包括:人工势场法、生物算法、采样法等6。人工势场法应用最为广泛，但在复杂环境中使用该算法容易出现陷入局部最优值的问题7。生物算法包括蚁群算法8、粒子群算法等9，这些算法的效率往往与借助外部的约束相关。采样法包括经典快速随机搜索树(apidly Exploring andomTree，T*)算法10 11、概率路线图(Probabilis
9、ticoad Map，PM)算法12 等，该类算法的优势在于无需在规划前对节点扩展进行处理，只需给出规划空间就能够对其进行快速有效地搜索，其不足之处在于计算量较大、难以生成最优航迹等。多无人机航迹规划问题是对单体无人机航迹规划的一种扩展，其进一步考虑了无人机之间的位置约束、协同避障13等问题。针对无人机编队中的航迹规划问题，文献 14提出了面向时间协同的多无人机队形变换最优效率模型。该模型基于编队集结、编队保持、编队重构的不同特点，以队形变换的耗能与完成时间作为衡量指标，给出了具体队形变换下的最优效率计算式。文献 15 以快速扩展随机树算法为基础，提出一种多无人机编队重构方法，对93Elect
10、ronic Science and Technology王杨斌，等:基于队形变化的多无人机航迹规划算法https:/航迹进行节点去除与修正，实现了编队在复杂环境下的编队重构。文献 16 提出了一种时间协同优化算法，结合鸽群优化算法与时间协同优化算法，对无人机的飞行进行约束，使得无人机群实现空间协同与时间协同。总体而言，在多无人机航迹规划的研究中，确定最优航迹的方法较多，但同时考虑航迹规划与编队队形、求解多无人机在每一飞行阶段各自最合适位置的方法较少。为解决多无人机系统在复杂环境下的编队航迹规划问题，本文提出了一种基于队形变化的多无人机航迹规划算法。该算法由编队集结、领航者航迹规划、编队变化 3
11、 种策略组成。首先，在进行编队集结时，根据时间航迹最优模型实现最优编队。其次，使用改进的 Informed T*算法对领航者进行航迹规划。然后，定义多无人机系统之间的领航 跟随拓扑结构与预设队形，结合领航者航迹与障碍物位置信息对跟随者进行航迹规划，解决多无人机之间的协同避障问题。最后对算法进行仿真实验，在定义了队形变化量、路径长度比、航向稳定性性能指标的基础上对航迹进行评价。仿真结果表明，该算法能够规划出一组多无人机航迹，且能够实现航迹渐近最优以及避障功能。1多无人机航迹规划基本定义1 1无人机基本定义本文以领航 跟随法为基础，设计无人机的行为。领航者承担编队的导航和航迹规划任务，所有无人机共
12、同承担队形的灵活变动任务。无人机群以=i|i=1，2，n 表示，选其中一个无人机作为领航者 L，其余无人机作为跟随者Fi。为使领航者和跟随者形成期望的编队队形，以领航者为核心生成跟随者的期望位置 e，Fi与 e的连线方向就是跟随者的前进方向。通过设置对Fi的合理控制策略，可以使 Fi运动到 e的位置。运用该模型可以将任意的无人机运动问题转换为 Fi与 e之间的跟踪问题。在实际情况中，通常将无人机队形以二维平面的方式表现，将立体队形简化为平面队形变化问题。在平面队形的研究中，领航者的坐标为 L=(x0，y0)，跟随者的坐标为Fi=(xi，yi)|i=1，2，n。对于队伍的具体参数定义如下:1)确
13、定领导者位置 L=(x0，y0);2)计算领导者 L与跟随者 Fi的距离 di为di=Fi L=xi x()02+yi y()02(1)3)计算 L与 Fi的连线和 x 轴的夹角 i，可得到跟随者 Fi的位置如式(2)所示。xi=x0+dicosiyi=y0+dicosi(2)1 2防撞定义无人机的碰撞问题主要分为两类:1)无人机内部碰撞问题。通常对该问题的处理方式是在无人机周围设置保护区，无人机的位置信息以(x，y，t)表示，其中(x，y)表示无人机保护区的圆心，t表示保护区的半径;2)无人机与周围障碍物碰撞的问题。将不规则的障碍物以多个障碍物圆进行替换，以(x，y，k)的格式表示，(x，y
14、)表示障碍物圆心，k表示障碍物圆的半径。为确保无人机飞行的安全性，任意无人机或者障碍物之间的相对距离为 l。对于编队而言，保证无人机的保护区不受侵犯，即可实现防碰撞。综合以上可将约束条件设置为式(3)所示。lij()t=xi(t)xj(t()2+yi(t)yj(t()2lij()t ti+tj，iji，j 0，1，Nlij()t ti+k，i 0，1，N，k 0，1，M(3)1 3队形定义为表示领航者与跟随者之间的相互关系和队形的形状参数，本文在文献 17的基础上，定义队形参数信息矩阵通式如下Fd=12j1110d2dj02j4n(4)定义后可得到跟随者 Fi的位置为Fd=Fs1Fs2Fsn4
15、n(5)Fsj=f1jf2jf3jf4jT，j 1，n;f1j=j，f2j=i，f3j=ldij，f4j=dij(6)式中，Fd表示队形形状的参数信息矩阵，其成员 Fsj表示第 j 个无人机的队形信息，由4 部分组成;f1 j表示跟随者编号;f2 j表示该跟随者在当前队形中跟踪的领导者的无人机编号;f3 j表示该无人机与其领导者需要保持的期望距离;f4 j表示该无人机与其领航者保持的期望方位角。将编号为 1 的无人机设置为队伍领导者，有Fs1=1100T。2多无人机航迹规划策略针对无人机编队在规划航迹的问题，本文提出包括编队集结、航迹规划、编队队形变化 3 种方法。编队集结指的是机群按照一定的
16、队形形成固定编队。航迹04王杨斌，等:基于队形变化的多无人机航迹规划算法Electronic Science and Technologyhttps:/规划是指根据算法在复杂环境中选择满足约束的最优路径。编队队形变化是指在无人机执行任务过程中，发生突变状况导致原定的航迹不能满足飞行需求，需要改变原有的编队队形。在进行编队重构的过程中，每一架无人机需要重新制定其在编队中的位置，重新规划飞行航迹，并且航迹需满足无人机的运动学、动力学特征和避障等约束条件。2 1无人机编队集结编队集结能够控制无人机形成预设的编队。本文已知所有无人机的初始位置以及预设队形，编队集结飞行速度固定，且忽略风向对无人机的影响。选择合适的无人机集结位置可显著提升编队集结效率。影响编队集结效率的因素主要包括飞行路程长度和飞行时间，选择合适的集结位置点能减少集结时间与节省耗能，因此本文提出了加权时间路程最优模型。该模型已知所有无人机的初始位置 =(xi，yi)|i=1，2，n。根据实际任务需求设置时间和路程两者之间的权重，确定最优的无人机编队的最优集结点为 e=(xei，yei)|i=1，2，n。路程最优模型计算式如下si
