Hierarchical POMDP Decomposition for A Conversational Robot
Joelle Pineau and Sebastian Thrun
POMDPs provide a useful framework for decision-making in the presence of uncertainty. Finding solutions to large-scale problems, however, has proven computationally infeasible. We propose a hierarchical approach to POMDPs which takes advantage of structure in the domain to decompose the problem into a collection of smaller POMDPs. These can be solved independently, allowing us to solve larger problems than were previously possible. We apply this approach to the problem of human-robot speech dialogues, and show that appropriate decomposition can yield significant computational time reduction when finding a POMDP solution.
Available in gzipped postscript and PDF