Multi-agent A* for parallel and distributed systems
Multi-agent A* for parallel and distributed systems
复制标题
DOI：
--
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
Raz Nissim;R. Brafman
中科院分区：
文献类型：
--
作者：
Raz Nissim;R. Brafman
搜索是解决问题的最基本的技术之一，而A* 可能是最著名的启发式搜索算法。在本文中，我们适应A* 的多智能体设置，专注于多智能体规划问题。我们提供了一个简单的配方多代理A*，并行和分布式的变体。我们的算法利用多代理问题的结构，不仅可以有效地分配不同代理之间的工作，而且还可以消除对称性，减少整体工作量。给定一个多智能体规划问题，其中的代理不是紧密耦合的，我们的并行版本的A* 导致超线性加速，解决以前没有解决的基准问题。在其分布式版本中，该算法确保私人信息不会在代理之间共享，但计算仍然是有效的-有时甚至超过集中式搜索-尽管每个代理只能访问部分信息。
Search is among the most fundamental techniques for problem solving, and A* is probably the best known heuristic search algorithm. In this paper we adapt A* to the multiagent setting, focusing on multi-agent planning problems. We provide a simple formulation of multi-agent A*, with a parallel and distributed variant. Our algorithms exploit the structure of multi-agent problems to not only distribute the work efficiently among different agents, but also to remove symmetries and reduce the overall workload. Given a multi-agent planning problem in which agents are not tightly coupled, our parallel version of A* leads to super-linear speedup, solving benchmark problems that have not been solved before. In its distributed version, the algorithm ensures that private information is not shared among agents, yet computation is still efficient -- sometimes even more than centralized search -- despite the fact that each agent has access to partial information only.