4.1 Basic Topological Concepts

This section introduces basic topological concepts that are helpful in understand- ing configuration spaces. Topology is a challenging subject to understand in depth. The treatment given here provides only a brief overview and is designed to stim-

127

ulate further study (see the literature overview at the end of the chapter). To advance further in this chapter, it is not necessary to understand all of the ma- terial of this section; however, the more you understand, the deeper will be your understanding of motion planning in general.

• • 1. Topological Spaces

Recall the concepts of open and closed intervals in the set of real numbers R. The open interval (0, 1) includes all real numbers between 0 and 1, except 0 and 1. However, for either endpoint, an infinite sequence may be defined that converges to it. For example, the sequence 1/2, 1/4, . . ., 1/2i converges to 0 as i tends to

infinity. This means that we can choose a point in (0, 1) within any small, positive distance from 0 or 1, but we cannot pick one exactly on the boundary of the interval. For a closed interval, such as [0, 1], the boundary points are included.

The notion of an open set lies at the heart of topology. The open set definition that will appear here is a substantial generalization of the concept of an open interval. The concept applies to a very general collection of subsets of some larger space. It is general enough to easily include any kind of configuration space that may be encountered in planning.

A set X is called a topological space if there is a collection of subsets of X called

open sets for which the following axioms hold:

• • • 1. The union of any number of open sets is an open set.
      2. The intersection of a finite number of open sets is an open set.
      3. Both X and ∅ are open sets.

Note that in the first axiom, the union of an infinite number of open sets may be taken, and the result must remain an open set. Intersecting an infinite number of open sets, however, does not necessarily lead to an open set.

For the special case of X = R, the open sets include open intervals, as ex- pected. Many sets that are not intervals are open sets because taking unions and

intersections of open intervals yields other open sets. For example, the set

I （ 1 , 2 ＼ , (4.1)

i=1

i=1

∞

3i

3i

which is an infinite union of pairwise-disjoint intervals, is an open set.

Closed sets Open sets appear directly in the definition of a topological space. It next seems that closed sets are needed. Suppose X is a topological space. A subset C X is defined to be a closed set if and only if X C is an open set. Thus, the complement of any open set is closed, and the complement of any closed set is open. Any closed interval, such as [0, 1], is a closed set because its complement,

⊂ \

(−∞, 0) ∪ (1, ∞), is an open set. For another example, (0, 1) is an open set;

Figure 4.1: An illustration of the boundary definition. Suppose X = R2, and U is a subset as shown. Three kinds of points appear: 1) x1 is a boundary point, 2) x2 is an interior point, and 3) x3 is an exterior point. Both x1 and x2 are limit points of U.

therefore, R (0, 1) = ( , 0] [1, ) is a closed set. The use of “(” may seem wrong in the last expression, but “[” cannot be used because and do not belong to R. Thus, the use of “(” is just a notational quirk.

−∞ ∞

\ −∞ ∪ ∞

Are all subsets of X either closed or open? Although it appears that open sets and closed sets are opposites in some sense, the answer is no. For X = R, the interval [0, 2π) is neither open nor closed (consider its complement: [2π, ) is

∞

closed, and ( , 0) is open). Note that for any topological space, X and are both open and closed!

−∞ ∅

Special points From the definitions and examples so far, it should seem that points on the “edge” or “border” of a set are important. There are several terms that capture where points are relative to the border. Let X be a topological space, and let U be any subset of X. Furthermore, let x be any point in X. The following terms capture the position of point x relative to U (see Figure 4.1):

If there exists an open set O1 such that x O1 and O1 U, then x is called an interior point of U. The set of all interior points in U is called the interior of U and is denoted by int(U).

• ∈ ⊆

If there exists an open set O2 such that x O2 and O2 X U, then x is called an exterior point with respect to U.

• ∈ ⊆ \

If x is neither an interior point nor an exterior point, then it is called a boundary point of U. The set of all boundary points in X is called the boundary of U and is denoted by ∂U.

•

All points in x X must be one of the three above; however, another term is often used, even though it is redundant given the other three. If x is either an interior point or a boundary point, then it is called a limit point (or accumulation point) of U. The set of all limit points of U is a closed set called

• ∈

the closure of U, and it is denoted by cl(U). Note that cl(U) = int(U) ∪ ∂U.

For the case of X = R, the boundary points are the endpoints of intervals. For example, 0 and 1 are boundary points of intervals, (0, 1), [0, 1], [0, 1), and (0, 1]. Thus, U may or may not include its boundary points. All of the points in (0, 1)

are interior points, and all of the points in [0, 1] are limit points. The motivation of the name “limit point” comes from the fact that such a point might be the limit of an infinite sequence of points in U. For example, 0 is the limit point of the

sequence generated by 1/2i for each i ∈ N, the natural numbers.

There are several convenient consequences of the definitions. A closed set C

contains the limit point of any sequence that is a subset of C. This implies that it contains all of its boundary points. The closure, cl, always results in a closed set because it adds all of the boundary points to the set. On the other hand, an open set contains none of its boundary points. These interpretations will come in handy when considering obstacles in the configuration space for motion planning.

Some examples The definition of a topological space is so general that an incredible variety of topological spaces can be constructed.

Example 4.1 (The Topology of Rn) We should expect that X = Rn for any integer n is a topological space. This requires characterizing the open sets. An open ball B(x, ρ) is the set of points in the interior of a sphere of radius ρ, centered at x. Thus,

B(x, ρ) = {x′ ∈ Rn | Ix′ − xI < ρ}, (4.2)

in which denotes the Euclidean norm (or magnitude) of its argument. The open balls are open sets in Rn. Furthermore, all other open sets can be expressed as a countable union of open balls.1 For the case of R, this reduces to representing any open set as a union of intervals, which was done so far.

I · I

Even though it is possible to express open sets of Rn as unions of balls, we pre- fer to use other representations, with the understanding that one could revert to open balls if necessary. The primitives of Section 3.1 can be used to generate many interesting open and closed sets. For example, any algebraic primitive expressed in the form H = x Rn f(x) 0 produces a closed set. Taking finite unions and intersections of these primitives will produce more closed sets. Therefore, all of the models from Sections 3.1.1 and 3.1.2 produce an obstacle region that is

O

{ ∈ | ≤ }

a closed set. As mentioned in Section 3.1.2, sets constructed only from primitives that use the < relation are open. ．

Example 4.2 (Subspace Topology) A new topological space can easily be con- structed from a subset of a topological space. Let X be a topological space, and let Y X be a subset. The subspace topology on Y is obtained by defining the open sets to be every subset of Y that can be represented as U Y for some open set U X. Thus, the open sets for Y are almost the same as for X, except

⊆

∩

⊂

that the points that do not lie in Y are trimmed away. New subspaces can be constructed by intersecting open sets of Rn with a complicated region defined by semi-algebraic models. This leads to many interesting topological spaces, some of

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

which will appear later in this chapter. ．

Example 4.3 (The Trivial Topology) For any set X, there is always one triv- ial example of a topological space that can be constructed from it. Declare that

1. and ∅ are the only open sets. Note that all of the axioms are satisfied. ．

Example 4.4 (A Strange Topology) It is important to keep in mind the al- most absurd level of generality that is allowed by the definition of a topological space. A topological space can be defined for any set, as long as the declared open sets obey the axioms. Suppose a four-element set is defined as

X = {cat, dog, tree, house}. (4.3)

In addition to and X, suppose that cat and dog are open sets. Using the axioms, cat, dog must also be an open set. Closed sets and boundary points

{ }

∅ { } { }

can be derived for this topology once the open sets are defined. ．

After the last example, it seems that topological spaces are so general that not much can be said about them. Most spaces that are considered in topology and analysis satisfy more axioms. For Rn and any configuration spaces that arise in

this book, the following is satisfied:

Hausdorff axiom: For any distinct x1, x2 ∈ X, there exist open sets O1 and

O2 such that x1 ∈ O1, x2 ∈ O2, and O1 ∩ O2 = ∅.

In other words, it is possible to separate x1 and x2 into nonoverlapping open sets. Think about how to do this for Rn by selecting small enough open balls. Any topological space X that satisfies the Hausdorff axiom is referred to as a Hausdorff

space. Section 4.1.2 will introduce manifolds, which happen to be Hausdorff spaces and are general enough to capture the vast majority of configuration spaces that arise. We will have no need in this book to consider topological spaces that are not Hausdorff spaces.

Continuous functions A very simple definition of continuity exists for topo- logical spaces. It nicely generalizes the definition from standard calculus. Let

f : X → Y denote a function between topological spaces X and Y . For any set

B ⊆ Y , let the preimage of B be denoted and defined by

f−1(B) = {x ∈ X | f(x) ∈ B}. (4.4)

Note that this definition does not require f to have an inverse.

The function f is called continuous if f−1(O) is an open set for every open set O Y . Analysis is greatly simplified by this definition of continuity. For example, to show that any composition of continuous functions is continuous requires only a one-line argument that the preimage of the preimage of any open set always yields

⊆

an open set. Compare this to the cumbersome classical proof that requires a mess of δ’s and ǫ’s. The notion is also so general that continuous functions can even be defined on the absurd topological space from Example 4.4.

Homeomorphism: Making a donut into a coffee cup You might have heard the expression that to a topologist, a donut and a coffee cup appear the same. In many branches of mathematics, it is important to define when two basic objects are equivalent. In graph theory (and group theory), this equivalence relation is called an isomorphism. In topology, the most basic equivalence is a homeomorphism, which allows spaces that appear quite different in most other subjects to be declared equivalent in topology. The surfaces of a donut and a coffee cup (with one handle) are considered equivalent because both have a single hole. This notion needs to be made more precise!

Suppose f : X Y is a bijective (one-to-one and onto) function between topological spaces X and Y . Since f is bijective, the inverse f−1 exists. If both f and f−1 are continuous, then f is called a homeomorphism. Two topological

→

spaces X and Y are said to be homeomorphic, denoted by X ∼= Y , if there exists a

homeomorphism between them. This implies an equivalence relation on the set of topological spaces (verify that the reflexive, symmetric, and transitive properties are implied by the homeomorphism).

Example 4.5 (Interval Homeomorphisms) Any open interval of R is home- omorphic to any other open interval. For example, (0, 1) can be mapped to (0, 5) by the continuous mapping x 5x. Note that (0, 1) and (0, 5) are each being interpreted here as topological subspaces of R. This kind of homeomorphism can

1→

be generalized substantially using linear algebra. If a subset, X Rn, can be

⊂

mapped to another, Y Rn, via a nonsingular linear transformation, then X and

⊂

1. are homeomorphic. For example, the rigid-body transformations of the previ-

ous chapter were examples of homeomorphisms applied to the robot. Thus, the topology of the robot does not change when it is translated or rotated. (In this example, note that the robot itself is the topological space. This will not be the case for the rest of the chapter.)

Be careful when mixing closed and open sets. The space [0, 1] is not homeomor- phic to (0, 1), and neither is homeomorphic to [0, 1). The endpoints cause trouble when trying to make a bijective, continuous function. Surprisingly, a bounded and unbounded set may be homeomorphic. A subset X of Rn is called bounded if there

exists a ball B ⊂ Rn such that X ⊂ B. The mapping x 1→ 1/x establishes that

(0, 1) and (1, ∞) are homeomorphic. The mapping x 1→ 2 tan−1(x)/π establishes that (−1, 1) and all of R are homeomorphic! ．

Example 4.6 (Topological Graphs) Let X be a topological space. The pre- vious example can be extended nicely to make homeomorphisms look like graph

Figure 4.2: Even though the graphs are not isomorphic, the corresponding topo- logical spaces may be homeomorphic due to useless vertices. The example graphs map into R2, and are all homeomorphic to a circle.

Figure 4.3: These topological graphs map into subsets of R2 that are not homeo- morphic to each other.

isomorphisms. Let a topological graph2 be a graph for which every vertex cor- responds to a point in X and every edge corresponds to a continuous, injective (one-to-one) function, τ : [0, 1] X. The image of τ connects the points in X that correspond to the endpoints (vertices) of the edge. The images of different edge functions are not allowed to intersect, except at vertices. Recall from graph theory that two graphs, G1(V1, E1) and G2(V2, E2), are called isomorphic if there

→

exists a bijective mapping, f : V1 → V2 such that there is an edge between v1 and

v1′ in G1, if and only if there exists an edge between f(v1) and f(v1′ ) in G2.

The bijective mapping used in the graph isomorphism can be extended to

produce a homeomorphism. Each edge in E1 is mapped continuously to its cor- responding edge in E2. The mappings nicely coincide at the vertices. Now you should see that two topological graphs are homeomorphic if they are isomorphic under the standard definition from graph theory.3 What if the graphs are not isomorphic? There is still a chance that the topological graphs may be homeo- morphic, as shown in Figure 4.2. The problem is that there appear to be “useless” vertices in the graph. By removing vertices of degree two that can be deleted without affecting the connectivity of the graph, the problem is fixed. In this case,

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

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

graphs that are not isomorphic produce topological graphs that are not homeomor-

phic. This allows many distinct, interesting topological spaces to be constructed. A few are shown in Figure 4.3. ．

• • 1. Manifolds

In motion planning, efforts are made to ensure that the resulting configuration space has nice properties that reflect the true structure of the space of transforma- tions. One important kind of topological space, which is general enough to include most of the configuration spaces considered in Part II, is called a manifold. Intu- itively, a manifold can be considered as a “nice” topological space that behaves at every point like our intuitive notion of a surface.

Manifold definition A topological space M Rm is a manifold4 if for every x M, an open set O M exists such that: 1) x O, 2) O is homeomorphic to Rn, and 3) n is fixed for all x M. The fixed n is referred to as the dimension of the manifold, M. The second condition is the most important. It states that

∈

∈ ⊂ ∈

⊆

in the vicinity of any point, x M, the space behaves just like it would in the vicinity of any point y Rn; intuitively, the set of directions that one can move appears the same in either case. Several simple examples that may or may not be

∈

∈

manifolds are shown in Figure 4.4.

One natural consequence of the definitions is that m n. According to Whit- ney’s embedding theorem [449], m 2n+1. In other words, R2n+1 is “big enough” to hold any n-dimensional manifold.5 Technically, it is said that the n-dimensional manifold M is embedded in Rm, which means that an injective mapping exists from M to Rm (if it is not injective, then the topology of M could change).

≤

≥

As it stands, it is impossible for a manifold to include its boundary points

because they are not contained in open sets. A manifold with boundary can be defined requiring that the neighborhood of each boundary point of M is homeo- morphic to a half-space of dimension n (which was defined for n = 2 and n = 3 in Section 3.1) and that the interior points must be homeomorphic to Rn.

The presentation now turns to ways of constructing some manifolds that fre-

quently appear in motion planning. It is important to keep in mind that two

4Manifolds that are not subsets of Rm 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 Rm; 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.

5One variant of the theorem is that for smooth manifolds, R2n is sufficient. This bound is tight because RPn (n-dimensional projective space, which will be introduced later in this section), cannot be embedded in R2n−1.

Yes

Yes

Yes No

Yes No

Yes No

Figure 4.4: Some subsets of R2 that may or may not be manifolds. For the three that are not, the point that prevents them from being manifolds is indicated.

manifolds will be considered equivalent if they are homeomorphic (recall the donut and coffee cup).

Cartesian products There is a convenient way to construct new topological spaces from existing ones. Suppose that X and Y are topological spaces. The Cartesian product, X Y , defines a new topological space as follows. Every x X and y Y generates a point (x, y) in X Y . Each open set in X Y is formed by taking the Cartesian product of one open set from X and one from Y . Exactly one open set exists in X Y for every pair of open sets that can be formed by taking one from X and one from Y . Furthermore, these new open sets are used as a basis for forming the remaining open sets of X Y by allowing any unions and finite intersections of them.

×

×

∈ ∈ × ×

×

A familiar example of a Cartesian product is R R, which is equivalent to R2. In general, Rn is equivalent to R Rn−1. The Cartesian product can be taken over many spaces at once. For example, R R R = Rn. In the coming text, many important manifolds will be constructed via Cartesian products.

× × · · · ×

×

×

1D manifolds The set R of reals is the most obvious example of a 1D manifold because R certainly looks like (via homeomorphism) R in the vicinity of every point. The range can be restricted to the unit interval to yield the manifold (0, 1)

because they are homeomorphic (recall Example 4.5).

Another 1D manifold, which is not homeomorphic to (0, 1), is a circle, S1. In this case Rm = R2, and let

S1 = {(x, y) ∈ R2 | x2 + y2 = 1}. (4.5)

If you are thinking like a topologist, it should appear that this particular circle is not important because there are numerous ways to define manifolds that are

homeomorphic to S1. For any manifold that is homeomorphic to S1, we will sometimes say that the manifold is S1, just represented in a different way. Also, S1 will be called a circle, but this is meant only in the topological sense; it only needs to be homeomorphic to the circle that we learned about in high school geometry. Also, when referring to R, we might instead substitute (0, 1) without any trouble. The alternative representations of a manifold can be considered as

changing parameterizations, which are formally introduced in Section 8.3.2.

Identifications A convenient way to represent S1 is obtained by identification, which is a general method of declaring that some points of a space are identical, even though they originally were distinct.6 For a topological space X, let X/ denote that X has been redefined through some form of identification. The open sets of X become redefined. Using identification, S1 can be defined as [0, 1]/ , in which the identification declares that 0 and 1 are equivalent, denoted as 0 1. This has the effect of “gluing” the ends of the interval together, forming a closed loop. To see the homeomorphism that makes this possible, use polar coordinates to obtain θ (cos 2πθ, sin 2πθ). You should already be familiar with 0 and 2π leading to the same point in polar coordinates; here they are just normalized to 0 and 1. Letting θ run from 0 up to 1, and then “wrapping around” to 0 is a convenient way to represent S1 because it does not need to be curved as in (4.5).

∼

∼

∼

1→

It might appear that identifications are cheating because the definition of a manifold requires it to be a subset of Rm. This is not a problem because Whitney’s theorem, as mentioned previously, states that any n-dimensional manifold can be embedded in R2n+1. The identifications just reduce the number of dimensions needed for visualization. They are also convenient in the implementation of motion

planning algorithms.

2D manifolds Many important, 2D manifolds can be defined by applying the Cartesian product to 1D manifolds. The 2D manifold R2 is formed by R× R. The product R × S1 defines a manifold that is equivalent to an infinite cylinder. The product S1 × S1 is a manifold that is equivalent to a torus (the surface of a donut).

Can any other 2D manifolds be defined? See Figure 4.5. The identification idea can be applied to generate several new manifolds. Start with an open square

M = (0, 1) (0, 1), which is homeomorphic to R2. Let (x, y) denote a point in the plane. A flat cylinder is obtained by making the identification (0, y) (1, y) for

∼

×

all y (0, 1) and adding all of these points to M. The result is depicted in Figure

∈

4.5 by drawing arrows where the identification occurs.

A M¨obius band can be constructed by taking a strip of paper and connecting the ends after making a 180-degree twist. This result is not homeomorphic to the cylinder. The M¨obius band can also be constructed by putting the twist into the identification, as (0, y) (1, 1 y) for all y (0, 1). In this case, the arrows are drawn in opposite directions. The M¨obius band has the famous properties that

∼ − ∈

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

Figure 4.5: Some 2D manifolds that can be obtained by identifying pairs of points along the boundary of a square region.

it has only one side (trace along the paper strip with a pencil, and you will visit both sides of the paper) and is nonorientable (if you try to draw it in the plane, without using identification tricks, it will always have a twist).

For all of the cases so far, there has been a boundary to the set. The next few manifolds will not even have a boundary, even though they may be bounded. If you were to live in one of them, it means that you could walk forever along any trajectory and never encounter the edge of your universe. It might seem like our physical universe is unbounded, but it would only be an illusion. Furthermore, there are several distinct possibilities for the universe that are not homeomorphic to each other. In higher dimensions, such possibilities are the subject of cosmology, which is a branch of astrophysics that uses topology to characterize the structure of our universe.

A torus can be constructed by performing identifications of the form (0, y) (1, y), which was done for the cylinder, and also (x, 0) (x, 1), which identifies the top and bottom. Note that the point (0, 0) must be included and is identified with three other points. Double arrows are used in Figure 4.5 to indicate the top and bottom identification. All of the identification points must be added to M. Note that there are no twists. A funny interpretation of the resulting flat torus is as the universe appears for a spacecraft in some 1980s-style Asteroids-like video games.

∼

∼

The spaceship flies off of the screen in one direction and appears somewhere else, as prescribed by the identification.

Two interesting manifolds can be made by adding twists. Consider performing all of the identifications that were made for the torus, except put a twist in the side identification, as was done for the M¨obius band. This yields a fascinating manifold called the Klein bottle, which can be embedded in R4 as a closed 2D surface in which the inside and the outside are the same! (This is in a sense similar to that of the M¨obius band.) Now suppose there are twists in both the sides and the top and bottom. This results in the most bizarre manifold yet: the real projective plane, RP2. This space is equivalent to the set of all lines in R3 that pass through the

origin. The 3D version, RP3, happens to be one of the most important manifolds

for motion planning!

Let S2 denote the unit sphere, which is defined as

S2 = {(x, y, z) ∈ R3 | x2 + y2 + z2 = 1}. (4.6)

Another way to represent S2 is by making the identifications shown in the last row of Figure 4.5. A dashed line is indicated where the equator might appear, if we wanted to make a distorted wall map of the earth. The poles would be at the upper left and lower right corners. The final example shown in Figure 4.5 is a

double torus, which is the surface of a two-holed donut.

Higher dimensional manifolds The construction techniques used for the 2D manifolds generalize nicely to higher dimensions. Of course, Rn, is an n-dimensional manifold. An n-dimensional torus, Tn, can be made by taking a Cartesian prod- uct of n copies of S1. Note that S1 S1 = S2. Therefore, the notation Tn is used for (S1)n. Different kinds of n-dimensional cylinders can be made by forming a Cartesian product Ri Tj for positive integers i and j such that i+ j = n. Higher dimensional spheres are defined as

×

× /

Sn = {x ∈ Rn+1 | IxI = 1}, (4.7)

in which x denotes the Euclidean norm of x, and n is a positive integer. Many interesting spaces can be made by identifying faces of the cube (0, 1)n (or even faces of a polyhedron or polytope), especially if different kinds of twists are allowed. An n-dimensional projective space can be defined in this way, for example. Lens spaces are a family of manifolds that can be constructed by identification of polyhedral faces [834].

I I

Due to its coming importance in motion planning, more details are given on projective spaces. The standard definition of an n-dimensional real projective

space RPn is the set of all lines in Rn+1 that pass through the origin. Each line is considered as a point in RPn. Using the definition of Sn in (4.7), note that each of these lines in Rn+1 intersects Sn Rn+1 in exactly two places. These intersection points are called antipodal, which means that they are as far from each other as possible on Sn. The pair is also unique for each line. If we identify

⊂

all pairs of antipodal points of Sn, a homeomorphism can be defined between each line through the origin of Rn+1 and each antipodal pair on the sphere. This means that the resulting manifold, Sn/ , is homeomorphic to RP .

n

∼

Another way to interpret the identification is that RPn is just the upper half of Sn, but with every equatorial point identified with its antipodal point. Thus, if

you try to walk into the southern hemisphere, you will find yourself on the other side of the world walking north. It is helpful to visualize the special case of RP2 and the upper half of S2. Imagine warping the picture of RP2 from Figure 4.5 from a square into a circular disc, with opposite points identified. The result still represents RP2. The center of the disc can now be lifted out of the plane to form the upper half of S2.

• • 1. Paths and Connectivity

Central to motion planning is determining whether one part of a space is reachable from another. In Chapter 2, one state was reached from another by applying a sequence of actions. For motion planning, the analog to this is connecting one point in the configuration space to another by a continuous path. Graph connectivity is important in the discrete planning case. An analog to this for topological spaces is presented in this section.

Paths Let X be a topological space, which for our purposes will also be a man- ifold. A path is a continuous function, τ : [0, 1] X. Alternatively, R may be used for the domain of τ . Keep in mind that a path is a function, not a set of points. Each point along the path is given by τ (s) for some s [0, 1]. This makes it appear as a nice generalization to the sequence of states visited when a plan from Chapter 2 is applied. Recall that there, a countable set of stages was defined, and the states visited could be represented as x1, x2, . . .. In the current setting τ (s) is used, in which s replaces the stage index. To make the connection clearer,

→

∈

we could use x instead of τ to obtain x(s) for each s ∈ [0, 1].

Connected vs. path connected A topological space X is said to be connected if it cannot be represented as the union of two disjoint, nonempty, open sets. While this definition is rather elegant and general, if X is connected, it does not imply that a path exists between any pair of points in X thanks to crazy examples like the topologist’s sine curve:

X = {(x, y) ∈ R2 | x = 0 or y = sin(1/x)}. (4.8)

Consider plotting X. The sin(1/x) part creates oscillations near the y-axis in which the frequency tends to infinity. After union is taken with the y-axis, this space is connected, but there is no path that reaches the y-axis from the sine curve. How can we avoid such problems? The standard way to fix this is to use the path definition directly in the definition of connectedness. A topological space X

is said to be path connected if for all x1, x2 ∈ X, there exists a path τ such that

• • • 1. (b)

Figure 4.6: (a) Homotopy continuously warps one path into another. (b) The image of the path cannot be continuously warped over a hole in R2 because it causes a discontinuity. In this case, the two paths are not homotopic.

τ (0) = x1 and τ (1) = x2. It can be shown that if X is path connected, then it is also connected in the sense defined previously.

Another way to fix it is to make restrictions on the kinds of topological spaces that will be considered. This approach will be taken here by assuming that all topo- logical spaces are manifolds. In this case, no strange things like (4.8) can happen,7 and the definitions of connected and path connected coincide [451]. Therefore, we will just say a space is connected. However, it is important to remember that this definition of connected is sometimes inadequate, and one should really say that X is path connected.

Simply connected Now that the notion of connectedness has been established, the next step is to express different kinds of connectivity. This may be done by using the notion of homotopy, which can intuitively be considered as a way to continuously “warp” or “morph” one path into another, as depicted in Figure 4.6a.

Two paths τ1 and τ2 are called homotopic (with endpoints fixed) if there exists a continuous function h : [0, 1] [0, 1] X for which the following four conditions are met:

× →

1. (Start with first path) h(s, 0) = τ1(s) for all s ∈ [0, 1] .
2. (End with second path) h(s, 1) = τ2(s) for all s ∈ [0, 1] .
3. (Hold starting point fixed) h(0, t) = h(0, 0) for all t ∈ [0, 1] .
4. (Hold ending point fixed) h(1, t) = h(1, 0) for all t ∈ [0, 1] .

7The 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 R.

The parameter t can be interpreted as a knob that is turned to gradually deform the path from τ1 into τ2. The first two conditions indicate that t = 0 yields τ1 and t = 1 yields τ2, respectively. The remaining two conditions indicate that the path endpoints are held fixed.

During the warping process, the path image cannot make a discontinuous jump. In R2, this prevents it from moving over holes, such as the one shown in Figure 4.6b. The key to preventing homotopy from jumping over some holes is that h must be

continuous. In higher dimensions, however, there are many different kinds of holes. For the case of R3, for example, suppose the space is like a block of Swiss cheese that contains air bubbles. Homotopy can go around the air bubbles, but it cannot

pass through a hole that is drilled through the entire block of cheese. Air bubbles and other kinds of holes that appear in higher dimensions can be characterized by generalizing homotopy to the warping of higher dimensional surfaces, as opposed to paths [439].

It is straightforward to show that homotopy defines an equivalence relation on the set of all paths from some x1 X to some x2 X. The resulting notion of “equivalent paths” appears frequently in motion planning, control theory, and many other contexts. Suppose that X is path connected. If all paths fall into the same equivalence class, then X is called simply connected; otherwise, X is called multiply connected.

∈ ∈

Groups The equivalence relation induced by homotopy starts to enter the realm of algebraic topology, which is a branch of mathematics that characterizes the structure of topological spaces in terms of algebraic objects, such as groups. These resulting groups have important implications for motion planning. Therefore, we give a brief overview. First, the notion of a group must be precisely defined. A group is a set, G, together with a binary operation, , such that the following group axioms are satisfied:

◦

1. (Closure) For any a, b ∈ G, the product a ◦ b ∈ G.
2. (Associativity) For all a, b, c ∈ G, (a◦ b) ◦ c = a◦ (b ◦ c). Hence, parentheses are not needed, and the product may be written as a ◦ b ◦ c.
3. (Identity) There is an element e ∈ G, called the identity, such that for all

a ∈ G, e ◦ a = a and a ◦ e = a.

1. (Inverse) For every element a ∈ G, there is an element a−1, called the

inverse of a, for which a ◦ a−1 = e and a−1 ◦ a = e.

Here are some examples.

Example 4.7 (Simple Examples of Groups) The set of integers Z is a group with respect to addition. The identity is 0, and the inverse of each i is i. The set Q 0 of rational numbers with 0 removed is a group with respect to multiplication. The identity is 1, and the inverse of every element, q, is 1/q (0 was removed to

\

−

avoid division by zero). ．

An important property, which only some groups possess, is commutativity: a b = b a for any a, b G. The group in this case is called commutative or Abelian. We will encounter examples of both kinds of groups, both commutative and noncommutative. An example of a commutative group is vector addition over Rn. The set of all 3D rotations is an example of a noncommutative group.

◦ ◦ ∈

The fundamental group Now an interesting group will be constructed from the space of paths and the equivalence relation obtained by homotopy. The funda- mental group, π1(X) (or first homotopy group), is associated with any topological

space, X. Let a (continuous) path for which f(0) = f(1) be called a loop. Let some xb ∈ X be designated as a base point. For some arbitrary but fixed base

point, xb, consider the set of all loops such that f(0) = f(1) = xb. This can be made into a group by defining the following binary operation. Let τ1 : [0, 1] → X

and τ2 : [0, 1] → X be two loop paths with the same base point. Their product

τ = τ1 ◦ τ2 is defined as

τ (t) = τ1(2t) if t ∈ [0, 1/2)

（

τ2(2t − 1) if t ∈ [1/2, 1].

(4.9)

This results in a continuous loop path because τ1 terminates at xb, and τ2 begins at xb. In a sense, the two paths are concatenated end-to-end.

Suppose now that the equivalence relation induced by homotopy is applied to the set of all loop paths through a fixed point, xb. It will no longer be important which particular path was chosen from a class; any representative may be used. The equivalence relation also applies when the set of loops is interpreted as a group. The group operation actually occurs over the set of equivalences of paths. Consider what happens when two paths from different equivalence classes are concatenated using . Is the resulting path homotopic to either of the first two? Is the resulting path homotopic if the original two are from the same homotopy class? The answers in general are no and no, respectively. The fundamental group describes how the equivalence classes of paths are related and characterizes the connectivity of X. Since fundamental groups are based on paths, there is a nice

◦

connection to motion planning.

Example 4.8 (A Simply Connected Space) Suppose that a topological space X is simply connected. In this case, all loop paths from a base point xb are homo- topic, resulting in one equivalence class. The result is π1(X) = 1G, which is the

group that consists of only the identity element. ．

Example 4.9 (The Fundamental Group of S1) Suppose X = S1. In this case, there is an equivalence class of paths for each i ∈ Z, the set of integers.

1 2

2 1

• 1. (b) (c)

Figure 4.7: An illustration of why π1(RP2) = Z2. The integers 1 and 2 indicate precisely where a path continues when it reaches the boundary. (a) Two paths are shown that are not equivalent. (b) A path that winds around twice is shown. (c)

This is homotopic to a loop path that does not wind around at all. Eventually, the part of the path that appears at the bottom is pulled through the top. It finally shrinks into an arbitrarily small loop.

If i > 0, then it means that the path winds i times around S1 in the counterclock- wise direction and then returns to xb. If i < 0, then the path winds around i times in the clockwise direction. If i = 0, then the path is equivalent to one that remains at xb. The fundamental group is Z, with respect to the operation of addition. If τ1 travels i1 times counterclockwise, and τ2 travels i2 times counterclockwise, then τ = τ1 τ2 belongs to the class of loops that travel around i1 + i2 times counter- clockwise. Consider additive inverses. If a path travels seven times around S1, and it is combined with a path that travels seven times in the opposite direction, the

◦

result is homotopic to a path that remains at xb. Thus, π1(S1) = Z. ．

Example 4.10 (The Fundamental Group of Tn) For the torus, π1(Tn) = Zn, in which the ith component of Zn corresponds to the number of times a loop path wraps around the ith component of Tn. This makes intuitive sense because Tn is just the Cartesian product of n circles. The fundamental group Zn is obtained by starting with a simply connected subset of the plane and drilling out n disjoint,

bounded holes. This situation arises frequently when a mobile robot must avoid collision with n disjoint obstacles in the plane. ．

By now it seems that the fundamental group simply keeps track of how many times a path travels around holes. This next example yields some very bizarre behavior that helps to illustrate some of the interesting structure that arises in algebraic topology.

Example 4.11 (The Fundamental Group of RP2) Suppose X = RP2, the projective plane. In this case, there are only two equivalence classes on the space of loop paths. All paths that “wrap around” an even number of times are homotopic. Likewise, all paths that wrap around an odd number of times are homotopic. This

strange behavior is illustrated in Figure 4.7. The resulting fundamental group therefore has only two elements: π1(RP2) = Z2, the cyclic group of order 2, which corresponds to addition mod 2. This makes intuitive sense because the group

keeps track of whether a sum of integers is odd or even, which in this application corresponds to the total number of traversals over the square representation of

RP2. The fundamental group is the same for RP3, which arises in Section 4.2.2 because it is homeomorphic to the set of 3D rotations. Thus, there are surprisingly

only two path classes for the set of 3D rotations. ．

Unfortunately, two topological spaces may have the same fundamental group even if the spaces are not homeomorphic. For example, Z is the fundamental group of S1, the cylinder, R S1, and the M¨obius band. In the last case, the fundamental group does not indicate that there is a “twist” in the space. Another

×

problem is that spaces with interesting connectivity may be declared as simply connected. The fundamental group of the sphere S2 is just 1G, the same as for R2. Try envisioning loop paths on the sphere; it can be seen that they all fall into one equivalence class. Hence, S2 is simply connected. The fundamental group also neglects bubbles in R3 because the homotopy can warp paths around them. Some of these troubles can be fixed by defining second-order homotopy groups. For

example, a continuous function, [0, 1] [0, 1] X, of two variables can be used instead of a path. The resulting homotopy generates a kind of sheet or surface

× →

that can be warped through the space, to yield a homotopy group π2(X) that wraps around bubbles in R3. This idea can be extended beyond two dimensions to detect many different kinds of holes in higher dimensional spaces. This leads to

the higher order homotopy groups. A stronger concept than simply connected for a space is that its homotopy groups of all orders are equal to the identity group. This prevents all kinds of holes from occurring and implies that a space, X, is contractible, which means a kind of homotopy can be constructed that shrinks X to a point [439]. In the plane, the notions of contractible and simply connected are equivalent; however, in higher dimensional spaces, such as those arising in motion planning, the term contractible should be used to indicate that the space has no interior obstacles (holes).

An alternative to basing groups on homotopy is to derive them using homology, which is based on the structure of cell complexes instead of homotopy mappings. This subject is much more complicated to present, but it is more powerful for proving theorems in topology. See the literature overview at the end of the chapter for suggested further reading on algebraic topology.