Beyond the trivial case of , the reachability graph is usually not a simple grid. Even if is bounded, the reachability graph may have an infinite number of vertices, even though is fixed and is finite. For a simple example, consider the Dubins car under the discretization . Fix (turn left) for all . This branch alone generates a countably infinite number of vertices in the reachability graph. The circumference of the circle is , in which is the minimum turning radius. Let . Since the circumference is an irrational number, it is impossible to revisit the initial point by traveling seconds for some integer . 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 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 and .
Suppose that and the discrete-time model is used. To ensure convergence of the discrete-time approximation, must be well-behaved. This can be established by requiring that all of the derivatives of with respect to and are bounded above and below by a constant. More generally, 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 is finite, then the Lipschitz condition is that there exists some such that
In the limit as and the dispersion of approach zero, the reachability graph becomes dense in the reachable set . 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 is bounded.
To see that resolution-complete algorithms nevertheless exist if the reachability graph is countably infinite, consider triangular enumeration, which proves that is countable, in which is the set of natural numbers. The proof proceeds by giving a sequence that starts at 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 and the dispersion of the sampling of approach zero. Each discretization produces a reachability graph that has a countable number of vertices.
A resolution-complete algorithm can be made by performing the same kind of zig-zagging that was used to show that is countable. See Figure 14.7; suppose that is finite and . 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 is finite. If is not finite, then 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 .
Steven M LaValle 2020-08-14