A Formalization of Equilibria for Multiagent Planning

Abstract

Planning has traditionally focused on single agent sys-tems. Although planning domain languages have been extended to multiagent domains, solution concepts have not. Previous solution concepts either focus on planning for teams of agents with a single goal, or on a single agent in an environment containing other agents with unknown and unpredictable behavior. In reality other agents are usually acting to achieve their own explicit goals, which may not be the same or even related. In game theory the notion of an equilibria provides a frame-work for thinking about self-interested, utility maximiz-ing agents. We define a formalization of the multiagent nondeterministic planning problem and introduce a no-tion of equilibria inspired by the game theoretic con-cept. As far as we know, this is the first solution frame-work that explicitly accounts for the various goals of all agents. In addition to the formalization we also demon-strate how this framework applies in a number of differ-ent domains.