Distributed Heuristic Forward Search for Multi-Agent Systems
This addresses efficient and private planning in multi-agent systems, representing an incremental improvement over existing distributed methods.
The paper tackles multi-agent planning by introducing distributed forward search algorithms, including MAD-A*, which outperform current state-of-the-art distributed planners and sometimes centralized search while preserving agent privacy.
This paper describes a number of distributed forward search algorithms for solving multi-agent planning problems. We introduce a distributed formulation of non-optimal forward search, as well as an optimal version, MAD-A*. 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. The algorithms ensure that private information is not shared among agents, yet computation is still efficient -- outperforming current state-of-the-art distributed planners, and in some cases even centralized search -- despite the fact that each agent has access only to partial information.