Approaches to macro decompositions of large Markov decision process planning problems

Terran Lane; Leslie Pack Kaelbling

doi:10.1117/12.457435

18 February 2002 Approaches to macro decompositions of large Markov decision process planning problems

Terran Lane, Leslie Pack Kaelbling

Proceedings Volume 4573, Mobile Robots XVI; (2002) https://doi.org/10.1117/12.457435
Event: Intelligent Systems and Advanced Manufacturing, 2001, Boston, MA, United States

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.

Citation Download Citation

Terran Lane and Leslie Pack Kaelbling "Approaches to macro decompositions of large Markov decision process planning problems", Proc. SPIE 4573, Mobile Robots XVI, (18 February 2002); https://doi.org/10.1117/12.457435

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available