8.5.1.2 Defining a feedback plan over a cover

The ideas from Section 8.4.2 can be adapted to define a feedback plan over ${\tilde{X}}$ using a cover. Let ${\check X}$ denote a discrete state space in which each superstate is a neighborhood. Most of the components of the associated discrete planning problems are the same as in Section 8.4.2. The only difference is in the definition of superactions because neighborhoods can overlap in a cover. For each neighborhood $O \in {\cal O}$, a superaction exists for each other neighborhood, $O' \in {\cal O}$ such that $O \cap O' \not = \emptyset$ (usually, their interiors overlap to yield $\operatorname{int}(O) \cap \operatorname{int}(O') \not = \emptyset$).

Figure 8.16: A transition from $O$ to $O'$ is caused by a vector field on $O$ for which all integral curves lead into $O \cap O'$.

Note that in the case of a cell decomposition, this produces no superactions because it is a partition. To follow the metaphor of composing funnels, the domains of some funnels should overlap, as shown in Figure 8.14. A transition from one neighborhood, $O$, to another, $O'$, is obtained by defining a vector field on $O$ that sends all states from $O \setminus O'$ into $O \cap O'$; see Figure 8.16. Once $O'$ is reached, the vector field of $O$ is no longer followed; instead, the vector field of $O'$ is used. Using the vector field of $O'$, a transition may be applied to reach another neighborhood. Note that the jump from the vector field of $O$ to that of $O'$ may cause the feedback plan to be a discontinuous vector field on ${\tilde{X}}$. If the cover is designed so that $O \cap O'$ is large (if they intersect), then gradual transitions may be possible by blending the vector fields from $O$ and $O'$.

Once the discrete problem has been defined, a discrete feedback plan can be computed over ${\check X}$, as defined in Section 8.2. This is converted into a feedback plan over $X$ by defining a vector field on each neighborhood that causes the appropriate transitions. Each ${\check x}\in {\check X}$ can be interpreted both as a superstate and a neighborhood. For each ${\check x}$, the discrete feedback plan produces a superaction ${\check u}= \pi ({\check x})$, which yields a new neighborhood ${\check x}'$. The vector field over ${\check x}= O$ is then designed to send all states into ${\check x}' = O'$.

If desired, a navigation function $\phi$ over $X$ can even be derived from a navigation function, ${\check \phi}$, over ${\check X}$. Suppose that ${\check \phi}$ is constructed so that every ${\check \phi}({\check x})$ is distinct for every ${\check x}\in {\check X}$. Any navigation function can be easily transformed to satisfy this constraint (because ${\check X}$ is finite). Let $\phi_O$ denote a navigation function over some $O \in {\cal O}$. Assume that ${X_{G}}$ is a point, ${x_{G}}$ (extensions can be made to more general cases). For every neighborhood $O \in {\cal O}$ such that ${x_{G}}\not \in O$, $\phi_O$ is defined so that performing gradient descent leads into the overlapping neighborhood for which ${\check \phi}({\check x})$ is smallest. If $O$ contains ${x_{G}}$, the navigation function $\phi_O$ simply guides the state to ${x_{G}}$.

The navigation functions over each $O \in {\cal O}$ can be easily pieced together to yield a navigation function over all of $X$. In places where multiple neighborhoods overlap, $\phi$ is defined to be the navigation function associated with the neighborhood for which ${\check \phi}({\check x})$ is smallest. This can be achieved by adding a large constant to each $\phi_O$. Let $c$ denote a constant for which $\phi_O(x) < c$ over all $O \in {\cal O}$ and $x \in O$ (it is assumed that each $\phi_O$ is bounded). Suppose that ${\check \phi}$ assumes only integer values. Let ${\cal O}(x)$ denote the set of all $O \in {\cal O}$ such that $x \in O$. The navigation function over $X$ is defined as

$$\phi(x) = \min_{O \in {\cal O}(x)} \Big\{ \phi_O(x) + c {\check \phi}(O) \Big\} .$$ (8.51)