Abstract

We introduce planning games, a study of interac-tions of self-motivated agents in automated plan-ning settings. Planning games extend STRIPS-like models of single-agent planning to systems of mul-tiple self-interested agents, providing a rich class of structured games that capture subtle forms of local interactions. We consider two basic models of plan-ning games and adapt game-theoretic solution con-cepts to these models. In both models, agents may need to cooperate in order to achieve their goals,but are assumed to do so only in order to increase their net benefit. For each model we study the com-putational problem of finding a stable solution and provide efficient algorithms for systems exhibiting acyclic interaction structure