Nondeterministic Dijkstra

Figure 10.8 shows an extension of Dijkstra's algorithm for solving the problem of Formulation 10.1 under nondeterministic uncertainty. It can also be considered as a variant of the algorithm in Figure 10.6 because it grows $S$ by using backprojections. The algorithm in Figure 10.8 represents a backward-search version of Dijkstra's algorithm; therefore, it maintains the worst-case cost-to-go, $G$, which sometimes becomes the optimal, worst-case cost-to-go, $G^*$. Initially, $G= 0$ for states in the goal, and $G= \infty$ for all others.

Figure 10.8: A Dijkstra-based algorithm for computing an optimal feasible plan under nondeterministic uncertainty.

Step 1 performs the initialization. Step 2 selects the state in $A$ that has the smallest value. As in Dijkstra's algorithm for deterministic problems, it is known that the cost-to-go for this state is the smallest possible. It is therefore declared in Step 3 that $G^*(x_s) = G(x_s)$, and $\pi^*$ is extended to include $x_s$.

Figure 10.9: The worst-case cost-to-go is computed for any state $x$ such that there exists a $u \in U(x)$ for which the one-stage forward projection is contained in the updated $S$ and one state in the forward projection is $x_s$.

Step 4 updates the costs for some states and expands the active set, $A$. Which costs could be immediately affected by the insertion of $x_s$ into $S$? These are states $x_k \in X \setminus S$ for which there exists some $u_k \in U(x_k)$ that produces a one-stage forward projection, $X_{k+1}(x_k,u_k)$, such that: 1) $x_s \in X_{k+1}(x_k,u_k)$ and 2) $X_{k+1}(x_k,u_k) \subseteq S$. This is depicted in Figure 10.9. Let the set of states that satisfy these constraints be called the frontier set, denoted by $\operatorname{Front}(x_s,S)$. For each $x \in \operatorname{Front}(x_s,S)$, let $U_f(x) \subseteq U(x)$ denote the set of all actions for which the forward projection satisfies the two previous conditions.

The frontier set can be interpreted in terms of backprojections. The weak backprojection $\operatorname{WB}(x_s)$ yields all states that can possibly reach $x_s$ in one step. However, the cost-to-go is only finite for states in $\operatorname{SB}(S)$ (here $S$ already includes $x_s$). The states in $S$ should certainly be excluded because their optimal costs are already known. These considerations reduce the set of candidate frontier states to $(\operatorname{WB}(x_s) \cap \operatorname{SB}(S)) \setminus S$. This set is still too large because the same action, $u$, must produce a one-stage forward projection that includes $x_s$ and is a subset of $S$.

The worst-case cost-to-go is computed for all $x \in \operatorname{Front}(x_s,S)$ as

$$G(x) = \min_{u \in U_f(x)} \Big\{ \max_{\theta \in \Theta(x,u)} \Big\{ l(x,u,\theta) + G(f(x,u,\theta)) \Big\} \Big\},$$ (10.63)

in which the restricted action set, $U_f(x)$, is used. If $x$ was already in $A$ and a previous $G(x)$ was computed, then the minimum of its previous value and (10.64) is kept.