Selecting preferred solutions in the minimax approach to dynamic programming problems under flexible constraints |
| |
Authors: | D. Dubois Ph. Fortemps |
| |
Affiliation: | a IRIT––CNRS, Université Paul Sabatier, 118 route de Narbonne, 31062, Toulouse Cedex 4, France;b MATHRO, Faculté Polytechnique de Mons, 9 rue de Houdain, 7000, Mons, Belgium |
| |
Abstract: | Dynamic Programming is a powerful approach to the optimization of sequential or multistage decision processes, e.g., in planning or in system control. In this paper, we consider both theoretical and algorithmic issues in sequential decision processes under flexible constraints. Such processes must attain a given goal within some tolerance. Tolerances or preferences also apply to the values the decision variables may take or on the action chosen at each step. Such problems boil down to maximin optimization. Unfortunately, this approach suffers from the so-called “drowning effect” (lack of discrimination) and the optimality principle of dynamic programming is not always verified. In this context, we introduce a general framework for refined minimax optimization procedures in order to compare and select preferred alternatives. This framework encompasses already introduced methods such as LexiMin and DiscriMin, but it allows their extension to the comparison of vectors of unequal lengths. We show that these refined comparisons restore compatibility with the optimality principle, and that classical algorithms can be adapted to compute such preferred solutions, by exploiting existing results on idempotent semirings. |
| |
Keywords: | Dynamic programming Flexible constraints Order relation Idempotent semiring |
本文献已被 ScienceDirect 等数据库收录! |
|