Landmarks Revisited

Abstract

Landmarks for propositional planning tasks are variable as-signments that must occur at some point in every solution plan. We propose a novel approach for using landmarks in planning by deriving a pseudo-heuristic and combining it with other heuristics in a search framework. The incorpo-ration of landmark information is shown to improve success rates and solution qualities of a heuristic planner. We fur-thermore show how additional landmarks and orderings can be found using the information present in multi-valued state variable representations of planning tasks. Compared to pre-viously published approaches, our landmark extraction algo-rithm provides stronger guarantees of correctness for the gen-erated landmark orderings, and our novel use of landmarks during search solves more planning tasks and delivers con-siderably better solutions.