Nondeterministic forward projections

To facilitate the notation, suppose in this section that $ U(x) = U$ for all $ x \in X$. In Section 10.1.3 this will be lifted.

Suppose that the initial state, $ x_1 = {x_{I}}$, is known. If the action $ u_1 \in U$ is applied, then the set of possible next states is

$\displaystyle X_2(x_1,u_1) = \{ x_2 \in X \;\vert\; \exists \theta_1 \in \Theta(x_1,u_1)$    such that $\displaystyle x_2 = f(x_1,u_1,\theta_1)\} ,$ (10.10)

which is just a special version of (10.5). Now suppose that an action $ u_2 \in U$ will be applied. The forward projection must determine which states could be reached from $ x_1$ by applying $ u_1$ followed by $ u_2$. This can be expressed as

\begin{displaymath}\begin{split}X_3(x_1,u_1,u_2) = \{ x_3 \in X \;\vert\; & \exi...
...theta_1) \mbox{ and } x_3 = f(x_2,u_2,\theta_2)\} . \end{split}\end{displaymath} (10.11)

This idea can be repeated for any number of iterations but becomes quite cumbersome in the current notation. It is helpful to formulate the forward projection recursively. Suppose that an action history $ {\tilde{u}}_k$ is fixed. Let $ X_{k+1}(X_k,u_k)$ denote the forward projection at stage $ k+1$, given that $ X_k$ is the forward projection at stage $ k$. This can be computed as

\begin{displaymath}\begin{split}X_{k+1}(X_k,u_k) = \{ x_{k+1} \in X \;\vert\; & ...
...mbox{ such that } x_{k+1} = f(x_k,u_k,\theta_k)\} . \end{split}\end{displaymath} (10.12)

This may be applied any number of times to compute $ X_{k+1}$ from an initial condition $ X_1 = \{x_1\}$.

Example 10..3 (Nondeterministic Forward Projections)   Recall the first model given in Example 10.1, in which $ U = \{-2,2,u_T\}$ and $ \Theta = \{-1,0,1\}$. Suppose that $ x_1 =
0$, and $ u=2$ is applied. The one-stage forward projection is $ X_2(0,2) = \{1,2,3\}$. If $ u=2$ is applied again, the two-stage forward projection is $ X_3(0,2,2) = \{2,3,4,5,6\}$. Repeating this process, the $ k$-stage forward projection is $ \{k,\ldots,3k\}$. $ \blacksquare$

Steven M LaValle 2012-04-20