多目标跟踪的飞行器集群协同实时任务分配策略

王厚鹏，曹素芝，闫 蕾，吴少俊

多目标跟踪的飞行器集群协同实时任务分配策略

王厚鹏1,2，曹素芝1，闫 蕾1，吴少俊1

（1. 中国科学院空间应用工程与技术中心，北京，100094；2. 中国科学院大学，北京，100049）

针对跟踪过程中，多动态目标优先级变化引起的飞行器任务实时重分配问题，提出了一种飞行器集群智能自组织控制方案。该方案基于飞行器集群组网和集群协同计算技术，实现分布式集群实时控制与协同任务分配，以保证对多目标的实时跟踪。针对跟踪目标优先级变化的场景，提出了具有双向选择机制的合同网改进算法，能够解决突发情况导致的飞行器集群任务实时分配问题。最后进行仿真验证，实验结果表明，该方案能够提高飞行器集群的协商效率，减少通信频率，提升任务分配的时效性。

合同网算法；飞行器集群；任务分配；动态目标

0 引 言

近年来，随着技术的发展，无人飞行器的应用领域越来越广泛，其能够适应多种复杂场景，执行实时侦察、跟踪和打击等多种任务。由于飞行器集群任务执行能力和抗突发事件能力高于单个飞行器，因此，飞行器执行任务逐步向自主化、智能化和集群化方向演变。如何通过有效的控制策略支持飞行器集群协同执行任务并使得整体的效益最佳，成为当前极具研究意义的问题[1]。

由于飞行器集群执行任务的环境日益复杂以及飞行器计算能力的提高，对飞行器集群任务分配的时效性、求解速度以及全局寻优等能力提出了更高的要求。为了确保集群控制体系的高效性和灵活性，为任务分配设计了多种分布式体系结构。飞行器任务分配有多种方式，按照执行任务过程中飞行器之间关联性的强弱，可以分为协同任务分配和独立任务分配[2]；按照任务场景突发情况的重要程度，可以分为执行任务前的预先分配和执行任务过程中的实时任务分配[3]。

本文针对飞行器集群对多动态目标跟踪的场景，提出使用合同网的思想解决突发情况导致的任务实时分配问题。基于合同网的任务分配方法原理易于理解，实现较为简单且执行效率较高，已经成为飞行器集群任务分配中应用最为广泛的方法[4]。文献[5]提出一种基于合同网协议的可扩展分布式无人机系统；文献[6]在传统合同网基础上引入了负载因子，减少了通信次数，优化了任务分配结果；文献[7]将合同网协议应用于分布式系统的任务分配，证明了其在降低分配成本和实时性方面的优势；针对集群执行追捕任务的场景，文献[8]基于合同网提出了带双向筛选的动态任务分配算法，减少了通信开销。为了让合同网算法更好的适用于动态目标跟踪问题，本文对其进行了改进，使用改进合同网算法对飞行器集群协同实时任务分配进行了研究。

1 任务分配问题描述与建模

为了解决飞行器集群对多个动态目标跟踪过程中的任务分配问题，关键是对飞行器资源与跟踪目标信息的协同整合，生成最优的任务分配方案。

结合飞行器集群对多动态目标进行跟踪的复杂场景，本文基于以下假设研究：a）在任何时刻，一个飞行器最多只会对一个动态目标进行跟踪；b）运动目标的移动速度始终小于飞行器的最大飞行速度；c）在飞行器捕获目标的转移过程中，移动目标的移动方向保持不变；d）用质点来模拟飞行器和跟踪目标；e）所有的飞行器之间均能够建立直接的通信链路；f）飞行器数量始终不少于所有跟踪目标所需飞行器的数量。

1.1 任务分配场景分析

飞行器集群协同实时任务分配是由突发情况导致原本的任务分配方案难以满足当前的任务需求，进而触发新一轮的集群任务分配。在本文中，结合飞行器集群协同执行多目标跟踪任务的实际场景，被跟踪目标不断移动，其威胁程度会随之发生变化。一般来说，威胁程度越大的目标，其优先级也越高，需要获取关于该目标的更多信息，因此需要分配较多的飞行器对其进行跟踪；反之，针对威胁程度较小的目标，集群会主动减少对其进行跟踪的飞行器的数量，从而实现资源的最优化分配。

1.2 相关模型的数学表达形式

1.3 任务分配数学模型

1.3.1 目标函数

为了实现分布式集群实时控制与协同任务分配，需要在集群进行实时任务分配协商时减少协商的次数，从而有效降低任务分配的时延，即：

在对运动目标的跟踪场景中，需要比较目标与飞行器集群中各飞行器的速度大小和方向之间的关系，计算飞行器去执行某一项跟踪任务的相对移动时间，从中选择移动时间最短的任务方案执行，即：

针对该场景，为使飞行器能够以最短的时间进行转移并捕获跟踪目标，因此时间的优先级较高，在转移时间相同的情况下，再比较其转移距离。

1.3.2 约束条件

a）跟踪目标的移动速度。

通过式（8）即可求出转移过程所需的时间以及飞行器移动的距离。

b）飞行器最大速度。

c）多机协同约束。

2 任务分配算法设计

任务分配是飞行器集群协同控制的基础，任务分配算法应该能够为每个移动目标分配合适的飞行器执行跟踪任务，同时使得该方案满足集群转移总时间与距离最短的优化目标。飞行器集群任务分配问题属于多目标优化问题，本节采用合同网的基本思想，并针对多动态目标跟踪的特殊场景对合同网进行改进，提高了任务分配的时效性。

2.1 合同网基本思想

合同网是在研究分布式问题求解过程中提出的概念，此后许多研究人员对其进行了改进和扩展[9]。合同网采用任务拍卖的方式，将投标值作为用户之间任务分配的控制变量，通过用户之间的任务竞争和协商，以较优的系统配置和代价完成任务。合同网由多个可以相互传递信息的用户组成，其中每一个用户都能够扮演3种角色：招标者、投标者和中标者。基于合同网的任务分配一般包括以下4个步骤：

a）任务发布：当发现自己的资源不足以完成某一项任务时，就会作为招标者把任务信息向外界公布；

b）投标：其他用户接收到招标信息后，根据任务信息和自己的能力对招标任务信息进行评估，计算自己的投标值，并向合适任务的招标者发送投标信息；

c）中标：招标者对所有投标信息进行处理，根据投标者的投标值选择成本最低的投标者，向其发送中标信息，同时向其它未中标的用户发送流标信息；

d）任务执行：收到中标信息的用户获得该任务的所有权，并执行该任务，向招标者发送执行任务信息，并对该目标进行捕获和跟踪。

合同网算法流程如图2所示。

图2 合同网算法流程

在基于合同网的任务规划方法中，整个分配过程依赖于各求解节点的控制策略和自主决策，是一种分布式自适应的分配方法，其协商过程具有以下特 点[1,10]：

a）协商是一个局部的过程，不涉及中央式的集中控制；

b）所有用户协商的目标相同，即招标者与投标者都以转移时间和转移距离最短为目标，这是协商成立的前提；

c）在整个过程中，招标者、投标者和中标者都是一个临时的角色，不由中心节点指派，随着任务信息发生变动。

2.2 基于改进合同网的飞行器集群协同任务实时分配算法

传统合同网算法适用于单任务、单中标者的分配场景，在一个拍卖周期中，单个招标者会独占所有投标者的资源，任务分配最终的中标者只有一个，造成大量的投标者有空闲资源无法进行任务分配。在任务信息频繁发生改变、同时需要对多个任务进行拍卖的场景中，合同网算法效率较低，缺少并发的交易机制。

针对合同网算法所面临的问题，结合飞行器集群对多动态目标进行跟踪任务实时规划的问题背景，本文在合同网的基础上引入并发交易机制。允许在一个交易回合中同时存在多个招标者对多个任务进行招标，投标者可以在所有的招标任务中选择一个自己执行该任务成本最少的任务，向其发送投标信息。所有招标者接收到投标信息后，按照最优的策略选择合适的投标者作为中标者去执行该任务。并发机制使得原来需要进行多个回合的拍卖过程变为了一个回合，极大地提高了协商效率，有效降低了任务实时分配的时延。

基于改进合同网的飞行器集群协同任务实时分配算法的描述如下：

a）Step1：确定招标飞行器。在当前跟踪目标优先级提高的情况下，由当前跟踪该目标的多个飞行器中编号最小的飞行器作为招标者，若当前只有一个飞行器正在跟踪该目标，则该飞行器就会成为招标者。

d）Step4：投标信息评估。所有接收到投标信息的招标飞行器，对其接收到的投标信息进行比较，选择转移时间和距离最小的投标信息作为中标者。

e）Step5：招标结果通知。招标者向所有投标者发送招标结果，向中标者发送中标信息，向其余飞行器发送流标信息。

f）Step6：任务执行。中标者收到中标信息后，在所有的中标信息中选择执行优先级最高的任务，并向优先级最高的任务招标者发布任务执行信息，完成位置转移并捕获跟踪目标。当前跟踪同一目标的多个飞行器之间交换信息，获得其他飞行器的编号等信息。

3 仿真结果及分析

为了验证改进的合同网算法在飞行器集群协同实时任务分配中的有效性，对跟踪场景进行了仿真实验。改进的合同网算法在一台笔记本电脑上进行了评估，该笔记本采用Intel core i7-8750h处理器，内存为16 GB，仿真环境为Python，版本为3.7。

假设在该场景中现有目标为两个，其位置、移动速度大小和方向、优先级等信息如表1所示。

表1 待跟踪目标信息

Tab.1 Information of the Target to be Track

目标位置坐标/m移动速度（m·s-1）方向（与x轴正方向夹角）/（°）优先级 （100，250）560（2，3） （200，300）5300（1，2）

集群由6个可以相互通信的飞行器组成，飞行器集群中各飞行器的位置信息、最大飞行速度、当前跟踪目标的优先级和飞行器编号等信息如表2所示，其中优先级（2，3）表示当前跟踪目标的优先级由2变为3，阈值为30。

表2 飞行器信息

Tab.2 Information of the Aeial Vehicle

飞行器位置坐标/m最大速度/(m·s-1)跟踪目标优先级 （100，250）121（2，3） （100，250）81（2，3） （200，300）152（1，2） （170，100）250（0，0） （200，320）80（0，0） （100，200）100（0，0）

图3 任务分配

为了进一步研究具有双向选择机制的合同网算法对传统合同网算法的改进效果，本文进行了25次相互独立的仿真实验。实验的自变量为需要处理的任务数量，而目标数量的变化会引起任务数量的变化，本文考虑了目标数量从1~25个的变化情况，同时为了确保有足够数量的飞行器执行任务，将飞行器的个数设置为50。其中，随机初始化目标和飞行器的位置坐标以及速度等信息，阈值为30。

任务数量的增加会提升任务分配的复杂度，改变任务数量，分别对传统的合同网和具有双向选择机制的改进合同网进行仿真。其交易回合数随任务数量的变化趋势如图4所示。

图4 交易回合数变化趋势

由图4可以看出，与传统合同网算法相比，改进的合同网算法能够有效地减少交易回合数，提升系统的协商效率，从而提高任务分配的时效性。

4 结束语

针对飞行器集群对多个动态目标跟踪过程中的协同实时任务分配问题，基于合同网的思想解决了集群任务分配中的效能优化问题。本文对合同网进行了改进，引入了并发机制，减少了协商过程中进行交易的回合数，同时减少了信息交换的次数，提高了协商效率和任务分配的时效性，达到了预期的效果。

本文提出的解决方法，未考虑到实际场景中通信时延问题，以及飞行器不能同时收到所有招投标信息的情况。在存在时延的情况下，如何通过获取的局部信息寻求效益优化，也是未来非常有必要的研究方向。

[1] 龙涛. 多UCAV协同任务控制中分布式任务分配与任务协调技术研究[D]. 长沙: 国防科学技术大学, 2006.

Long Tao. Research on distributed task allocation and coordination for multiple UCAVs cooperative mission control[D]. Changsha: National University of Defense Technology, 2006.

[2] Kaushik R. Task allocation and scheduling of concurrent applications to multiprocessor systems[D]. California: Electrical Engineering and Computer Sciences University of California at Berkeley, 2007.

[3] Bui H N , Han X , Mandal S , et al. Optimization-based decision support algorithms for a team-in-the-loop planning experiment[C]. San Antonio: 2009 IEEE International Conference on Systems, Man and Cybernetics, 2009.

[4] Atkinson M. Contract nets for control of distributed agents in unmanned air vehicles[C]. San Diego: 2nd AIAA "Unmanned Unlimited" Conf. and Workshop & Exhibit, 2003.

[5] Krakowczyk D, Wolff J, Ciobanu A, et al. Developing a distributed drone delivery system with a hybrid behavior planning system[C]. Berlin: Joint German/Austrian Conference on Artificial Intelligence (Künstliche Intelligenz), 2018.

[6] Li Y W, Li B A. Research of multiple UAVs task allocation based on improved contract net[J]. Advanced Materials Research Trans Tech Publications Ltd, 2013(823): 439-444.

[7] Saleh B B, El Moudni A, Hajjar M, et al. A cooperative control model foroperating theaterscheduling[C]. Thessaloniki: 2018 5th International Conference on Control, Decision and Information Technologies (CoDIT), 2018.

[8] 刘政强, 陈寿元, 邵增珍, 等. 多机器人追捕中带双向筛选的动态任务分配算法研究[J]. 小型微型计算机系统, 2017, 38(7): 1568-1572.

Liu Zhengqiang, Chen Shouyuan, Shao Zengzhen, et al. Research on dynamic task allocation algorithm with bilateral selective in multi-robot capture[J]. Journal of Chinese Computer Systems, 2017, 38(7): 1568-1572.

[9] Szczerba R J, Galkowski P, Glicktein I S, et al. Robust algorithm for real-time route planning[J]. IEEE Transactions on Aerospace and Electronic Systems, 2000, 36(3): 869-878.

[10] 张梦颖, 等. 基于改进合同网的无人机群协同实时任务分配问题研究[J]. 航空兵器, 2019, 26(4): 38-46.

Zhang Mengying, et al. Cooperative real-time task assignment of UAV group based on improved contract net[J]. Aero Weaponry, 2019, 26(4): 38-46.

Collaborative Real-time Task Allocation for Multi-target Tracking Aerial Vehicle Cluster

Wang Hou-peng1,2, Cao Su-zhi1, Yan Lei1, Wu Shao-jun1

(1. Technology and Engineering Center for Space Utilization, Chinese Academy of Sciences, Beijing, 100094;2. University of Chinese Academy of Sciences, Beijing, 100049)

The collaborative tracking of multiple dynamic targets by aerial vehicle cluster has become a research hotspot in recent years. Aiming at the problem of real-time reallocation of tasks caused by the change of priority of multiple dynamic targets during the tracking process, an intelligent self-organizing control scheme for aerial vehicle clusters is proposed. Based on the aerial vehicle cluster networking and cluster collaborative computing technology, this solution implements the real-time control of distributed cluster and the collaborative allocation of tasks. The contract net algorithm with a two-way selection mechanism for the scenario of multi-target priority change is improved. It can quickly handle the real-time collaborative allocation of tasks. Finally, simulation verification is performed. The experimental results show that the proposed scheme can improve the negotiation efficiency of the aerial vehicle cluster, reduce the communication frequency, and improve the timeliness of task assignment.

contract net algorithm; aerial vehicle cluster; task allocation; dynamic targets

1004-7182(2020)03-0032-06

10.7654/j.issn.1004-7182.20200307

V448

A

王厚鹏（1997-），男，硕士研究生，主要研究方向为分布式系统、边缘计算和图像处理。

曹素芝（1981-），女，副研究员，研究方向包括卫星网络、边缘计算和分布式计算。

闫 蕾（1978-），女，高级工程师，研究方向包括卫星网络、边缘计算和分布式计算。

吴少俊（1983-），男，研究员，主要研究方向为空间信息处理与组网技术。

2020-04-13；

2020-04-29