Efficient approaches for multi-agent planning Articles uri icon

publication date

  • February 2019

start page

  • 425

end page

  • 479

issue

  • 2

volume

  • 58

international standard serial number (ISSN)

  • 0219-1377

electronic international standard serial number (EISSN)

  • 0219-3116

abstract

  • Multi-agent planning (MAP) deals with planning systems that reason on long-term goals by multiple collaborative agents which want to maintain privacy on their knowledge. Recently, new MAP techniques have been devised to provide efficient solutions. Most approaches expand distributed searches using modified planners, where agents exchange public information. They present two drawbacks: they are planner-dependent; and incur a high communication cost. Instead, we present two algorithms whose search processes are monolithic (no communication while individual planning) and MAP tasks are compiled such that they are planner-independent (no programming effort needed when replacing the base planner). Our two approaches first assign each public goal to a subset of agents. In the first distributed approach, agents iteratively solve problems by receiving plans, goals and states from previous agents. After generating new plans by reusing previous agents' plans, they share the new plans and some obfuscated private information with the following agents. In the second centralized approach, agents generate an obfuscated version of their problems to protect privacy and then submit it to an agent that performs centralized planning. The resulting approaches are efficient, outperforming other state-of-the-art approaches.

keywords

  • multi-agent planning; automated planning; privacy-preserving planning; distributed planning; centralized planning; complexity; algorithms; protocol; privacy