Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:Compiling Uncertainty Away: Solving Conformant Planning Problems using a Classical Planner (Sometimes)
Authors: H Palacios ; Hector Geffner
Date: 2006
Publication Title:Proc. 20th National Conf. on Artificial Intelligence (AAAI 06)
Publisher:AAAI Press
Publication Type:Conference Paper
Page Nos:6
Even under polynominal restrictions on plan length, conformant planning remains a very hard computational problem as plan verification itself can take exponential time. This heavy price cannot be avoided in general although in many cases conformant plans are verifiable efficiently by means of simple forms of disjunctive inference. This raises the question of whether it is possible to identify and use such forms of inference for developing an efficient but incomplete planner capabale of solving non-trivial problems quickly. In this work, we show that this is possible by mapping conformant into classical problems that are then solved by an off-the-shelf classical planner. The formulation is sound as the classical plans obtained are all conformant, but it is incomplete as the inverse relation does not always hold. The translation accommodates 'reasoning by cases' by means of a 'split-protect-and-merge' strategy; namely atoms $L/X_i$ that represent conditional beliefs 'if $X_i$ then $L$' are introduce in the classical encoding that are combined by suitable actions when certain invariants are verified. Empricial results over a wide variety of problems illustrate the power of the approach.
Links To Paper
No links available
Bibtex format
author = { H Palacios and Hector Geffner },
title = {Compiling Uncertainty Away: Solving Conformant Planning Problems using a Classical Planner (Sometimes)},
book title = {Proc. 20th National Conf. on Artificial Intelligence (AAAI 06)},
publisher = {AAAI Press},
year = 2006,
pages = {6},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh