Propositional Probabilistic Planning-as-Satisfiability using Stochastic Local Search

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.