重叠联盟形成理论及应用研究

通过联盟方式实现各agent间的协调合作是复杂智能系统中的关键问题，而重叠联盟形成问题（OCF）是其中极具挑战性的前沿课题。本项目通过引入问题相关的领域知识和约束条件，在多agent系统领域开展应用基础研究，通过构建基于资源冲突的OCF模型，重点研究基于离散粒子群和冲突消解的OCF算法，从而在agent资源有限的情况下，实现各agent自由竞争任务，且能根据各agent的负荷状况明确给出各agent在各任务中的实际承担量，以从根本上杜绝资源冲突现象，同时探索OCF的效用分配策略，激励agent积极、及时合作，提高重叠联盟的稳定性和任务求解效率，并基于上述的OCF理论研究复杂供应链系统中的多任务决策问题，以验证OCF理论的有效性。此项目属于多学科交叉的应用基础研究，通过实施该项目，可以为实际复杂系统的研制和开发提供理论指导和方法依据，推动复杂系统仿真技术的发展。

通过联盟方式实现各agent间的协调合作是多agent系统（multi-agent systems, MAS）和AI领域中的一个非常重要和活跃的方向，而重叠联盟形成问题（overlapping coalition formation, OCF）是其中极具挑战性的前沿课题。本项目通过引入问题相关的领域知识和约束条件，在MAS和AI领域开展应用基础研究，主要创新成果有：（1）构建了资源受限下的OCF数学模型，并分析了其相关性质。本项目对传统OCF模型进行了扩充，提出了“临时承担量”、“剩余资源量”和“实际贡献量”等相关分量，以衡量每个agent的资源负荷状况。本项目重点分析和推理了OCF模型的计算复杂性以及各分量之间的逻辑关系，从数学层面严格清晰的刻画了发生资源冲突的条件，从而为避免资源冲突提供参考依据，为后续设计切实可行的联盟形成算法提供理论支撑。（2）提出了基于二进制粒子群优化（binary particle swarm optimization, BPSO）和冲突消解的OCF算法。本项目将BPSO扩充至二维二进制编码（每一列代表一个agent，每一行代表一个联盟），着重研究了相应的编码修正策略，既允许agent自由竞争任务，又充分考虑了各agent的资源负荷状况，且能根据各agent的资源负荷状况明确给出各agent在各个任务中的实际承担量，从而可以从根本上杜绝资源冲突现象，为后续的任务执行和效用分配提供了可靠的依据。（3）提出了一种基于讨价还价的重叠联盟效用划分策略。本项目针对OCF问题中一个agent可以同时参与多个联盟的复杂情形，依据OCF模型的若干重要性质，设计了相应的讨价还价策略和效用非减原则，既实现了多任务的快速分派和多联盟效用的公平分配，又有效避免了资源冲突，从而能够保证不会有agent脱离其所在联盟而加入其他联盟后更有利可图，维持了重叠联盟的稳定性。（4）基于上述理论和方法搭建了灾害应急管理仿真系统。本项目以灾害应急管理作为应用背景，其中应急资源分配方案的优劣直接决定了灾害救援的成功与否，对促进社会发展、保持社会稳定具有重要的现实意义。因此，本项目将上述OCF理论和方法应用到灾害应急管理中的多应急点资源分配问题，搭建了一个灾害应急管理仿真系统，从而既验证了所提OCF理论和方法的整体有效性，又为解决重大灾害的应急管理问题提供了理论指导和方法依据。