A Linear Programming Heuristic for Optimal Planning

Abstract

I introduce a new search heuristic for propositional STRIPS planning that is based on transforming planning instances to linear programming instances. The linear programming heuristic is admissible for finding minimum length plans and can be used by partial-order planning algorithms. This heuristic appears to be the first non-trivial admissible heuristic for partial-order planning. An empirical study compares Lplan, a partial-order planner incorporating the heuristic, to Graphplan, Satplan, and UCPOP on the tower of Hanoi domain, random blocks-world instances, and random planning instances. Graphplan is far faster in the study than the other algorithms. Lplan is often slower because the heuristic is time-consuming, but Lplan shows promise because it often performs a small search. Introduction Planning is the problem of finding a combination of actions that achieves a goal (Allen, Hendler, & Tate 1990; Hendler, Tate, & Drummond 1990). So far, there is limited success in general-purpose...