... machine.^1.1

Of course, having infinitely long tape seems impossible in the physical world. Other versions of Turing machines exist in which the tape is finite but as long as necessary to process the given input. This may be more appropriate for the discussion.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... computation.^1.2

Performing computations with mechanical systems is discussed in [815]. Computation models over the reals are covered in [118].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...optimal^2.1

As in optimization literature, we will use $^*$ to mean optimal.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....^2.2

In some variations, the vertex could be added without a corresponding edge. This would start another tree in a multiple-tree approach

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... iteration,^2.3

The ``value'' here refers to the optimal cost-to-go or cost-to-come. Therefore, an alternative name could be cost-to-go iteration.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... literals^2.4

The pair of literals need not be a complementary pair, as defined in Section 2.4.1.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... conjunction^2.5

Conjunction means logical AND.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... contains^3.1

In this section, we want the resulting set to include all of the points along the boundary. Therefore, $<$ is used to model a set for removal, as opposed to $\leq$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... primitives.^3.2

An alternative that yields the same expressive power is to still use $\leq$, but allow set complements, in addition to unions and intersections.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... frame.^3.3

The world frame serves the same purpose as an inertial frame in Newtonian mechanics. Intuitively, it is a frame that remains fixed and from which all measurements are taken. See Section 13.3.1.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...placing^3.4

Technically, this placement is a function called an orientation-preserving isometric embedding.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... balls.^4.1

Such a collection of balls is often referred to as a basis.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... graph^4.2

In topology this is called a 1-complex [439].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... theory.^4.3

Technically, the images of the topological graphs, as subspaces of $X$, are homeomorphic, not the graphs themselves.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...manifold^4.4

Manifolds that are not subsets of ${\mathbb{R}}^m$ may also be defined. This requires that $M$ is a Hausdorff space and is second countable, which means that there is a countable number of open sets from which any other open set can be constructed by taking a union of some of them. These conditions are automatically satisfied when assuming $M \subseteq {\mathbb{R}}^m$; thus, it avoids these extra complications and is still general enough for our purposes. Some authors use the term manifold to refer to a smooth manifold. This requires the definition of a smooth structure, and the homeomorphism is replaced by diffeomorphism. This extra structure is not needed here but will be introduced when it is needed in Section 8.3.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... manifold.^4.5

One variant of the theorem is that for smooth manifolds, ${\mathbb{R}}^{2n}$ is sufficient. This bound is tight because ${\mathbb{RP}}^n$ ($n$-dimensional projective space, which will be introduced later in this section), cannot be embedded in ${\mathbb{R}}^{2n - 1}$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... distinct.^4.6

This is usually defined more formally and called a quotient topology.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... happen,^4.7

The topologist's sine curve is not a manifold because all open sets that contain the point $(0,0)$ contain some of the points from the sine curve. These open sets are not homeomorphic to ${\mathbb{R}}$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... space.^4.8

The groups considered in this section are actually Lie groups because they are smooth manifolds [63]. We will not use that name here, however, because the notion of a smooth structure has not yet been defined. Readers familiar with Lie groups, however, will recognize most of the coming concepts. Some details on Lie groups appear later in Sections 15.4.3 and 15.5.1.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...eqn:quatmat).^4.9

Since that function was two-to-one, it is technically not an inverse until the quaternions are restricted to the upper hemisphere, as described previously.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... difference^4.10

In some contexts, which include mathematics and image processing, the Minkowski difference or Minkowski subtraction is defined differently (instead, it is a kind of ``erosion''). For this reason, some authors prefer to define all operations in terms of the Minkowski sum, $\oplus$, which is consistently defined in all contexts. Following this convention, we would define $X \oplus (-Y)$, which is equivalent to $X \ominus Y$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... nicely.^4.11

This is called a Whitney stratification [173,968].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... space.^5.1

Some topological spaces are not metrizable, which means that no function exists that satisfies the axioms. Many metrization theorems give sufficient conditions for a topological space to be metrizable [451], and virtually any space that has arisen in motion planning will be metrizable.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... measure^5.2

Such a measure is unique up to scale and exists for any locally compact topological group [346,836].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... random,^5.3

See Section 9.1.2 for a review of probability theory.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... random.^5.4

The directions will be formalized in Section 8.3.2 when smooth manifolds are introduced. In that case, the directions correspond to the set of possible velocities that have unit magnitude. Presently, the notion of a direction is only given informally.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... random.^5.5

There are exceptions, which use physical phenomena as a random source [808].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...dispersion^5.6

The definition is unfortunately backward from intuition. Lower dispersion means that the points are nicely dispersed. Thus, more dispersion is bad, which is counterintuitive.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... is^5.7

The $\sup$ represents the supremum, which is the least upper bound. If $X$ is closed, then the $\sup$ becomes a $\max$. See Section 9.1.1 for more details.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... direction^5.8

To formally talk about directions, it would be better to define a differentiable structure on ${\cal C}$. This will be deferred to Section 8.3, where it seems unavoidable.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... trap^5.9

This principle is actually used in real life to trap flying bugs. This analogy was suggested by James O'Brien in a discussion with James Kuffner.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... form^5.10

Alternatively, the general lattice definition in (5.21) could be used.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... nearly^5.11

It is not constant because the running time is proportional to the inverse Ackerman function, which grows very, very slowly. For all practical purposes, the algorithm operates in constant time. See Section 6.5.2.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... bowl.^5.12

Of course, that problem does not appear to need so many points per axis; fewer may be used instead, if the algorithm can adapt the sampling resolution or dispersion.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... algorithms.^5.13

The exciting results obtained by the method even helped inspire me many years ago to work on motion planning.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... tuning.^5.14

The original RRT [598] was introduced with a step size parameter, but this is eliminated in the current presentation. For implementation purposes, one might still want to revert to this older way of formulating the algorithm because the implementation is a little easier. This will be discussed shortly.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... behavior.^5.15

If ${\alpha }$ is uniform, random, then a stochastic fractal [586] is obtained. Deterministic fractals can be constructed using sequences that have appropriate symmetries.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... PSPACE-hard^6.1

This implies NP-hard. An overview of such complexity statements appears in Section 6.5.1.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... simple^6.2

A polygonal region that has no holes.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... advance.^6.3

Exceptions to this are some algorithms mentioned in Section 6.5.3, which obtain greater efficiency by only maintaining one connected component of ${\cal C}_{obs}$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... collision-free.^6.4

This is the reason why the approach is defined differently from Chapter 1 of [588]. In that case, sample points were not placed in the interiors of the 2-cells, and collision could result for some queries.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... independent^6.5

Form $k$ vectors by subtracting $p_1$ from the other $k$ points for some positive integer $k$ such that $k \leq n$. Arrange the vectors into a $k \times n$ matrix. For linear independence, there must be at least one $k \times k$ cofactor with a nonzero determinant. For example, if $k=2$, then the three points cannot be collinear.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... polynomials^6.6

It will be explained shortly why ${\mathbb{Q}}[x_1,\ldots, x_n]$ is preferred over ${\mathbb{R}}[x_1,\ldots, x_n]$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... time.^6.7

Note that this definition may be absurd in practice; an algorithm that runs in time $O(n^{90125})$ would probably not be too efficient for most purposes.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... etc.).^6.8

If you remember hearing that a planning problem is NP-something, but cannot remember whether it was NP-hard or NP-complete, then it is safe to say NP-hard because NP-complete implies NP-hard. This can similarly be said for other classes, such as PSPACE-complete vs. PSPACE-hard.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...Sha04^6.9

The following asymptotic notion is used: $O(f(n))$ denotes an upper bound, $\Omega(f(n))$ denotes a lower bound, and $\Theta(f(n))$ means that the bound is tight (both upper and lower). This notation is used in most books on algorithms [243].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....^6.10

It may seem odd for $O(\cdot)$ to appear in the middle of an expression. In this context, it means that there exists some $c \in [0,\infty)$ such that the running time is bounded by $(md)^{c^n}$. Note that another $O$ is not necessary in front of the whole formula.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... necessary.^7.1

The infinite acceleration and unbounded speed assumptions may annoy those with mechanics and control backgrounds. In this case, assume that the present models approximate the case in which every body moves slowly, and the dynamics can be consequently neglected. If this is still not satisfying, then jump ahead to Part IV, where general nonlinear systems are considered. It is still helpful to consider the implications derived from the concepts in this chapter because the issues remain for more complicated problems that involve dynamics.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...portiernia,^7.2

This is a place where people guard the keys at some public facilities in Poland.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... plane^7.3

Tangent planes are defined rigorously in Section 8.3.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... stopped.^7.4

This model allows infinite acceleration. Imagine that the speeds are slow enough to allow this approximation. If this is still not satisfactory, then jump ahead to Chapter 13.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... constraints.^8.1

Section 8.4.4 will actually consider some simple differential constraints, such as acceleration bounds; the full treatment of differential constraints is deferred until Part IV.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... function.^8.2

This term was developed for continuous configuration spaces in [541,829]; it will be used more broadly in this book but still retains the basic idea.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... space.^8.3

Difficulty in distinguishing between these two caused researchers for many years to believe that grids yield terrible performance for the open-loop path planning problems of Chapter 5. This was mainly because it was assumed that a high-resolution grid was necessary. For many problems, however, they could terminate early after only considering a few points per axis.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... field^8.4

Unfortunately, the term field appears in two unrelated places: in the definition of a vector space and in the term vector field. Keep in mind that this is an accidental collision of terms.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... structure^8.5

Alternative names are differentiable structure and $C^\infty$ structure.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... family^8.6

In literature in which the coordinate neighborhoods are called charts, this family is called an atlas.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... them.^8.7

This is under the assumption that $M$ is Hausdorff and has a countable basis of open sets, which applies to the manifolds considered here.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... manifold.^8.8

Alternative names are differentiable manifold and $C^\infty$ manifold.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...sec:defbmp.^8.9

Note that $X$ already excludes the obstacle region. For some problems in Part IV, the state space will be $X = {\cal C}$, which includes the obstacle region.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... state.^8.10

This allows discontinuous changes in velocity, which is unrealistic in many applications. Additional constraints, such as imposing acceleration bounds, will also be discussed. For a complete treatment of differential constraints, see Part IV.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... time.^8.11

This is possible in finite time, even if $X_g$ is a single point, because the vector field is not continuous. Otherwise, only asymptotic convergence may be possible.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... connectivity.^8.12

This precludes a choice of ${\cal C}_{free}$ for which adding the boundary point enables a homotopically distinct path to be made through the boundary point. An example of this is when two square obstacles in ${\mathbb{R}}^2$ contact each other only at a pair of corners.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... definite,^8.13

Positive definite for an $n \times n$ matrix $A$ means that for all $x \in {\mathbb{R}}^n$, $x^T A x > 0$. If $A$ is symmetric (which applies to $H(\phi)$), then this is equivalent to $A$ having all positive eigenvalues.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... definite,^8.14

Negative definite means that for all $x \in {\mathbb{R}}^n$, $x^T A x < 0$. If $A$ is symmetric, then this is equivalent to $A$ having all negative eigenvalues.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....^8.15

Some authors do not include the global minimum as a local minimum. In this case, one would say that there are no local minima.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... degenerate.^8.16

Technically, to be Morse, the values of the function must also be distinct at each critical point.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... variable^9.1

This is a terrible name, which often causes confusion. A random variable is not ``random,'' nor is it a ``variable.'' It is simply a function, $X : S \rightarrow {\mathbb{R}}$. To make matters worse, a capital letter is usually used to denote it, whereas lowercase letters are usually used to denote functions.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... then^9.2

Using the language of measure theory, both definitions are just special cases of the Lebesgue integral. Measure theory nicely unifies discrete and continuous probability theory, thereby avoiding the specification of separate cases. See [346,546,836].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... space).^9.3

Alternatively, a random variable may be defined over $U \times \Theta$, and conditional expectation would be taken, in which $u$ is given.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... matrices.^9.4

If you enjoy working with tensors, these could be used to capture $n$-player cost functions [107].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... outcomes.^9.5

In most utility theory literature, this is referred to as a reward space, ${\mathcal R}$ [89].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...:^9.6

Alternative axiom systems exist [268,839].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... transitive.^9.7

For some reasonable problems, however, transitivity is not desirable. See the Candorcet and Simpson paradoxes in [831].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... reward.^9.8

Some axiom systems allow infinite rewards, which lead to utility and cost functions with infinite values, but this is not considered here.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... practice.^9.9

A locally compact topological group is required [346,836].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... distributions.^9.10

Readers familiar with the movie The Princess Bride may remember the humorous dialog between Vizzini and the Dread Pirate Roberts about which goblet contains the deadly Iocane powder.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ``Doh!''^9.11

In 2001, the Homer Simpson term``Doh!'' was added to the Oxford English Dictionary as an expression of regret.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....^10.1

The state space $X$ may even be infinite, but this requires that the set of possible costs is bounded.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... available.^11.1

Such a problem could be quite interesting to study, but it will not be considered here.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... I-map.^11.2

Ideally, the mapping should be onto ${\cal I}_{der}$; however, to facilitate some definitions, this will not be required.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....^11.3

One notable exception is in the theory of nondeterministic finite automata, in which it is possible that all copies of the machine die and there is no possible current state [891].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... space.^11.4

If you did not read Chapter 4 and are not familiar with manifold concepts, then assume $X = {\mathbb{R}}^n$; it will not make much difference. Make similar assumptions for $Y$, $\Psi(x)$, $U$, and $\Theta(x,u)$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...,^11.5

Assume that all continuous spaces are measure spaces and all probability density functions are measurable functions over these spaces.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... functions.^11.6

To appreciate of the size of this space, it can generally be viewed as an infinite-dimensional vector space (recall Example 8.5). Consider, for example, representing each function with a series expansion. To represent any analytic function exactly over $[0,1]$, an infinite sequence of real-valued coefficients may be needed. Each sequence can be considered as an infinitely long vector, and the set of all such sequences forms an infinite-dimensional vector space. See [346,836] for more background on function spaces and functional analysis.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...sec:col-reg.^11.7

This can also be handled, but it just adds unnecessary complication to the current discussion.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... edges.^11.8

This example was significantly refined after a helpful discussion with Rob Ghrist.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... functions.^12.1

These are single points that are assigned a nonzero probability mass, which is not allowed, for example, in the construction of a continuous probability density function.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... sensors:^12.2

This is just one possible sensing model. Alternative combinations of sensors may be used, provided that they enable the required motions and decisions to be executed in the coming motion strategies.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... as^12.3

In practice, a logarithm is applied to $p({\eta}_K,q_k\vert\;e)$ because densities that contain exponentials usually arise. Taking the logarithm makes the expressions simpler without affecting the result of the optimization. The $\log$ is not applied here because this level of detail is not covered.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....^12.4

Following from standard function notation, it is better to use ${\tilde{e}}(t)$ instead of $e(t)$ to denote the position at time $t$; however, this will not be followed.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....^12.5

To follow the notation of Section 11.4 more closely, the motion model $\dot{p} = u$ can be used, in which $u$ represents the velocity of the pursuer. Nature actions can be used to model the velocity of the evader to obtain $\dot{e}$. By integrating $\dot{p}$ over time, $p(t)$ can be obtained for any $t$. This means that ${\tilde{p}_t}$ can be used as a simpler representation of the input history, instead of directly referring to velocities.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... plan,^12.6

Note that this open-loop plan is composed of closed-loop motion commands. This is perfectly acceptable using hierarchical modeling.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... NEXPTIME-hard.^12.7

NEXPTIME is the complexity class of all problems that can be solved in nondeterministic exponential time. This is beyond the complexity classes shown in Figure 6.40.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... independent.^13.1

If the coefficients are placed into an $k \times n$ matrix, its rank is $k$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... speed^13.2

Having a signed speed is somewhat unorthodox. If the car moves in reverse, then $s$ is negative. A more correct name for $s$ would be velocity in the $x$ direction of the body frame, but this is too cumbersome.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....^13.3

In many works, the speed $u_s = 0$ is not included. It appears here so that a proper termination condition can be defined.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...MurSas93.^13.4

The original model required a continuous steering angle.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Integrating^13.5

Wherever integrals are performed, it will be assumed that the integrands are integrable.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... integrators.^13.6

It is called this because in block diagram representations of systems it is depicted as a chain of integrator blocks.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... system.^13.7

Be careful not to confuse control-affine systems with affine control systems, which are of the form ${\dot x}= Ax + Bu + w$, for some constant matrices $A,B$ and a constant vector $w$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... resultant^13.8

This is the sum of all forces acting on the point.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... velocity.^13.9

One important issue to be aware of is that the integral of $\omega$ is not path-invariant (see Example 2.15 of [994]).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...functional.^13.10

This is the reason why a cost functional has been used throughout the book. It is a function on a space of functions.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....^13.11

Unfortunately, $L$ is used here to represent a cost function, on which a functional $\Phi$ will be based. This conflicts with using $l$ as a cost function and $L$ as the functional in motion planning formulations. This notational collision remains because $L$ is standard notation for the Lagrangian. Be careful to avoid confusion.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... action^13.12

The notation $\gamma$ is used instead of $\theta$ to avoid conflicting with the car orientation variable $\theta$ in this particular example.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...symmetry.^14.1

Sometimes in control theory, the term symmetry applies to Lie groups. This is a different concept and means that the system is invariant with respect to transformations in a group such as $SE(3)$. For example, the dynamics of a car should not depend on the direction in which the car is pointing.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... spacecraft^14.2

This project was canceled in 2001, but similar crafts have been under development.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... complicated.^14.3

It may, however, be possible to compute crude approximations of ${X_{ric}}$ and use them in planning.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... systems^14.4

The class is all driftless, nilpotent systems. The term nilpotent will be defined in Section 15.5.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... obstacles.^14.5

One technical point: It is actually only pseudopolynomial [765] in $a_{max}$, $v_{max}$, $c_0$, $c_1$, and the width of the bounding cube in ${\cal W}$. This means that the running time is polynomial if the representations of these parameters are treated as having constant size; however, it is not polynomial in the actual number of bits needed to truly represent them.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... neighborhood^15.1

An open neighborhood of a point $x$ means an open set that contains $x$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... converges^15.2

This convergence can be evaluated using the metric $\rho$ on $X$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... analytically.^15.3

It is often surprising to computer scientists that dynamic programming in this case does not yield an algorithm. It instead yields a closed-form solution to the problem.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... definite^15.4

Nonnegative definite means $x^T Q x \geq 0$ for all $x \in {\mathbb{R}}$, and positive definite means $x^T R x > 0$ for all $x \in {\mathbb{R}}^n$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... principle^15.5

This is often called Pontryagin's maximum principle, because Pontryagin originally defined it as a maximization [801]. The Hamiltonian used in most control literature is negated with respect to Pontryagin's Hamiltonian; therefore, it becomes minimized. Both names are in common use.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...fig:rsnotation.^15.6

This differs conceptually from the notation used in [903]. There, $r^-$ corresponds to $L^-$ here. The $L$ here means that the steering wheel is positioned for a left turn, but the car is in reverse. This aids in implementing the rule that $R$ and $L$ cannot be consecutive in a word.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... driftless.^15.7

Actually, if the convex hull of $U$ contains an open set that contains the origin, then a driftless system can be simulated by rapid switching.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... distribution^15.8

This distribution has nothing to do with probability theory. It is just an unfortunate coincidence of terminology.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... sideways!^15.9

It also moves slightly forward; however, this can be eliminated by either lengthening the time of the third primitive or by considering the limit as $\Delta$ approaches zero.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... integrable.^15.10

This system is singular at the origin. A variant of the Frobenius theorem given here is technically needed.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... algebra^15.11

Intuitively, being an algebra means that polynomials can be added and multiplied; for all of the required axioms, see [469].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.