Propositional Probabilistic Planning-as-Satisfiability using Stochastic Local Search

File Size Format
51612_1.pdf 188Kb Adobe PDF View
Title Propositional Probabilistic Planning-as-Satisfiability using Stochastic Local Search
Author Robinson, Nathan Mark; Gretton, Charles; Pham, Duc Nghia; Sattar, Abdul
Publication Title Eighteenth International Conference on Automated Planning and Scheduling - Workshop on A Reality Check for Planning and Scheduling Under Uncertainty
Editor Daniel Bryce, Mausam, Sungwook Yoon
Year Published 2008
Place of publication Menlo Park California
Publisher AAAI Press
Abstract Recent times have seen the development of a number of planners that exploit advances in SAT(isfiability) solving technology to achieve good performance. In that spirit we develop the approximate contingent planner PSLSPLAN. Our approach is based on a stochastic local search procedure for solving stochastic SAT (SSAT) representations of probabilistic planning problems. PSLSPLAN first constructs an SSAT representation of the n-time step probabilistic plangraph for the problem at hand. It then iteratively calls a stochastic local search procedure to find a linear plan (sequence of actions) which achieves the goal (i.e. satisfies the SSAT formula) with non-zero probability. Linear plans thus generated are merged to create a single contingent plan. Successive iterations progress from deciding the outcomes of stochastic actions in order to find a linear plan quickly, to sampling the outcomes of actions. Consequently, PSLSPLAN efficiently finds a linear plan which logically achieves the goal. Over time it refines its contingent plan for likely scenarios. We empirically evaluate PSLSPLAN on benchmarks from the probabilistic track of the 5th International Planning Competition.
Peer Reviewed Yes
Published Yes
Publisher URI http://www.aaai.org/Press/press.php
Alternative URI http://icaps08.cecs.anu.edu.au
Copyright Statement Copyright 2008 AAAI Press. This is the author-manuscript version of this paper. Reproduced in accordance with the copyright policy of the publisher. Use hypertext link for access to conference website.
Conference name The Eighteenth International Conference on Automated Planning and Scheduling - Workshop 5
Location Sydney, Australia
Date From 2008-09-14
Date To 2008-09-18
URI http://hdl.handle.net/10072/22578
Date Accessioned 2009-03-24
Date Available 2009-04-26T06:47:49Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Faculty of Science, Environment, Engineering and Technology
Subject PRE2009-Other Artificial Intelligence
Publication Type Conference Publications (Full Written Paper - Refereed)
Publication Type Code e1

Show simple item record

Griffith University copyright notice