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 @math , 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.
Finally, MAPR is a recent planner that performs goal allocation to each agent @cite_20 . Agents iteratively solve the assigned goals by extending the plan of the previous agent. In this approach, agents work under limited knowledge of the environment by obfuscating the private information in their plans. MAPR is particularly effective for loosely-coupled problems, but it cannot deal with tasks that feature specialized agents and cooperative goals since it assumes that each goal is achieved by a single agent. Section will show a comparative performance evaluation between MAPR and FMAP, our proposed approach.
@cite_20
2394593764
Generating plans for a single agent has been shown to be a difficult task. If we generalize to a multi-agent setting, the problem becomes exponentially harder in general. The centralized approach where a plan is jointly generated for all agents is only possible in some applications when agents do not have private goals, actions or states. We describe in this paper an alternative approach, MAPR (Multi-Agent Planning by plan Reuse), that considers both the agents private and public information. We have been inspired by iterative Multi-Agent Planning (MAP) techniques as the one presented in [1]. MAPR first assigns a subset of public goals to each agent, while each agent might have a set of private goals also. Then, MAPR calls the first agent to provide a solution (plan) that takes into account its private and public goals. MAPR iteratively calls each agent with the solutions provided by previous agents. Each agent receives its own goals plus the goals of the previous agents. Thus, each agent solves its problem, but taking into account the previous agents solutions. Since previous solutions might consider private data, all private information from an agent is obfuscated for the next ones. Since each agent receives the plan from the previous agent that implicitly considers the solutions to all previous agents, instead of starting the search from scratch, it can also reuse the previous whole plan or only a subset of the actions. Experiments show that MAPR outperforms in several orders of magnitude state-of-the-art techniques in the tested domains.