A hybrid genetic/optimization algorithm for finite-horizon, partially observed Markov decision processes

A hybrid genetic/optimization algorithm for finite-horizon, partially observed Markov decision processes

0.00 Avg rating0 Votes
Article ID: iaor2007356
Country: United States
Volume: 16
Issue: 1
Start Page Number: 27
End Page Number: 38
Publication Date: Dec 2004
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: heuristics: genetic algorithms, programming: integer
Abstract:

The partially observed Markov decision process (POMDP) is a generalization of a Markov decision process that allows for noise-corrupted and costly observations of the underlying system state. The value function of the finite horizon POMDP is known to be piecewise affine and convex in the probability mass vector over the state space. Such a function can be represented by a finite set of affine functions. In this paper, we develop and evaluate an exact algorithm, GAMIP, which combines a genetic algorithm and a mixed integer program to construct the minimal set of affine functions that describes the value function. Numerical results indicate that GAMIP takes up to 60% less time to construct the minimal set than does the most efficient linear programming-based exact solution method in the literature.

Reviews

Required fields are marked *. Your email address will not be published.