For the first time in this book, uncertainty will be directly modeled. There are two DMs:
Imagine that the robot and nature each make a decision. Each has a set of actions to choose from. Suppose that the cost depends on which actions are chosen by each. The cost still represents the effect of the outcome on the robot; however, the robot must now take into account the influence of nature on the cost. Since nature is unpredictable, the robot must formulate a model of its behavior. Assume that the robot has a set, , of actions, as before. It is now assumed that nature also has a set of actions. This is referred to as the nature action space and is denoted by . A nature action is denoted as . It now seems appropriate to call the robot action space; however, for convenience, it will often be referred to as the action space, in which the robot is implied.
This leads to the following formulation, which extends Formulation 9.1.
The cost function, , now depends on and . If and are finite, then it is convenient to specify as a matrix called the cost matrix.

In Formulation 9.3, it appears that both DMs act at the same time; nature does not know the robot action before deciding. In many contexts, nature may know the robot action. In this case, a different nature action space can be defined for every . This generalizes Formulation 9.3 to obtain:
Steven M LaValle 20120420