Heuristic multiagent planning with self-interested agents

The focus of multiagent planning research has recently turned towards domains with self-interested agents leading to the definition of Coalition--Planning Games (CoPGs). In this paper, we investigate algorithms for solving a restricted class of "safe" CoPGs, in which no agent can benefit from making another agent's plan invalid. We introduce a novel, generalised solution concept, and show how problems can be translated so that they can be solved by standard single--agent planners. However, standard planners cannot solve problems like this efficiently. We then introduce a new multiagent planning algorithm and the benefits of our approach are illustrated empirically in an example logistics domain.