Theory and Algorithms for Partial Order Based Reduction in Planning
  Search is a major technique for planning. It amounts to exploring a state
space of planning domains typically modeled as a directed graph. However,
prohibitively large sizes of the search space make search expensive. Developing
better heuristic functions has been the main technique for improving search
efficiency. Nevertheless, recent studies have shown that improving heuristics
alone has certain fundamental limits on improving search efficiency. Recently,
a new direction of research called partial order based reduction (POR) has been
proposed as an alternative to improving heuristics. POR has shown promise in
speeding up searches.
  POR has been extensively studied in model checking research and is a key
enabling technique for scalability of model checking systems. Although the POR
theory has been extensively studied in model checking, it has never been
developed systematically for planning before. In addition, the conditions for
POR in the model checking theory are abstract and not directly applicable in
planning. Previous works on POR algorithms for planning did not establish the
connection between these algorithms and existing theory in model checking.
  In this paper, we develop a theory for POR in planning. The new theory we
develop connects the stubborn set theory in model checking and POR methods in
planning. We show that previous POR algorithms in planning can be explained by
the new theory. Based on the new theory, we propose a new, stronger POR
algorithm. Experimental results on various planning domains show further search
cost reduction using the new algorithm.
