基于MMDP模型的多无人机分布式动态协同任务规划研究

基于MMDP模型的多无人机分布式动态协同任务规划研究

李季

山东英才学院  山东济南  250000

摘要：本文针对无人作战飞机编队内单架无人机（Uninhabited Combat Aerial Vehicle, UCAV）在作战区域决策任务的时变性，以马尔可夫决策过程理论为基础，建立了一种基于多智能体马尔可夫决策过程（Multi-Agent Markov Decision Process, MMDP）的动态任务分配模型；提出了一种分布式多智能体动态协同任务分配策略寻优算法。仿真结果表明，该算法能够有效的解决多无人作战飞机动态协同任务分配问题。

关键词：MMDP模型 ；UCAV；动态协同； 任务规划； 选择寻优

1.引言

随着无人作战飞机的大量应用，现代战争尤其是空地作战模式已经呈现出了新的特点和趋势。对无人作战飞机的控制和指挥正朝集群化、自主化、智能化方向发展，多架无人机协同执行复杂的作战任务是未来无人机应用的趋势，多机协同作战提高了成功率，发挥了无人机的优势，但也对指挥、任务决策和规划控制提出了更高的要求。因此，对多无人机协同作战任务决策与规划系统的研究是目前无人机领域诸多研究热点之一[1]。

在任务分配初始阶段，有效的方法是采用静态任务分配算法或人工确定最优的编队层任务分配策略方案，但是随着任务分配过程的进行，在编队到达不同的目标群所在的作战区域后，任务环境比如子目标出现的位置、时间、数量可能会迅速发生变化，此时如果再按照任务开始阶段以静态任务分配模式制定单机层即编队内部所有UCAV的任务分配策略显然已经不合时宜，有效的方法应该是按照动态任务决策与优化分配规则实时对子目标任务进行优化分配。本文基于Multi-Agent Markov Decision Process (MMDP)模型采用分布式多智能体决策策略[2]，对UCAV编队内动态协同任务分配问题进行了研究，从而将任务细化到了单机层层面上。

在任务优化分配过程中，系统状态和任务队列不断变化，任务分配系统不断改变任务分配策略，使任务分配适应环境变化[3]。动态任务分配下对分配算法要求较高，要求系统在较短时间内作出决策，获得最优策略和寻优时间存在冲突，有效的模型和算法是解决冲突的关键。因此，动态任务分配研究面向的对象仅限于单机层UCAV即同一个编队内部多架无人作战飞机的任务分配与重分配情况。

多UCAV协同作战动态任务分配模型以Multi-Agent系统为基础，将每一架UCAV视为一个Agent，通过赋予Agent自治能力分配和和执行任务。系统中存两类Agent：决策Agent和成员Agent，或者分别称为编队控制Agent(Group_CA)和编队功能Agent(Group_FA_i)。决策Agent具有任务分配决策能力，获取系统状态信息并为成员Agent作出任务分配决策；成员Agent协同执行分配任务并反馈其状态。根据模型结构不同，决策Agent与成员Agent可为同类型Agent，也可为不同类型Agent。

动态任务分配模型中每一Agent具有不同的初始状态，系统根据任务属性和Agent状态进行任务分配，通过数据链完成状态信息交换和决策指令下达。

2.MMDP动态任务分配模型

针对多无人机动态协同任务分配问题的特点，以Multi-Agent马尔可夫决策过程理论为基础，参考马尔可夫理论的建模方法，建立MMDP模型由如下五部分组成：

(1)时间

系统时间为有限值，以有限离散的时间点表示，其中、分别为起始和终止时刻。

(2)任务

协同任务分配模型中将无人机执行某一任务或对某一目标攻击等统称为任务。任务类型对任务分配规模有重要影响。任务类型越多，任务分配时需考虑的任务执行秩序将使可能解规模急剧增大。根据实战中执行任务需求不同，文献[4]将任务类型分为四种：搜索（Search）、分类（Classification）、攻击（Attack）、证实或战场损伤评估（Verification or Battlefield Damage Assessment BDA）。

任务类型增加将使可能解规模急剧增加，严重影响动态任务分配效率。为简化问题建模，论文采用单一任务类型，将对每一Agent分配的任务视为相同类型的任务。每一目标进入系统时通过任务评估系统将所有任务解耦为不同的、独立的任务，并对每一任务设定不同的初始状态。通过对任务解耦并控制其进入任务队列的时间和先后顺序可避免处理多任务类型和执行顺序问题，有效减小可能解规模，提高效率。

时刻系统中所有任务构成的任务队列可表示为：

（1）

在时刻状态为：

                    （2）

其中，、分别表示时刻的位置和速度，均为二维向量，，。为Agent执行任务的预期消耗，包括威胁代价、战伤损耗、武器消耗等，在进入系统时决定。不同Agent执行同一任务时相同。为简化建模过程，假定每一任务进入系统时具有随机确定的速度和方向，且执行任务过程中不变。

为Agent执行任务的奖励值，且。奖励值大小反映每一任务的重要程度。奖励值大说明任务重要，系统执行该任务获得收益越大。

(3)无人机

将每一个具有自主决策和执行任务能力的无人机视为一个Agent，表示为：

，

对Agent作如下假设：Agent是刚体，地面坐标为惯性坐标，将地面视为平面，重力加速度不随高度变化[171]。执行任务过程中每一Agent的状态随时间不断变化，其状态信息包括：

（3）

其中，为在时刻状态，、分别为位置和速度信息，，。为在时刻攻击能力。为在时刻是否分配任务的状态。表示Agent当前未分配任务，说明Agent当前已分配。

(4)策略集

时刻系统中Agent数和任务数分别记为和，可选任务分配策略可表示为：

                  （4）

其中为的0-1矩阵，或者也可以看作由策略向量集合组成，，且均为维的任务Agent列向量。

策略集采用单步规划机制，即每次任务分配只为Agent分配一个任务，任务分配过程中依战场态势变化对每一Agent的任务动态调整[5]。系统在整个任务分配过程中策略的集合定义为策略集，表示为：

（5）

策略集反映了每一Agent在整个执行任务过程中执行任务情况，是评价Agent间协同的依据。

(5)评价函数

从前文对于评价函数的分析可知，多UCAV协同任务分配需考虑无人机飞行距离、攻击目标收益值、武器消耗值、威胁代价等因素。例如，要求无人机在最短时间内完成任务时，设定目标函数以飞行距离最短为目标；要求无人机执行任务中消耗最小时，则以消耗值最小为目标。上述各因素相互耦合，需进行各因素间的折衷，通常任务分配评价函数是各因素的集合，通过权值区分各因素权重。

对于已经进入作战区域的UCAV编队来说，目标价值攻击收益无疑是最为重要的事情。因此在本阶段的任务分配，论文以系统在整个任务分配过程中全体Agent执行任务所获收益值为目标函数，任务分配以目标函数值最大为目标，并将时间折扣因子和任务消耗折扣因子引入目标函数。

时刻系统在决策、状态时的收益值定义为：

             （6）

其中为时间折扣因子，。越小，系统所获收益值随时间减小越快。时不考虑时间推移对收益值的影响，时不考虑收益值。为任务分配决策过程消耗时间和决策下达后Agent运动到目标位置的时间。一般决策时间较短，可不考虑，飞行时间与距离成正比，又可表示为：，其中为时刻飞行到与相遇时的飞行距离，为速率。由Agent和任务位置、速度大小和方向共同决定。为执行任务消耗，包括处理个任务时Agent攻击能力消耗和任务分配时通信成本以及决策成本，通信成本在任务分配时决定，与执行过程无关，决策成本与可能解规模及采用的分配算法有关。为任务消耗折扣引子，，表示不考虑任务消耗。通信成本只考虑为完成任务分配获取Agent状态时通信的成本，执行任务时Agent间通信不计成本。

                               （7）

为罚函数，当系统中存在个任务未分配或未完成时，

                                  （8）

表示未被分配任务奖励值之和，为罚函数因子，。表示不考虑罚函数对收益值的影响，越大，对未被分配和未被完成任务的处罚越重，通过此设置来保证系统尽可能完成更多的任务。

综上，系统在时刻收益为：

         （9）

系统在整个任务分配过程中总收益为：

，            （10）

3.基于选择寻优的策略优化算法

多无人机协同任务规划问题需要考虑使系统总收益最大的策略集为最优策略。最优策略意味着全体Agent以最优分配方式执行任务，实现全体Agent协同[5]。

可能解规模与每一任务备选Agent数有关，减小每一任务备选Agent数可减小可能解规模。通过对最优任务分配策略分析，发现最优任务分配策略下每一任务基本都由其周围一定范围内的Agent执行。一方面任务与Agent之间航路较短有利于降低成本，另一方面较短的航路带来的任务执行延时和威胁代价较小。

选择寻优法进行任务分配策略寻优时，以每一任务为中心作一定半径的圆，调整每一任务对所在圆内Agent的选择实现策略寻优。选择机制保证每次迭代都使系统分配策略向更优方向移动。经过有限次迭代，系统将获得最优分配策略。

假设系统中存在个Agent，个任务。选择寻优法的策略寻优步骤如下：

第一步：以任务所在位置为圆心，以为半径作圆，圆的半径选择满足：

(1) 每一圆内都有至少个Agent；

(2) 每一圆的半径大于。

第二步：生成初始分配策略：对系统内每一任务随机选择一个Agent，将此时决策矩阵表示为，计算收益值：

（11）

其中，，且为维的任务Agent向量，并满足：，。时，将有个任务未被分配执行。

第三步：随机选择一个任务，将该任务调整为，且满足：，同时，调整后所选择的Agent应在该任务所在圆内。将此时分配策略表示为

。

第四步：策略合理性检查：判断内是否存在：，，，若存在，将再作调整为，使满足：，，，调整所选择的Agent仍应符合与该任务在同一个圆内。将此时分配策略表示为，策略收益值为：

                             （12）

第五步：针对，对其余任务，，依次按照第三步的内容进行操作，并将新调整的策略表示为，使

（13）

满足：。

第六步：更新系统最优策略。将最优策略定义为。若，则。

第七步：若满足系统要求，寻优过程结束，否则，转至第三步。

选择寻优法以一定范围内的可选Agent为寻优对象，减少了可能解规模，提高了寻优速度，同时保证了分配策略随迭代过程不断接近最优分配策略。

采用选择寻优法经有限次迭代，系统将获得最优分配策略。在每一时刻，系统中任务数和Agent数为有限值，所有可选分配策略数也为有限值。当足够大使得以每一任务为中心的圆都能覆盖系统中的所有Agent时，选择寻优算法要求每次选择过程中都选择最优策略，这一过程保证了经有限次迭代，系统将获得最优分配策略。

基于Agent的选择寻优算法能减少可能解规模。假定系统中Agent数为，，，任务数为，且。在每一任务周围分布的Agent数同为，且。则选择寻优法的可能解规模为：

（14）

选择寻优算法中，选择半径对于获得的最优策略具有重要影响。当选择半径为无穷大时，每一任务的可选Agent为系统中所有Agent，这使得选择寻优法可能解规模与基于遗传算法的策略寻优相同，这时选择寻优法能获得系统全局最优解。当缩小选择半径使得系统可能解规模减小时，将有可能使系统中某些任务的最优Agent处于选择圆外，系统将得不到最优分配策略。因此，对选择半径的选取需对可能解规模和策略性能进行权衡。

4.分布式多智能体动态任务分配

采用分布式模式能够减少计算和通信成本，降低对系统状态可观测程度的要求，提高可靠性，从而获得系统最优任务分配策略。在这一模式中，任务分配过程由多个决策Agent协同完成，各决策者间并非彼此独立，而是最大限度的进行状态信息共享，尽可能地得到最优策略。对于本节所研究的问题来说，UCAV编队中会有多架无人机担任决策Agent角色，决策Agent经过策略寻优得到当前任务环境下的最优任务策略方案后，会由其中的长机将方案以广播的方式传达给编队中所有成员，从而完成协同作战任务。

分布式任务分配过程流程图如图1所示：

图1分布式任务分配过程流程图

分布式模型中新任务出现后的任务分配过程步骤如下：

第一步：各决策Agent获取系统状态信息，包括本组成员Agent状态信息和任务信息等。其中任务信息指系统中所有未执行任务的信息。

第二步：各决策Agent分别采用任务分配策略选择寻优算法获得局部最优任务分配策略。最优任务分配策略以前文建立的任务分配模型中的评价函数为依据，使当前时刻本组所有Agent总收益值最大为目标。

第三步：各决策Agent之间进行通信和策略共享，对各自分配策略进行优化和调整，解决策略间的冲突，实现不同状态可观测等级下的协同。

第四步：全体Agent执行分配的任务，计算总的策略收益。

在分布式任务分配模式下，多个决策Agent在不同状态可观测等级下分别完成任务分配，通过各决策Agent间的协调解决策略间的冲突，获得在当前状态可观测条件下的最优策略。

5.仿真实例与分析

首先对最优策略解进行解编码染色体设置。染色体采用单染色体编码机制，将编队内每一架无人机视为染色体中一个基因，长度为，基因为整数值，代表对应任务队列中任务编号，基因位值为0表示该UCAV未参与攻击任何编号的子目标。基因位表示为，。

(1)仿真环境和初始条件定义

以某无人机编队攻击某区域内目标群为例，编队内无人机抽象为决策Agent和一般成员Agent，假设该仿真实例中系统为全局状态可观测模式。策略优化模型中时间折扣因子，任务消耗折扣引子。假定时刻系统中Agent数，任务数。随机生成Agent和任务的初始位置如图2所示。假设每一任务的速度随机确定，且m/s，m/s，且大小和方向不变。全体Agent的速度绝对值为10，单位也为m/s。Agent和任务初始位于横坐标和纵坐标为m的区域内。且每一任务的奖励值在范围内，单位为1。

图2 Agent和任务初始位置图

随机生成任务和Agent的初始位置、速度和奖励值。

(2)Agent动态分组策略寻优仿真

Agent动态分组模式中，初始时刻对全体Agent共分为4组。设定。依据组长Agent和成员Agent评估函数，s时Agent分组情况如图3所示：

图3s时Agent分组图

选择寻优法中参数设置为，m，采用选择寻优算法并经策略优化和调整后，得到系统初始最优染色体基因为：

对应的最优任务分配策略如图4所示。

图4初始最优任务分配策略图

在初始分组基础上，系统中决策Agent和成员Agent的分组情况随Agent相对位置变化不断调整。编队在该仿真区域的

UCAV群体分波次对所有子目标进行攻击，每一波次攻击进行完毕后系统根据各成员与剩余子目标的位置关系重新进行策略优化与任务分配，直到所有任务均已完成[6]。任务执行过程中，假设所有UCAV均具有反复多次攻击的能力。

本仿真实例中，在系统中全体Agent按照初始最优分配策略执行任务之后，假设s时刻第一波次攻击结束，此时、任务已执行完毕，同时a2和a12在任务执行过程中被敌防空火力击伤坠毁。根据余下的每架UCAV之间的相对位置关系，对Agent成员重新进行分组。经第二次策略优化与调整后，新的最优策略为：

如图5所示。

图5s时Agent分组及最优任务分配策略图

经s时刻第二波次攻击结束，此时、、、已执行完毕，在此期间a4在任务执行过程中被敌防空火力击伤坠毁。对Agent成员分组情况再次进行调整，经第三次策略优化与调整后，更新的最优策略为：

如图6所示。

图6 s时Agent分组及最优任务分配策略图

经s时刻第三波次攻击结束，剩余目标、、、也被摧毁。上述仿真过程中没有加入新的任务，UCAV在所有任务执行完毕后以编队形式返航。在整个分配策略下，系统在作战过程中总路径为3728.9m，各任务奖励值之和为5668.57。时间折扣因子时系统收益值为3889.6。

不同时间折扣因子下系统收益值不同，其变化关系如图7所示，系统收益值随值的增大由-1781.8上升至3889.6。

图7值对系统收益值的影响

6.结束语

单机层多UCAV动态协同任务分配是编队层任务分配的延续工作，这一阶段的规划具有马尔可夫属性，即任务决策与执行只与系统当前状态有关，而与历史状态无关，编队内UCAV在作战区域的任务决策具有时变性。针对这一特点，本文以马尔可夫决策过程理论为基础，建立了基于多智能体马尔可夫决策过程的动态任务分配模型，提出了一种分布式多智能体动态协同任务分配策略寻优算法，该方法以多个决策Agent和成员Agent为任务执行载体，采用分组模式按照目标收益最大原则对多个任务进行分块随机选择、迭代更新寻优。在策略寻优过程中，多个决策Agent负责策略冲突的消解。该算法与目前大多数学者所采用的集中式算法相比，具有更低的决策成本和通信成本，同时具有更高的可靠性。仿真结果表明，本文所提出的算法非常适合于解决动态协同任务分配问题。

参考文献

[1]李静茹.基于改进蚁群算法的多无人机协同路径规划研究[D].徐州:中国矿业大学,2020.

[2]姚兴虎.非中心化多智能体强化学习中的协作算法研究[D].南京:南京航空航天大学,2021.

[3]李士波.基于动态环境的多无人机协同攻击路径规划[J].电脑知识与技术，2018,14(01):242-245.

[4]Philp R. Chandler, Meir Pachter, Complexity in UAV Cooperative Control[C].Proceedings of the

American Control Conference. Anchorage. AK. 2002.05:1831-1836

[5]李月娟,吕永健,常迁臻,朱李云.基于MMDP的无人作战飞机任务分配模型研究[J].计算机应用与软件,2013,30(07):276-279+286.

[6]李湘清,孙秀霞,夏岩.Multi Agent动态分组模型用于多无人机协同任务分配[J].系统仿真学报,2010,22(05):1266-1269.