LILaC - paper abstract

Planning as abduction

Herzig, Andreas and Marquis, Pierre and Lang, Jérôme


We show that while planning in deterministic domains with a fixed horizon can be encoded as a satisfiability problem, assuming that actions are nondeterministic leads to a more complex problem, whose complexity (in the general case) makes a polynomial translation into a satisfiability problem impossible (under the standard assumptions of complexity theory). We show that a logical operation which suits well to planning under incomplete knowledge is abduction. We study the problem successively in the cases where the environment is unobservable and fully observable.


PostScript, gzipped


@InProceedings{ HeLaMaWsIjcai01,
author    = {Herzig, Andreas and Lang, Jérome and Marquis, Pierre},
title     = "{Planning as abduction}",
booktitle = {IJCAI'01 Workshop on Planning under Uncertainty, Seattle},
year      = {2001},
month     = aug,
pages     = {},