当前,无人技术蓬勃发展[1-3],无人机等无人装备广泛应用于现代战场,改变了传统作战模式。为充分发挥无人机集群在现代战场的使用效能,研究人员需要对无人机集群指挥控制进行研究。任务规划作为无人机集群指挥控制的关键技术,其目标是在满足任务约束的条件下,为每架无人机分配任务、规划航线,使得任务效能达到最大。无人机集群任务规划可以被解耦为任务分配和航迹规划两个子问题。
任务分配是任务规划的首要环节,根据预先收集的有限战场信息和预设任务分配算法将任务进行分解,得到一组满足任务约束、最大化任务效能的任务子集。对此,国内外学者开展了大量研究。MANYAM等[4]将空地协同路由问题建模为混合整数线性规划模型,并开发了一种分支切割算法求解最优分配方案;漆海霞等[5]针对植保无人机处方变量作业任务分配问题,提出了一种融入学习因子和贪婪均值思想的改进蛛蜂算法;张彪等[6]对传统遗传算法进行改进解决了人工林区无人机巡检任务规划问题。然而上述研究着眼于单一无人机的应用场景,难以直接应用于多无人机协同任务分配问题。为了进一步推动无人机集群任务适应能力,优化无人机集群的任务分配算法,WU等[7]将任务分配转化为组合优化问题,提出了一种遗传/模拟退火融合算法,通过部署多个无人机编队来执行不同的任务;赵得霖等[8]采用谱聚类的方法将任务节点转换到谱空间,提出分支定界和模拟退火相结合的算法进行多无人机任务分配。这些算法虽然能解决协同任务分配问题,但直接将航迹规划的结果作为任务分配算法的输入,忽略了任务分配和航迹规划之间的耦合关系,难以实现最大化的任务效能。为此,ZHANG等[9]提出了一种分布式编队结构下基于时间窗机制的多无人机任务规划算法,构建了以最小任务执行成本和路径规划成本为优化目标的无人机编队任务规划模型。但该方法直接将任务节点间的欧氏距离作为航迹代价,没有考虑限制区域的影响,且深度强化学习的方法对于训练分布外的实例难以取得较好的效果;YAO等[10]则运用A*算法对航迹代价进行估计,将估计结果作为任务分配的输入。但A*算法难以处理非结构化环境上的路径规划问题。此外,航迹预估阶段的引入也显著增加了算法求解时间。
航迹规划是任务规划的后续环节,根据任务分配结果和无人机周围环境信息采样生成一条高质量的航迹。在航迹规划算法研究领域,SHAO等[11]提出了一种综合改进粒子群算法解决了无人机三维航迹自动生成问题;WU等[12]考虑了无人机的物理约束,提出了一种改进的快速收敛人工蜂群算法生成预期航迹,并采用ε-Boltzmann选择策略跳出局部最优;CHEN等[13]将空地协同无人机航迹规划问题解耦,提出了一种蚁群算法和遗传算法相结合的两阶段策略改进算法。这些基于群智能的算法能够生成高质量的航迹,但这种优化求解的方法通常需要感知全局信息,且时间复杂度较高,难以实现全局最优。针对这些问题,基于采样的RRT*算法[14]被广泛应用于航迹规划中。QI等[15]将RRT*算法生成的初始路径保存为状态树作为先验知识,设计了一种向后扩展策略,解决了RRT*算法探索随机导致效率低的问题;ZHANG等[16]将RRT*与机会约束策略相结合,引入了一个目标函数来平衡路径长度和风险,提升了RRT*算法在狭窄通道的通行能力,并证明了算法的渐进最优性;WANG等[17]针对RRT*算法规划航迹质量不高的问题,提出了一种基于圆弧圆角法的路径平滑策略,有效缩短了航迹长度;HUANG[18]结合人工势场法在RRT*算法基础上增加引力和排斥分量,加快了搜索过程,减少了航迹的随机性。尽管上述改进显著提升了RRT*算法的性能,但在应用于无人机航迹规划时,仍需充分考虑无人机动力学约束和实际避障需求,以生成安全可行的最优航迹。
本文将无人机集群搜索任务规划分解为任务分配和航迹规划两个子问题。针对任务分配问题,将多目标任务分配建模为带容量约束的多旅行商问题,设计一种改进孤雌遗传算法以实现高效求解。随后,在任务分配结果的基础上,针对航迹规划问题,设计一种融合折半圆形采样策略与人工势场法的改进RRT*算法,并进一步采用切线圆弧过渡法对航迹进行平滑优化,生成高质量航迹。
1 问题描述与模型建立
1.1 问题描述
搜索任务区域内存在多架无人机,该无人机集群执行任务区域内针对多目标的搜索任务。各无人机从相同起点出发,完成任务后抵达同一终点。任务区域内存在多个任务目标,已知各任务目标大致位置与目标搜索时长(任务执行时长)。在任务规划过程中,需根据无人机起点、终点、任务目标分布、任务约束条件、限制区域信息, 规划获得各无人机执行任务的航迹,使得任务执行效率最高,任务场景如图1所示。
本文将搜索任务规划问题分解为两个阶段:第一阶段,任务分配。首先,根据任务目标区域和限制区域已知信息计算任务区域之间的闵可夫斯基距离,并据此生成初始种群;其次,计算种群中个体的适应度函数,采用轮盘赌和精英选择的方式筛选得到父代种群。而后,对父代种群进行变异操作得到后代种群;最后,判断是否满足终止条件,是则输出适应度最佳个体和任务分配方案,否则重复筛选和变异操作。第二阶段,航迹规划。各无人机根据阶段一得到的分配方案确定起点和终点位置;首先,根据折半圆形采样策略对无人机附近空间进行采样。其次,根据采样信息和人工势场法扩展得到不发生碰撞、距离终点最近的下一节点;再次,采用切线圆弧过渡法对航迹进行优化;最后,重复上述采样、扩展和优化操作直至到达终点。算法结构如图2所示。
1.2 任务分配模型
假设无人机集群同时从同一起点起飞,以相同的巡航速度vC飞行。无人机集群U= 有N架无人机,另有M个任务目标区域Q= 。无人机对各任务目标区域搜索所需时间代价为T= 。搜索任务从无人机集群起飞开始,至所有无人机到达终点结束。任务目标是对所有目标区域进行一次搜索且使整个任务完成时间最短。D= 为路程代价矩阵,其中前M行和列分别代表M个任务区域,M+1和M+2行和列分别代表起点和终点,其元素大小表示两者之间的路程代价。
1.2.1 任务评价指标
对于无人机ui,假设其被分配的任务序列为Mi= ,mi,k表示ui搜索的第k个目标区域的序号,数量为ni个。因此,无人机ui总路程Si可由下式计算:
$ S_{i}=d_{M+1, m_{i, 1}}+\sum_{k=1}^{n_{i}-1} d_{m_{i, k}, m_{i, k+1}}+d_{m_{i, n_{i}}, M+2}$
搜索任务分配的效能与任务完成时间有关,所有无人机同时从起点起飞,任务完成时间就是耗时最长无人机的任务执行时间。据此设计评价指标如下:
$ J_{1}=\max _{i \in\{1,2, \cdots, N\}}\left(\frac{S_{i}}{v_{C}}+\sum_{k=1}^{n_{i}} t_{m_{i, k}}\right)$
但上述指标只针对任务执行时间最长的无人机,仅对J1进行优化会导致任务时间较短的无人机没有得到最优分配方案。因此,将任务平均执行时间也作为评价指标:
$ J_{2}=\frac{1}{N} \sum_{i=1}^{N}\left(\frac{S_{i}}{v_{C}}+\sum_{k=1}^{n_{i}} t_{m_{i, k}}\right)$
1.2.2 约束条件
对于无人机集群搜索任务,建立如下约束:
(1)完备性约束:各无人机任务子序列的并集应覆盖所有目标区域。
$ \bigcup_{i=1}^{N} M_{i}=\{1,2, \cdots, M\}$
(2)任务总数约束:各无人机任务数量之和等于目标区域数量。
$ \sum_{i=1}^{N} n_{i}=M$
(3)滞空时间约束:假设无人机最大滞空时间为Tmax,各无人机执行任务时长不能超过Tmax。
$ J_{1} \leqslant T_{\max }$
综上,令w为权重变量,取值范围为[0,1],无人机集群搜索任务分配模型为
$ \begin{array}{c}\min J=w J_{1}+(1-w) J_{2} \\\text { s.t. }(4)-(6)\end{array}$
1.3 航迹规划模型
假设在任务区域中存在P个限制区域O= ,无人机通过预先收集的战场信息和机载传感器获取限制区域信息,并对其进行规避生成航迹。记无人机位置向量为p=[x,y]T,航向角为θ,可以建立如下离散的无人机动力学模型:
$ \left[\begin{array}{c}x_{i+1} \\y_{i+1} \\\theta_{i+1}\end{array}\right]=\left[\begin{array}{c}v_{C} \Delta t \cdot \cos \theta_{i} \\v_{C} \Delta t \cdot \sin \theta_{i} \\\Delta \theta_{i}\end{array}\right]+\left[\begin{array}{c}x_{i} \\y_{i} \\\theta_{i}\end{array}\right]$
其中,Δt为时间步长,Δθi为时刻i转弯角。记无人机航迹点序列为P= ,其中,L为航迹点数量。则航迹规划问题可以建立为如下模型:
$ \begin{array}{l}\min Q=\sum_{i=1}^{L-1}\left\|p_{i+1}-p_{i}\right\| \\\text { s.t. }\left\{\begin{array}{l}\underset{1 \leqslant i \leqslant L-1}{\forall} \overrightarrow{p_{i} p_{i+1}} \cap o_{j}=\varnothing \\p_{1}=p_{S}, p_{L}=p_{T} \\\forall \underset{1 \leqslant i \leqslant L}{\forall} \frac{v_{C}^{2}}{g \tan \Delta \theta_{i}} \geqslant R_{\min }\end{array}\right.\end{array}$
其中,pS,pT分别为起点、终点坐标,Rmin为无人机最小转弯半径。
2 改进孤雌遗传任务分配算法
由于遗传算法的交叉操作在解决多旅行商问题时会产生大量违反约束的个体,因此本文在PGA算法文献[19]基础上,放弃了染色体交叉步骤,采用自适应变异概率,提升算法的全局搜索能力和收敛性能。
2.1 不完全信息下的路程代价估计
两个区域之间的路程代价通常可以用中心点的欧几里得距离来估计;但当区域间被障碍物遮挡时,则需改用曼哈顿距离。如图3所示,虚线表示欧氏路径,实线为两条等价的曼哈顿路径,两者大小相等。显然,若两点之间可达,那么两者之间曼哈顿路径必定存在。曼哈顿距离大小通过下式计算:
显然采用曼哈顿距离估计路程代价并不准确,在障碍物比较稀疏的环境中对路程估计得过大。闵可夫斯基距离将欧氏距离和曼哈顿距离统一为一个公式,对于二维空间,其表达式如下:
$d_{i j}=\sqrt[\varepsilon]{\left|x_{i}-x_{j}\right|^{\varepsilon}+\left|y_{i}-y_{j}\right|^{\varepsilon}}$
ε为距离参数,式(11)当ε=1就是曼哈顿距离,ε=2时为欧氏距离。据此,本文设计了一个自适应参数ε,在障碍物密集时ε→1,稀疏时ε→2。ε表达式如下:
$\varepsilon=1+e^{-\frac{M}{P} N_{O}}$
障碍物密集程度由起点和终点为顶点的矩形区域内包含的限制区域数量No量化,设定阈值Nth。若No≥Nth,则认为该路径规划环境障碍物密集,取ε→1;若No<Nth,则认为障碍物稀疏,取ε→2。
2.2 基因编码
基因编码是遗传算法的关键,它将问题从解空间转换为编码空间。本文采用序列编码的方式,为每个任务区域预先设置唯一的编号,将基因表示为一组序列。如图4所示,每个基因包括任务序列基因片和分割点基因片。任务序列基因片长度等于任务区域数量,分割点基因片数量等于无人机数量减1,起点终点未在基因中体现。图4为7个任务目标和3架无人机的基因编码,2个分割点将7个任务目标分为3个部分,分别对应3架无人机的任务执行子序列。对该基因编码信息描述如下:无人机u1从起点出发,依次对q7,q4进行搜索,最后到达终点。无人机u2从起点出发,依次对q6,q2,q5进行搜索,最后到达终点。无人机u3从起点出发,依次对q1,q3进行搜索,最后到达终点。显然,序列编码的方式确保了所有目标区域都能被无人机搜索到,并且每个区域仅被搜索1次。
2.3 适应度函数
在上文设计的评价指标的基础上增加违反约束惩罚。由于在上述基因编码下约束(4)(5)总能被满足,对于违反式 (6)约束的个体增加惩罚项Penalty。因此适应度函数设计如下:
$F=J+Penalty$
其中,J为式(7)确定的评价指标,其路程代价矩阵由式(11)计算得出,Penalty为一大正数。在本问题下适应度值越小,个体对任务的适应程度越好。
2.4 选择
本文采用轮盘赌和精英选择的方式产生子代个体。每轮在当前种群Pop中选择适应度最小的个体作为精英,在剩余的个体中采用轮盘赌的方式选择部分个体和精英个体一起作为父代种群。设个体i适应度大小为Fi,被轮盘赌选中的概率为Pi,则Pi的表达式如下:
$P_{i}=\frac{F_{i}}{\sum_{j \in P_{o p}} F_{j}}$
2.5 变异
变异操作用于改变父代种群基因产生子代种群。变异有利于种群的多样性,避免陷入局部最优。变异类型主要包括任务序列变异和分割点变异。任务序列变异用于改变各无人机执行的任务及顺序。主要方法是随机生成两个不同的小于任务数量的正整数i,j,不妨设i<j,包括以下4种基本操作，如图5所示。
(1)交换。将个体中i,j对应的任务序列号进行交换。
(2)反转。将个体从i到j片段进行反转。
(3)左移。将i到j片段依次向左移动,位置i对应的任务序列号放入位置j。
(4)右移。将i到j片段依次向右移动,位置j对应任务序列号放入位置i。
分割点变异的作用是改变各无人机执行的任务数量,进行集群任务负载分配。对于个体有一定的概率Pv发生分割点变异,若发生变异则根据无人机数量随机产生一组不相同的小于任务数量的正整数作为分割点。借鉴Damia等[20]设计的自适应遗传算法,对分割点变异概率Pv进行自适应调整,其表达式如下:
$P_{v}=k e^{-\frac{F_{\max }-F}{F_{\mathrm{avg}}-F_{\min }} \cdot \frac{g}{G}}$
其中,F、Fmin、Fmax、Favg分别为变异个体的适应度值、当前种群适应度最小值、最大值和平均值,g,G分别为当前迭代轮次和算法的最大迭代轮次,其中,k为[0,1]上的实数,用于调节自适应变异概率的数值范围。在同一迭代轮次内,适应度值越大变异概率越高,而在整个算法的运行过程中,变异概率随迭代轮次的增加而减小。算法前期变异概率主要受迭代轮次影响,算法后期变异概率主要受个体适应度值影响。这种自适应调整变异概率的机制,既在算法前期保证了对解空间的有效探索,又在算法后期保护了优秀个体,提高了算法的求解效率。
每个父代个体经过变异将得到以下9个子代:
(a)父代进行交换变异操作得到的子代。
(b)父代进行反转变异操作得到的子代。
(c)父代进行左移变异操作得到的子代。
(d)父代进行右移变异操作得到的子代。
(e)父代进行分割点变异操作得到的子代。
(f)父代同时进行(a)(e)操作得到的子代。
(g)父代同时进行(b)(e)操作得到的子代。
(h)父代同时进行(c)(e)操作得到的子代。
(i)父代同时进行(d)(e)操作得到的子代。
3 改进RRT*航迹规划算法
各无人机在得到任务序列后进入航迹规划阶段,根据序列进行任务点之间的航迹规划。
3.1 折半圆形采样策略
本文对RRT*算法采样偏置策略进行改进,传统RRT*算法为了绕开限制区域在周围空间进行随机采样,虽然这种方式可以实现绕行效果,但容易偏离目标点进行无效空间探索。由于在扩展时使用人工势场法实现限制区域绕行,因此采用折半圆形采样策略采样。如图6所示,连接目标点qgoal和当前RRT*树中距离qgoal最近的节点qnearest,以qgoal为圆心 长度d的一半为半径做出采样圆(图6中红色虚线圆)。在采样圆中随机采样得到qrand,沿 方向以当前采样步长采样得到qnew。显然,采样点qnew分布在以最大采样步长为半径的扇形区域内(图6中绿色虚线扇形),并且由于折半采样圆的特性,采样点qnew的分布概率以 中心向扇形区域的两边依次降低。折半圆形采样策略平衡了对采样空间的探索和利用,使采样方向更偏向目标方向,避免过于随机,减少了无效探索,同时保持一定的多样性。
3.2 人工势场法改进节点扩展
人工势场法是一种局部路径规划的算法,其主要思想是假设无人机处在一个充斥着人工势场的空间,目标节点周围存在引力场,而限制区域周围存在斥力场,无人机在这两者共同的作用下移动。由于折半圆形采样策略能够保证无人机朝着目标节点运动,因此本文不考虑引力场的作用,将人工势场法中斥力场的概念引入节点扩展,以引导局部随机扩展树向远离限制区域的方向生长。
如图7所示,qnew为采样得到的节点,Frep表示斥力场对无人机的作用,qnew'根据Frep和 矢量合成得到,Frep数学表达式如下:
$F_{\text {rep }}=\left\{\begin{array}{ll}0 & r>r_{0} \\C_{\text {rep }} \rho\left(\frac{1}{r}-\frac{1}{r_{o}}\right) \frac{\overrightarrow{q_{\text {obs }} q_{\text {nearest }}}}{r^{3}} & r \leqslant r_{0}\end{array}\right.$
其中,Crep为斥力增益系数,ρ为当前采样步长,r0为限制区域影响范围,qobs为限制区域中心点,r= 表示限制区域和qnearest节点的距离。
3.3 航迹优化
上述改进RRT*算法生成的航迹为离散点组成的折线,而无人机受动力学特性限制,无法瞬时改变方向或执行无限小的转弯。因此,本文需要对改进RRT*生成的初始航迹进行优化,使之满足式(9)中给出的无人机最小转弯半径约束。
本文借鉴Dubins曲线的路径构造理论,针对无人机航迹平滑优化问题,提出一种基于切线圆弧过渡的轨迹优化方法。该方法通过几何约束建模,将初始折线航迹中的航向突变节点替换为满足最小转弯半径的相切圆弧段,并辅以直线过渡连接,实现曲率连续的可飞行轨迹生成。研究人员仅需解析几何运算即可生成曲率连续的可飞行轨迹,其计算复杂度显著低于Dubins曲线的组合优化和3次B样条曲线的参数迭代过程。如图8所示,黑色实线为初始航迹,红色虚线圆是以最小转弯半径大小构建的过渡圆,黑色虚线为折线夹角的角平分线,红色实线部分为优化后的航迹。
4 仿真实验与分析
4.1 实验设置
表1 无人机属性Tab.1 UAV properties |
| 参数 | 数值 |
|---|---|
| 起点坐标/(m,m) | (20,20) |
| 终点坐标/(m,m) | (980,980) |
| 飞行速度vC/m·s-1 | 10 |
| 最大滞空时间Tmax/s | 1 000 |
| 最小转弯半径Rmin/m | 10 |
表2 任务区域属性Tab.2 Task area properties |
| 任务区域 | 位置坐标/ (m,m) | 区域大小/ [m,m] | 时间代价/s |
|---|---|---|---|
| q1 | (650,600) | [38,19] | 420 |
| q2 | (320,120) | [35,24] | 385 |
| q3 | (550,350) | [17,39] | 370 |
| q4 | (900,50) | [39,16] | 364 |
| q5 | (100,920) | [22,35] | 363 |
| q6 | (450,40) | [37,20] | 361 |
| q7 | (950,750) | [28,26] | 351 |
| q8 | (400,400) | [33,22] | 342 |
| q9 | (750,450) | [39,18] | 338 |
| q10 | (30,600) | [19,36] | 332 |
| q11 | (500,950) | [25,27] | 323 |
| q12 | (850,900) | [34,19] | 322 |
| q13 | (250,450) | [23,28] | 320 |
| q14 | (480,600) | [32,20] | 312 |
| q15 | (980,300) | [15,39] | 293 |
| q16 | (120,400) | [29,20] | 290 |
| q17 | (300,900) | [21,27] | 284 |
| q18 | (820,680) | [24,23] | 276 |
| q19 | (650,800) | [18,30] | 270 |
| q20 | (180,270) | [12,39] | 234 |
表3 限制区域属性Tab.3 Restricted region properties |
| 限制区域 | 位置坐标/(m,m) | 区域大小/[m,m] |
|---|---|---|
| o1 | (160,160) | [120,120] |
| o2 | (475,480) | [150,80] |
| o3 | (750,700) | [100,200] |
| o4 | (90,775) | [80,150] |
| o5 | (400,240) | [200,80] |
| o6 | (860,360) | [120,120] |
| o7 | (280,650) | [160,100] |
| o8 | (500,810) | [120,120] |
| o9 | (645,145) | [90,90] |
4.2 实验结果
根据上文设置的场景,本文对MAPGA-IRRT*算法进行测试,不同数量无人机任务时间如图9所示。
若无人机执行任务时间超过Tmax,记其完成时间为其任务执行时间加上一极大惩罚值Penalty=10 000 s,表示任务未完成。由图9可知,当无人机数量为7时恰好集群能够完成搜索任务,此后随着无人机数量增加任务完成时间下降并不明显,而增加无人机数量将导致资源浪费。记此临界点无人机数量为最优配置。
4.3 算法对比实验
以各算法的最优无人机数量和4.1节设置参数作为MAPGA-IRRT*、IPGA、SBSP-SC-HO 3种算法的输入进行仿真测试,三种算法适应度值随迭代次数变化曲线如图11所示。三种算法适应度值最终大致趋于同一水平,而3种算法收敛速度快慢排序是MAPGA-IRRT* > SBSP-SC-HO > IPGA,分别在51,109,165轮次收敛。显然,本文所提算法在收敛速度上优于两种对比算法,较SBSP-SC-HO和IPGA两种对比算法收敛速度分别提升了53.2%和69.1%。
为了说明算法在任务目标数量变化情形下的有效性,本文设置任务目标数量分别为10、15、20、25、30、35、40,进行算法对比仿真实验,结果如图12所示,其中,柱状图表示对应目标区域数量下各算法求解得到的最优无人机配置,折线图表示对应的任务完成时间。3种算法最优无人机配置都随目标区域数量增加而增加。当目标数量为10、15、25、30、40时MAPGA-IRRT*算法的最优无人机配置少于2种对比算法,目标数量为20和35时,虽然最优配置相同,但MAPGA-IRRT*算法的任务完成时间更短。由此可知,与IPGA和SBSP-SC-HO算法相比,本文所提算法能够更有效地利用无人机资源,并且在相同的资源配置下任务耗时更短。
在任务目标数量变化的情况下,本文采用相同的任务分配方案,RRT*、APF-RRT*和MAPGA-IRRT*3种算法生成航迹总长度对比如图13所示。3种算法航迹总长度均随目标数量增加而增加。在目标数量较少时(少于25时)APF-RRT*算法航迹总长度小于RRT*算法,当目标数量超过25时,两种算法航迹总长度基本相当。而MAPGA-IRRT*算法航迹总长度始终小于其余两种算法。具体而言,相较于APF-RRT*算法航迹总长度平均减少了9.2%。
5 结束语
本文针对无人机集群协同搜索任务规划问题,提出一种分阶段协同规划方法,实现了高效任务分配和高质量航迹规划。结果表明,本文所提方法较对比算法任务分配速度提升53.2%,航迹总长度减少9.2%。
本文未来研究将聚焦强对抗环境下的动态重规划能力。研究基于多源感知融合的在线决策方法,实现新增威胁的实时响应与航迹重构,提升集群在突变环境中的任务完成效率。