8.4.2 Vector Fields Over Cell Complexes

This section describes how to construct a piecewise-smooth vector field over a cell complex. Only normalized vector fields will be considered. It is assumed that each cell in the complex has a simple shape over which it is easy to define a patch of the vector field. In many cases, the cell decomposition techniques that were introduced in Chapter 6 for motion planning can be applied to construct a feedback plan.

Suppose that an $n$-dimensional state space $X$ has been decomposed into a cell complex, such as a simplicial complex or singular complex, as defined in Section 6.3.1. Assume that the goal set is a single point, ${x_{G}}$. Defining a feedback plan $\pi$ over $X$ requires placing a vector field on $X$ for which all integral curves lead to ${x_{G}}$ (if ${x_{G}}$ is reachable). This is accomplished by defining a smooth vector field for each $n$-cell. Each $(n-1)$-cell is a switching boundary, as considered in Section 8.3.1. This leads directly to solution trajectories in the sense of Filipov. If $\pi$ is allowed to be discontinuous, then it is actually not important to specify values on any of the cells of dimension $n-1$ or less.

A hierarchical approach is taken to the construction of $\pi$:

1. Define a discrete planning problem over the $n$-cells. The cell that contains ${x_{G}}$ is designated as the goal, and a discrete navigation function is defined over the cells.
2. Define a vector field over each $n$-cell. The field should cause all states in the cell to flow into the next cell as prescribed by the discrete navigation function.

One additional consideration that is important in applications is to try to reduce the effect of the discontinuity across the boundary as much as possible. It may be possible to eliminate the discontinuity, or even construct a smooth transition between $n$-cells. This issue will not be considered here, but it is nevertheless quite important [235,643].

The approach will now be formalized. Suppose that a cell complex has been defined over a continuous state space, $X$. Let ${\check X}$ denote the set of $n$-cells, which can be interpreted as a finite state space. A discrete planning problem will be defined over ${\check X}$. To avoid confusion with the original continuous problem, the prefix super will be applied to the discrete planning components. Each superstate ${\check x}\in {\check X}$ corresponds to an $n$-cell. From each ${\check x}$, a superaction, ${\check u}\in {\check U}({\check x})$ exists for each neighboring $n$-cell (to be neighboring, the two cells must share an $(n-1)$-dimensional boundary). Let the goal superstate ${{\check x}_g}$ be the $n$-cell that contains ${x_{G}}$. Assume that the cost functional is defined for the discrete problem so that every action (other than $u_T$) produces a unit cost. Now the concepts from Section 8.2 can be applied to the discrete problem. A discrete navigation function, ${\check \phi}: {\check X}\rightarrow {\mathbb{R}}$, can be computed using Dijkstra's algorithm (or another algorithm, particularly if optimality is not important). Using the discrete local operator from Section 8.2.2, this results in a discrete feedback plan, ${\check \pi }: {\check X}\rightarrow {\check U}$.

Based on the discrete feedback plan, there are two kinds of $n$-cells. The first is the goal cell, ${{\check x}_g}$, for which a vector field needs to be defined so that all integral curves lead to $X_g$ in finite time.^8.11 A termination action can be applied when ${x_{G}}$ is actually reached. The remaining $n$-cells are of the second kind. For each cell ${\check x}$, the boundary that is shared with the cell reached by applying ${\check u}= {\check \pi }({\check x})$ is called the exit face. The vector field over the $n$-cell ${\check x}$ must be defined so that all integral curves lead to the exit face. When the exit face is reached, a transition will occur into the next $n$-cell. If the $n$-cells are convex, then defining this transition is straightforward (unless there are additional requirements on the field, such as smoothness at the boundary). For more complicated cells, one possibility is to define a vector field that retracts all points onto a single curve in the cell.

A simple example of the approach is illustrated for the case of $X = {\cal C}_{free}\subset {\mathbb{R}}^2$, in which the boundary of ${\cal C}_{free}$ is polygonal. This motion planning problem was considered in Section 6.2, but without feedback. Suppose that a triangulation of $X$ has been computed, as described in Section 6.3.2. An example was shown in Figure 6.16. A discrete feedback plan is shown for a particular goal state in Figure 8.10. Each $2$-cell (triangle) is labeled with an arrow that points to the next cell.

Figure 8.10: A triangulation is used to define a vector field over $X$. All solution trajectories lead to the goal.

For the cell that contains ${x_{G}}$, a normalized version of the inward vector field shown in Figure 8.5b can be formed by dividing each nonzero vector by its magnitude. It can then be translated to move its origin to ${x_{G}}$. For each remaining $2$-cell, a vector field must be constructed that flows into the appropriate neighboring cell. Figure 8.11 illustrates a simple way to achieve this. An outward vector field can be made by negating the field shown in Figure 8.5b to obtain $f = [x\;\;y]$. This field can be normalized and translated to move the origin to the triangle vertex that is not incident to the exit edge. This is called the repulsive vertex in Figure 8.11. This generates a vector field that pushes all points in the triangle to the ext edge. If the fields are constructed in this way for each triangle, then the global vector field represents a solution feedback plan for the problem. Integral curves (in the sense of Filipov) lead to ${x_{G}}$ in finite time.

Figure 8.11: A vector field can be defined for each triangle by repelling from a vertex that opposes the exit edge.