Title: Multi-Agent Planning with Planning Graph
Authors: The Duy Bui, Parlevink Group, University of Twente;
   Wojciech Jamroga, Parlevink Group, University of Twente, and Institute of Mathematics, University of Gdansk

In this paper, we consider planning for multi-agents situations in STRIPS-like domains with planning graph. Three possible relationships between agents' goals are considered in order to evaluate plans: the agents may be collaborative, adversarial or indifferent entities. We propose algorithms to deal with each situation. The collaborative situations can be easily dealt with the original Graphplan algorithm by redefining the domain in a proper way. Forward-chaining and backward chaining algorithms are discussed to find infallible plans in adversarial situations. In case such plans cannot be found, the agent can still attempt to find a plan for achieving some part of the goals. A forward-chaining algorithm is also proposed to find plans for agents with independent goals.

Keywords: multiagent systems, planning in STRIPS-like domains, planning graph, collaborative planning, adversarial planning best defense.

Computational Intelligence Group @ Technical University of Clausthal Home
Human Media Interaction Group @ University of Twente
Computer Science Group @ University of Gdansk Last modified 2003-05-08