Reachable set

Assume temporarily that there are no obstacles: $ {X_{free}}= X$. Let $ {\cal U}$ be the set of all permissible action trajectories on the time interval $ [0,\infty)$. From each $ {\tilde{u}}\in {\cal U}$, a state trajectory $ {\tilde{x}}(x_0,{\tilde{u}})$ is defined using (14.1). Which states in $ X$ are visited by these trajectories? It may be possible that all of $ X$ is visited, but in general some states may not be reachable due to differential constraints.

Let $ R(x_0,{\cal U}) \subseteq X$ denote the reachable set from $ x_0$, which is the set of all states that are visited by any trajectories that start at $ x_0$ and are obtained from some $ {\tilde{u}}\in {\cal U}$ by integration. This can be expressed formally as

$\displaystyle R(x_0,{\cal U}) = \{ x_1 \in X \;\vert\; \exists {\tilde{u}}\in {\cal U}$ and $\displaystyle \exists t \in [0,\infty)$    such that $\displaystyle x(t) = x_1 \} ,$ (14.4)

in which $ x(t)$ is given by (14.1) and requires that $ x(0) = x_0$.

The following example illustrates some simple cases.

Example 14..2 (Reachable Sets for Simple Inequality Constraints)   Suppose that $ X = {\cal C}= {\mathbb{R}}^2$, and recall some of the simple constraints from Section 13.1.1. Let a point in $ {\mathbb{R}}^2$ be denoted as $ q = (x,y)$. Let the state transition equation be $ {\dot x}=
u_1$ and $ {\dot y}= u_2$, in which $ (u_1,u_2) \in U = {\mathbb{R}}^2$.

Several constraints will now be imposed on $ U$, to define different possible action spaces. Suppose it is required that $ u_1 > 0$ (this was $ {\dot x}> 0$ in Section 13.1.1). The reachable set $ R(q_0,{\cal U})$ from any $ q_0 = (x_0,y_0) \in {\mathbb{R}}^2$ is an open half-plane that is defined by the set of all points to the right of the vertical line $ x = x_0$. In the case of $ u_1 \leq 0$, then $ R(q_0,{\cal U})$ is a closed half-plane to the left of the same vertical line. If $ U$ is defined as the set of all $ (u_1,u_2) \in {\mathbb{R}}^2$ such that $ u_1 > 0$ and $ u_2 > 0$, then the reachable set from any point is a quadrant.

For the constraint $ a u_1 + b u_2 = 0$, the reachable set from any point is a line in $ {\mathbb{R}}^2$ with normal vector $ (a,b)$. The location of the line depends on the particular $ q_0$. 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 $ u_1^2 + u_2^2 \leq 1$, the reachable set from any $ (x_0,y_0)$ is $ {\mathbb{R}}^2$. Thus, any state can reach any other state. $ \blacksquare$

So far the obstacle region has not been considered. Let $ {{\cal U}_{free}}
\subseteq {\cal U}$ denote the set of all action trajectories that produce state trajectories that map into $ {X_{free}}$. In other words, $ {{\cal U}_{free}}$ is obtained by removing from $ {\cal U}$ all action trajectories that cause entry into $ {X_{obs}}$ for some $ t > 0$. The reachable set that takes the obstacle region into account is denoted $ R(x_0,{{\cal U}_{free}})$, which replaces $ {\cal U}$ by $ {{\cal U}_{free}}$ in (14.4). This assumes that for the trajectories in $ {{\cal U}_{free}}$, 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 $ u_T$.

The completeness of an algorithm can be expressed in terms of reachable sets. For any given pair $ {x_{I}},{x_{G}}\in {X_{free}}$, a complete algorithm must report a solution action trajectory if $ {x_{G}}
\in R({x_{I}},{{\cal U}_{free}})$, 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