分布式协同动态任务规划的建模与一体化求解方法

崔乃刚，吴蔚楠，郭继峰

（哈尔滨工业大学 航天学院，哈尔滨 150001）

分布式协同动态任务规划的建模与一体化求解方法

崔乃刚，吴蔚楠，郭继峰

（哈尔滨工业大学 航天学院，哈尔滨 150001）

以多异构无人机执行侦查、打击、评估任务为背景，开展了协同任务规划问题建模、一体化求解算法设计。采用分布式规划框架及图论思想对问题进行建模，且将无人机避碰、燃油、任务执行次序作为约束条件，并充分考虑任务分配与路径规划存在的强耦合特性，采用禁忌/遗传算法，设计包含任务序列和路径位姿点的基因编码，将问题进行一体化求解。结果表明：算法能够适用于动态任务场景，且能够较为快速地解决任务空间较为复杂的规划问题。

异构无人机；一体化求解；协同任务规划；分布式决策；Dubins路径；禁忌/遗传混合算法

无人飞行器（后文均用 UAV表述）越来越多地被用来执行各种自主任务[1]，而这些任务的成功与否依赖于UAV的自主程度。根据Kendou[2]提出的无人飞行系统自主等级可知，当前相对成熟的是 UAV本体的自主控制、单机自主避障与路径规划等自主等级较低的技术，为了适应更为复杂的任务需求，需要采用多机协同替代单机执行任务，而协同任务规划技术是协同控制领域的关键技术。

协同任务规划问题是一个典型的组合优化问题，文献[3-8]均证明其为 NP（Non-deterministic polynomial）完全问题，故其求解难度较大。为了降低求解难度，通常将协同任务规划问题简化为协同任务分配和路径规划两个子问题，弱化或不考虑它们之间的耦合性，采用分层解耦的方法对它们进行分别求解[3,7,10-14]。这些解法的共同点为：将任务分配和路径规划分别求解，在任务分配求解时不考虑对象本身的运动学约束、环境障碍、威胁区约束，仅考虑任务本身的时序约束，任务间的相互影响关系等；路径规划将任务分配的结果作为其输入，寻找满足 UAV自身约束、障碍、威胁区、避碰等约束的平滑航迹。分层解耦方式降低了问题的求解难度，且能够适用于任务空间态势确定的离线任务规划问题。但是，实际的任务空间态势通常是时变且不确定的，而分层解耦方法的解算过程是异步的，由于任务分配过程的时间消耗，其运算结果并非响应当前的任务空间态势，从而带来的路径规划结果往往不能满足实际任务需求，且极有可能造成任务失效。所以，分层解耦求解方法的应用范围有限，且不能满足实际任务需求。

基于此，文献[5,15-18]对任务规划问题的一体化求解算法进行了研究。A. Richards[15]采用欧几里德线段集表示 UAV的路径规划结果，通过建立混合整数线性规划模型完成对协同任务规划问题的等效，最后采用一体化求解方法完成问题求解；Rasmussen[16]采用图论等效方法完成任务规划模型建立，并通过图搜索算法完成对相同 UAV协同任务规划问题的求解；Shima[5]采用集中式一体化任务规划求解方法，通过图论方法完成 UAV协同任务规划问题的等效，采用Dubins路径表示UAV飞行路径，最后通过遗传算法完成问题求解；Deng[17]在文献[5]的基础上，附加考虑了 UAV的弹药数量约束，通过改变遗传算法的基因编码方式，完成了问题的求解。以上文献均是基于集中式架构完成协同任务规划问题的建模与求解，将规划运算过程完全在地面站或某个 UAV上完成，而集中式架构普遍存在对通信链路依赖性较强、可靠性较差等缺点[7]，所以其实用性较差。Edison[18]提出了采用分布式一体化策略求解协同任务规划问题的思路，但是其并未实现。由协同任务规划一体化求解方法的研究现状可知，现有方法主要存在以下不足：

1）采用集中式架构，可靠性及规划更新速度较慢；

2）能够适应的任务场景较为简单；

3）考虑到的约束条件较少，不能反映真实任务场景。

鉴于现有的协同任务规划方法存在的普遍问题，基于文献[5][15-17]的研究成果，以异构 UAV协同执行侦查确定、打击、评估任务为背景，基于分布式规划策略，通过图论思想将协同任务规划问题进行描述，在考虑 UAV转弯半径约束、特性（包括载荷特性、巡航速度）约束、任务执行时序性约束、侦查范围约束、避碰约束等前提下，采用一体化求解方法，设计禁忌/遗传算法，完成协同任务规划问题求解。

1 协同任务规划问题建模

1.1 参数定义

以UAV协同执行侦查、打击、评估任务为背景，首先对涉及到的相关参数进行定义。

目标集与任务集：

UAV的异构性主要体现在两个方面：1）UAV的可执行的任务不一致；2）UAV的速度和极限转弯半径不一致。UAV可分为三类：1）作战UAV：可执行所有任务，用侦查UAV：可执行侦查和评估任务，用弹药 UAV：仅能执行打击透明目标任务，用

1.2 问题的数学描述

在给定一个包含Ntask个子任务的任务集和Nuav个可分配 UAV的情况下，任务规划的目标为：在满足任务自身约束和外部约束条件的前提下，寻求一种最优的分配方案，使系统的效用最大。该问题包含连续的规划路径以及离散的决策变量，是一个典型的组合优化问题。

不失一般性，任务规划问题可描述如下：

由式(2)可知，任务规划的可行解集由S×χ×Γ决定，但是由于协同任务存在多UAV多目标、UAV异构、UAV燃油约束、UAV避碰、任务间存在时间序列约束等因素，将会极大地增加问题解集的势，对问题的求解带来较大的难度。

1.3 问题的简化

本文采用图论的思想，将任务规划问题用有向图形式等效描述[5]，完成对问题的适当简化，并基于分布式规划架构，将任务决策和路径规划过程分布到各UAV上，完成对问题的分布式描述。

通过离散UAV在目标处的进入航向角（UAV航向角定义参见图1），完成对任务规划问题的简化，再通过图论思想将任务空间表述为有向图。

图1 UAV的航向角定义Fig.1 Definition of UAV orientation angle

离散后的航向角可表示如下：

式中：nd表示航向角的离散化程度，nd取值越大，离散化程度越高；iφ表示UAV在目标处的航向角。

根据图论的思想，有向图由顶点V和有向边E组成。协同任务规划问题的有向图顶点可表示如下：

式中：M表示包含离散化后的所有任务位姿点的集合；N表示包含所有UAV初始位姿点的集合；V为M与N的并集，表示有向图的所有顶点集合，

有向图的边E为M中各顶点间的有向连线、 N中各UAV初始位姿点与M中的目标点的有向连线的并集。

下面通过实例说明离散简化过程，设置侦查(Search)、打击(Attack)、评估(Verify)任务场景如下：

2) 目标为2个：Ntarget=2，且每个目标处对应的任务数量为 3，均包括侦查(S)、打击(A)、评估(V)三项任务，即

有：

图2为该任务场景对应的有向图。

图2 协同任务规划问题的有向图例图Fig.2 Example diagram of the SAV task planning by graph theory

由图 2可知，图中的有向边路径表示 UAV1、UAV2、UAV3的任务次序与飞行路径：绿线表示UAV1首先搜索目标1并对其进行攻击，最后再飞向目标2处完成对目标2的毁伤效果评估；紫线表示UAV2对目标1进行毁伤效果评估；蓝线表示UAV3首先对目标2进行搜索，然后对目标2进行攻击。

上述有向图对应任务规划的一个可行解，其解集可表示为S为所有飞行路径的解集，由图2可知，其解集包括6条飞行路径，每一条路径的长度对应两个位姿点间的 Dubins路径，路径总长度为所有 Dubins路径长度之和。

χ代表任务分配的决策变量集，由图2可知：

式中，ijχ表示第i个UAV与第j个任务的匹配结果。

Γ代表规划结果中各任务的执行时间戳，仅需满足侦查、打击、评估任务的执行次序即可。

由上述分析可知，可将 UAV的总飞行距离作为协同任务规划问题的指标，则该问题的效用函数可简化为如下形式：

式中：c为系统的效用值；为有向图中顶点集V的基数，即顶点的个数；为取值为0或1的决策变量，表示第j架UAV是否选择有向图中第k个顶点与第m个顶点连线对应的Dubins路径作为其飞行路径；skm为对应该UAV选择的Dubins路径的长度。

将式(5)进行分布式处理，分布到各 UAV上进行独立求解，即：

式(6)为式(5)的分布式形式，可将单个cj的运算分布到每个UAV完成独立解算。

为了反映较为真实的任务空间，还需要满足如下5项约束：

1）任务完成约束：UAV需要执行完所有规定的任务，可表示为：

2）任务时序约束：对于某一目标，其侦查、打击、评估三项任务间需满足如下约束条件：

即该目标需要先进行侦查才能进行攻击，且被攻击后才能进行毁伤评估。

3）载荷约束：只有装有相应任务载荷的UAV才能执行对应的任务，即只有作战 UAV才能执行所有三项任务，侦查 UAV只能执行侦查和评估任务，弹药类UAV只能执行攻击任务。

4）避碰约束：主要考虑多UAV间的避碰约束，采用不相交路径法[8]，即UAV的路径存在相交点，当且仅当UAV同时到达相交点时，才会发生碰撞，给出避碰约束如下。

令sp,sq分别表示UAVp和UAVq的Dubins路径，若sp与sq存在相交点ℓ，则需要满足：

式中：dℓ,p,q表示相交点处路径sp,ℓ与sq,ℓ的长度之差；分别表示 UAV的安全圆半径；分别表示UAV在路径sp,ℓ、sq,ℓ的平均飞行速度。

5）燃油约束：

式中，kχ表示第k个UAV的任务分配决策矩阵，Lk为第k个UAV可飞行的总路径长度。

由目标函数式(5)(6)和约束条件(7)～(11)完成描述了异构UAV的分布式协同任务规划问题。

最后给出UAV的运动学模型，将其等效为Dubins Car模型。

给出如下假设：

1）战场环境是事先已知的，且战场环境的态势信息获取是瞬间完成且准确的；

2）仅考虑二维平面内的规划问题；

3）各UAV之间的通信链路是可靠且信息一致的，且数据传输是瞬间完成的；

4）UAV的巡航速度为恒定的。

Dubins Car等效建模的思想主要来自于Dubins得出的证明结论：两个位姿点间的最短路径是 Dubins路径[9]，

Dubins Car模型适合于描述有转弯半径约束的UAV状态，故建立UAV运动学方程如下：

将遗传算法作为求解上述混合整数优化问题的主算法，基于分布式架构[19]，采用一体化求解方法，重新设计遗传算法的基因编码方式，由任务分配信息和路径规划信息组成染色体，最后加入禁忌搜索思想，对遗传算法进行改进，完成问题的求解。

式中：x,y为笛卡尔惯性坐标系下的水平分量；v为UAV巡航速度；φ为UAV速度方向与x方向的夹角，称为UAV航向角，且规定顺时针方向为正，参见图2；r为UAV的极限转弯半径，r越大，其机动能力越差；u为UAV的控制输入量，易知，

2 禁忌/遗传算法及算法评估准则

2.1 禁忌/遗传混合算法的基本步骤

禁忌/遗传混合算法的主体是遗传算法，只是将禁忌搜索算法的思想引入遗传算法中，对遗传算法中的交叉或者变异操作进行一定的改进，提高遗传算法的搜索速度，避免遗传算法的“早熟”现象。

禁忌/遗传混合算法的基本步骤如图3所示。

图3 禁忌/遗传混合算法的基本步骤Fig.3 Flow diagram of the tabu/genetic hybrid search algorithm

2.2 算法评估准则

算法的定量分析主要包括三个方面：

1）算法品质

算法品质定义为如下形式：

式中：Jbase表示所有参与评估的算法得出的解对应的最小航迹长度；表示某算法得出的解对应的航迹长度；quality表示该算法对应的算法品质。

由式(13)可知，算法品质可用于量化描述某算法相比于其他算法的性能优劣。算法品质可与蒙特卡洛法配合使用，当算法运行的次数为N时，其算法的品质得分为：

2）算法运行速度品质

3）算法品质与运行时间的加权

算法的优劣不能单一的通过运行时间和算法品质进行评估。通过设定权值，从算法品质和运行时间两方面评估算法的优劣：

3 仿真验证与分析

算法测试环境为Interval Zero RTX64实时操作系统。

任务空间场景基本参数如表1所示。

表1 任务空间设置Tab.1 Setting of task scenes

1）任务场景1

任务空间参数设置如表1所示，UAV的安全圆半径均为50 m，每架UAV可飞行的总路径长度为10 km。

分配结果如表2所示。

表2 算法运行分配结果Tab.2 Allocation result of the algorithm

算法运行结果对应的Dubins路径如图4所示。

记录算法在RTX64环境下的运行时间为21.92 s。

图4 UAV规划结果对应的Dubins路径Fig.4 Dubins trajectory of scenario with 3 targets and 5 UAVs

2）任务场景2

其他参数不变，考虑目标位置发生变化的情况。设Target 1和Target 2在仿真开始后10s开始机动：Target 1向笛卡尔坐标系X轴正向移动1700 m，向Y轴机动400 m；Target 2向Y轴移动800 m，且机动过程瞬间完成。

算法得到的分配结果与表2中相同，得到的更新Dubins路径如图5所示。

由图5的仿真结果可知，由于目标机动，UAV2、UAV3、UAV4的Dubins路径均发生变化，算法完成了对动态环境的响应，记录算法运算时间为26.41 s。

图5 目标机动时的重规划结果对应的Dubins路径Fig.5 Dubins trajectory of scenario with moving targets

3）任务场景3

任务场景3的参数设置如表1所示，设置任务空间在 20 km×20 km范围内，UAV的极限转弯半径为UAV的速度大小为v∈[60 m/s,80 m/s]，禁忌/遗传算法的基本参数设置如表3所示。

表3 禁忌/遗传混合算法参数设置Tab.3 Parameters setting on tabu/genetic hybrid algorithm

采用蒙特卡洛分析方法，设置实验次数为100，用于对比分布式一体化求解方法与优化工具CLPEX、典型分布式分层解耦求解算法[12]的性能，令 ==0.5 α β ；记录算法运行的时间和算法得出的总路径长度，如表4所示。

表4 各算法运行结果Tab.4 Results of three algorithms

各算法的运行时间对比结果如图6所示。

图6 基于蒙特卡洛试验的各算法运行时间对比结果Fig.6 Running time results of three algorithms based on Monte Carlo test

根据上述结果可知，相比CPLEX，虽然分布式一体化解法得出的解对应的总路径长度略大，但分布式一体化解法的平均运算时间缩短约90s，综合两项算法评估标准，分布式一体化解法性能更好；相比MRTA-RTPP[12]，分布式一体化解法得出的解更逼近最优解，但MRTA-RTPP[12]方法的运算速度更快，其平均运算时间比分布式一体化解法快约5 s，其运算时间优势并不明显，综合两项评估标准，分布式一体化解法性能更优。

4 结 论

1）相比于分层解耦求解方法，一体化求解方法更接近最优解；分布式规划框架将问题的求解分散到各 UAV实体上，可有效提高算法的求解速度。实验证明，在任务空间存在一定动态性的情况下，基于分布式架构的一体化求解算法具有较好的实时性，可以完成任务的快速响应，具有一定的实用价值，且算法对比实验在实时系统 RTX上进行，运行环境相对稳定，对比结果具有说服力。

2）在考虑UAV避碰、UAV燃油、UAV任务载荷、UAV异构、任务执行次序等约束条件下，结合Dubins Car模型可实现UAV飞行航迹与UAV动力学模型的等效转换，基于图论思想，通过 UAV的飞行航向角的离散化完成对协同任务规划这一NP问题的离散简化，可以实现对协同任务规划问题的等效建模。通过与针对混合整数线性规划的优化算法包 CPLEX的仿真对比，证明建模方法具有一定的有效性和实用性。

3）由于未考虑UAV间的通信延迟、UAV的飞行航迹的高度维，且假设侦查类UAV完成侦查任务是瞬间完成的，故现有工作存在不足，且一体化求解算法不能适用于任务空间更为复杂（参与任务的实体数大于20）的情况，求解过程需要考虑“死锁”情况，所以建模方法与算法仍需进一步改善；同时，经初步分析可知，UAV飞行航向角的离散程度的nd越大，算法求解时间亦会增加，但是带来的解的最优度并不能显著提高，所以离散量nd的取值也是后续研究的关键内容。

（References）：

[1]Maza I, Caballero F, Capitan J, et al. Experimental results in multi-UAV coordination for disaster management and civil security applications[J]. Journal of intelligent &robotic systems, 2011, 61(1): 563-585.

[2]Kendou F. Survey of advances in guidance, navigation,and control of unmanned rotorcraft systems[J]. Journal of Field Robotics, 2012, 29(2): 315-378.

[3]Rathinam S, Sengupta R, Darbha S. A resource allocation algorithm for multivehicle systems with nonholonomic constraints[J]. IEEE Trans. Autom. Sci. Eng.,2007, 4(1): 98-104.

[4]Savla K, Frazzoli E, Bullo F. On the point-to-point and traveling salesperson problems for Dubins’ vehicle[C]//American Control Conference. June 2005: 786-791.

[5]Edison E, Shima T. Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms[J]. Computers and Operations Research, 2010, 38(1): 340-356.

[6]Cons M S, Shima T, Domshlak C. Integrating task and motion planning for unmanned aerial vehicles[J]. Unmanned Systems, 2014, 2(1): 19-38.

[7]Ponda S S, Johnson L B, Geramifard A, et al. Cooperative mission planning for multi-UAV teams[M]. Handbook of Unmanned Aerial Vehicles. Springer Netherlands,2015: 1447-1490.

[8]Chandler P R, Pachter M, Swaroop D, et al. Complexity in UAV cooperative control[C]//American Control Conference. IEEE, 2002, Vol.3: 1831-1836.

[9]Dubins L E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents[J]. American Journal of Mathematics, 1957, 79(3): 497-516.

[10]沈林成, 陈璟, 王楠. 飞行器任务规划技术综述[J]. 航空学报, 2014, 35(3): 593-606.Shen Lin-cheng, Chen Jing, Wang Nan. Survey on task planning technology for aircraft[J]. Acta Aeronautica Et Astronautica Sinica, 2014, 35(3): 593-606.

[11]Tsourdos A, White B, Shanmugavel M. Cooperative path planning of unmanned aerial vehicles[M]. John Wiley &Sons, 2010.

[12]Woosley B, Dasgupta P. Multi-robot task allocation with real-time path planning[C]//Proc. of the Twenty-Sixth International Florida Artificial Intelligence Research Society Conference. 2013: 574-579.

[13]Arsie A, Savla K, Frazzoli E. Efficient routing algorithms for multiple vehicles with no explicit communications[J].IEEE Transactions on Automatic Control, 2009, 54(10):2302-2317.

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

[15]Richards A, Bellingham J, Tillerson M, et al. Coordination and control of multiple UAVs[C]//AIAA Guidance,Navigation, and Control Conference. Monterey, CA. 2002.

[16]Rasmussen S J, Shima T. Tree search algorithm for assigning cooperating UAVs to multiple tasks[J]. International Journal of Robust and Nonlinear Control, 2008,18(2): 135-153.

[17]Deng Q B, Yu J Q, Wang N F. Cooperative task assignment of multiple heterogeneous unmanned aerial vehicles using a modified genetic algorithm with multi-type genes[J]. Chinese Journal of Aeronautics, 2013, 26(5): 1238-1250.

[18]Edison E. Task assignment and path optimization for cooperating uninhabited aerial vehicles[D]. Technion Israel Institute of Technology, Faculty of Aerospace Engineering, 2009.

[19]Pospichal P, Jaros J, Schwarz J. Parallel genetic algorithm on the cuda architecture[M]. Applications of Evolutionary Computation. Springer Berlin Heidelberg, 2010: 442-451.

[20]黄荣, 崔乃刚, 韦常柱, 等. 基于 RRT-GPM 两阶策略的导弹编队协同突防最优轨迹快速设计[J]. 中国惯性技术学报, 2015, 23(3): 356-362.Huang Rong, Cui Nai-gang, Wei Chang-zhu, et al. Rapid trajectory optimization for cooperative penetration of missile formation based on two-stage RRT-GMP strategy[J]. Journal of Chinese Inertial Technology, 2015, 23(3):356-362.

[21]郑重, 熊朝华, 党宏涛, 等. 时变通信延迟下的无人机编队鲁棒自适应控制[J]. 中国惯性技术学报, 2016,24(1): 108-113.Zheng Zhong, Xiong Zhao-hua, Dang Hong-tao, et al.Robust adaptive control for unmanned aerial vehicle’s formation with time-varying communication delays[J]. Journal of Chinese Inertial Technology, 2016, 24(1): 108-113.

Integrated distributed method for dynamic cooperative mission planning problem

CUI Nai-gang, WU Wei-nan, GUO Ji-feng
(School of Astronautics, Harbin Institute of Technology, Harbin 150001, China)

Based on multi-heterogeneous UAVs in dynamic mission scenario of reconnaissance, striking and verifying, this paper establishes the models for cooperative mission planning problem, and designs an integrated distributed algorithm. Because of the disadvantages of the centralized planning framework, this paper adopts distributed planning framework. First, the graph theory is employed to transform the mission planning problem into directed graph under the constraint conditions of collision avoiding, fuel consuming,and the mission sequence. The Dubins Car Model is used to stand for the UAV’s kinematic model. Then,without decoupling the planning solution problems, this paper designs an integrated planning framework, and adopts the genetic/tabu search hybrid algorithm to solve the planning problem. At Last, some examples was presented in several simulation scenarios to compare the performance and computational results from different algorithms, which show that the integrated distributed method can be applied to the dynamic mission scenario, and can rapidly solve the planning problem with complex missions.

heterogeneous UAVs; integrated method; cooperative mission planning; distributed decisionmaking; Dubins path; tabu/genetic hybrid algorithm

1005-6734(2017)04-0523-07

10.13695/j.cnki.12-1222/o3.2017.04.018

TP29

A

2017-04-08；

2017-07-20

国家自然科学基金（11472090）

崔乃刚（1965—），男，教授，博士生导师，主要飞行器总体设计、制导控制、任务规划领域研究。E-mail: Cui_Naigang@163.com