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.
% latex2html id marker 55494
...inal value or the new computed value. Go to Step 2.

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

$\displaystyle 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.

Steven M LaValle 2012-04-20