The controllability concept discussed so far has no concern for how
far the trajectory travels in before is reached. This
issue becomes particularly important for underactuated systems and
planning among obstacles. These concerns motivate a natural question:
Is there a form of controllability that is naturally suited for
obstacles? It should declare that if a state is reachable from
another in the absence of differential constraints, then it is also
reachable with the given system
. This can be
expressed using time-limited reachable sets. Let
denote
the set of all states reachable in time less than or equal to ,
starting from . A system
is called
*small-time locally controllable* (STLC) from if there
exists some such that
for
all
(here,
denotes the interior of a set, as
defined in Section 4.1.1). If the system
is STLC from every
, then the whole system is
said to be STLC.

Consider using this definition to answer the question above. Since is an open set, there must exist some small for which the open ball is a strict subset of . See Figure 15.2. Any point on the boundary of can be reached, which means that a step of size can be taken in any direction, even though differential constraints exist. With obstacles, however, we have to be careful that the trajectory from to the surface of does not wander too far away.

Suppose that there is an obstacle region , and a violation-free state trajectory is given that terminates in at time and does not necessarily satisfy a given system. If the system is STLC, then it is always possible to find another trajectory, based on , that satisfies the differential constraints. Apply the plan-and-transform method of Section 14.6.2. Suppose that intervals for potential replacement are chosen using binary recursive subdivision. Also suppose that an LPM exists that computes that shortest trajectory between any pair of states; this trajectory ignores obstacles but respects the differential constraints. Initially, is replaced by a trajectory from the LPM, and if it is not violation-free, then is subdivided into and , and replacement is attempted on the smaller intervals. This idea can be applied recursively until eventually the segments are small enough that they must be violation-free.

This final claim is implied by the STLC property. No matter how small the intervals become, there must exist a replacement trajectory. If an interval is large, then there may be sufficient time to wander far from the original trajectory. However, as the time interval decreases, there is not enough time to deviate far from the original trajectory. (This discussion assumes mild conditions on , such as being Lipschitz.) Suppose that the trajectory is protected by a collision-free tube of radius . Thus, all points along the trajectory are at least from the boundary of . The time intervals can be chosen small enough to ensure that the trajectory deviations are less than from the original trajectory. Therefore, STLC is a very important property for a system to possess for planning in the presence of obstacles. Section 15.4 covers some mathematical tools for determining whether a nonlinear system is STLC.

A concept closely related to controllability is *accessibility*,
which is only concerned with the dimension of the reachable set. Let
be the dimension of . If there exists some for which
the dimension of
is , then the system is called
*accessible* from .
Alternatively, this may be expressed as requiring that
.

Steven M LaValle 2012-04-20