首页|面向任务的重叠联盟结构生成计算复杂性

面向任务的重叠联盟结构生成计算复杂性

扫码查看
原文链接
  • 万方数据
  • 维普
传统的重叠联盟形成问题大都聚焦智能体，鲜有从任务视角出发。为此，本文首先构建了一种面向任务的重叠联盟结构生成模型，并分析了其解空间和相关决策问题的计算复杂性。此外，基于流网络分别设计了相应的孤立联盟、重叠联盟、重叠联盟结构成功性判别算法和最优重叠联盟结构生成算法。分析结果表明，判别孤立联盟、重叠联盟、重叠联盟结构的成功性的时间复杂度均与智能体数和任务数呈多项式关系，而搜索最优重叠联盟结构的时间复杂度与智能体数和任务数呈指数关系。最后，通过仿真实验验证了上述结果。
On the computational complexity of task-oriented overlapping coalition structure generation
The traditional overlapping coalition formation problems mostly focus on agents rather than tasks.In this work,a new model of task-oriented overlapping coalition structure(OCS)generation is first presented.Next,the solution space and the computational complexity of the proposed model are analyzed.Then,the checking algorithms for non-overlapping coalitions,overlapping coalitions,and OCS and the search algorithm for the optimal OCS are developed based on the flow network,respectively.The analysis results show that checking whether non-overlapping coalitions,overlapping coalitions,or OCS is successful is in time polynomial in the number of agents and tasks,but finding the optimal OCS is in time exponential in the number of agents and tasks.Finally,the simulation and experimental results demonstrate the above properties.

multi-agent systemsoverlapping coalition structure generationcomputational complexitysuccess checkflow network

张国富、宋晓晓、苏兆品、岳峰

展开 >

合肥工业大学计算机与信息学院,安徽合肥 230601

合肥工业大学智能互联系统安徽省实验室,安徽合肥 230009

合肥工业大学工业安全应急技术安徽省重点实验室,安徽合肥 230601

多智能体系统 重叠联盟结构生成 计算复杂性 成功性判别 流网络

安徽省重点研发计划安徽省重点研发计划广东省类脑智能计算重点实验室开放基金中央高校基本科研业务费专项中央高校基本科研业务费专项

202004d07020011202104d07020001GBL202117PA2021GDSK0073PA2021GDSK0074

2024

10.7641/CTA.2022.11203

控制理论与应用
华南理工大学 中国科学院数学与系统科学研究院

控制理论与应用

CSTPCD北大核心
影响因子：1.076
ISSN：1000-8152
年,卷(期)：2024.41(1)
  • 20