Premium
Shrinking‐horizon dynamic programming
Author(s) -
Skaf Joëlle,
Boyd Stephen,
Zeevi Assaf
Publication year - 2010
Publication title -
international journal of robust and nonlinear control
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.361
H-Index - 106
eISSN - 1099-1239
pISSN - 1049-8923
DOI - 10.1002/rnc.1566
Subject(s) - dynamic programming , horizon , mathematical optimization , time horizon , optimal control , current (fluid) , computer science , action (physics) , state (computer science) , extension (predicate logic) , heuristic , model predictive control , process (computing) , markov decision process , control (management) , markov process , mathematics , algorithm , engineering , artificial intelligence , statistics , physics , geometry , electrical engineering , quantum mechanics , programming language , operating system
We describe a heuristic control policy for a general finite‐horizon stochastic control problem, which can be used when the current process disturbance is not conditionally independent of the previous disturbances, given the current state. At each time step, we approximate the distribution of future disturbances (conditioned on what has been observed) by a product distribution with the same marginals. We then carry out dynamic programming (DP), using this modified future disturbance distribution, to find an optimal policy, and in particular, the optimal current action. We then execute only the optimal current action. At the next step, we update the conditional distribution, and repeat the process, this time with a horizon reduced by one step. (This explains the name ‘shrinking‐horizon dynamic programming’). We explain how the method can be thought of as an extension of model predictive control, and illustrate our method on two variations on a revenue management problem. Copyright © 2010 John Wiley & Sons, Ltd.