Robust Combination of Local Controllers
Carlos Guestrin, Dirk Ormoneit
Abstract:
Planning problems are hard, motion planning, for example, isPSPACEhard. Such problems are even more difficult in the presence of uncertainty. Although, Markov Decision Processes (MDPs) provide a formal framework for such problems, finding solutions to high dimensional continuous MDPs is usually difficult, especially when the actions and time measurements are continuous. Fortunately, problemspecific knowledge allows us to design controllers that are good locally, though having no global guarantees. We propose a method of nonparametrically combining local controllers to obtain globally good solutions. We apply this formulation to two types of problems : motion planning (stochastic shortest path) and discounted MDPs. For motion planning, we argue that usual MDP optimality criterion (expected cost) may not be practically relevant. Wepropose an alternative: finding the minimum cost path,subject to the constraint that the robot must reach the goal withhigh probability. For this problem, we prove that a polynomial number of samples is sufficient to obtain a high probability path. For discounted MDPs, we propose a formulation that explicitly deals with model uncertainty, i.e., the problem introduced when transition probabilities are not known exactly. We formulate the problem as a robust linear program which directly incorporates this type of uncertainty.
Keywords:
Pages: 178185
PS Link: http://robotics.stanford.edu/~guestrin/Publications/UAI2001/uai2001.ps
PDF Link: /papers/01/p178guestrin.pdf
BibTex:
@INPROCEEDINGS{Guestrin01,
AUTHOR = "Carlos Guestrin
and Dirk Ormoneit",
TITLE = "Robust Combination of Local Controllers",
BOOKTITLE = "Proceedings of the Seventeenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI01)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2001",
PAGES = "178185"
}

