Abstract
Probabilistic conformant planning is a task of finding a plan that achieves the goal without sensing, where the outcome of an action is probabilistic and the initial state is uncertain. In this thesis, we formulate the probabilistic conformant planning as marginal Maximum A Posteriori (MAP) probabilistic inference based on the finite horizon state transition model. In practice, most of the planning problems are expressed in Probabilistic Planning Domain Definition Languag. Therefore, we developed a translation that reads a PPDDL instance and compiles the instance into a graphical model to provide a planning problem to existing marginal MAP solvers. The compilation is based on SAT encoding of planning problems, and the encoding is extended from the linear encodings used to solve classical planning problems by SAT solvers. The graphical model is obtained by converting CNF clauses into a mixed network, where the probabilistic state transitions are compiled as Bayesian network and deterministic constraints are compiled as an auxiliary network. We performed empirical evaluation to compare marginal MAP algorithms and Probabilistic-FF planner. The experiment results show that marginal MAP algorithms were able to solve selected problem domains.