The ideas from Section 8.4.2 can be adapted to define a feedback plan over using a cover. Let 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 , a superaction exists for each other neighborhood, such that (usually, their interiors overlap to yield ).
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, , to another, , is obtained by defining a vector field on that sends all states from into ; see Figure 8.16. Once is reached, the vector field of is no longer followed; instead, the vector field of is used. Using the vector field of , a transition may be applied to reach another neighborhood. Note that the jump from the vector field of to that of may cause the feedback plan to be a discontinuous vector field on . If the cover is designed so that is large (if they intersect), then gradual transitions may be possible by blending the vector fields from and .
Once the discrete problem has been defined, a discrete feedback plan can be computed over , as defined in Section 8.2. This is converted into a feedback plan over by defining a vector field on each neighborhood that causes the appropriate transitions. Each can be interpreted both as a superstate and a neighborhood. For each , the discrete feedback plan produces a superaction , which yields a new neighborhood . The vector field over is then designed to send all states into .
If desired, a navigation function over can even be derived from a navigation function, , over . Suppose that is constructed so that every is distinct for every . Any navigation function can be easily transformed to satisfy this constraint (because is finite). Let denote a navigation function over some . Assume that is a point, (extensions can be made to more general cases). For every neighborhood such that , is defined so that performing gradient descent leads into the overlapping neighborhood for which is smallest. If contains , the navigation function simply guides the state to .
The navigation functions over each can be easily pieced together to yield a navigation function over all of . In places where multiple neighborhoods overlap, is defined to be the navigation function associated with the neighborhood for which is smallest. This can be achieved by adding a large constant to each . Let denote a constant for which over all and (it is assumed that each is bounded). Suppose that assumes only integer values. Let denote the set of all such that . The navigation function over is defined as
Steven M LaValle 2012-04-20