Combinatorial methods

In some cases, combinatorial methods can be used to solve time-varying problems. If the motion model is algebraic (i.e., expressed with polynomials), then ${X_{obs}}$ is semi-algebraic. This enables the application of general planners from Section 6.4, which are based on computational real algebraic geometry. The key issue once again is that the resulting roadmap must be directed with all edges being time-monotonic. For Canny's roadmap algorithm, this requirement seems difficult to ensure. Cylindrical algebraic decomposition is straightforward to adapt, provided that time is chosen as the last variable to be considered in the sequence of projections. This yields polynomials in ${\mathbb{Q}}[t]$, and ${\mathbb{R}}$ is nicely partitioned into time intervals and time instances. Connections can then be made for a cell of one cylinder to an adjacent cell of a cylinder that occurs later in time.

If ${X_{obs}}$ is polyhedral as depicted in Figure 7.1, then vertical decomposition can be used. It is best to first sweep the plane along the time axis, stopping at the critical times when the linear motion changes. This yields nice sections, which are further decomposed recursively, as explained in Section 6.3.3, and also facilitates the connection of adjacent cells to obtain time-monotonic path segments. It is not too difficult to imagine the approach working for a four-dimensional state space, $X$, for which ${\cal C}_{obs}(t)$ is polyhedral as in Section 6.3.3, and time adds the fourth dimension. Again, performing the first sweep with respect to the time axis is preferable.

Figure 7.2: Transitivity is broken if the cells are not formed in cylinders over $T$. A time-monotonic path exists from $C_1$ to $C_2$, and from $C_2$ to $C_3$, but this does not imply that one exists from $C_1$ to $C_3$.

If $X$ is not decomposed into cylindrical slices over each noncritical time interval, then cell decompositions may still be used, but be careful to correctly connect the cells. Figure 7.2 illustrates the problem, for which transitivity among adjacent cells is broken. This complicates sample point selection for the cells.