From Stochastic Planning to Marginal MAP
Hao(Jackson) Cui · Radu Marinescu · Roni Khardon

Wed Dec 5th 05:00 -- 07:00 PM @ Room 517 AB #169

It is well known that the problems of stochastic planning and probabilistic inference are closely related. This paper makes two contributions in this context. The first is to provide an analysis of the recently developed SOGBOFA heuristic planning algorithm that was shown to be effective for problems with large factored state and action spaces. It is shown that SOGBOFA can be seen as a specialized inference algorithm that computes its solutions through a combination of a symbolic variant of belief propagation and gradient ascent. The second contribution is a new solver for Marginal MAP (MMAP) inference. We introduce a new reduction from MMAP to maximum expected utility problems which are suitable for the symbolic computation in SOGBOFA. This yields a novel algebraic gradient-based solver (AGS) for MMAP. An experimental evaluation illustrates the potential of AGS in solving difficult MMAP problems.

Author Information

Hao(Jackson) Cui (Tufts University)
Radu Marinescu (IBM Research)
Roni Khardon (Indiana University, Bloomington)

More from the Same Authors