Please use this identifier to cite or link to this item:
Title: Computing higher order exclusion relations in propositional planning
Authors: Refanidis, Ioannis
Sakellariou, Ilias
Type: Article
Subjects: FRASCATI::Natural sciences::Computer and information sciences
Keywords: propositional planning
exclusion relations
Issue Date: 2013
Publisher: Taylor & Francis
Source: Journal of Experimental & Theoretical Artificial Intelligence
Volume: 25
Issue: 1
First Page: 23
Last Page: 51
Abstract: 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
Electronic ISSN: 1362-3079
Other Identifiers: 10.1080/0952813X.2012.660991
Appears in Collections:Department of Applied Informatics

Files in This Item:
File Description SizeFormat 
JETAI-Hoex-Names-revised.pdfpostprint revised655,97 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.