8.5.1 Computing a Composition of Funnels

Mason introduced the concept of a funnel as a metaphor for motions that converge to the same small region of the state space, regardless of the initial position [679]. As grains of sand in a funnel, they follow the slope of the funnel until they reach the opening at the bottom. A navigation function can be imagined as a funnel that guides the state into the goal. For example, the cost-to-go function depicted in Figure 8.13d can be considered as a complicated funnel that sends each piece of sand along an optimal path to the goal.

Rather than designing a single funnel, consider decomposing the state space into a collection of simple, overlapping regions. Over each region, a funnel can be designed that leads the state into another funnel; see Figure 8.14. As an example, the approach in [162] places a Lyapunov function (such functions are covered in Section 15.1.2) over each funnel to ensure convergence to the next funnel. A feedback plan can be constructed by composing several funnels. Starting from some initial state in $ X$, a sequence of funnels is visited until the goal is reached. Each funnel essentially solves the subgoal of reaching the next funnel. Eventually, a funnel is reached that contains the goal, and a navigation function on this funnel causes the goal to be reached. In the context of sensing uncertainty, for which the funnel metaphor was developed, the composition of funnels becomes the preimage planning framework [659], which is covered in Section 12.5.1. In this section, however, it is assumed that the current state is always known.

Figure 8.14: A navigation function and corresponding vector field can be designed as a composition of funnels.

Steven M LaValle 2012-04-20