10.3.1 Problem Formulation

Both of the cost models presented in this section were designed to force the cumulative cost to become finite, even though there is an infinite number of stages. Each can be considered as a minor adaptation of cost functional used in Formulation 10.1.

The following formulation will be used throughout Section 10.3.

Formulation 10..2 (Infinite-Horizon Problems)  

1. A nonempty, finite state space $X$.
2. For each state $x \in X$, a finite action space $U(x)$ (there is no termination action, contrary to Formulation 10.1).
3. A finite nature action space $\Theta(x,u)$ for each $x \in X$ and $u \in U(x)$.
4. A state transition function $f$ that produces a state, $f(x,u,\theta)$, for every $x \in X$, $u \in U(x)$, and $\theta \in \Theta(x,u)$.
5. A set of stages, each denoted by $k$, that begins at $k=1$ and continues indefinitely.
6. A stage-additive cost functional, $L({\tilde{x}},{\tilde{u}},{\tilde{\theta}})$, in which ${\tilde{x}}$, ${\tilde{u}}$, and ${\tilde{\theta}}$ are infinite state, action, and nature histories, respectively. Two alternative forms of $L$ will be given shortly.

In comparison to Formulation 10.1, note that here there is no initial or goal state. Therefore, there are no termination actions. Without the specification of a goal set, this may appear to be a strange form of planning. A feedback plan, $\pi$, still takes the same form; $\pi (x)$ produces an action $u \in U(x)$ for each $x \in X$.

As a possible application, imagine a robot that delivers materials in a factory from several possible source locations to several destinations. The robot operates over a long work shift and has a probabilistic model of when requests to deliver materials will arrive. Formulation 10.2 can be used to define a problem in which the goal is to minimize the average amount of time that materials wait to be delivered. This strategy should not depend on the length of the shift; therefore, an infinite number of stages is reasonable. If the shift is too short, the robot may focus only on one delivery, or it may not even have enough time to accomplish that.