Planning as abduction

International audienceWe 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