Groupe d’études et de recherche en analyse des décisions

G-90-02

A Turnpike Improvement Algorithm for Piecewise Deterministic Control

, et

This paper proposes a numerical technique, called Turnpike Improvement, for the approximation of the solution of a class of piecewise deterministic control problems typically associated with manufacturing flow control models. This algorithm exploits the structure of Markov decision process with continuous state and action spaces that can be associated with piecewise deterministic control systems. The numerical method is applicable whenever a turnpike property holds for some associated infinite horizon deterministic control problems. To illustrate the approach we use a simple model fully studiedfrom an analytic point of view in the literature. We compare the turnpike improvement technique with a direct approximation of the solution of a continuous-time Hamilton-Jacobi-Bellman dynamic programming equations, inspired from Kushner's. The two approaches agree remarkably on this simple problem. We conclude with a discussion of the relative advantages of the two approaches.

, 26 pages