OPTIMIZATION OF STOCHASTIC FINITE STATE SYSTEMS.
CRUFT LAB HARVARD UNIV CAMBRIDGE MASS
Pagination or Media Count:
The paper is concerned with the determination of optimal policy under specified performance criteria for finite state systems, i.e., systems whose allowable state space consists only of a finite number of points. It was assumed that the state transitions occur at discrete instants of time t0,1,2..t sub f. Moreover the attention is focused on stochastic finite state systems i.e., systems in which the state transitions are governed probabilistically by the given input. These systems are more amenable for simulation by digital computer than continuous state systems and have found application in various branches like learning theiry, pursuit problems, time-sharing computer systems, the latter of which will be discussed later in the paper. The basic problem is to specify the input to the system at each instant so that the expected value of the sum of the cost of the system in the terminal state and the cost suffered by the system during the transition is minimized. Since the number of available inputs to the system is finite, the variational theory cannot be applied directly to the solution of such problems. Some of these problems, in which the state of the system at each instant can be measured exactly, have been analyzed with the aid of dynamic programming by a number of investigators like Bellman, Howard, Zadeh, and Eaton etc. The author rephrases and solves a large class of problems, including those in which the state of the system cannot be measured exactly, with the aid of discrete maximum principle.
- Operations Research
- Computer Hardware
- Computer Systems