Recall from Lesson 1 that a robot is modeled by a configuration space \( C \), typically a smooth manifold (e.g. \( \mathbb{R}^n \), \( (S^1)^n \), or a product of these). A configuration \( q \in C \) determines a rigid placement of the robot's body in the workspace \( W \subset \mathbb{R}^m \) via a continuous placement map

\[ \Phi : C \to \mathcal{K}(W), \qquad q \mapsto A(q), \]

where \( \mathcal{K}(W) \) denotes compact subsets of \( W \) and \( A(q) \) is the region occupied by the robot at configuration \( q \).

Let the (closed) workspace obstacle region be \( O \subset W \). A configuration is in collision if the placed robot intersects an obstacle:

\[ q \text{ is in collision } \iff A(q) \cap O \neq \emptyset. \]

This induces the C-obstacle subset \( C_{\mathrm{obs}} \subset C \):

\[ C_{\mathrm{obs}} = \{\, q \in C \mid A(q) \cap O \neq \emptyset \,\}, \qquad C_{\mathrm{free}} = C \setminus C_{\mathrm{obs}}. \]

A basic but important topological fact under mild regularity assumptions is that \( C_{\mathrm{obs}} \) is closed and \( C_{\mathrm{free}} \) is open in \( C \). One way to see this is via a distance function \( d : C \to \mathbb{R} \):

\[ d(q) = \inf\{\, \|x-y\| \mid x \in A(q),\; y \in O \,\}. \]

Under continuity of \( \Phi \), the function \( d(q) \) is continuous, so \( C_{\mathrm{obs}} = d^{-1}((-\infty,0]) \) is closed and \( C_{\mathrm{free}} = d^{-1}((0,\infty)) \) is open. This openness implies that any collision-free configuration has a small neighborhood of nearby collision-free configurations: local motion is always possible within \( C_{\mathrm{free}} \).

flowchart TD
  A["Robot geometry + joint limits"] --> B["Placement map Phi: q |-> A(q)"]
  B --> C["Workspace obstacles O"]
  C --> D["Collision test: A(q) intersects O?"]
  D --> E["C_obs: colliding configurations"]
  D --> F["C_free: collision-free configurations"]
  F --> G["Analyze topology: components, holes, topological complexity"]
        

For a pure translation robot (no rotation) with shape \( B \subset \mathbb{R}^m \) and configuration \( q \in \mathbb{R}^m \), we have \( A(q) = B + q \) (Minkowski sum with the singleton \( \{q\} \)), and the C-obstacle for a single workspace obstacle \( O \) can be written as

\[ C_{\mathrm{obs}} = \{\, q \in \mathbb{R}^m \mid (B + q) \cap O \neq \emptyset \,\} = O \oplus (-B), \]

where \( \oplus \) denotes Minkowski sum and \( -B = \{ -x \mid x \in B \} \). This classic construction (originating with Lozano-Pérez) generalizes to more complex rigid motions and articulated robots, though the resulting sets typically live on manifolds like \( SE(2) \), \( SE(3) \), or tori.

In this section we study the geometric and analytic structure of \( C_{\mathrm{obs}} \). Assume the workspace obstacles are unions of basic primitives (half-planes, polygons, polyhedra, or algebraic surfaces), and the forward kinematics are analytic in joint coordinates. Then each contact condition between a robot feature and an obstacle feature becomes a system of analytic equations and inequalities in \( q \).

Consider a planar 2-DOF manipulator with link lengths \( \ell_1, \ell_2 \), joint angles \( q = (q_1,q_2) \in C = (S^1)^2 \), and a circular obstacle \( O = \{ x \in \mathbb{R}^2 \mid \|x - c\| \le r \} \). The end-effector position is

\[ x(q) = \begin{bmatrix} \ell_1 \cos q_1 + \ell_2 \cos(q_1 + q_2) \\ \ell_1 \sin q_1 + \ell_2 \sin(q_1 + q_2) \end{bmatrix}. \]

An end-effector collision occurs when \( \|x(q) - c\| \le r \), i.e. when

\[ h(q_1,q_2) := \big\|x(q) - c\big\|^2 - r^2 \le 0. \]

Expanding \( h \) gives a real-analytic function of \( q_1,q_2 \) (a trigonometric polynomial). The set of colliding configurations for this contact mode is \( \{ q \in C \mid h(q) \le 0 \} \), a semi-analytic subset of \( C \). Including link collisions (not just the end-effector) yields additional inequalities.

More generally, for polyhedral robots and obstacles, each contact constraint can be expressed as finitely many polynomial inequalities in sines and cosines of joint angles. Using the relations \( \sin^2 q_i + \cos^2 q_i = 1 \) one can eliminate trigonometric functions, showing that \( C_{\mathrm{obs}} \) is a semi-algebraic subset of some Euclidean embedding of \( C \). This has two important consequences:

• Finite topological type. Semi-algebraic sets admit finite cell decompositions; hence \( C_{\mathrm{Free}} \) has finitely many connected components and finitely many homotopy types of cells.
• Stratification. One can decompose \( C_{\mathrm{obs}} \) into strata corresponding to contact modes (no contact, edge-vertex contact, edge-edge contact, etc.), giving a combinatorial description of how the robot can slide along obstacles.

In practice, we almost never construct the full semi-algebraic description; instead, we rely on numerical collision checkers. Nevertheless, understanding this structure is crucial when proving completeness or complexity results for planners.

Motion planning problems are usually posed on the free configuration space \( C_{\mathrm{free}} \) with start and goal configurations \( q_{\mathrm{s}}, q_{\mathrm{g}} \in C_{\mathrm{free}} \). A path is a continuous map \( \gamma : [0,1] \to C_{\mathrm{free}} \) with \( \gamma(0) = q_{\mathrm{s}} \) and \( \gamma(1) = q_{\mathrm{g}} \).

Two configurations are path-connected if such a path exists. Path connectivity partitions \( C_{\mathrm{free}} \) into disjoint path-connected components \( \{ C_{\mathrm{free}}^{(i)} \} \).

Proposition. Let \( C \) be a finite-dimensional manifold and \( C_{\mathrm{free}} \subset C \) a nonempty open subset. Then for \( q_{\mathrm{s}}, q_{\mathrm{g}} \in C_{\mathrm{free}} \),

\[ \text{There exists a collision-free path from } q_{\mathrm{s}} \text{ to } q_{\mathrm{g} } \iff q_{ \mathrm{s} }, q_{ \mathrm{g} } \\ \text{ lie in the same connected component of } C_{\mathrm{free}}. \]

Sketch of proof. One direction is immediate: a continuous path witnesses connectivity. Conversely, if \( q_{\mathrm{s}}, q_{\mathrm{g}} \) lie in the same connected component, then in an open subset of a manifold, connectedness implies path-connectedness; thus a path exists entirely within \( C_{\mathrm{free}} \).

Obstacles do more than split \( C_{\mathrm{free}} \) into components; they can introduce nontrivial holes and accordingly distinct homotopy classes of paths. Two paths \( \gamma_0,\gamma_1 : [0,1] \to C_{\mathrm{free}} \) with the same endpoints are (endpoint-fixed) homotopic if there exists a continuous \( H : [0,1] \times [0,1] \to C_{\mathrm{free}} \) such that

\[ H(0,t) = \gamma_0(t), \quad H(1,t) = \gamma_1(t), \quad H(s,0) = q_{\mathrm{s}}, \quad H(s,1) = q_{\mathrm{g}} \quad \forall s,t \in [0,1]. \]

Intuitively, we can continuously deform \( \gamma_0 \) into \( \gamma_1 \) without colliding, while keeping endpoints fixed. For a point robot in the plane with a disc-shaped obstacle, \( C_{\mathrm{free}} \) is homotopy-equivalent to an annulus, and paths that go around the obstacle different numbers of times belong to different homotopy classes.

These homotopy classes affect algorithm design: some planners try to find paths in multiple homotopy classes (e.g. to generate qualitatively distinct motions) or to bias sampling towards underexplored classes. This leads naturally to a global invariant of \( C_{\mathrm{free}} \): topological complexity.

We now formalize how the global topology of \( C_{\mathrm{free}} \) constrains the structure of any continuous motion planning algorithm. Following Farber, let \( X = C_{\mathrm{free}} \) be a path-connected topological space. The path space of \( X \) is

\[ PX = \{\, \gamma : [0,1] \to X \mid \gamma \text{ continuous} \,\} \]

equipped with the compact-open topology. Define the endpoint evaluation map

\[ \pi : PX \to X \times X, \qquad \pi(\gamma) = \big(\gamma(0), \gamma(1)\big). \]

A (global) motion planning algorithm on \( X \) is a map \( s : X \times X \to PX \) such that

\[ \pi \circ s = \mathrm{id}_{X \times X}, \]

i.e. \( s(x_0,x_1) \) is a path in \( X \) from \( x_0 \) to \( x_1 \). We would like \( s \) to be continuous so that small changes in the query pair \( (x_0,x_1) \) produce small changes in the path.

However, if \( X \) has nontrivial topology, such a global continuous section rarely exists. Farber's key definition quantifies this obstruction.

Definition (Topological complexity). The topological complexity of a path-connected space \( X \), denoted \( \operatorname{TC}(X) \), is the least integer \( k \ge 1 \) such that there exists an open cover \( X \times X = U_1 \cup \cdots \cup U_k \) and continuous \( s_i : U_i \to PX \) with

\[ \pi \circ s_i = \mathrm{id}_{U_i}, \qquad i = 1,\dots,k. \]

Each pair \( (x_0,x_1) \in U_i \) is handled by the local planner \( s_i \). Then \( \operatorname{TC}(X) \) is the minimal number of continuous "rules" required for motion planning on \( X \).

flowchart TD
  X["Free space X = C_free"] --> COV["Cover XxX by open sets U_i"]
  COV --> LOC["On each U_i: continuous local planner s_i"]
  LOC --> ALG["Algorithm = union of local rules {U_i, s_i}"]
  ALG --> TC["Minimum number of rules = TC(X)"]
        

Some fundamental properties:

• \( \operatorname{TC}(X) = 1 \) iff \( X \) is contractible (in particular, homotopy-equivalent to a point). In this case a single continuous planner exists globally.
• \( \operatorname{TC}(X) \) is a homotopy invariant: if \( X \) and \( Y \) are homotopy-equivalent, then \( \operatorname{TC}(X) = \operatorname{TC}(Y) \).
• Let \( \operatorname{cat}(X) \) be the Lusternik–Schnirelmann category of \( X \). Then

\[ \operatorname{cat}(X) \le \operatorname{TC}(X) \le 2\,\operatorname{cat}(X) - 1. \]

For spheres \( S^n \) (a common simplified C-space model),

\[ \operatorname{TC}(S^n) = \begin{cases} 2 & \text{if } n \text{ is odd}, \\ 3 & \text{if } n \ge 2 \text{ is even}. \end{cases} \]

Thus, even for a very simple non-contractible manifold, any continuous motion planner requires at least two or three local rules. In robotics terms, \( \operatorname{TC}(C_{\mathrm{free}}) \) lower-bounds the number of "charts" on configuration space on which we can implement smooth, predictable planning strategies without discontinuities.

While computing \( \operatorname{TC}(X) \) exactly for realistic robot C-spaces is typically intractable, the concept provides:

• a qualitative classification of planning difficulty, and
• a link between algebraic topology (cohomology operations) and algorithm design.

We now build simple numerical approximations of \( C_{\mathrm{obs}} \) for a planar 2-DOF arm. The goal is not to compute topological complexity exactly, but to:

• sample \( C \) on a grid,
• classify configurations as free or colliding, and
• inspect the connectivity structure of sampled free cells.

We will implement this in Python, C++, Java, MATLAB/Simulink, and Wolfram Mathematica. For realism, we will also mention standard robotics libraries that can replace or augment the from-scratch code.

5.1 Python: Grid Sampling of \( C_{\mathrm{free}} \)

We assume basic familiarity with Python and numpy. In a more advanced setup you could replace the inner collision function with calls to pybullet, fcl bindings, or OMPL's Python interface, but here we stay self-contained.

import numpy as np

# 2-DOF planar arm
L1, L2 = 1.0, 1.0
obstacle_center = np.array([0.8, 0.4])
obstacle_radius = 0.25

def forward_kinematics(q):
    """q = (q1, q2) in radians. Return joint and end-effector positions."""
    q1, q2 = q
    p0 = np.array([0.0, 0.0])
    p1 = np.array([L1 * np.cos(q1), L1 * np.sin(q1)])
    p2 = p1 + np.array([L2 * np.cos(q1 + q2), L2 * np.sin(q1 + q2)])
    return p0, p1, p2

def segment_point_distance(a, b, p):
    """Distance from point p to segment ab in R^2."""
    ab = b - a
    t = np.dot(p - a, ab) / (np.dot(ab, ab) + 1e-12)
    t_clamped = np.clip(t, 0.0, 1.0)
    proj = a + t_clamped * ab
    return np.linalg.norm(p - proj)

def in_collision(q):
    """Simple collision: any link too close to the circular obstacle."""
    p0, p1, p2 = forward_kinematics(q)
    d1 = segment_point_distance(p0, p1, obstacle_center)
    d2 = segment_point_distance(p1, p2, obstacle_center)
    return (d1 <= obstacle_radius) or (d2 <= obstacle_radius)

# Sample a grid in C = [-pi, pi] x [-pi, pi]
def sample_cspace(n_per_dim=80):
    q1_vals = np.linspace(-np.pi, np.pi, n_per_dim)
    q2_vals = np.linspace(-np.pi, np.pi, n_per_dim)
    free_mask = np.zeros((n_per_dim, n_per_dim), dtype=bool)
    for i, q1 in enumerate(q1_vals):
        for j, q2 in enumerate(q2_vals):
            if not in_collision((q1, q2)):
                free_mask[i, j] = True
    return q1_vals, q2_vals, free_mask

if __name__ == "__main__":
    q1_vals, q2_vals, free_mask = sample_cspace(n_per_dim=100)
    # Approximate number of connected components by BFS on 4-neighborhood
    visited = np.zeros_like(free_mask, dtype=bool)
    n_components = 0
    for i in range(free_mask.shape[0]):
        for j in range(free_mask.shape[1]):
            if free_mask[i, j] and not visited[i, j]:
                n_components += 1
                stack = [(i, j)]
                visited[i, j] = True
                while stack:
                    ci, cj = stack.pop()
                    for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
                        ni, nj = ci + di, cj + dj
                        if 0 <= ni < free_mask.shape[0] and 0 <= nj < free_mask.shape[1]:
                            if free_mask[ni, nj] and not visited[ni, nj]:
                                visited[ni, nj] = True
                                stack.append((ni, nj))
    print("Approximate number of connected components of C_free:", n_components)
      

A visualization using matplotlib can show the structure of sampled \( C_{\mathrm{free}} \), revealing holes or narrow passages that contribute to planning difficulty.

5.2 C++: Collision Test Skeleton (with OMPL/FCL Context)

In C++, low-level geometry is often delegated to libraries such as FCL (Flexible Collision Library) and high-level planning to OMPL. The snippet below shows a minimal from-scratch collision test similar to the Python code. It can be wrapped inside an OMPL StateValidityChecker.

#include <cmath>
#include <iostream>
#include <array>

struct Vec2 {
    double x, y;
};

Vec2 operator+(const Vec2& a, const Vec2& b) {
    return {a.x + b.x, a.y + b.y};
}

Vec2 operator-(const Vec2& a, const Vec2& b) {
    return {a.x - b.x, a.y - b.y};
}

Vec2 operator*(double s, const Vec2& v) {
    return {s * v.x, s * v.y};
}

double dot(const Vec2& a, const Vec2& b) {
    return a.x * b.x + a.y * b.y;
}

double norm(const Vec2& v) {
    return std::sqrt(dot(v, v));
}

std::array<Vec2,3> forwardKinematics(double q1, double q2,
                                      double L1 = 1.0, double L2 = 1.0) {
    Vec2 p0{0.0, 0.0};
    Vec2 p1{L1 * std::cos(q1), L1 * std::sin(q1)};
    Vec2 p2 = {p1.x + L2 * std::cos(q1 + q2),
               p1.y + L2 * std::sin(q1 + q2)};
    return {p0, p1, p2};
}

double segmentPointDistance(const Vec2& a, const Vec2& b, const Vec2& p) {
    Vec2 ab = {b.x - a.x, b.y - a.y};
    double denom = dot(ab, ab) + 1e-12;
    double t = dot(p - a, ab) / denom;
    if (t < 0.0) t = 0.0;
    if (t > 1.0) t = 1.0;
    Vec2 proj = {a.x + t * ab.x, a.y + t * ab.y};
    return norm(p - proj);
}

bool inCollision(double q1, double q2,
                 const Vec2& center, double radius) {
    auto pts = forwardKinematics(q1, q2);
    double d1 = segmentPointDistance(pts[0], pts[1], center);
    double d2 = segmentPointDistance(pts[1], pts[2], center);
    return (d1 <= radius) || (d2 <= radius);
}

int main() {
    Vec2 center{0.8, 0.4};
    double radius = 0.25;
    double q1 = 0.3, q2 = -1.0;
    std::cout << "Collision? " <<
        (inCollision(q1, q2, center, radius) ? "yes" : "no") << std::endl;
    return 0;
}
      

In OMPL, one would implement isValid(const ob::State *state) using inCollision and let OMPL explore \( C_{\mathrm{free}} \) with PRM or RRT variants.

5.3 Java: Simple Collision Checker

Java is less common in motion planning research, but similar geometry code applies. The following snippet uses plain doubles; an actual system might embed this inside a robotics toolkit or a simulation engine such as jMonkeyEngine.

public final class PlanarArmCollision {

    static class Vec2 {
        final double x, y;
        Vec2(double x, double y) { this.x = x; this.y = y; }
        Vec2 add(Vec2 o) { return new Vec2(x + o.x, y + o.y); }
        Vec2 sub(Vec2 o) { return new Vec2(x - o.x, y - o.y); }
        Vec2 scale(double s) { return new Vec2(s * x, s * y); }
        double dot(Vec2 o) { return x * o.x + y * o.y; }
        double norm() { return Math.sqrt(dot(this)); }
    }

    static Vec2[] forwardKinematics(double q1, double q2,
                                    double L1, double L2) {
        Vec2 p0 = new Vec2(0.0, 0.0);
        Vec2 p1 = new Vec2(L1 * Math.cos(q1), L1 * Math.sin(q1));
        Vec2 p2 = p1.add(new Vec2(
                L2 * Math.cos(q1 + q2),
                L2 * Math.sin(q1 + q2)));
        return new Vec2[]{p0, p1, p2};
    }

    static double segmentPointDistance(Vec2 a, Vec2 b, Vec2 p) {
        Vec2 ab = b.sub(a);
        double denom = ab.dot(ab) + 1e-12;
        double t = p.sub(a).dot(ab) / denom;
        if (t < 0.0) t = 0.0;
        if (t > 1.0) t = 1.0;
        Vec2 proj = a.add(ab.scale(t));
        return p.sub(proj).norm();
    }

    static boolean inCollision(double q1, double q2,
                               Vec2 center, double radius) {
        Vec2[] pts = forwardKinematics(q1, q2, 1.0, 1.0);
        double d1 = segmentPointDistance(pts[0], pts[1], center);
        double d2 = segmentPointDistance(pts[1], pts[2], center);
        return (d1 <= radius) || (d2 <= radius);
    }

    public static void main(String[] args) {
        Vec2 center = new Vec2(0.8, 0.4);
        double radius = 0.25;
        double q1 = 0.3, q2 = -1.0;
        boolean coll = inCollision(q1, q2, center, radius);
        System.out.println("Collision? " + coll);
    }
}
      

5.4 MATLAB/Simulink: Using Robotics Toolbox

MATLAB's Robotics System Toolbox provides high-level primitives to build kinematic chains and check collisions. Below is a script that constructs a 2-DOF planar arm and tests collisions with a spherical obstacle. In a Simulink model, one can wrap this logic in a MATLAB Function block that outputs a Boolean collision flag for a given joint vector.

% Link lengths
L1 = 1.0; L2 = 1.0;

% Build a simple planar rigidBodyTree
robot = rigidBodyTree("DataFormat","row","MaxNumBodies",2);
body1 = rigidBody("link1");
jnt1 = rigidBodyJoint("joint1","revolute");
setFixedTransform(jnt1, trvec2tform([0 0 0]));
body1.Joint = jnt1;
addBody(robot, body1, "base");

body2 = rigidBody("link2");
jnt2 = rigidBodyJoint("joint2","revolute");
setFixedTransform(jnt2, trvec2tform([L1 0 0]));
body2.Joint = jnt2;
addBody(robot, body2, "link1");

% Collision sphere as an environment object
[obsCenter, obsRadius] = deal([0.8 0.4 0.0], 0.25);
obs = collisionSphere(obsRadius);
obs.Pose = trvec2tform(obsCenter);

% Joint configuration
q = [0.3 -1.0];

% Collision check
isColliding = checkCollision(robot, q, {obs}, ...
    "IgnoreSelfCollision", true);

disp(isColliding);
      

Inside Simulink, this collision flag can gate a path-following controller, blocking motion commands which would leave \( C_{\mathrm{free}} \).

5.5 Wolfram Mathematica: Visualizing C-Space Obstacles

Mathematica is well-suited for visualizing semi-algebraic sets. The following code samples joint angle pairs and plots \( C_{\mathrm{obs}} \) and \( C_{\mathrm{free}} \) in the \( (q_1,q_2) \) plane.

L1 = 1.0; L2 = 1.0;
center = {0.8, 0.4};
radius = 0.25;

forwardKinematics[{q1_, q2_}] := Module[
  {p0, p1, p2},
  p0 = {0., 0.};
  p1 = {L1 Cos[q1], L1 Sin[q1]};
  p2 = p1 + {L2 Cos[q1 + q2], L2 Sin[q1 + q2]};
  {p0, p1, p2}
];

segmentPointDistance[a_, b_, p_] := Module[
  {ab, t, proj},
  ab = b - a;
  t = (p - a).ab/(ab.ab + 10.^-12);
  t = Min[Max[t, 0.], 1.];
  proj = a + t ab;
  Norm[p - proj]
];

inCollision[{q1_, q2_}] := Module[
  {pts, d1, d2},
  pts = forwardKinematics[{q1, q2}];
  d1 = segmentPointDistance[pts[[1]], pts[[2]], center];
  d2 = segmentPointDistance[pts[[2]], pts[[3]], center];
  (d1 <= radius) || (d2 <= radius)
];

samples = Table[{q1, q2}, {q1, -Pi, Pi, Pi/80.},
                          {q2, -Pi, Pi, Pi/80.}];
flatSamples = Flatten[samples, 1];

obsPoints = Select[flatSamples, inCollision];
freePoints = Select[flatSamples, Not@*inCollision];

ListPlot[
 {obsPoints, freePoints},
 PlotRange -> { {-Pi, Pi}, {-Pi, Pi} },
 PlotMarkers -> {Automatic, Automatic},
 AxesLabel -> {"q1", "q2"},
 PlotLegends -> {"C_obs", "C_free"}
]
      

By inspecting the cluster structure and holes in these plots, one develops intuition for how \( C_{\mathrm{obs}} \) deforms the torus \( (S^1)^2 \) and for why continuous planners may require several local rules.

Problem 1 (Closedness of C-obstacles). Let \( C \) be a configuration manifold and \( W \subset \mathbb{R}^m \) the workspace. Suppose the placement map \( \Phi : C \to \mathcal{K}(W) \) is continuous in the Hausdorff metric and the workspace obstacle region \( O \subset W \) is closed. Show that \( C_{\mathrm{obs}} = \{ q \in C \mid A(q) \cap O \neq \emptyset \} \) is closed, and hence \( C_{\mathrm{free}} \) is open.

Solution. Define the signed distance \( d(q) = \inf \{ \|x-y\| \mid x \in A(q), y \in O \} \). Continuity of \( \Phi \) in the Hausdorff metric implies continuity of \( d \). Then \( C_{\mathrm{obs}} = d^{-1}((-\infty,0]) \) is the preimage of a closed set under a continuous map, and is therefore closed. Similarly, \( C_{\mathrm{free}} = d^{-1}((0,\infty)) \) is open.

Problem 2 (Connectivity and existence of a path). Let \( C \) be a finite-dimensional manifold, and \( C_{\mathrm{free}} \subset C \) a nonempty open subset. Prove that any two points in the same connected component of \( C_{\mathrm{free}} \) can be joined by a continuous collision-free path.

Solution. In a finite-dimensional manifold, every point has a neighborhood homeomorphic to an open ball in \( \mathbb{R}^n \). Open subsets of manifolds are themselves manifolds (possibly with fewer components). For manifolds that are second countable and locally path connected, connectedness implies path-connectedness. Since \( C_{\mathrm{free}} \) is open in \( C \), it inherits local path connectivity. Therefore each connected component of \( C_{\mathrm{free}} \) is path-connected, and any two points in the same component can be joined by a continuous path lying entirely in \( C_{\mathrm{free}} \).

Problem 3 (Annulus free space and homotopy classes). Consider a point robot in \( \mathbb{R}^2 \) with a single circular obstacle of radius \( r > 0 \) centered at the origin. The free configuration space is \( C_{\mathrm{free}} = \mathbb{R}^2 \setminus \{ x \mid \|x\| \le r \} \), which is homotopy equivalent to a circle \( S^1 \). Describe the distinct homotopy classes of paths between two fixed configurations outside the obstacle.

Solution. Since \( C_{\mathrm{free}} \) deformation retracts onto the circle \( S^1 \), the fundamental group \( \pi_1(C_{\mathrm{free}}) \cong \mathbb{Z} \). A path between fixed endpoints can wind around the obstacle an integer number of times, with positive or negative orientation. The homotopy class is characterized by the winding number \( k \in \mathbb{Z} \): two paths are homotopic (with fixed endpoints) if and only if they have the same winding number around the obstacle. Intuitively, you cannot continuously deform a path that goes around the obstacle once into one that does not encircle it without crossing the obstacle.

Problem 4 (Topological complexity of contractible free spaces). Let \( X \) be a contractible configuration space (e.g. a convex subset of \( \mathbb{R}^n \)). Show that \( \operatorname{TC}(X) = 1 \), i.e. there exists a global continuous motion planner.

Solution. Since \( X \) is contractible, there exists a homotopy \( H : X \times [0,1] \to X \) from the identity to a constant map at some base point \( x_0 \in X \):

\[ H(x,0) = x, \quad H(x,1) = x_0. \]

Define a path from \( x_0 \) to any \( x \in X \) by \( \gamma_x(t) = H(x,1-t) \). A path from \( x_{\mathrm{s}} \) to \( x_{\mathrm{g}} \) can be obtained by concatenating the reverse of \( \gamma_{x_{\mathrm{s}}} \) (moving from \( x_{\mathrm{s}} \) to \( x_0 \)) with \( \gamma_{x_{\mathrm{g}}} \) (moving from \( x_0 \) to \( x_{\mathrm{g}} \)). This concatenation depends continuously on the endpoints, yielding a global continuous section \( s : X \times X \to PX \). Therefore \( \operatorname{TC}(X) = 1 \).

Problem 5 (Qualitative lower bound on number of local planners). Suppose a robot's free configuration space \( C_{\mathrm{free}} \) is homotopy equivalent to a torus \( T^2 = S^1 \times S^1 \), which occurs for some 2-DOF arms without obstacles and in other settings. It is known (from algebraic topology) that \( \operatorname{cat}(T^2) = 3 \). Use the inequality \( \operatorname{cat}(X) \le \operatorname{TC}(X) \le 2\,\operatorname{cat}(X) - 1 \) to bound \( \operatorname{TC}(C_{\mathrm{free}}) \), and interpret the result.

Solution. Since \( C_{\mathrm{free}} \) is homotopy equivalent to \( T^2 \), they have the same Lusternik–Schnirelmann category and topological complexity. Using \( \operatorname{cat}(T^2) = 3 \), we obtain

\[ 3 = \operatorname{cat}(T^2) \le \operatorname{TC}(T^2) \le 2 \cdot 3 - 1 = 5. \]

Thus \( \operatorname{TC}(C_{\mathrm{free}}) \) lies in \( \{3,4,5\} \) (more refined calculations show \( \operatorname{TC}(T^2) = 3 \)). In robotics terms, no globally continuous planner exists; at least three local planning rules are required to cover all pairs of start and goal configurations. Any algorithm that attempts to use only one or two rules must necessarily have discontinuities, reflected in abrupt changes of path as the query varies.

In this lesson we rigorously defined configuration-space obstacles, established basic topological properties of \( C_{\mathrm{obs}} \) and \( C_{\mathrm{free}} \), and related connectivity to the existence of collision-free paths. We introduced homotopy classes of paths and the notion of topological complexity \( \operatorname{TC}(C_{\mathrm{free}}) \), which quantitatively captures how many continuous local rules are needed for motion planning. Finally, we implemented simple C-space approximations for a planar arm in multiple programming languages, laying the groundwork for later chapters on graph search and sampling-based motion planning where these topological ideas implicitly guide algorithm design.