Decision-theoretic, high-level robot programming in the situation calculus.

C. Boutilier, R. Reiter, M. Soutchanski, and S. Thrun.

We propose a method of approximate dynamic programming for Markov decision processes (MDPs) using algebraic decision diagrams (ADDs). We produce near-optimal value functions and policies with much lower time and space requirements than exact dynamic programming. Our method reduces the sizes of the intermediate value functions generated during value iteration by replacing the values at the terminals of the ADD with ranges of values. A representation using decision diagrams is well-suited to this task, for similar values can be directly merged without the need for reordering variables. Our method is demonstrated on a class of large MDPS (with up to 34 billion states), and we compare the results with the optimal value functions.

The full paper is available in PDF and gzipped Postscript

@INPROCEEDINGS{Boutilier00a,
  AUTHOR	= {C. Boutilier and R. Reiter and M. Soutchanski and S. Thrun},
  TITLE		= {Decision-Theoretic, High-level Robot Programming in the Situation Calculus},
  YEAR		= {2000},
  BOOKTITLE	= {Proceedings of the AAAI National Conference on Artificial Intelligence},
  PUBLISHER	= {AAAI},
  ADDRESS	= {Austin, TX}
}