Mixed Acceleration Techniques for Solving Quickly Stochastic Shortest-Path Markov Decision Processes
Fuente:
Redalyc
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Artículo científico |
| Sprache: | en |
| Veröffentlicht: |
Universidad Nacional Autónoma de México
2011
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1876435508293271552 |
|---|---|
| author | M. de G. García-Hernández |
| author_facet | M. de G. García-Hernández |
| contents | Mixed Acceleration Techniques for Solving Quickly Stochastic Shortest-Path Markov Decision Processes 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 Ingeniería prioritization acceleration techniques Markov decision processes 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. 2011 artículo científico 1665-6423 https://www.redalyc.org/articulo.oa?id=47419293002 en http://www.redalyc.org/revista.oa?id=474 Journal of Applied Research and Technology application/pdf Universidad Nacional Autónoma de México Journal of Applied Research and Technology (México) Num.2 Vol.9 |
| format | Artículo científico |
| id | redalyc_47419293002 |
| institution | Redalyc |
| language | en |
| publishDate | 2011 |
| publisher | Universidad Nacional Autónoma de México |
| spellingShingle | Mixed Acceleration Techniques for Solving Quickly Stochastic Shortest-Path Markov Decision Processes M. de G. García-Hernández Ingeniería prioritization acceleration techniques Markov decision processes Mixed Acceleration Techniques for Solving Quickly Stochastic Shortest-Path Markov Decision Processes 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 Ingeniería prioritization acceleration techniques Markov decision processes 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. 2011 artículo científico 1665-6423 https://www.redalyc.org/articulo.oa?id=47419293002 en http://www.redalyc.org/revista.oa?id=474 Journal of Applied Research and Technology application/pdf Universidad Nacional Autónoma de México Journal of Applied Research and Technology (México) Num.2 Vol.9 |
| title | Mixed Acceleration Techniques for Solving Quickly Stochastic Shortest-Path Markov Decision Processes |
| topic | Ingeniería prioritization acceleration techniques Markov decision processes |
| url | https://www.redalyc.org/articulo.oa?id=47419293002 |