Multi-Agent Planning with Planning Graph

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 redening the domain in a proper way. Forward-chaining and backward chaining algorithms are discussed to nd infallible plans in adversarial situations. In case such plans cannot be found, the agent can still attempt to nd a plan for achieving some part of the goals. A forward-chaining algorithm is also proposed to nd plans for agents with independent goals.