Planning in belief space with a labelled uncertainty graph

Daniel Bryce, Subbarao Kambhampati, David E. Smith

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


Planning in belief space with a Labelled Uncertainty Graph, LUG, is an approach that uses a very compact planning graph to guide search in the space of belief states to construct conformant and contingent plans. A conformant plan is a plan that transitions (without sensing) all possible initial states through possibly non-deterministic actions to a goal state. A contingent plan adds the ability to observe state variables and branch execution. The LUG provides heuristics to guide a regression belief space planner, CAltAlt, and a progression belief space planner, PBSP. The key innovation of the LUG is to compactly represent the optimistic projection of several states (those in a belief state) within a single planning graph. Labels on the actions and literals denote the state projections that include them. We show the improvements of using a LUG by comparing it with a multiple planning graphs (one for each possible world) approach within CAltAlt. We also compare the approach to other conformant planners. Lastly, we outline an algorithm that can adapt the approach to stochastic planning.

Original languageEnglish (US)
Title of host publicationAAAI Workshop - Technical Report
Number of pages6
StatePublished - 2004
Event19th National Conference on Artificial Intelligence - San Jose, CA, United States
Duration: Jul 25 2004Jul 26 2004


Other19th National Conference on Artificial Intelligence
Country/TerritoryUnited States
CitySan Jose, CA

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'Planning in belief space with a labelled uncertainty graph'. Together they form a unique fingerprint.

Cite this