14.2.1.1 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

$$R(x_0,{\cal U}) = \{ x_1 \in X \;\vert\; \exists {\tilde{u}}\in {\cal U} \exists t \in [0,\infty) 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.