Share Email Print

Proceedings Paper

Approaches to macro decompositions of large Markov decision process planning problems
Author(s): Terran Lane; Leslie Pack Kaelbling
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

Mobile robot navigation tasks are subject to motion stochasticity arising from the robot's local controllers, which casts the navigational task into a Markov decision process framework. The MDP may, however, be intractably large; in this work we consider the prioritized package delivery problem which yields an exponentially large state space. We demonstrate that the bulk of this state space is tied to a sub-problem that is an instance of the traveling salesdroid problem and that exponential improvements in solution time for the MDP can be achieved by addressing the TSP sub-problem separately. This process produces a suboptimal solution, but we show that the degree of suboptimality can be controlled by employing more effective TSP approximators. The key contribution is the demonstration that MDP solution techniques can substantially benefit from careful application of well-understood deterministic optimization techniques.

Paper Details

Date Published: 18 February 2002
PDF: 10 pages
Proc. SPIE 4573, Mobile Robots XVI, (18 February 2002); doi: 10.1117/12.457435
Show Author Affiliations
Terran Lane, MIT Artificial Intelligence Lab. (United States)
Leslie Pack Kaelbling, MIT Artificial Intelligence Lab. (United States)

Published in SPIE Proceedings Vol. 4573:
Mobile Robots XVI
Douglas W. Gage; Howie M. Choset, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?