Tractable Classes of a Problem of Finding Supporting Actions for a Goal in AI Planning

We are studying tractable classes of a problem of finding supporting actions for a goal using projection global consistency. The projection consistency is a recent technique designed to prune the search space along the search for supports for a sub-goal in AI planning context. The problem of finding supporting actions for a sub-goal (briefly supports problem) is exactly what the GraphPlan planning algorithm must solve many times during plan extraction from the planning graph. The supports problem was shown to be NP-complete. We found that there exist tractable instances of the problem. We define a special intersection graph according to the supports problem. We showed that if the intersection graph is acyclic then the supports problem can be solved in polynomial time by using projection consistency. On this basis we propose a heuristic which prefers tractable cases of the problem and we integrate it into our experimental planning system written in C++. The performed experiments showed that preference of tractable cases bring significant improvement in the number of backtracks as well as in the overall solving time