Applying search based probabilistic inference algorithms to probabilistic conformant planning: Preliminary results

Abstract

Probabilistic conformant planning problems can be solved by probabilistic inference algorithms after translating their PPDDL specifications into graphical models. We present two translation schemes that convert probabilistic conformant planning problems as graphical models. The first encoding is based on the probabilistic extension of the serial encoding of PDDL in SatPlan, and the second encoding compiles a graphical model from the finite-domain representation of the SAS+ formalism. We show that a probabilistic conformant plan can be found by answering a marginal MAP inference, and the plan is optimal with respect to the length of the plan as well as the probability of achieving the goal. Since a common task of the conformant planning is to find a plan achieving the goal with a probability that exceeds a threshold, we can consider relaxing of the marginal MAP query to the pure MAP which is far easier to compute. The success probability of the suboptimal plan derived by a pure MAP solver can be re-evaluated by solving a summation problem, also a hard task. The probabilistic inference algorithms for marginal MAP that we evaluated are based on anytime AND/OR branch and bound search guided by weighted mini-bucket heuristics. Our preliminary evaluation highlights the potential and the challenges in this methodology of applying search based probabilistic inference algorithms to probabilistic conformant planning.