论文标题
为指定任务创建简单代理的团队：计算复杂性的观点
Creating Teams of Simple Agents for Specified Tasks: A Computational Complexity Perspective
论文作者
论文摘要
已经提出了相互作用和合作代理的团队，作为在各种应用中执行指定任务的整体集中控制的有效且可靠的替代方案。已经研究了许多不同的团队和代理体系结构，例如，基于单个行为赋予的代理类型（均质与异质团队），简单与复杂的代理，直接与间接代理与代理到代理通信的团队。一致认为，（1）由简单的代理组成的异质团队间接交流是可取的，并且（2）必须使用用于验证和设计此类团队的自动方法。在本文中，我们使用计算复杂性分析来评估针对各种团队的这种自动化方法的可行算法选项。在最近的复杂性分析的基础上，我们证明自动化的团队验证和设计总体上是完全和近似的多项式时间，对于最基本的类型的均质和异质团队通常都可以棘手，这些团队由简单的机构组成，这些团队由间接通信的简单代理人组成。我们的结果表明，对于这些问题的障碍性必须相对于对团队，代理，操作环境和任务的其他限制。
Teams of interacting and co-operating agents have been proposed as an efficient and robust alternative to monolithic centralized control for carrying out specified tasks in a variety of applications. A number of different team and agent architectures have been investigated, e.g., teams based on single vs multiple behaviorally-distinct types of agents (homogeneous vs heterogeneous teams), simple vs complex agents, direct vs indirect agent-to-agent communication. A consensus is emerging that (1) heterogeneous teams composed of simple agents that communicate indirectly are preferable and (2) automated methods for verifying and designing such teams are necessary. In this paper, we use computational complexity analysis to assess viable algorithmic options for such automated methods for various types of teams. Building on recent complexity analyses addressing related questions in swarm robotics, we prove that automated team verification and design are by large both exact and approximate polynomial-time intractable in general for the most basic types of homogeneous and heterogeneous teams consisting of simple agents that communicate indirectly. Our results suggest that tractability for these problems must be sought relative to additional restrictions on teams, agents, operating environments, and tasks.
