- Abstract:
- 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
- @InProceedings{EDI-INF-RR-1104,
- 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},
- }
|
