# Vhpop: Versatile Heuristic Partial Order Planner

H˚akan L. S. Younes lorens@cs.cmu.edu Reid G. Simmons reids@cs.cmu.edu School of Computer Science, Carnegie Mellon University Pittsburgh, PA 15213, USA

## Abstract

VHPOP **is a partial order causal link (POCL) planner loosely based on** UCPOP**. It**
draws from the experience gained in the early to mid 1990's on **flaw selection strategies**
for POCL planning, and combines this with more recent developments in the field of domain independent planning such as distance based heuristics and reachability analysis. We present an adaptation of the additive heuristic for plan space planning, and modify it to account for possible reuse of existing actions in a plan. We also propose a large set of novel flaw selection strategies, and show how these can help us solve more problems than previously possible by POCL planners. VHPOP **also supports planning with durative actions**
by incorporating standard techniques for temporal constraint reasoning. We demonstrate that the same heuristic techniques used to boost the performance of classical POCL planning can be effective in domains with durative actions as well. The result is a versatile heuristic POCL planner competitive with established CSP-based and heuristic state space planners.

## 1. Introduction

During the first half of the last decade, much of the research in domain independent plan generation focused on partial order causal link **(POCL) planners. The two dominant POCL**
planners were SNLP **(McAllester & Rosenblitt, 1991) and** UCPOP **(Penberthy & Weld,**
1992), and a large part of the planning research was aimed at scaling up these two planners.

The most promising attempts at making POCL planning practical involved alternative **flaw** selection **strategies (Peot & Smith, 1993; Joslin & Pollack, 1994; Schubert & Gerevini, 1995;**
Williamson & Hanks, 1996; Pollack, Joslin, & Paolucci, 1997). A flaw in POCL planning is either an unlinked precondition (called open condition**) for an action, or a threatened causal** link. While flaw selection is not a backtracking point in the search through plan space for a complete plan, the order in which flaws are resolved can have **a dramatic effect on the**
number of plans searched before a solution is found. The role **of flaw selection in POCL**
planning is similar to the role of variable selection in constraint programming.

There have been dramatic advances in domain independent planning in the past seven years, but the focus has shifted from POCL planning to CSP-based planning algorithms
(Blum & Furst, 1997; Kautz & Selman, 1996) and state space **planning as heuristic search**
(Bonet & Geffner, 2001b; Hoffmann & Nebel, 2001). Recently, Nguyen and Kambhampati (2001) showed that with techniques such as distance based heuristics and reachability analysis—largely responsible for the efficiency of today's best domain independent planners—can also be used to dramatically improve the efficiency of POCL planners, thereby initiating a revival of this previously popular approach to **domain independent planning. We**