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 algor...

Full description

Saved in:
Bibliographic Details
Published in:Journal of experimental & theoretical artificial intelligence 2013-03, Vol.25 (1), p.23-51
Main Authors: Refanidis, Ioannis, Sakellariou, Ilias
Format: Article
Language:English
Subjects:
Algorithms
Artificial intelligence
Computation
Consistency
Dynamics
exclusion relations
Expert systems
Extraction
Graphplan
Planning
propositional planning
Statistics
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0952-813X
1362-3079
DOI:10.1080/0952813X.2012.660991