Reducing Computational Complexity in Markov Decision Processes Using Abstract Actions
Ma. de Guadalupe García-Hernández, José Ruiz-Pinales, Alberto Reyes, Eva Onaindía, Juan Gabriel Avina‐Cervantes · 2008
In this paper we present a new approach for the solution of Markov decision processes based on the use of an abstraction technique over the action space, which results in a set of abstract actions. Markovian processes have successfully solved many probabilistic problems such as: process control, decision analysis and economy. But for problems with continuous or high dimensionality domains, high computational complexity arises because the search space grows exponentially with the number of variables. In order to reduce computational complexity, our approach avoids the use of the whole domain actions during value iteration, calculating instead over the abstract actions that really operate on each state, as a state function. Our experimental results on a robot path planning task show an important reduction of computational complexity.