Interaction Graphs for Planning Problem Decomposition

摘要

Most of the research in distributed planning so far is about important issues of cooperation, communication, coordination and negotiation among agents. Problem decomposition is one of the key problems in distributed planning. Current distributed planners do not use general and effective automatic problem decomposition techniques. In this paper we showed how interaction graphs can be used to decompose problems effectively. Interaction Graphs can be constructed in low order polynomial time. We showed how distributed planners can use decompositions based on interaction graphs. Experimental results which show that distributed planners using IG-based decomposition are significantly faster than centralized planners are reported in [Iwen & Mali 2002].