Extending SATPLAN to multiple agents

Abstract

Multi-agent planning is a core issue in the multi-agent systems field. In this work we focus on the coordination of multiple agents in a setting where agents are able to achieve individual goals that may be either independent, or necessary for the achievement of a global common goal. The agents are able to generate individual plans in order to achieve their own goals, but, as they share the same environment, they need to find a coordinated course of action that avoids harmful (or negative) interactions, and benefits from positive interactions, whenever this is possible. Moreover, agents are interested in finding plans with optimal length where preference is given to the length of the joint plan. We formalize these problems in a more general way with respect to previous works and present a coordination algorithm which provides the optimal solution 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 well known classical planner SATPLAN, aiming to deal with negative and positive interactions and, therefore, with multi-agent planning problem. Finally we present the experimental results using the multi-agent planning problems from the domains proposed and used in classical planning, which demonstrate the effectiveness of μ-SATPLAN and the coordination algorithm. © 2011 Springer-Verlag London Limited.