Efficient and distributable methods for solving the multiagent plan coordination problem
Efficient and distributable methods for solving the multiagent plan coordination problem
复制标题
DOI：
10.3233/mgs-2009-0134
复制
发表时间：
2009-12
期刊：
影响因子：
--
通讯作者：
J. Cox;E. Durfee
中科院分区：
文献类型：
--
作者：
J. Cox;E. Durfee
当多个代理计划独立地实现其各自的目标时，可能需要协调，但可能通过协调他们的计划来避免交叉目的或重复工作而互惠互利。虽然在文献中已经研究了这些问题的变化，但尚未就它们的一般特征达成一致。在本文中，我们正式定义了一个共同的协调问题子类，我们称之为多智能体计划协调问题，这是丰富的，足以代表各种各样的多智能体协调问题。然后，我们描述了一个一般的框架，扩展的偏序，cabinet链接计划表示的多智能体的情况下，并将协调作为一种形式的迭代修复代理之间的计划缺陷。我们表明，这种算法配方可以扩展到多智能体的情况下，可以比现有的计划协调技术的直接应用，突出我们的算法框架和这些早期的方法之间的根本差异。然后，我们研究是否以及如何多智能体计划协调问题可以作为一个分布式约束优化问题（DCOP）。我们这样做使用ADOPT，一个国家的最先进的系统，可以解决DCOP在一个异步的，并行的方式使用本地通信之间的个别计算代理。最后，我们讨论了我们工作的可能扩展。
Coordination can be required whenever multiple agents plan to achieve their individual goals independently, but might mutually benefit by coordinating their plans to avoid working at cross purposes or duplicating effort. Although variations of such problems have been studied in the literature, there is as yet no agreement over a general characterization of them. In this paper, we formally define a common coordination problem subclass, which we call the Multiagent Plan Coordination Problem, that is rich enough to represent a wide variety of multiagent coordination problems. We then describe a general framework that extends the partial-order, causal-link plan representation to the multiagent case, and that treats coordination as a form of iterative repair of plan flaws between agents. We show that this algorithmic formulation can scale to the multiagent case better than can a straightforward application of the existing plan coordination techniques, highlighting fundamental differences between our algorithmic framework and these earlier approaches. We then examine whether and how the Multiagent Plan Coordination Problem can be cast as a Distributed Constraint Optimization Problem (DCOP). We do so using ADOPT, a state-of-the-art system that can solve DCOPs in an asynchronous, parallel manner using local communication between individual computational agents. We conclude with a discussion of possible extensions of our work.