A Factored Approach to Deterministic Contingent Multi-Agent Planning
A Factored Approach to Deterministic Contingent Multi-Agent Planning
复制标题
确定性应急多智能体规划的分解方法
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Guy Shani
中科院分区：
文献类型：
--
作者：
Shashank Shekhar;R. Brafman;Guy Shani
具有部分可观测性的不确定性下的协同多智能体规划（MAP）是一个非常困难的问题。这样的MAP问题通常被建模为decpomdp，或者它的定性变体QDec-POMDP，它本质上是偶然计划的MAP版本。引入QDecPOMDP模型的目的是希望其更简单的非概率结构能够提供更好的可伸缩性。事实上，至少在确定性行为方面，最近的IMAP算法比可比的DecPOMDP算法（Bazinin and Shani 2018）的可扩展性要好得多。在这项工作中，我们提出了一种基于问题分解的求解确定性qdecpomdp的新方法。首先，我们找到了MAP问题的解决方案，其中任何观察结果都可用于所有代理。这本质上是整个团队的单代理规划问题。然后，我们将解树投影到子树中，每个agent一个子树，并让每个agent将其投影树转换为合法的局部树。如果所有代理都成功，我们将这些树组合成一个有效的联合计划。否则，我们将继续探索团队解决方案的空间。这种方法是合理的、完整的，并且正如我们的经验评估所证明的那样，它比IMAP算法的可伸缩性要好得多。
Collaborative Multi-Agent Planning (MAP) under uncertainty with partial observability is a notoriously difficult problem. Such MAP problems are often modeled as DecPOMDPs, or its qualitative variant, QDec-POMDP, which is essentially a MAP version of contingent planning. The QDecPOMDP model was introduced with the hope that its simpler, non-probabilistic structure will allow for better scalability. Indeed, at least with deterministic actions, the recent IMAP algorithm scales much better than comparable DecPOMDP algorithms (Bazinin and Shani 2018). In this work we suggest a new approach to solving Deterministic QDecPOMDPs based on problem factoring. First, we find a solution to a MAP problem where the results of any observation is available to all agents. This is essentially a single-agent planning problem for the entire team. Then, we project the solution tree into sub-trees, one per agent, and let each agent transform its projected tree into a legal local tree. If all agents succeed, we combine the trees into a valid joint-plan. Otherwise, we continue to explore the space of team solutions. This approach is sound, complete, and as our empirical evaluation demonstrates, scales much better than the IMAP algorithm.