Multi-Agent Planning by Plan Reuse

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 [3]. 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.

Authors

• Daniel Borrajo J.P. Morgan AI Research

Keywords

• Automated planning
• Multi-Agent Planning