SAT-Based Parallel Planning Using a Split Representation of Actions

There are no files associated with this record.

Title SAT-Based Parallel Planning Using a Split Representation of Actions
Author Robinson, Nathan Mark; Gretton, Charles; Pham, Duc Nghia; Sattar, Abdul
Publication Title Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling (ICAPS-09)
Editor Alfonso Gerevini, Adele Howe, Amedeo Cesta and Ioannis Refanidis
Year Published 2009
Place of publication Menlo Park, California
Publisher AAAI Press
Abstract Planning based on propositional SAT(isfiability) is a powerful approach to computing step-optimal plans given a parallel execution semantics. In this setting: (i) a solution plan must be minimal in the number of plan steps required, and (ii) non-conflicting actions can be executed instantaneously in parallel at a plan step. Underlying SAT-based approaches is the invocation of a decision procedure on a SAT encoding of a bounded version of the problem. A fundamental limitation of existing approaches is the size of these encodings. This problem stems from the use of a direct representation of actions – i.e. each action has a corresponding variable in the encoding. A longtime goal in planning has been to mitigate this limitation by developing a more compact split – also termed lifted – representation of actions in SAT encodings of parallel step-optimal problems. This paper describes such a representation. In particular, each action and each parallel execution of actions is represented uniquely as a conjunct of variables. Here, each variable is derived from action pre and post-conditions. Because multiple actions share conditions, our encoding of the planning constraints is factored and relatively compact. We find experimentally that our encoding yields a much more efficient and scalable planning procedure over the state-of-the-art in a large set of planning benchmarks.
Peer Reviewed Yes
Published Yes
Publisher URI http://icaps09.icaps-conference.org/
ISBN 978-1-57735-406-2
Conference name International Conference on Automated Planning and Scheduling (ICAPS-09)
Location Thessaloniki, Greece
Date From 2009-09-19
Date To 2009-09-23
URI http://hdl.handle.net/10072/31985
Date Accessioned 2010-05-05
Date Available 2010-10-13T10:03:40Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Artificial Intelligence and Image Processing
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Brief Record

Griffith University copyright notice