On the complexity of planning for agent teams and its implications for single agent planning
On the complexity of planning for agent teams and its implications for single agent planning
复制标题
关于代理团队规划的复杂性及其对单个代理规划的影响
DOI：
10.1016/j.artint.2012.08.005
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Carmel Domshlak
中科院分区：
文献类型：
--
作者：
R. Brafman;Carmel Domshlak
如果单个代理的规划复杂性由输入的某个函数 f 来描述，那么为 n 个合作代理组成的团队进行规划要困难多少？如果这些智能体完全独立，我们可以简单地解决 n 个单智能体问题，并随智能体数量线性扩展。但如果所有智能体紧密交互，我们确实需要解决一个大 n 倍的问题，这可能会以指数级（以 n 为单位）难以解决。是否可以进行更一般的表征？为了精确地表述这个问题，我们最小限度地扩展了标准 STRIPS 模型来描述多智能体规划问题。然后，我们确定两个问题参数来帮助我们回答问题。第一个参数与多智能体系统应该规划的精确任务无关，它通过团队生成的图的树宽来捕获智能体之间可能的直接交互的结构。第二个参数与任务相关，它捕获团队中“交互最多”代理解决问题所需的最少交互次数。我们证明，多智能体规划问题只能在这些参数下以时间指数方式解决。因此，当这些参数有界时，复杂性仅与代理团队的规模成多项式缩放。这些结果对单智能体情况也有直接影响：通过将单智能体规划任务转换为多智能体规划任务，我们可以为单智能体设计基于分解的规划的新方法。我们分析了一种这样的方法，并使用所开发的技术为经典的单智能体规划提供了迄今为止最强的易处理结果。
If the complexity of planning for a single agent is described by some function f of the input, how much more difficult is it to plan for a team of n cooperating agents? If these agents are completely independent, we can simply solve n single agent problems, scaling linearly with the number of agents. But if all the agents interact tightly, we really need to solve a single problem that is n times larger, which could be exponentially (in n) harder to solve. Is a more general characterization possible? To formulate this question precisely, we minimally extend the standard STRIPS model to describe multi-agent planning problems. Then, we identify two problem parameters that help us answer our question. The first parameter is independent of the precise task the multi-agent system should plan for, and it captures the structure of the possible direct interactions between the agents via the tree-width of a graph induced by the team. The second parameter is task-dependent, and it captures the minimal number of interactions by the “most interacting” agent in the team that is needed to solve the problem. We show that multi-agent planning problems can be solved in time exponential only in these parameters. Thus, when these parameters are bounded, the complexity scales only polynomially in the size of the agent team. These results also have direct implications for the single-agent case: by casting single-agent planning tasks as multi-agent planning tasks, we can devise novel methods for decomposition-based planning for single agents. We analyze one such method, and use the techniques developed to provide some of the strongest tractability results for classical single-agent planning to date.