Graph representations of a plan

The game against nature involves two decision makers: nature and the robot. Once the plan is formulated, the decisions of the robot become fixed, which leaves nature as the only remaining decision maker. Using this interpretation, a directed graph can be defined in the same way as in Section 2.1, except nature actions are used instead of the robot's actions. It can even be imagined that nature itself faces a discrete feasible planning problem as in Formulation 2.1, in which $\Theta(x,\pi (x))$ replaces $U(x)$, and there is no goal set. Let ${\cal G}_\pi$ denote a plan-based state transition graph, which arises under the constraint that $\pi$ is executed. The vertex set of ${\cal G}_\pi$ is $X$. A directed edge in ${\cal G}_\pi$ exists from $x$ to $x^\prime$ if there exists some $\theta \in \Theta(x,\pi (x))$ such that $x^\prime = f(x,\pi (x),\theta)$. Thus, from each vertex in ${\cal G}_\pi$, the set of outgoing edges represents all possible transitions to next states that are possible, given that the action is applied according to $\pi$. In the case of probabilistic uncertainty, ${\cal G}_\pi$ becomes a weighted graph in which each edge is assigned the probability $P(x^\prime \vert x, \pi (x), \theta)$. In this case, ${\cal G}_\pi$ corresponds to the graph representation commonly used to depict a Markov chain.

A nondeterministic forward projection can easily be derived from ${\cal G}_\pi$ by following the edges outward from the current state. The outward edges lead to the states of the one-stage forward projection. The outward edges of these states lead to the two-stage forward projection, and so on. The probabilistic forward projection can also be derived from ${\cal G}_\pi$.