Pathological Dependency Cycles in State-Space Planning: When control rules fail

Pathological dependency cycles occur in state-space planners when control structures cannot efficiently determine a maximal matching for a bipartite operator/binding graph. Without proper search control, the planner will require many computationally expensive backtracks to arrive at a solution. We present a method for improving planning efficiency in the midst of pathological dependency cycles by employing informed resource reallocation in lieu of uninformed backtracking. Empirical studies demonstrate significant improvement in search effort when search control is employed in backtracking. Existing theoretical results suggest that some form of informed resource re-allocation can be used to produce an approximately O(n 2.5) solution for many pathological domain classes, as opposed to the O(k n) solution produced in uninformed backtracking