New prioritized value iteration for Markov decision processes

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...

Full description

Saved in:
Bibliographic Details
Published in:The Artificial intelligence review 2012-02, Vol.37 (2), p.157-167
Main Authors: Garcia-Hernandez, Ma. de Guadalupe, Ruiz-Pinales, Jose, Onaindia, Eva, Aviña-Cervantes, J. Gabriel, Ledesma-Orozco, Sergio, Alvarado-Mendez, Edgar, Reyes-Ballesteros, Alberto
Format: Article
Language:English
Subjects:
Acceleration
Algorithms
Artificial Intelligence
Back up systems
Computer Science
Dijkstra's algorithm
Dynamic programming
Expected utility
Heuristic
Iterative methods
Linear programming
Markov analysis
Markov processes
Mathematical models
Order disorder
Queuing theory
Shortest-path problems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0269-2821
1573-7462
DOI:10.1007/s10462-011-9224-z