Projection Global Consistency: An Application in AI Planning

Abstract. We are dealing with solving planning problems by the GraphPlan algorithm. We concentrate on solving a problem of finding supporting actions for a goal. This problem arises as a sub-problem many times during search for a solution. We showed in the paper that the supports problem is NP-complete. In order to improve the solving process of the supports problems we proposed a new global consistency technique which we call projection consistency. We present a polynomial algorithm for enforcing projection consistency. The projection consistency was implemented within our experimental planning system which we used for empirical evaluation. The empirical tests showed improvements in order of magnitudes compared to the standard GraphPlan (both in time and number of constraint checks). A significant improvement was also reached compared to the recent similar technique based on maintaining of arc-consistency