SSPOP: A State Space Partial-Order Planner

摘要

This paper presents a new planner for STRIPS-style problems, named State-Space Partial-Order Planner. (SSPOP). This planner is a hybrid one, since it com-bines state-space search, the reduced search-space feature of the partial-order planners and heuristic search guided by a domain-independent algorithm. Using local search techniques, SSPOP discovers groups of plans that are equivalent re-orderings of a set of actions and keeps one plan of each group for further exploration. Moreover, additional checks detect and eliminate plans with redundant actions. Finally, SSPOP has been enhanced with Greedy Regression Tables (GRT), a domain-independent heuristic algorithm that estimates distances between intermediate states and the goal. SSPOP has been implemented in PROLOG and has been tested in several domains, being quite competitive against other known planners, like SATPLAN, BLACKBOX and HSP, in terms of solution time and length.