14.2.1.1 Reachable set

Assume temporarily that there are no obstacles: . Let be the set of all permissible action trajectories on the time interval . From each , a state trajectory is defined using (14.1). Which states in are visited by these trajectories? It may be possible that all of is visited, but in general some states may not be reachable due to differential constraints.

Let denote the reachable set from , which is the set of all states that are visited by any trajectories that start at and are obtained from some by integration. This can be expressed formally as

 and     such that (14.4)

in which is given by (14.1) and requires that .

The following example illustrates some simple cases.

Example 14..2 (Reachable Sets for Simple Inequality Constraints)   Suppose that , and recall some of the simple constraints from Section 13.1.1. Let a point in be denoted as . Let the state transition equation be and , in which .

Several constraints will now be imposed on , to define different possible action spaces. Suppose it is required that (this was in Section 13.1.1). The reachable set from any is an open half-plane that is defined by the set of all points to the right of the vertical line . In the case of , then is a closed half-plane to the left of the same vertical line. If is defined as the set of all such that and , then the reachable set from any point is a quadrant.

For the constraint , the reachable set from any point is a line in with normal vector . The location of the line depends on the particular . Thus, a family of parallel lines is obtained by considering reachable states from different initial states. This is an example of a foliation in differential geometry, and the lines are called leaves [872].

In the case of , the reachable set from any is . Thus, any state can reach any other state.

So far the obstacle region has not been considered. Let denote the set of all action trajectories that produce state trajectories that map into . In other words, is obtained by removing from all action trajectories that cause entry into for some . The reachable set that takes the obstacle region into account is denoted , which replaces by in (14.4). This assumes that for the trajectories in , the termination action can be applied to avoid inevitable collisions due to momentum. A smaller reachable set could have been defined that eliminates trajectories for which collision inevitably occurs without applying .

The completeness of an algorithm can be expressed in terms of reachable sets. For any given pair , a complete algorithm must report a solution action trajectory if , or report failure otherwise. Completeness is too difficult to achieve, except for very limited cases [171,747]; therefore, sampling-based notions of completeness are more valuable.

Steven M LaValle 2012-04-20