Mixed Acceleration Techniques for Solving Quickly Stochastic Shortest-Path Markov Decision Processes

Main Article Content

M. de G. García-Hernández
J. Ruiz-Pinales
E. Onaindía
S. Ledesma-Orozco
J. G. Aviña-Cervantes
E. Alvarado-Méndez
A. Reyes-Ballesteros

Abstract

In this paper we propose the combination of accelerated variants of value iteration mixed with improved prioritized

sweeping for the fast solution of stochastic shortest-path Markov decision processes. Value iteration is a classical

algorithm for solving Markov decision processes, but this algorithm and its variants are quite slow for solving

considerably large problems. In order to improve the solution time, acceleration techniques such as asynchronous

updates, prioritization and prioritized sweeping have been explored in this paper. A topological reordering algorithm

was also compared with static reordering. Experimental results obtained on finite state and action-space stochastic

shortest-path problems show that our approach achieves a considerable reduction in the solution time with respect to

the tested variants of value iteration. For instance, the experiments showed in one test a reduction of 5.7 times with

respect to value iteration with asynchronous updates.

 

PLUM ANALYTICS

Article Details

How to Cite
García-Hernández, M. de G., Ruiz-Pinales, J., Onaindía, E., Ledesma-Orozco, S., Aviña-Cervantes, J. G., Alvarado-Méndez, E., & Reyes-Ballesteros, A. (2011). Mixed Acceleration Techniques for Solving Quickly Stochastic Shortest-Path Markov Decision Processes. Journal of Applied Research and Technology, 9(02). https://doi.org/10.22201/icat.16656423.2011.9.02.439

Most read articles by the same author(s)