רונן ברפמן

Search is among the most fundamental techniques for problem solving, and A* is probably the best known heuristic\nsearch 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\nplanning problem in which agents are not tightly coupled, our\nparallel version of A* leads to super-linear speedup, solving\nbenchmark problems that have not been solved before. In its\ndistributed 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.