  This paper proposes FMAP (Forward Multi-Agent Planning), a fully-distributed
multi-agent planning method that integrates planning and coordination. Although
FMAP is specifically aimed at solving problems that require cooperation among
agents, the flexibility of the domain-independent planning model allows FMAP to
tackle multi-agent planning tasks of any type. In FMAP, agents jointly explore
the plan space by building up refinement plans through a complete and flexible
forward-chaining partial-order planner. The search is guided by $h_{DTG}$, a
novel heuristic function that is based on the concepts of Domain Transition
Graph and frontier state and is optimized to evaluate plans in distributed
environments. Agents in FMAP apply an advanced privacy model that allows them
to adequately keep private information while communicating only the data of the
refinement plans that is relevant to each of the participating agents.
Experimental results show that FMAP is a general-purpose approach that
efficiently solves tightly-coupled domains that have specialized agents and
cooperative goals as well as loosely-coupled problems. Specifically, the
empirical evaluation shows that FMAP outperforms current MAP systems at solving
complex planning tasks that are adapted from the International Planning
Competition benchmarks.
