μ-SATPLAN: Multi-agent planning as satisfiability

Abstract

Planning is a fundamental issue in multi-agent systems. In this work we focus on the coordination of multiple agents in two different settings. In the first, agents are able to attain individual goals that are necessary for the achievement of a global common goal. As the agents share the same environment, they need to find a coordinated course of action that avoids harmful (or negative) interactions, and benefit from positive interactions, whenever this is possible. In the second setting some of the agents may need the assistance of other agents to achieve their individual goals. This is the case where some of the actions of the plan of an agent may be executed by another agent who will play the role of the assistant. We formalize these two problems in a more general way than in previous works, and present a coordination algorithm which generates optimal solutions in the case of two agents. In this algorithm, agents use μ-SATPLAN as the underlying planner for generating individual and joint consistent plans. This planner is an extension of the classical SATPLAN planner, that tackles negative and positive interactions and, therefore, multi-agent planning. We also present an algorithm that solves the assistance problem. The underlying algorithm is again μ-SATPLAN, and is used for the generation of individual (based on assistance) and joint consistent plans. Finally experimental results on multi-agent versions of problems taken from International Planning Competitions demonstrate the effectiveness of μ-SATPLAN and the coordination algorithm. © 2011 Elsevier B.V. All rights reserved.