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 replaces , and there is no goal set. Let denote a plan-based state transition graph, which arises under the constraint that is executed. The vertex set of is . A directed edge in exists from to if there exists some such that . Thus, from each vertex in , the set of outgoing edges represents all possible transitions to next states that are possible, given that the action is applied according to . In the case of probabilistic uncertainty, becomes a weighted graph in which each edge is assigned the probability . In this case, corresponds to the graph representation commonly used to depict a Markov chain.
A nondeterministic forward projection can easily be derived from 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 .
Steven M LaValle 2012-04-20