LPSP: A Linear Plan-Level Stochastic Planner

Ronen I. Brafman
Department of Math and Computer Science
Ben-Gurion University
Beer Sheva, ISRAEL 84105
email: brafman@cs.bgu.ac.il

Holger H. Hoos
Department of Computer Science
Darmstadt University of Technology
D-62483 Darmstadt, GERMANY
email: hoos@informatik.tu-darmstadt.de

Craig Boutilier
Department of Computer Science
University of British Columbia
Vancouver, BC, CANADA, V6T 1Z4
email: cebly@cs.ubc.ca

We describe LPSP, a domain-independent planning algorithm that searches the space of linear plans using stochastic local search techniques. Because linear plans, rather than propositional assignments, comprise the states of LPSP's search space, we can incorporate into its search various operators that are suitable for manipulating plans, such as plan-step reordering based on action dependencies, and limited forward/backward search. This, in turn, leads to a flexible planning algorithm that outperforms the SATPLAN planner on difficult blocks world problems.

Submitted, 1998

Return to List of Papers