  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.
