异构多智能体系统协同任务规划研究初探

摘要：文章探讨了云环境下异构多智能体系统协同任务规划国内外相关技术研究、共性技术和算法框架，针对云环境下异构多智能体系统协同任务规划算法在应用效果、类型、实时响应及效率等方面的问题，展望了异构多智能体系统协同任务规划研究中面临的技术难题。

关键词：多智能体；任务规划；云计算

中图分类号：TP391 文献标识码：A

文章编号：1009-3044（2024）31-0018-03

开放科学（资源服务）标识码（OSID） ：

0 引言

多智能体系统已成为人工智能领域的前沿研究方向之一。多智能体系统（Multi-Agent System，MAS） 是一种全新的分布式计算技术，是由在环境中交互的多个智能体组成的计算系统。近年来，研究者广泛深入地研究了自然界中蜂群筑巢、鸟群迁徙、蚁群搬运和兽群围猎等生物集体行为，通过研究生物集体协作行为，为智能体和多智能体系统的模型、概念及理论提供借鉴和启发。多智能体系统产生于20世纪70年代，由分布式人工智能演化而来。随着信息科技的飞速发展，近年来，多智能体系统已取得长足发展，且被人工智能与计算机科学的众多研究领域广泛应用于求解复杂问题。多智能体系统的研究旨在将复杂的大系统构建为小型、易于管理的系统，这些小系统能够相互通信和协调，用于解决大规模的、复杂的现实问题。由于具有较好的实用性和可扩展性强等突出特点，其广泛应用在多机器人协作、协同决策系统、协同作战系统、分布式控制、数据挖掘、虚拟现实等领域，已成为人工智能领域最前沿的学科研究方向之一。

1 国内外相关技术研究

多智能体协同任务规划根据智能体的位置、环境因素及能力约束，为多智能体执行多目标任务制定最佳规划方案和路径，通过协同实现多智能体之间的优势互补，提高整体效能。一般而言，多智能体协同任务规划包括任务分配模型建立及算法求解、路径规划及算法求解。近年来，国内外学文献库中大量研究了关于多智能体协同任务规划算法方面。

1.1 多智能体任务模型研究

任务分配的具体问题众多，主要有多旅行商问题、机车路径问题、混合整数线性规划问题[1-3]。文献[4]建立了CVRP 模型，将智能体载荷约束加入了模型。文献[5]建立了CMTAP模型，将执行时间、时序、协同约束等加入了模型。文献[6]基于CMTAP模型，将动态任务和智能体执行任务能力等约束加入了模型，建立了扩展分配模型。

1.2 多智能体任务分配研究

模型建立后，关键步骤是任务分配。主要的方式为传统式和启发式两种。文献[7]针对具有优先约束的多目标、多任务的智能体任务分配问题，提出了分支价格优化的列生成方法。文献[8]针对防空任务中的多智能体任务分配问题，提出了混合整数线性规划方法。文献[9]针对智能体协同任务分配问题，采用了蚁群算法。文献[10]针对多智能体的任务分配问题，采用了树搜索算法。

1.3 多智能体任务动态重分配研究

多智能体任务动态重分配，即在故障或取消任务等紧急或突发状况时，对原任务分配进行动态调整。

文献[11]提出一种基于监督的顺序拍卖机制，应用于解决多智能体任务重分配问题。文献[12]提出了两种动态任务再分配算法，应用于多智能体森林灭火并实践检验算法效果。文献[13]提出了初步分组与组内任务分配思路，采用了改进的K均值聚类算法和分合粒子群优化算法。文献[14]提出了一种多智能体时间敏感任务动态分配算法，应用在智能体编队结构下，且充分考虑了时间窗口对智能体编队执行当前任务后续时敏目标任务的影响。

1.4 多智能体算法优化研究

任务分配完成后，设计具体算法进行求解并检验，检验效果靠算法。目前，主要算法有最优化方法和启发式方法两种。匈牙利算法是一种最常用的最优化算法之一，文献[15]采用了匈牙利算法，为多智能体目标分配问题提供了解决方案。文献[16]采用了蚁群算法，应用在求解多约束条件下的多智能体任务规划中，文献[17]采用了改进的蚁群算法，对蚁群信息素更新规则进行重定义，应用在多智能体任务规划中。

2 多智能体系统协作共性技术

协同规划已成为多智能体系统协作的三大关键共性技术之一。多智能体系统是用多个相对简单的个体构建复杂系统群体进行研究，其关键为以下三方面：一是环境的感知与学习，二是彼此间的协调与协作，三是任务完成的能力和效率。多智能体系统是人工智能最重要的技术之一，其包含的协同协调、交互通信、协作机制等智能行为在软件开发、智能交通管理、智能制造系统等诸多领域广泛运用。多智能体系统协作最关键的三大共性技术分别是：协同感知、协同规划和协同控制。在多智能体系统中，单个智能体在环境中分散开，它们可通过合作、竞争或部分组合等方式并行地完成目标任务。协同任务规划是对最优决策/路线/动作的求取，其本质是对状态空间的搜索求解。其利用分布式原理进行求解具有三大优点：一是有效提高了问题的解决效率，增强了个体隐私性。二是减少了信息的传递开销，降低了系统负荷。三是增强了系统的鲁棒性。协同规划已成为多智能体系统协作最关键的共性技术之一。

3 多智能体协同任务规划算法框架

云环境下的异构多智能体协同任务规划算法已成为多智能体研究的热点。近年来，云计算迅速发展成为IT领域技术热点，集并行计算、分布式计算、网格计算及虚拟化等技术的优点于一身，已被公认为是下一代计算的基础设施。随着智能设备的发展进步和技术需求，加之云计算服务的类型更丰富，应用更广泛，功能也更强大，其有着非常巨大的未来发展空间。云计算有低成本、灵活性、可伸缩性、安全性、可靠性、多租户、自适应性和提供服务等诸多特点，为满足多智能体系统的日益增长的计算需求，是解决多智能体系统日益增长的计算需求的现实途径。同时，通过云中的多智能体的资源共享与协作，使得系统在资源配置、任务协作及服务质效等方面获得有效的管理和性能优化，可以进行协同任务规划来完成复杂功能，多智能体系统的云计算框架如图1所示。

多智能体系统可分为同构多智能体系统和异构多智能体系统，其具备分布式、自主性强、协调性好、效率高、开发成本低、鲁棒性强等优势。多智能体系统主要研究多智能体的协作，实质是每个智能体在协作过程中的交互学习过程。通常使用贝叶斯学习和强化学习方法对智能体数量、结构、类型、协同策略等内容进行学习。智能体协作问题求解的目的是使得每个智能体之间能够合理有效地合作，通过协调保证效率和公平。多智能体系统的基本结构如图2所示。

云环境下异构多智能体协同任务规划算法研究具有重要意义。协同任务规划算法，使智能体系统的任务规划更加合理且高效。协同任务规划算法，是多智能体系统完成任务的关键。通过对智能体协同任务规划问题建模将任务规划问题转化为一个优化问题。在综合考虑智能体资源能力和任务要求的基础上，对多智能体系统资源进行有效地分配与调度，制订合理的任务计划，充分利用有限的系统资源，最大限度地完成系统的目标任务。多智能体协同任务规划问题本质上仍是NP问题的求解。因此，其模型的建立和算法的使用则是求解关键。智能体任务规划模型具有众多约束条件，使用算法求解智能体系统任务规划模型是一个具有挑战性的课题，也是学术界的研究热点。

协同任务规划算法，使智能体之间的沟通机制更加健全且有效。随着多智能体系统场景的日益增多，单智能体向多智能体发展面临通信技术及沟通机制等问题。多智能体系统有大量的信息，研究减少智能体之间的资源消耗和信息交互，增加多智能体系统的自适应能力，是当前的技术热点。近年来研究人员将关注的焦点投入多智能体的算法研究，达到使智能体之间的相互协同配合的策略，解决通信机制建立方法所面临泛化性能的挑战。尤其是在多智能体环境中，状态信息是部分可观测的，智能体数量是动态变化的，要解决这些难题的有效方法之一就是通过协同任务规划算法在智能体之间互相建立沟通机制。

协同任务规划算法，使智能体系统的决策能力更加科学且智效。未来，推理系统将从“面向信息”到“智能自主”，以探索新的思想和方法进行智能自主行为、渗透和实现预定的目标。但是，多智能体系统研究以及目前的知识框架仍然存在着不够精细、应用粗糙等问题，这就为协同任务规划算法理论及应用带来深度研究空间。任务类型、时序约束、智能体执行任务类型和能力差异等因素，须在任务分配过程中充分考虑，合理地将任务分配给智能体，目标为满足整体任务完成及效率达到最优。关键是任务分配模型的建立和分配算法的使用。由此，将多智能体系统与分布式约束优化问题进行融合，依据多智能体建立系统模型进行研究，采用分布式约束优化算法进行计算，即可在满足实时性需要的前提下，获得相对完备的最优化方案以供智能体系统决策。多智能体系统在军事、生产和生活的各个方面，都取得了极大的效益并解决了很多以前难以有效解决的复杂问题。行业的迅速发展，使得协同任务规划算法在多智能体系统中的应用具有很重要的应用价值和广阔的发展前景。

4 展望

针对多智能体协同任务规划问题，研究人员在多智能体系统建模和算法应用等主要研究方向上取得了大量研究成果。但是，从应用效果改进和技术发展的角度看，仍然存在以下4个方面的问题：1） 算法中简约化处理的目标任务和约束条件，使实际应用效果欠佳。2） 智能体和规划任务相对单一，对异构体和多任务考量不多，降低了复杂度。3） 现有的某些任务规划算法计算结果准确但是时间代价过大，实时性不强，不具备对突发情况的响应能力。4） 大多算法在面对动态环境变化增加的系统不确定性时，算法的实时性不足。如何在云环境中实现不同类型、不同能力智能体的协同任务规划，最大限度地利用多智能体系统资源，成为其中的核心和关键问题。

随着人工智能的发展，深度强化学习的决策能力和深度卷积神经的感知能力为许多悬而未决的问题提供新的视角和优异的解决方案。特别是，深度强化学习算法已被证明能够解决以前具有高维状态和动作空间的棘手的决策问题。

参考文献：

[1] 杨杰，席建祥，王成，等.多无人机协同巡视任务规划方法综述[J].飞行力学，2018，36（5）：1-6.

[2] 高扬.基于智能优化算法的无人机任务规划[D].南京：南京邮电大学，2019.

[3] CAI J L，ZHANG N.Mixed integer nonlinear programming foraircraft conflict avoidance by applying velocity and altitudechanges[J].Arabian Journal for Science and Engineering，2019，44（10）：8893-8903.

[4] ZORLU O.Routing unmanned aerial vehicles as adapting to ca⁃pacitated vehicle routing problem with genetic algorithms[C]//2015 7th International Conference on Recent Advances inSpace Technologies （RAST）.June 16-19，2015.Istanbul，Turkey.IEEE，2015：675-679.

[5] JIA Z Y，YU J Q，AI X L，et al.Cooperative multiple task assign⁃ment problem with stochastic velocities and time windows forheterogeneous unmanned aerial vehicles using a genetic algo⁃rithm[J].Aerospace Science and Technology，2018，76：112-125.