Combining knowledge compilation and search for conformant probabilistic planning
Jinbo Huang · 2006
We present a new algorithm for conformant probabilistic planning, which for a given horizon produces a plan that max-imizes the probability of success under quantified uncertainty about the initial state and action effects, and absence of sen-sory information. Recent work has studied systematic search in the space of all candidate plans as a feasible approach to conformant probabilistic planning, but the algorithms pro-posed require caching of intermediate computations in such a way that memory is often exhausted quickly except for small planning horizons. On the other hand, planning problems in typical formulations generally have treewidths that do not grow with the horizon, as connections between variables are local to the neighborhood of each time step. These exist-ing planners, however, are unable to directly benefit from the bounded treewidth owing to a constraint on the variable or-dering which is necessary for correct computation of the op-timal plan. We show that lifting such constraint allows one to obtain a compact compilation of the planning problem, from which an upper bound can be efficiently computed on the value of any partial plan generated during search. Coupled with several optimizations, this results in a depth-first branch-and-bound algorithm which on the tested domains runs an or-der of magnitude faster than its predecessors, and at the same time is able to solve problems for significantly larger horizons thanks to its minimal memory requirements.