Solving stochastic shortest-path problems with RTDP.pdf

Solving Stochastic Shortest-Path Problems with RTDP Blai Bonet Cognitive Systems Laboratory Deptartment of Computer Science University of California, Los Angeles Los Angeles, CA 90024 He?ctor Geffner Departamento de Computacio?n Universidad Simo?n Bol??var Aptdo. 89000, Caracas 1080-A Venezuela Abstract We present a modification of the Real-Time Dy- namic Programming (rtdp) algorithm that makes it a genuine off-line algorithm for solving Stochas- tic Shortest-Path problems. Also, a new domain- independent and admissible heuristic is presented for Stochastic Shortest-Path problems. The new algo- rithm and heuristic are compared with Value Itera- tion over benchmark problems with large state spaces. The results show that the modified rtdp algorithm can beat standard Value Iteration by several orders of magnitude in problems with large state space. Introduction The class of Stochastic Shortest-Path (ssp) problems is a subset of Markov Decision Processes (mdps) that is of central importance to AI: they are the natural gen- eralization of the classic search model to the case of stochastic transitions and general cost functions. ssps had been recently used to model a broad range of problems going from robot navigation and control of non-deterministic systems to stochastic game-playing and planning under uncertainty and partial informa- tion (Bertsekas Tsitsiklis 1996; Sutton Barto 1998; Bonet Geffner 2000). The theory of mdps had re- ceived great attention from the AI community for three important reasons. First, it provides an easy frame- work for modeling complex real-life problems that have large state-space (even infinite) and complex dynamics and cost functions. Second, mdps provide mathemat- ical foundation for independently-developed learning algorithms in Reinforcement Learning. And third, gen- eral and efficient algorithms for solving mdps had been developed, the most important being Value Iteration and Policy Iteration. As the name suggests, an ssp problem is