控制与决策  2019, Vol. 34 Issue (6): 1169-1177  
0

引用本文 [复制中英文]

陈志旺, 夏顺, 李建雄, 宋娟, 彭勇. 基于定向A*算法的多无人机同时集结分步策略[J]. 控制与决策, 2019, 34(6): 1169-1177.
[复制中文]
CHEN Zhi-wang, XIA Shun, LI Jian-xiong, SONG Juan, PENG Yong. Serial strategy for rendezvous of multiple UAVS based on directional A* algorithm[J]. Control and Decision, 2019, 34(6): 1169-1177. DOI: 10.13195/j.kzyjc.2017.1636.
[复制英文]

基金项目

国家自然科学(61573305)

作者简介

陈志旺(1978-), 男, 副教授, 博士, 从事多旋翼飞行控制、目标跟踪等研究, E-mail:czwaaron@ysu.edu.cn;
夏顺(1995-), 男, 硕士生, 从事无人机路径规划、任务分配的研究, E-mail:xiashun9388@163.com;
李建雄(1981-), 男, 副教授, 博士, 从事连铸轧钢自动化技术与应用、优化控制等研究, E-mail:jxli@ysu.edu.cn;
宋娟(1978-), 女, 工程师, 从事无人机电力系统巡线的研究, E-mail:1138812341@qq.com;
彭勇(1963-), 男, 教授, 博士生导师, 从事电脑应用科学等研究, E-mail:PY81@sina.com

通讯作者

夏顺, E-mail: xiashun9388@163.com

文章历史

收稿日期:2017-12-03
修回日期:2018-07-13
基于定向A*算法的多无人机同时集结分步策略
陈志旺 1,2, 夏顺 1, 李建雄 1,2, 宋娟 3, 彭勇 4     
1. 燕山大学 工业计算机控制工程河北省重点实验室,河北 秦皇岛 066004;
2. 燕山大学 国家冷轧板带装备及工艺工程技术研究中心,河北 秦皇岛 066004;
3. 国网黑龙江省电力有限公司 佳木斯供电公司,黑龙江 佳木斯 154002;
4. 燕山大学 电气工程学院,河北 秦皇岛 066004
摘要:设计一种基于定向A*算法的多无人机同时集结分步策略.首先, 提出一种定向A*算法, 将无人机最大俯仰角与偏航角作为A*算法搜索约束, 从而缩小节点扩展区域, 并通过循环寻优规避“死区”点, 进而产生平滑可飞的预规划航迹; 其次, 论述了补偿航程差的变步长多点搜索、三维盘旋机动、虚拟威胁等分步再规划算法, 使得多无人机同时集结于目标点附近.仿真结果表明, 所提出的算法能够有效完成多无人机同时集结任务.
关键词多无人机    航迹规划    A*算法    同时集结    
Serial strategy for rendezvous of multiple UAVS based on directional A* algorithm
CHEN Zhi-wang 1,2, XIA Shun 1, LI Jian-xiong 1,2, SONG Juan 3, PENG Yong 4     
1. Key Lab of Industrial Computer Control Engineering of Hebei Province, Yanshan University, Qinhuangdao 066004, China;
2. National Engineering Research Center for Equipment and Technology of Cold Strip Rolling, Yanshan University, Qinhuangdao 066004, China;
3. Jiamusi Electric Power Company, State Grid Heilongjiang Electric Power Co., Ltd, Jiamusi 154002, China;
4. School of Electrical Engineering, Yanshan University, Qinhuangdao 066004, China
Abstract: In this paper, a serial strategy based on the directional A* algorithm for multiple UAVs is proposed. Firstly, the directional A*algorithm is presented to create a smooth and feasible pre-planning route, in which the maximum pitch and yaw angles are used as search constraints of the A* algorithm to narrow expansion area of nodes, and the successive trial and error procedure is adopted to avoid "dead zones". Then, the serial re-planning algorithm is discussed to extend the path length for aggregating at the same time, which generally consists of three steps: variable step size and multiple nodes, three-dimensional circle maneuver and virtual threats. Finally, the effectiveness of the proposed algorithm is demonstrated using numerical simulation.
Keywords: multiple UAVs    path planning    A* algorithm    simutaneous arrival    
0 引言

无人机航迹规划为根据所执行任务需求, 按照一定规划算法, 生成满足飞行约束条件及性能指标的最佳飞行航迹.关于无人机航迹规划方法, 国内外学者已经展开大量研究并取得了丰硕的成果.其中代表性成果有: 1)群智能算法, 即通过模拟生物的群体行为解决问题, 如粒子群优化算法[1]、蚁群算法[2-3]等; 2)基于图论的方法, 典型的图论方法是Voronoi图[4]方法, 将威胁源视为在平面上有区别的点, 按照最近原则划分平面, 以此规划航迹; 3)启发式搜索算法, 其中A*算法是经典的启发搜索算法之一.但A*算法由于其性能局限及计算负担较重, 在实际应用中并不能取得令人满意的结果.文献[5-6]针对A*算法易陷入“死区”问题, 分别提出局部回溯算法和节点安全性检测策略, 有效避了免搜索死区, 但对航迹平滑问题考虑不足.为此, 文献[7]在对节点扩展时进行了角度约束, 从而有效解决了航迹平滑问题.而文献[8]改进了A*算法评价函数并与人工势场法结合, 将其应用于旋翼无人机, 更进一步平滑了可飞航迹.

多架无人机(UAVs)协同航迹规划[9-10]是多无人机系统在未来战场中的主要应用.多无人机在执行协同任务时常常需要同时到达某个或多个目标点, 例如空中加油、协同侦查、火力覆盖等问题.当所有无人机的目标相同时, 同时到达也称为同时集结[11].多无人机同时集结问题的实现方式一般有两种[12]:一是速度控制, 即保持规划的航迹基本不变, 通过实时调节飞行速度同时集结于目标点; 二是航迹控制, 即保持无人机飞行速度基本不变, 通过调节航迹长度完成同时集结任务.在速度控制方面, 袁利平等[11]提出了一种基于一致性算法的分散化控制策略, 并成功实现了多无人机同时到达.关旭宁等[13]使用Laguerre图法进行航迹规划, 并提出一种速度闭环控制方法处理时序到达问题. Manathara等[14]指出速度控制容易造成速度饱和, 无法完成同时到达任务, 故该问题可转化为无人机最大飞行速度下航迹长度控制问题.在航迹控制问题上, Owen等[15]基于Dubins路径规划方法, 提出了基于向量场的三维会合航路规划算法.肖自兵等[16]提出一种改进A*算法, 通过改进算法搜索步长, 实现多机协同航迹规划, 但面对威胁较少情况时, 该算法无法完成搜索任务.孙小雷等[12]针对多无人机交会过程通过修改Dubins路径补偿无人机航程差实现航迹控制, 但对三维威胁情况考虑不足, 且仿真无人机数量较少. Lim等[17]则以目标为中心, 使远航程无人机实行盘旋等待, 进而实现协同攻击, 但该算法使无人机在目标附近暴露时间过长, 大大降低了无人机的安全存活概率.

本文主要研究多无人机同时集结的航迹规划问题.首先, 考虑到无人机物理运动约束, 提出一种定向A*搜索算法, 在缩小搜索区域、提高搜索效率的同时, 能够克服航迹不平滑问题.针对算法容易陷入“死区”问题, 提出了循环寻优求解方法, 实现单机航迹规划.其次, 多机执行同时集结任务时, 以最长无人机航迹作为目标航迹, 通过比较各无人机航程与目标航程的大小, 对短航程无人机设计了变步长多点搜索、三维初始盘旋机动、虚拟威胁航迹微整的多步控制方案, 保证与目标航程保持在允许误差范围, 实现多无人机同时集结.

1 多无人机同时集结问题

在多无人机规划航迹的初始阶段, 指挥所无法预料无人机某个时间点的飞行状态, 也无法考虑不确定性外界因素.较为详细的航迹规划策略往往不能处理实际集结任务, 而较为粗略的规划方法可以为决策初期提供规划方向, 故对某些因素可以进行近似考虑, 如将无人机速度考虑为匀速飞行, 这对于航迹初始的宏观规划是合理的.当无人机速度一定时, 多无人机同时性到达问题可视为保证航程差在一定范围内的航迹控制问题.

假设某次任务区域中分布D个已知障碍威胁, 任务要求N架处于飞行状态的无人机同时集结于目标点T执行同时打击任务.为简化研究问题, 作出如下假设:

1) 无人机初始分布在不同起点;

2) 无人机具有相同的物理特性, 最大飞行速度固定, 且只考虑无人机质心运动方程.

不考虑无人机的形状大小, 将无人机视为三维空间中运动的质点.无人机的简化运动模型[18]如下:

(1)

其中: (xi, yi, zi)为无人机的位置与高度, Vi为飞行速度, ϕiψi分别为无人机的俯仰角和偏航角.无人机执行任务时需主要满足如下约束.

1) 最大偏航角约束.

最大偏航角为无人机可飞航迹的最大转弯角度, 设航迹点坐标为(xi, yi, zi), 则每一航段向量pi=(xi-xi-1, yi-yi-1, zi-zi-1), 用ψmax表示最大偏航角, 应满足

(2)

2) 最大俯仰角约束.

最大俯仰角约束无人机进行爬升/俯冲的最大角度范围, 它是航迹在纵向上的约束.用ϕmax表示最大俯仰角, 应满足

(3)

3) 协同航程约束.

协同航程约束指各无人机间航迹长度(即航程大小)满足任务要求, 即

(4)

其中: PiPj分别为规划后无人机ij的航程值, ε为任务允许航程差值.

2 定向A*算法的航迹预规划 2.1 航迹规划评价函数

A*算法是一种经典的启发式搜索算法, 它在搜索过程中引入启发信息, 其评价函数为

(5)

其中: i为搜索过程中的任意节点, f(i)为从起点经过节点i到达目标点的最优路径代价, 又称为评价函数, 以下简称f; g(i)为在状态空间中从起点到达节点i的实际代价; h(i)为启发函数, 表示节点i到目标点最佳路径的估计代价.本文以当前节点到目标点的欧氏距离为启发函数, 记当前节点坐标为(xi, yi, zi), 目标点坐标为(xT, yT, zT), 则启发函数

(6)
2.2 定向A*算法

传统A*算法[16]中, 节点扩展方向无针对性, 考虑实际应用中的无人机俯仰角与偏航角约束, 结合无人机当前飞行方向, 为无人机的下一次到达位置进行角度约束(俯仰角ϕi, 偏航角ψi), 如图 1所示.即无人机每次的搜索区域是一个类锥体区域, 该区域为无人机当前姿态所有可能到达位置的集合.

图 1 三维定向搜索

定向搜索过程能够有效避免盲目搜索大量无用节点, 缩小无人机的搜索范围, 从而提高搜索效率.同时, 由于搜索过程满足航向角约束, 规划出的轨迹无需进行平滑处理, 即可得到满足约束的可飞航迹.

2.3 循环寻优求解

在传统A*算法中当航迹搜索点进入到凹形的障碍区域时, 会在凹形区域的小范围内反复徘徊, 形成航迹规划的局部“死区”[5], 其形成原因是当前位置的所有可扩展点都处于威胁区, 无法进行下一步搜索.针对该问题, 本文提出一种循环寻优求解方法, 该方法具体过程如下.

通过给定循环次数阀值, 并在定向A*算法中增加死区判断函数, 当循环次数大于循环阀值时, 检测死区点位置, 并触发循环寻优求解策略.策略基本思想是将“死区”点视为约束条件, 假设第i步搜索过程中陷入“死区”的航迹点为k, 可知点k是第i步搜索过程的最优评价函数点, 即该解为局部“死区”中的点, 因此该点是该次规划中的约束条件之一.将该点舍弃并放入威胁区集合(即加入A*算法中CLOSED表), 转而寻找次优解, 即求解

(7)

假设次优点为j, 若j点仍然为“死区”点, 则继续寻找其他节点.同时, 将j点放入威胁区域集合, 通过循环求解直到寻找到可行解, 跳出搜索“死区”, 该解即为可行解.

3 多机同时集结的航迹再规划

对于同时集结任务, 与二维机器人等规划路径时明显的区别之一在于无人机一旦离开基地后, 在返回基地之前将无法停止飞行.本文将此类情况纳入考虑之中, 为正在飞行的无人机规划飞行路线.航迹再规划分步策略均以定向A*算法为基础, 以最长航迹作为目标航迹, 分步补偿较短航程无人机航程.以下叙述均针对无人机s展开.

3.1 变步长多点搜索算法

在定向A*算法基础上, 通过调节算法的搜索步长与搜索点数量使之产生多条航迹.搜索步长定义为无人机保持飞行状态时两次搜索间隔之间的飞行距离.变步长多点搜索算法二维示意如图 2所示.

图 2 变步长多点搜索算法

图 2AB为无人机的初始航向, 从B点开始节点扩展. LL'表示定向A*算法的不同搜索步长, C1表示步长为L时原搜索数目点下, 下一步无人机可能到达的位置; C2表示步长L不变但增加搜索点个数后下一步无人机可能到达位置; C3表示步长L变为L'的原搜索数目点下, 下一步无人机可能到达的位置; C4表示步长改变为L'且增加搜索点个数后下一步无人机可能到达的位置.设B节点的位置信息为(xi, yi, zi), 结合无人机运动学方程, 由B点扩展的下一节点的位置为

(8)

ψiϕi可通过改变数值, 调整下一步搜索点的个数M, 可知下一节点位置与LM相关.对于步长L进行如下分析.

1) 面对同一个威胁, 不同步长所对应的避让轨迹不同.具体而言, L较小时, 搜索距离间隔较短, 搜索更为仔细, 但无人机更容易陷入上文所提到的威胁“死区”; L较大时, 往往在规避威胁时步数更少, 所得路径更为平滑, 但搜索较为粗略, 容易错过目标点, 导致任务失败.

2) 定向A*算法在空间建模时, 采用栅格化建模, L以栅格倍数为单位取值, 如L=3表示3倍栅格长度. 图 3表示无人机俯仰角为θ、偏航角取值为[-π/3, π/3]时的二维搜索示意图, M=3时实线箭头将搜索区域进行3等分, 其中箭头与表示步长的圆弧的交点称为搜索点, 用空心圆表示, 对于不在栅格交点的搜索点e1e2, 可以等效为扇形搜索范围内最近距离的栅格点e'1e'2, 以实心圆表示, 并称为“等效点”.这种等效方式称之为“就近等效”, 某一L值下所有等效点称为“可等效点”.同理, M=6时将搜索区域进行6等分, 以同样的方式寻找等效点.

图 3 “就近等效”示意图

搜索点个数M的取值决定搜索效果的全面或稀疏. M参数在定向A*算法中的实际意义可以做如下理解:在图 3中, 当L=1时, 令M=3, 可得3个实线箭头与L=1圆弧的交点, 即搜索点e1e2e3, 等效后得到3个等效点e'1e'2e'3; 若令M=6, 则可以得到6个搜索点, 但进行等效后, 仍然为3个等效点.这说明某些等效点被多个搜索点等效, 称这种情况为“重复等效”, 故M取值应以包含更多可等效点而不产生重复等效为原则进行选取.随着L的增大, M也必然随之增大才能使搜索更为全面而不产生重复搜索, 两者存在较弱的正向线性关系.实际算法实现过程中, 将参数LM作为外循环变量. 表 1给出了变步长多点搜索算法的算法步骤, 其中LstepMstep分别表示LM在循环过程中的变化步长.

表 1 变步长多点搜索过程

综上所述, 变步长多点搜索算法可以通过变量LM的不同取值, 得到航迹相异的多条航迹.无人机s通过变步长多点搜索算法产生再规划航迹集Zs{Ks1, Ks2, …, Ksm}, 从航迹集中选择与最长航迹长度差值最小的航迹作为当前规划航迹.

3.2 三维盘旋机动算法

面对威胁分布较少情况, 变步长多点搜索往往不能有效规划出多条航迹, 且受无人机机载雷达搜索半径的约束, 搜索步长的长度不能总是处于理想状态.因此, 需要继续对预规划航迹进行航迹调整.为保证无人机间的安全距离, 减少执行协同攻击任务时被发现的概率, 盘旋机动起点为无人机接到同时集结任务时的当前位置, 三维盘旋的航迹长度取决于盘旋半径.设无人机受物理约束的最小转弯半径为Rmin, 对于任意航程差, 短航迹无人机的盘旋半径

(9)

其中: PmaxPi分别为最长航迹长度和当前航迹长度, R的必要条件为RRmin.由于三维空间下无人机初始航向与目标点航向通常不共面, 无人机基于当前航向确定盘旋圆时, 圆心由以下方程确定[18]:

(10)

其中

(10)

根据盘旋圆心、起始点位置以及初始速度方向, 即可确定空间盘旋圆方程.对于无人机s, 由此获得修改后航迹集Z's{Kopt's}.三维盘旋机动算法至少需要延长2π Rmin的航迹长度, 盘旋后无人机将回到盘旋起点继续通过定向A*算法规划出的航迹向前飞行.在如下情况下, 三维盘旋算法不可用:

1) 待延长航迹小于2πRmin时;

2) 当前环境不允许时, 即盘旋圆心与最近威胁的直线距离仍小于最小盘旋半径时.

3.3 虚拟威胁算法

针对航迹长度差值小于最小盘旋圆周长且不满足任务要求的航迹, 在当前航迹Ksopt中虚拟出半径大小为Rx的威胁, 无人机在规划航迹时必须避让此威胁, 从而实现航迹的有效延长.定义虚拟球体威胁的球心H为虚拟中心, 设当前航迹上航迹点个数为q.设起点与目标点的连线中点坐标为(xb, yb, zb), 则H可表示为(xt*opt, yt*opt, zt*opt), 其中t*为下式中求得最优值时的t值:

(12)

而实际中往往由于所延长航迹不足而不能一次性满足任务要求.本文提出两种调整方法, 分别为调整Rx法和变动H法.

1) 调整法Rx是在确定一个虚拟中心后, 保持虚拟中心H坐标不变.即只有一个虚拟中心, 不断增大虚拟半径Rx的大小, 为避让该虚拟球形威胁, 无人机航程随着虚拟威胁球的膨胀而不断延长, 直到满足任务航程要求.该虚拟球应满足不接触其他无人机航迹以及威胁区域的约束, 设RxRxmax, 其中Rxmax为虚拟半径最大值, 即应满足约束条件

(13)

其中d(·)为两点间的欧氏距离, 可由式(6)计算.

2) 变动H法是确定虚拟中心H并得到新航迹后保持Rx一定, 在新航迹上根据式(12)重新确定虚拟中心, 并再次生成新航迹, 故虚拟威胁一次产生一个虚拟中心.以此类推, 直到新航迹满足任务要求时为止.通过虚拟威胁算法得到再规划航迹集Zs"{Ks1", Ksd2", …, Ksm"}, 从中选择满足任务要求的航迹作为无人机的最优规划航迹.

其他短航程无人机所使用的方法与无人机相同, 即由变步长多点算法和三维盘旋机动算法进行大幅度航迹调整, 由虚拟威胁算法进行小幅度长度航迹调整, 在尽量保证无人机安全的前提下完成任务. 3种算法依次分步执行, 在所有无人机最终再规划航迹集Z{Z1", Z2", …, ZN}中选取每架无人机最优规划航迹, 即为多无人机同时集结最终规划航迹.

4 算法步骤

总结前文算法流程, 无人机首先根据初始环境信息, 使用定向A*算法进行航迹预规划, 在不满足任务要求时, 在定向A*算法中, 依次加入并执行3种航迹调整方法, 形成航迹再规划算法, 通过航迹选择, 得到最终规划航迹.

4.1 航迹预规划定向A*算法流程

Step 1:获取环境信息, 将起始点插入OPEN表, 并将其作为当前节点, 将威胁点插入CLOSED列表.

Step 2:若当前节点为目标点, 则跳转到Step 5.

Step 3:根据无人机当前速度方向, 结合步长L和搜索点个数M, 将当前节点的类锥体区域内的所有节点作为可扩展点, 并计算其评价函数f.对于可扩展点, 若不在OPEN表和CLOSED表中, 则加入OPEN表, 并将其父节点指针指向当前节点.若已在OPEN表中, 则比较其评价函数值f与该节点在OPEN表中的原评价函数值f; 如果较小, 则记录新的f值并将其父节点指针指向当前节点; 如果该节点在CLOSED表中, 则跳过它继续扩展其他节点.

Step 4:从OPEN列表中选择最小评价函数f值的节点作为当前节点.若OPEN列表为空, 则将当前节点插入CLOSED列表, 将其父节点作为当前节点, 转至Step 2.若其父节点为起始点则跳转到搜索失败处理程序.

Step 5:程序结束, 从目标点开始向上回溯直到起始位置, 得到从起始到目标的最小代价路径.

4.2 航迹再规划算法流程

Step 1:按照定向A*算法进行航迹预规划, 获取各无人机航程信息.若满足任务要求, 则跳转到Step 6;否则, 以最大航程无人机航迹作为目标航迹, 令s =1, 跳转到Step 2.

Step 2:对第s架无人机根据表 1执行变步长多点搜索算法, 选择航程最接近目标航迹的航迹作为当前航迹.判断第s架无人机航程是否满足任务要求, 若是则转到Step 6, 若否转到Step 3.

Step 3:判断第s架无人机飞行起点周围环境, 若环境允许则执行三维盘旋机动算法, 判断第s架无人机航程是否满足任务要求, 若是则转到Step 6, 若否则转到Step 4.

Step 4:执行虚拟威胁算法, 选择最接近目标航程的航迹作为该机最终规划航迹.判断第s架无人机航程是否满足任务要求, 若是则转到Step 5, 若否则任务失败, 转至任务失败处理程序, 然后转到Step 5.

Step 5:判断全部无人机规划是否完成, 若是则转Step 6, 若否则令s=s+1并转到Step 2.

Step 6:任务结束.

5 仿真与分析

为验证本文算法的有效性, 分别对定向A*算法性能及同时集结分步策略进行仿真实验.实验在Matlab环境中进行, 环境设置为:任务区域65 km×65 km×30 km, 单位栅格表示长度为1 km, L表示单位栅格倍数.威胁数量D=6, 任务要求所有无人机选择合适的路径规避威胁, 保持航程差在[-1, 1]之间的范围同时集结于目标点.无人机的特征参数如表 2所示.

表 2 无人机特征参数
5.1 算法性能仿真

为验证定向A*算法搜索的有效性, 将本文提出的算法与文献[16]算法从航迹长度、规划航迹所用时间及OPEN栅格数目3个方面进行比较.设置UAV1飞行起点为(3, 4, 5), UAV2飞行起点为(60, 4, 5), 目标点为(35, 28, 25), 设置定向A*算法搜索参数L=2.5, M=3, 实验结果如图 4所示.

图 4 不同算法规划航迹比较

图 4(a)可以看出, 文献[16]算法规划航迹不够平滑, 规划时产生约束点(41, 12, 22), 该点导致实际飞行中无人机无法有效沿着规划航迹飞行.而定向A*算法通过角度约束则不存在这一问题, 但仍然存在图 4(b)中“死区”点(14, 14, 14).针对此问题, 算法通过循环寻优求解, 仍然能有效规划出可飞航迹, 且由于步长可变, 规划航迹更为平滑.

表 3为实验详细数据, 可以看出定向A*算法由于避免搜索大量无用节点, 使算法在OPEN表数目以及规划用时方面大大优于文献[16]算法, 且由于步长L=2.5相比于文献[16]算法逐格的搜索, 定向A*搜索时能以更少的航迹点直线距离向前扩展, 使得定向A*算法规划航程更短.

表 3 算法性能仿真结果
5.2 同时集结分步策略仿真

以4架无人机为例, 对不同起点的无人机进行同时集结仿真. 4架无人机初始数据如表 4所示.

表 4 无人机初始参数

对于4架无人机设置初始参数L=2.5, M=6, 目标点为(37, 28, 25).定向A*算法得到4条航迹如图 5所示, UAV1~UAV4四条航迹长度分别为52.279 km, 44.983 km, 52.961 km, 56.131 km, 不满足同时集结任务要求.现以最长航程UAV4作为目标航迹K4opt, 通过对另外3架无人机调整航迹, 使其航程保持在区间[55.131, 57.131]内, 即式(4)中ε=1.

图 5 预规划航迹
5.2.1 变步长多点搜索算法仿真

为验证参数L取值对算法规划航迹的影响, 并寻找较有代表性的L取值, 取参数M=6, 对多组不同的起始点与目标点进行变步长仿真实验. 图 6L=4时起始点(10, 12, 12)、目标点(30, 30, 25)的算法规划航迹.由图 6可知, 由于步长较大, 错过目标点后, 经过反复原地“转圈式”搜索才找到目标点, 这种情况称之为搜索失败.经过多次实验表明, 该环境下应设置Lmax=3最为合理.需要说明的是, 对于不同位置, 不同大小的威胁区域, L取值将会稍有误差.在实际应用中, 面对不同飞行环境, 应结合具体问题具体分析.

图 6 搜索失败案例

上述实验用以寻求较有代表性的L取值上界, 在L∈[1, 3]的取值范围下, 暂令Lstep=0.1、Mstep=1, M为整数.以UAV3作为示例, 通过对LM循环取值观察实验效果, 实验数据如表 5所示.

表 5 不同LM取值时航程值

表 5可以总结出4点结论: 1)在L取值较小时, 随着M变大产生了“重复等效”, 此时增大M不会产生正面收益, 只会产生更多的相等航程; 2)随着L取值的增大, 大多数情况下M变大能够产生更多相异的航程, “重复等效”情况得以好转, 体现了LM两者的正向线性关系, 即两者同步增大可使搜索更为全面; 3)在同一M值下, 当Lstep=0.1时存在较多不同L值下航程相等情况, 故Lstep取值不应过小, 由表 5可知Lstep=0.2时效果较好, 因此本节之后的实验中取值为0.2; 4)无论L取何值, M=7, 8时都存在与M=6时的较为严重的“重复等效”, 故在该环境下Mmax的取值应为6.面对不同环境情况, 结合具体问题依此方法具体分析.

图 7表 5中不同LM取值所得航迹图示, 可知无人机在避让威胁时, 步长与搜索点个数的差异能够产生不同的绕行方式, 进而产生不同航程的多条航迹, 形成规划航迹集.根据任务要求, 选择与UAV4航程最为接近的一组作为当前最优航迹.由表 5可知, 选择在步长L=3、搜索点个数M=3时航程为55.8 km的航迹为K3opt, 该机航迹规划完成.

图 7 变步长多点搜索算法
5.2.2 三维盘旋机动算法仿真

以UAV2作为示例, 首先执行变步长多点搜索算法, 这里不做重复论述, 对执行结果进行筛选, 得到UAV2当前最优航迹K2optL=2.8、M=6时的航迹, 其航程大小为45.152 km, 并不满足任务要求.经计算, UAV2最大可允许盘旋半径为7.920 km.通过式(9)得到其所需盘旋半径为1.748 km, 故三维盘旋机动方法可执行.由式(10)和(11)得盘旋中心坐标为(58.25, 4.00, 6.00), 对UAV执行三维盘旋机动算法后仿真如图 8所示.

图 8 三维盘旋机动算法

图 8可知, UAV2成功避开所有威胁, 到达目标点.经计算, 规划后航迹长度为56.131 km, 满足任务要求, UAV2航迹规划完成.

5.2.3 虚拟威胁算法仿真

对UAV1执行变步长搜索算法, 选择出UAV1航迹集中L=2.6、M=6时的航迹为当前最优航迹K1opt, 其航迹长度为52.279 km, 仍需要航迹调整.经式(9)判断, 其与K1opt航程差值不满足最小盘旋圆周长, 故三维盘旋机动算法不可行, 转而执行虚拟威胁算法. 图 9对两种虚拟威胁方法分别仿真, 其中图 9(a)为调整虚拟威胁半径仿真图, 图中虚拟中心为(18, 22, 22), 虚拟半径Rx=2.0 km, 航程为55.247 km, 故航程满足任务要求. 图 9(b)为3次变动H, 每次虚拟威胁半径Rx=1.0 km, 虚拟中心分别为(18, 22, 22), (20, 24, 23), (14, 18, 21).航程分别为53.601 km, 53.950 km, 55.750 km, 可知第3次虚威胁后航程同样满足任务要求, 至此UAV1航迹规划完成, 任务结束.

图 9 虚拟威胁算法仿真

4架无人机依次执行3种航迹调整算法, 通过不断调整航迹长度, 最终满足任务要求, 从而实现多无人机同时集结于目标点.最终航迹仿真如图 10所示.

图 10 虚拟威胁算法仿真
6 结论

本文针对多无人机同时集结问题提出了一种航迹规划方法.充分考虑无人机真实作战过程中的飞行器本体约束条件, 改进了A*算法并形成定向A*算法进行预规划航迹高效搜索, 当算法陷入“死区”时, 采用循环寻优寻找次优解的方法作出解决.根据实际同时集结的作战任务, 通过控制无人机航程进行航迹再规划, 包括变步长多点搜索、三维盘旋机动、虚拟威胁的3种再规划分步策略.仿真结果表明, 本文提出的搜索算法和分步策略具有有效性和可行性.对于动态威胁适用性有限, 如何应对动态威胁情形, 是本文今后需要深入研究的方向.}

参考文献
[1]
Wang Q, Zhang A, Qi L. Three-dimensional path planning for UAV based on improved PSO algorithm[C]. The 26th Chinese Control and Decision Conf. Changsha: IEEE, 2014: 3981-3985. http://cpfd.cnki.com.cn/Article/CPFDTOTAL-KZJC201405001753.htm
[2]
Tao J, Wang Y, Yang H, et al. Three-dimensional path planning of unmanned aerial vehicle under complicated environment[C]. The 26th Chinese Control and Decision Conf. Yinchuan: IEEE, 2016: 6377-6382. https://www.researchgate.net/publication/306113887_Three-dimensional_path_planning_of_unmanned_aerial_vehicle_under_complicated_environment
[3]
Mou C, Jian X, Jiang C S. Three dimensional path planning of UAV with improved ant algorithm[J]. J of Jilin University, 2008, 38(4): 991-995.
[4]
赵文婷, 彭俊毅. 基于VORONOI图的无人机航迹规划[J]. 系统仿真学报, 2006, 18(22): 159-162.
(Zhao W T, Peng J Y. VORONOI diagram-based path planning for UAVs[J]. J of System Simulation, 2006, 18(22): 159-162.)
[5]
张启瑞, 魏瑞轩, 何仁珂, 等. 城市密集不规则障碍空间无人机航路规划[J]. 控制理论与应用, 2015, 32(10): 1407-1413.
(Zhang Q R, Wei R X, He R K, et al. Path planning for unmanned aerial vehicle in urban space crowded with irregular obstacles[J]. Control Theory & Applications, 2015, 32(10): 1407-1413. DOI:10.7641/CTA.2015.50351)
[6]
谭雁英, 李洋, 周军, 等. 复杂环境下基于A*算法的无人机路径再规划[J]. 系统工程与电子技术, 2017, 39(6): 1268-1273.
(Tan Y Y, Li Y, Zhou J, et al. Path replanning approach for UAV based on A* algorithm in complex environment[J]. Systems Engineering and Electronics, 2017, 39(6): 1268-1273.)
[7]
Ren T, Zhou R, Xia J, et al. Three-dimensional path planning of UAV based on an improved A* algorithm[C]. Guidance, Navigation and Control Conf. Nanjing: IEEE, 2017: 140-145. https://ieeexplore.ieee.org/document/7828772
[8]
Tan J, Zhao L, Wang Y, et al. The 3D path planning based on A* algorithm and artificial potential field for the rotary-wing flying robot[C]. Int Conf on Intelligent Human-Machine Systems and Cybernetics. Hangzhou: IEEE, 2016: 5551-556. https://ieeexplore.ieee.org/document/7783899
[9]
程晓明, 曹东, 李春涛. 多无人机协同航迹规划技术研究[J]. 航空计算技术, 2014, 44(4): 71-75.
(Cheng X M, Cao D, Li C T. Cooperative Path Planning for multiple UAVs[J]. Aeronautical Computing Technique, 2014, 44(4): 71-75. DOI:10.3969/j.issn.1671-654X.2014.04.019)
[10]
Mclain T W, Beard R W. Coordination variables, coordination functions, and cooperative timing missions[J]. J of Guidance, Control, & Dynamics, 2005, 28(1): 150-161.
[11]
袁利平, 陈宗基, 周锐, 等. 多无人机同时到达的分散化控制方法[J]. 航空学报, 2010, 31(4): 797-805.
(Yuan L P, Chen Z J, Zhou R, et al. Decentralized control for simultaneous arrival of multiple UAVs[J]. Acta Aeronautica et Astronautica Sinica, 2010, 31(4): 797-805.)
[12]
孙小雷, 孟宇麟, 齐乃明, 等. 多无人机交会过程的协同航迹规划方法[J]. 机器人, 2015, 37(5): 621-627.
(Sun X L, Meng Y L, Qi N M, et al. Cooperative path planning for rendezvous of unmanned aerial vehicles[J]. Robot, 2015, 37(5): 621-627.)
[13]
关旭宁, 魏瑞轩, 郭庆, 等. 多无人机时序到达协同控制方法[J]. 电光与控制, 2014, 21(1): 18-22.
(Guan X N, Wei R X, Guo Q, et al. A Cooperative control method for tight sequencing arrival of multiple UAVs[J]. Electronics Optics & Control, 2014, 21(1): 18-22. DOI:10.3969/j.issn.1671-637X.2014.01.005)
[14]
Manathara J G, Ghose D. Rendezvous of multiple UAVs with collision avoidance using consensus[J]. J of Aerospace Engineering, 2012, 25(4): 480-489. DOI:10.1061/(ASCE)AS.1943-5525.0000145
[15]
Owen M, Nichols J, Colton M. Cooperative aerial tracking and rendezvous along time-optimal 3-dimensional curves[C]. AIAA Guidance, Navigation, and Control Conf. Portland, 2011: 1-14. https://www.researchgate.net/publication/258009987_Cooperative_Aerial_Tracking_and_Rendezvous_Along_Time-Optimal_3-Dimensional_Curves
[16]
肖自兵, 袁冬莉, 屈耀红. 基于A*定长搜索算法的多无人机协同航迹规划[J]. 飞行力学, 2012, 30(1): 92-96.
(Xiao Z B, Yuan D L, Qu Y H. Multi-UAVs cooperative path planning based on A* fixed length search algorithm[J]. Flight Dynamics, 2012, 30(1): 92-96.)
[17]
Lim S, Kim Y, Lee D, et al. Standoff target tracking using a vector field for multiple unmanned aircrafts[J]. J of Intelligent & Robotic Systems, 2013, 69(1/2/3/4): 347-360.
[18]
胡春鹤, 陈宗基. 多无人机空中加油的最优会合航路规划[J]. 控制理论与应用, 2015, 32(10): 1400-1406.
(Hu C H, Chen Z J. Optimal rendezvous path planning for multiple unmanned aerial vehicle on air refueling[J]. Control Theory & Applications, 2015, 32(10): 1400-1406. DOI:10.7641/CTA.2015.50433)