Computing higher order exclusion relations in propositional planning
This article presents a systematic and complete algorithm to compute all higher order exclusion relations for a propositional planning problem, that is, sets of propositions that cannot hold simultaneously at specific time points, without any bound on the order of the exclusion
relations. This algorithm is proved to allow for backtrack-free plan extraction, provided that all goals have to be achieved simultaneously. In particular, levelled global consistency is achieved, i.e. all exclusion relations between propositions within each time step are computed.
However, achieving levelled global consistency is impractical for most non-trivial planning problems. Indeed, as our empirical evaluation over a variety of planning problems suggests, best performance is achieved when setting a bound on the order of the computed exclusion relations and using
search to extract a plan. Additional statistics extracted from our experiments shed light on the internal dynamics of Graphplan-style planners.
Keywords: Graphplan; consistency; exclusion relations; propositional planning
Document Type: Research Article
Affiliations: Department of Applied Informatics,University of Macedonia, Egnatia str. 156Thessaloniki 54006, Greece
Publication date: 01 March 2013
- Editorial Board
- Information for Authors
- Subscribe to this Title
- Ingenta Connect is not responsible for the content or availability of external websites
- Access Key
- Free content
- Partial Free content
- New content
- Open access content
- Partial Open access content
- Subscribed content
- Partial Subscribed content
- Free trial content