Partial Order Based Reduction in Planning: A Unifying Theory and New Algorithms

Partial order based reduction (POR) has recently attracted research in planning. POR algorithms reduce search space by recognizing interchangable orders between actions and expanding only a subset of all possible orders during the search. POR has been extensively studied in model checking and proved to be an enabling technique for reducing the search space and costs. Recently, two POR algorithms, including the expansion core (EC) and stratified planning (SP) algorithms, have been proposed. Being orthogonal to the development of accurate heuristic functions, these reduction methods show great potential to improve the planning efficiency from a new perspective. However, it is unclear how these POR methods relate to each other and whether there exist stronger reduction methods. We propose a unifying theory for POR. The theory gives a necessary and sufficient condition for two actions to be semi-commutative, a condition that enables POR. We interpret both EC and SP in the theoretical framework. Further, based on the new theory, we propose new, stronger POR algorithms. Experimental results on various planning domains show significant search cost reduction