14.2.2.3 Resolution completeness for ${\dot x}= f(x,u)$

Beyond the trivial case of ${\dot x}= u$, the reachability graph is usually not a simple grid. Even if $X$ is bounded, the reachability graph may have an infinite number of vertices, even though $\Delta t$ is fixed and $U_d$ is finite. For a simple example, consider the Dubins car under the discretization $\Delta t = 1$. Fix $u_\phi = -\phi_{max}$ (turn left) for all $t \in T$. This branch alone generates a countably infinite number of vertices in the reachability graph. The circumference of the circle is $2 \pi \rho_{min}$, in which $\rho_{min}$ is the minimum turning radius. Let $\rho_{min} = 1$. Since the circumference is an irrational number, it is impossible to revisit the initial point by traveling $k$ seconds for some integer $k$. It is even impossible to revisit any point on the circle. The set of vertices in the reachability graph is actually dense in the circle. This did not happen in Figure 14.6 because $\Delta t$ and the circumference were rationally related (i.e., one can be obtained from the other via multiplication by a rational number). Consider what happens in the current example when $\rho_{min} = 1/\pi$ and $\Delta t = 1$.

Suppose that ${\dot x}= f(x,u)$ and the discrete-time model is used. To ensure convergence of the discrete-time approximation, $f$ must be well-behaved. This can be established by requiring that all of the derivatives of $f$ with respect to $u$ and $x$ are bounded above and below by a constant. More generally, $f$ is assumed to be Lipschitz, which is an equivalent condition for cases in which the derivatives exist, but it also applies at points that are not differentiable. If $U$ is finite, then the Lipschitz condition is that there exists some $c \in (0,\infty)$ such that

$$\Vert f(x,u) - f(x',u)\Vert \leq c \Vert x - x'\Vert$$ (14.10)

for all $x,x' \in X$, for all $u \in U$, and $\Vert\cdot\Vert$ denotes a norm on $X$. If $U$ is infinite, then the condition is that there must exist some $c \in (0,\infty)$ such that

$$\Vert f(x,u) - f(x',u')\Vert \leq c (\Vert x - x'\Vert + \Vert u - u'\Vert) ,$$ (14.11)

for all $x,x' \in X$, and for all $u,u' \in U$. Intuitively, the Lipschitz condition indicates that if $x$ and $u$ are approximated by $x'$ and $u'$, then the error when substituted into $f$ will be manageable. If convergence to optimal trajectories with respect to a cost functional is important, then Lipschitz conditions are also needed for $l(x,u)$. Under such mild assumptions, if $\Delta t$ and the dispersion of samples of $U_d$ is driven down to zero, then the trajectories obtained from integrating discrete action sequences come arbitrarily close to solution trajectories. In other words, action sequences provide arbitrarily close approximations to any ${\tilde{u}}\in U$. If $f$ is Lipschitz, then the integration of (14.14) yields approximately the same result for ${\tilde{u}}$ as the approximating action sequence.

In the limit as $\Delta t$ and the dispersion of $U_d$ approach zero, the reachability graph becomes dense in the reachable set $R({x_{I}},{\cal U})$. Ensuring a systematic search for the case of a grid was not difficult because there is only a finite number of vertices at each resolution. Unfortunately, the reachability graph may generally have a countably infinite number of vertices for some fixed discrete-time model, even if $X$ is bounded.

To see that resolution-complete algorithms nevertheless exist if the reachability graph is countably infinite, consider triangular enumeration, which proves that ${\mathbb{N}}\times {\mathbb{N}}$ is countable, in which ${\mathbb{N}}$ is the set of natural numbers. The proof proceeds by giving a sequence that starts at $(0,0)$ and proceeds by sweeping diagonally back and forth across the first quadrant. In the limit, all points are covered. The same idea can be applied to obtain resolution-complete algorithms. A sequence of discrete-time models can be made for which the time step $\Delta t$ and the dispersion of the sampling of $U$ approach zero. Each discretization produces a reachability graph that has a countable number of vertices.

Figure 14.7: By systematically alternating between exploring different reachability graphs, resolution completeness can be achieved, even if each reachability graph has a countably infinite number of vertices.

A resolution-complete algorithm can be made by performing the same kind of zig-zagging that was used to show that ${\mathbb{N}}\times {\mathbb{N}}$ is countable. See Figure 14.7; suppose that $U$ is finite and $U_d = U$. Along the horizontal axis is a sequence of improving discrete-time models. Each model generates its own reachability graph, for which a systematic search eventually explores all of its vertices. Imagine this exploration occurs one step at a time, in which one new vertex is reached in each step. The vertical axis in Figure 14.7 indicates the number of vertices reached so far by the search algorithm. A countably infinite set of computers could explore all of reachability graphs in parallel. With a single computer, it can still be assured that everything is eventually explored by zig-zagging as shown. Thus a resolution-complete algorithm always exists if $U$ is finite. If $U$ is not finite, then $U_d$ must also be refined as the time step is decreased. Of course, there are numerous other ways to systematically explore all of the reachability graphs. The challenging task is to find a way that leads to good performance in practice.

The discussion so far has assumed that a sampling-based algorithm can uncover a subgraph of the reachability graph. This neglects numerical issues such as arithmetic precision and numerical integration error. Such issues can additionally be incorporated into a resolution completeness analysis [196].