New prioritized value iteration for Markov decision processes
| Autor: | Sergio Eduardo Ledesma-Orozco, J. Gabriel Aviña-Cervantes, Eva Onaindia, Edgar Alvarado-Mendez, Ma. de Guadalupe García-Hernández, Jose Ruiz-Pinales, A. Reyes-Ballesteros |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: |
Linguistics and Language
Mathematical optimization Computer science Partially observable Markov decision process Prioritized value iteration Markov model Language and Linguistics Markov decision processes Dijkstra's algorithm Artificial Intelligence Shortest path problem Topological sorting Markov decision process Suurballe's algorithm Pathfinding LENGUAJES Y SISTEMAS INFORMATICOS |
| Zdroj: | RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia instname |
| Popis: | The problem of solving large Markov decision processes accurately and quickly is challenging. Since the computational effort incurred is considerable, current research focuses on finding superior acceleration techniques. For instance, the convergence properties of current solution methods depend, to a great extent, on the order of backup operations. On one hand, algorithms such as topological sorting are able to find good orderings but their overhead is usually high. On the other hand, shortest path methods, such as Dijkstra's algorithm which is based on priority queues, have been applied successfully to the solution of deterministic shortest-path Markov decision processes. Here, we propose an improved value iteration algorithm based on Dijkstra's algorithm for solving shortest path Markov decision processes. The experimental results on a stochastic shortest-path problem show the feasibility of our approach. © Springer Science+Business Media B.V. 2011. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|