LILaC - paper abstract


Planning as abduction

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


Abstract:

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

PostScript, gzipped


Bibtex-entry:


@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     = {},
}

							

https://www.irit.fr/~Andreas.Herzig