A hybrid genetic/optimization algorithm for piecewise affine and convex Markov decision processes.

摘要

A variety of finite horizon models of sequential decision making under uncertainty have value functions that are piecewise affine and convex ( PAC) or equivalently, can be represented by a finite set of affine functions. Such models include: the partially observed Markov decision problem (POMDP) and the Markov decision problem (MDP) with affine single-step and/or terminal reward function, examples of which are the multi-objective MDP and the nonhomogeneous MDP (NMDP). We develop both optimal and suboptimal solution procedures for this class of models. Our optimal solution approach, GAMIP, integrates a genetic algorithm (GA) and a mixed integer program (MIP). The genetic algorithm step only is a suboptimal design with good solution quality. Both optimal approach and suboptimal design construct the minimal set of affine functions that describe the value function. The POMDP and NMDP are investigated numerically.; The POMDP is a generalization of a MDP that allows for observations that are probabilistically related to the underlying system state. The value function of the finite horizon POMDP is known to be PAC in the probability mass vector over the state space. For suboptimal design, we develop two heuristic approaches based on genetic algorithms, termed as dc-niche and spatial, to construct approximations of the minimal set of affine functions that describes the value function. Error bounds of these two approaches are presented. Numerical results indicate that these heuristics can quickly yield high quality solutions for a set of small-scale problems where exact solutions are feasible and can provide suboptimal designs for realistically sized problems. Numerical results indicate that GAMIP takes up to 60% less time than the most efficient linear programming-based exact solution method in the literature to construct the minimal set.; For the study of an infinite horizon NMDP, the objective is to determine an optimal initial action. We transform this infinite horizon NMDP into a finite horizon NMDP having a terminal reward vector described by set inclusion. Our approach involves finding a forecast horizon, a problem horizon such that an optimal initial decision for the finite horizon problem is optimal for the infinite horizon problem. We make use of the fact that the value function of the finite horizon NMDP having a terminal reward vector described by set inclusion is PAC in the terminal reward vector. Our solution procedure is based on a combination of the genetic algorithm and mixed integer programming. We show that a suboptimal procedure based solely on the genetic algorithm quickly identifies high quality candidates for the minimal forecast horizon. The mixed integer program is used to confirm or rule out a candidate for a forecast horizon. We then present a numerical evaluation that compares our approach with several other algorithms.