# Planning Graph Heuristics For Belief Space Search

Daniel Bryce DAN.BRYCE@ASU.EDU Subbarao Kambhampati, RAO@ASU.EDU
Department of Computer Science and Engineering Ira A. Fulton School of Engineering Arizona State University, Brickyard Suite 501 699 South Mill Avenue, Tempe, AZ 85281 David E. Smith DE2SMITH@EMAIL.ARC.NASA.GOV
NASA Ames Research Center Intelligent Systems Division, MS 269-2 Moffett Field, CA 94035-1000

## Abstract

Some recent works in conditional planning have proposed reachability heuristics to improve planner scalability, but many lack a formal description of the properties of their distance estimates. To place previous work in context and extend work on heuristics for conditional planning, we provide a formal basis for distance estimates between belief states. We give a definition for the distance between belief states that relies on aggregating underlying state distance measures. We give several techniques to aggregate state distances and their associated properties. Many existing heuristics exhibit a subset of the properties, but in order to provide a standardized comparison we present several generalizations of planning graph heuristics that are used in a single planner. We compliment our belief state distance estimate framework by also investigating efficient planning graph data structures that incorporate BDDs to compute the most effective heuristics.

We developed two planners to serve as test-beds for our investigation. The first, CAltAlt, is a conformant regression planner that uses A* search. The second, **P OND**, is a conditional progression planner that uses AO* search. We show the relative effectiveness of our heuristic techniques within these planners. We also compare the performance of these planners with several state of the art approaches in conditional planning.

## 1. Introduction

Ever since CGP (Smith & Weld, 1998) and SGP (Weld, Anderson, & Smith, 1998) a series of planners have been developed for tackling conformant and conditional planning problems - including GPT (Bonet & Geffner, 2000), C-Plan (Castellini, Giunchiglia, & Tacchella, 2001), PKSPlan (Petrick & Bacchus, 2002), Frag-Plan (Kurien, Nayak, & Smith, 2002), MBP (Bertoli, Cimatti, Roveri,
& Traverso, 2001b), KACMBP (Bertoli & Cimatti, 2002), CFF (Hoffmann & Brafman, 2004), and YKA (Rintanen, 2003b). Several of these planners are extensions of heuristic state space planners that search in the space of "belief states" (where a belief state is a set of possible states). Without full-observability, agents need belief states to capture state uncertainty arising from starting in an uncertain state or by executing actions with uncertain effects in a known state. We focus on the first type of uncertainty, where an agent starts in an uncertain state but has deterministic actions.

We seek strong plans, where the agent will reach the goal with certainty despite its partially known state. Many of the aforementioned planners find strong plans, and heuristic search planners are 