8.5.1.1 An approximate cover

Figure: An approximate cover is shown. Every point of $ {\tilde{X}}$ is contained in at least one neighborhood, and $ {\tilde{X}}$ is a subset of $ X$.
\begin{figure}\centerline{\psfig{file=figs/appcov.eps,width=3.0truein}}\end{figure}

Figure 8.15 illustrates the notion of an approximate cover, which will be used to represent the funnel domains. Let $ {\tilde{X}}$ denote a subset of a state space $ X$. A cover of $ {\tilde{X}}$ is a collection $ {\cal O}$ of sets for which

  1. $ O \subseteq X$ for each $ O \in {\cal O}$.
  2. $ {\tilde{X}}$ is a subset of the union of all sets in the cover:

    $\displaystyle {\tilde{X}}\subseteq \bigcup_{O \in {\cal O}} O .$ (8.50)

Let each $ O \in {\cal O}$ be called a neighborhood. The notion of a cover was actually used in Section 8.3.2 to define a smooth manifold using a cover of coordinate neighborhoods.

In general, a cover allows the following:

  1. Any number of neighborhoods may overlap (have nonempty intersection).
  2. Any neighborhood may contain points that lie outside of $ {\tilde{X}}$.
A cell decomposition, which was introduced in Section 6.3.1, is a special kind of cover for which the neighborhoods form a partition of $ {\tilde{X}}$, and they must fit together nicely (recall Figure 6.15).

So far, no constraints have been placed on the neighborhoods. They should be chosen in practice to greatly simplify the design of a navigation function over each one. For the original motion planning problem, cell decompositions were designed to make the determination of a collision-free path trivial in each cell. The same idea applies here, except that we now want to construct a feedback plan. Therefore, it is usually assumed that the cells have a simple shape.

A cover is called approximate if $ {\tilde{X}}$ is a strict subset of $ X$. Ideally, we would like to develop an exact cover, which implies that $ {\tilde{X}}= X$ and each neighborhood has some nice property, such as being convex. Developing such covers is possible in practice for state spaces that are either low-dimensional or exhibit some special structure. This was observed for the cell decomposition methods of Chapter 6.

Consider constructing an approximate cover for $ X$. The goal should be to cover as much of $ X$ as possible. This means that $ \mu(X
\setminus {\tilde{X}})$ should be made as small as possible, in which $ \mu$ denotes Lebesgue measure, as defined in Section 5.1.3. It is also desirable to ensure that $ {\tilde{X}}$ preserves the connectivity of $ X$. In other words, if a path between two points exists in $ X$, then it should also exist in $ {\tilde{X}}$.

Steven M LaValle 2020-08-14