| 引用本文: | 张国富,宋晓晓,苏兆品,岳峰.面向任务的重叠联盟结构生成计算复杂性[J].控制理论与应用,2024,41(1):163~171.[点击复制] |
| ZHANG Guo-fu,Song Xiaoxiao,Su Zhaopin,Yue Feng.On the computational complexity of task-oriented overlapping coalition structure generation[J].Control Theory and Technology,2024,41(1):163~171.[点击复制] |
|
| 面向任务的重叠联盟结构生成计算复杂性 |
| On the computational complexity of task-oriented overlapping coalition structure generation |
| 摘要点击 1081 全文点击 1668 投稿时间：2021-12-09 修订日期：2023-10-08 |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| DOI编号 10.7641/CTA.2022.11203 |
| 2024,41(1):163-171 |
| 中文关键词 多智能体系统 重叠联盟结构生成 计算复杂性 成功性判别 流网络 |
| 英文关键词 multi-agent systems overlapping coalition structure generation computational complexity success check flow network |
| 基金项目 安徽省重点研究与开发计划项目(202004d07020011, 202104d07020001), 广东省类脑智能计算重点实验室开放课题项目(GBL202117), 中央高校 基本科研业务费专项资金项目(PA2021GDSK0073, PA2021GDSK0074)资助. |
|
| 中文摘要 |
| 传统的重叠联盟形成问题大都聚焦智能体, 鲜有从任务视角出发. 为此, 本文首先构建了一种面向任务的
重叠联盟结构生成模型, 并分析了其解空间和相关决策问题的计算复杂性. 此外, 基于流网络分别设计了相应的孤
立联盟、重叠联盟、重叠联盟结构成功性判别算法和最优重叠联盟结构生成算法. 分析结果表明, 判别孤立联
盟、重叠联盟、重叠联盟结构的成功性的时间复杂度均与智能体数和任务数呈多项式关系, 而搜索最优重叠联盟结
构的时间复杂度与智能体数和任务数呈指数关系. 最后, 通过仿真实验验证了上述结果. |
| 英文摘要 |
| 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 nonoverlapping
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. |
|
|
|
|
|