无人机多阶段航迹预测协同任务规划

齐 骥，王宇鹏，钟 志

(1.哈尔滨工程大学 自动化学院，哈尔滨 150001;2.哈尔滨工程大学 信息与通信工程学院，哈尔滨 150001)



无人机多阶段航迹预测协同任务规划

齐 骥1，王宇鹏1，钟 志2

(1.哈尔滨工程大学 自动化学院，哈尔滨 150001;2.哈尔滨工程大学 信息与通信工程学院，哈尔滨 150001)

针对多无人机(Unmanned Aerial Vehicles, UAVs)协同控制问题，提出了一种UAVs多阶段航迹预测分布式任务规划方法；定义从一次任务分配开始到其中一项任务完成为一个任务周期；在每个规划周期，首先，各UAV使用A*算法快速预测到所有任务目标的路径，提供至任务分配；然后，采用聚类算法修改目标价值向量，协商分配结果，并实时计算探测范围内的最短路径；最后，采用三次B样条曲线平滑所分配的最短路径，在线规划出满足飞行约束的飞行航迹；通过仿真实验对算法的有效性进行了验证，结果表明，提出的算法能够实时获得近似最优的任务分配结果并规划出可飞行航迹，并有效处理突发任务。

任务规划；多无人机；任务分配；航迹规划

0 引言

多无人机(unmanned aerial vehicles, UAVs)协同自主控制中，航迹规划与任务分配，一般作为任务规划的两个独立的层次开展研究。在公开文献中，学者们先后提出了最优控制法、图论法、人工势场法和人工智能等多种航迹规划方法[1]。为满足飞行约束，航迹规划进一步与航迹平滑的组合用于生成可飞行航迹[2]。

另一方面，任务分配技术经历了从以最优化方法或启发式方法为核心的集中式算法，到基于协商或市场机制等分布式算法[3]的发展。为实现全局最优分配，这些算法在规划开始后一次性计算出所有任务的分配结果，计算量过于集中，同时，在出现突发任务等应用场景变化时，需对整个任务分配进行重新计算。此外，任务分配的全局目标函数以任务航程为核心变量[4]，所以联合任务规划的航迹规划和任务分配两个层次进行整体研究具有更重要的理论和现实意义。

针对上述问题，相关学者进行了任务规划整体研究工作[5]，但一般只考虑了任务规划的某些方面，完整的研究应包括：分布式任务分配、考虑障碍规避的实时航迹规划和包含飞行约束的航迹平滑3个部分[6]。针对前人研究的局限性，本文针对物理特性一致的UAVs协同任务分配问题，提出了一种多阶段航迹预测(Multi-Stage Path Prediction, MSPP)分布式任务规划方法(Decentralized Mission Planning System, D-MPS)。

1 任务规划问题描述及系统建模

1.1 基本定义及假设

规定每个任务只由一架UAV执行，设UAVs应用于远程任务，高度变化对航程影响可线性近似。考虑N个UAV完成M个任务的任务规划问题，目的是：1) 实现任务分配，即UAVs与任务目标间的最优匹配；2) 规划出可飞行航迹。为了描述问题方便，本文中采用如下定义和假设：

定义1 (任务规划周期，Mission Planning Period)：从一次任务分配开始到其中一项任务被完成定义为一个任务周期.

假设1 (质心运动假设)：只考虑UAVs质心运动，忽略空气运动的影响；

假设2 (等速假设)：UAVs以相同的恒速飞行，控制量只改变其飞行方向；

假设3 (禁飞区假设)：采用凸多边形建模禁飞区[6]，模型间距离足够，即UAV具有足够的空间生成所需航迹。

1.2 UAV运动学方程

图1 UAVs航迹倾角和航向角定义

采用UAVn,n(N，表示第n架UAV，其中索引集合N= {1,…,N}。UAVn相对于地面坐标系Oxyz的航迹角θn和航向角φn的定义如图1所示，其运动学[7]方程为：

(1)

式中，(xn, yn, zn)为三维坐标；V为飞行速度；uθ和uφ分别为航迹倾角和航向角对应的控制量，如。记Sn= [xn, yn, zn, θn, φn]T为UAVn的状态向量，Un= [uθn, uφn]T为对应的控制量。

1.3 约束条件

记第m个任务为Taskm, m (M, M = {1,…, M}为目标索引集合。假设UAVn分配到Taskm，则在初始时刻为t0，对应UAVn的初始状态向量为：

(2)

在控制量Un,n∈N的作用下，UAVn终端约束为Taskm的位置(Xm, Ym, Zm)。

UAVn航迹倾角、航向角及相应的控制量应满足的机动性能约束为：

(3)

式中,uθmax为最大航迹倾角控制量；uφmax为最大航向角控制量；对应的最小转弯半径为：

(4)

1.4 任务分配模型

考虑目标价值时效性，Taskm对于UAVn的价值函数由奖励函数Gm和惩罚函数Jnm组成：

(5)

式中,gm为Taskm静态价值；εm为价值耗损系数；ωn为燃料消耗系数；性能约束Θnm= 1表示UAVn能够执行Taskm，否则为0。

任务分配的全局目标为：

(6)

式中，当hnm= 1表示UAVn获得Taskm，否则为0。

2 多阶段航迹预测任务规划算法

如图2所示，D-MPS系统包括MSPP和任务分配两个部分。而MSPP由3个阶段组成：

图2 任务规划系统整体架构

阶段1：UAVs将探测范围内的障碍多边形顶点实时添加至搜索空间，采用A*算法快速计算全部任务的估计路径，生成价值向量。

阶段2：利用聚类算法修改价值向量完成任务分配；UAV仍采用A*算法，实时更新探测范围内的最短路径；突发任务添加至下一规划周期。

阶段3：采用三次B样条曲线同步平滑上述最短路径，规划出满足飞行约束的平滑航迹。

2.1 路径估计

为快速计算至所有目标的估计航程，采用UAV当前位置临近区域内(或探测范围)的禁飞区多边形顶点建立A*算法的搜索空间。如图3所示，该时刻搜索空间为{B, B1, B2, B3, C, C1}。与利用单元分解等传统建模方法相比搜索空间维度大大减小。A*算法的性能指标函数为：

minF(d)=min[L(d)+H(d)]

(7)

式中，d为搜索点位置，L(d)为探测范围内实际路径；H(d)为至目标的启发式路径。图3所示的预测航迹结果为连接{A,B,C,T}的路径线段组合。

图3 A*算法路径估计过程

2.2 路径规划

路径规划需根据任务分配结果展开。UAVs基于估计路径计算全部任务的价值向量，采用聚类算法对价值向量进行修改。在聚类算法中，距离最近的两个任务归为一类，重复该过程，至类间距离达到给定上限。对于UAVn，若Taski与Taskj组成一类，则Taski的价值Rni修改为：

(8)

式中，γ为权重系数，pij为类间距离。

每架UAV首先选择自身任务列表中价值最高的任务，UAVn选择的任务为：

(9)

设竞争同一任务Taskk*的UAVs集合记为Μk*，价值最高的UAVn*获得相应任务，即：

(10)

重复上述过程，至消除所有分配冲突。

各UAV根据分配结果利用A*算法计算探测范围内的最短路径，并随飞行过程实时更新。

2.3 路径平滑

m次B样条曲线方程定义[7]为：

(11)

式中,0 ≤s≤ 1,Pi= (Xi,Yi,Zi),i= 0,…,b为选择的控制点；m阶基函数Bi,m(s)为：

(12)

三次B样条每段曲线由相邻4个控制点决定，在连接点处两阶导数连续，通过添加和修正控制点使B样条曲线满足UAVs机动性能约束和避障安全距离约束。图4(a)所示为控制点的选取。首先根据最短路径，将UAV位置A、目标位置T及转向点B确定为备选控制点。避障安全距离为Rs，威胁圆B以Rs为半径，其切线AB'与B'T交于点B'，则{A,B',T}为满足安全距离约束的控制点。为使曲线经过控制点A，增加与其共线距离接近的辅助控制点{A1,A2}，同理{B1,B2}、{C1,C2}分别为扩展辅助控制点。线段A1A2与AB'共线、线段C1C2与B'C共线，线段B1B2垂直于BB'。则满足安全距离约束的控制点序列为{A1,A,A2,B1,B',B2,C1,C,C2}。

图4 B样条控制点选取与曲率近似

初选控制点确定后，需验证其B样条曲线是否满足转弯半径约束。如图4(b)所示，连续3个控制点A、B、C所组成的三角形中，ai为边AC的长度，li为该边上的高，则由该三角形确定的该段曲线的极限曲率半径ri可近似[7]表达为：

(13)

曲线上点Zi为控制点B对应的极限曲率点。根据这种近似方式可以快速验证所选控制点是否满足转弯半径约束ri≥rmin。在不满足最小转弯半径约束时，采用“能量最优法”[8]调整辅助控制点使其满足约束要求。

3 仿真结果及分析

仿真实验中给出5架UAVs及13个任务的仿真场景。以CoreE5800 3.2GHzCPU，4G内存的DellPC为仿真实验环境。设飞行速度为200m/s，对应转弯半径为1.91km；探测范围为25km，避障安全距离为3km；航迹倾角和航向角取值范围分别为[-25°, 25°]和[-180°, 180°]，对应的控制约束分别为3°/s和6°/s。

图5 三维仿真结果

为了验证任务分配方法的有效性，随机选取UAVs与任务位置，重复多次仿真实验。本文采用可得到全局最优解的集中式任务分配结果作为仿真对比。以任务完成后的全局目标函数收益值作为评价标准，仿真结果如表1所示。其中实验1、4、5、6、7中，D-MPS均得到与集中式任务分配一致的最优结果，实验2、3、8也得到了较好的近似最优解。

表1 不同任务场景实验结果

表2 实验1任务分配结果

表3 仿真初值

表2给出实验1的分配结果，表3为对应的UAVs初始状态。在相同的仿真场景下，任务规划开始后50 s在位置(20, 30, 10)和(120, 65, 10)分别出现突发任务T1和T2，三维仿真结果如图5所示。对比后可以看出，为实现全局最优，UAVs在后续阶段分配进行了调整。UAV3将执行的任务由{Task12, Task2}调整为{Task12, T1}，Task2在第二阶段的任务规划中分配至UAV2。T2被分配至UAV5，其任务执行顺序由{Task8, Task6, Task4}调整为{Task8, T2, Task6, Task4}。

4 结论

本文提出了一种多阶段航迹预测算法，应用于包含任务分配和航迹规划的分布式实时任务规划中。航迹预测算法由3个阶段组成：基于A*算法的路径估计、任务分配后的路径规划以及基于三次B样条的航迹平滑算法。任务分配过程采用聚类算法修改任务价值函数。仿真结果表明算法能够逼近最优分配结果，并且分布式控制方式可有效处理突发任务目标，控制量满足约束，验证了规划航迹的可行性。

[1]Luca D F, Giorgio G, Fulvia B Q. A novel approach for trajectory tracking of UAVs[J]. Aircraft Engineering and Aerospace Technology, 2014, 86(3): 198-206.

[2]Sun T, Huo C, Tsai S, et al. Intelligent flight task algorithm for unmanned aerial vehicle[J]. Expert Systems with Applications. 2011, 38(8): 10036-10048.

[3]Ren W, Beard R W, Atkin E M. Information consensus in multivehicle cooperative control[J]. IEEE Control System Magazine, 2007, 27(2): 71-82.

[4]Choi H L, Brunet L, How, J P. Consensus-based decentralized auctions for robust task allocation[J]. IEEE Transactions on Robotics, 2009, 25(4): 912-926.

[5]Sahingoz O K. Generation of Bezier curve-based flyable trajectories for multi-UAV systems with parallel genetic algorithm[J]. Journal of Intelligent and Robotic Systems: Theory & Applications, 2014, 74: 499-511.

[6]Moon S, Oh E, Shim D H. An integral framework of task assignment and path planning for multiple unmanned aerial vehicles in dynamic environments[J]. Journal of Intelligent and Robotic Systems, 2013, 70(1-4): 303-314.

[7]Wang Y, Wang S, Tan M, et al. Real-time dynamic Dubins-helix method for 3-D trajectory smoothing[J]. IEEE Transactions on Control Systems Technology, 2015, 23(2): 730-736.

[8]Abbas A, Nasri A, Maekawa T. Generating B-spline curves with points, normals and curvature constraints: a constructive approach[J]. Visual Computer, 2010, 26: 823-829.

Multi-stage Path Prediction Mission Planning Algorithm for Multiple Unmanned Aerial Vehicles

Qi Ji1, Wang Yupeng1, Zhong Zhi2

(1.College of Automation, Harbin Engineering University, Harbin 150001, China;2.College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China)

In this paper, a multi-stage path prediction algorithm of the decentralized mission planning for cooperative UAVs is presented. The planning horizon is defined as the period between the start of task assignment and completion of any task. In every planning horizon, each UAV utilizes the A* algorithm to predict the paths to all tasks and provide the path distances for task assignment. Furthermore, the cluster algorithm is introduced to modify the tasks value vector. The UAVs negotiate the task assignment solution and calculate the shortest path to assigned task in the detection range in real time. Finally, the B-spline curve is addressed to convert the shortest path into flyable smoothing trajectory that subject to the flight constraints. For validation, the scenario of multiple UAVs to perform cooperative missions is considered. Numerical results show that the proposed algorithm can achieve the quasi-optimal assignment solution and generate the flyable trajectory in real time. In addition, the satisfactory performance to accomplish the pop-up tasks is demonstrated.

mission planning; unmanned aerial vehicles; task assignment; path planning

2015-12-08；

2015-12-29。

齐 骥(1995-)，男，黑龙江哈尔滨人，本科，主要从事智能算法与控制方向的研究。

钟 志(1976-)，男，湖南岳阳人，副教授，硕士生导师，主要从事通信、信号处理方向的研究。

1671-4598(2016)06-0189-03

10.16526/j.cnki.11-4762/tp.2016.06.052

V19

A