This post is one my most important one, because i choose topological complexity notion in my studies on topological robotics.

Before continuing this note, if you had not read these two notes, i suggest to look at them first and come back here;

linkage and configuration space of a linkage; different definitions

Lusternik–Schnirelmann category; a prelude to Topological complexity

## Topological Complexity of Motion Planning

Professor M.Farber has wrote in the abstract of his paper; Topological Complexity of Motion Planning that:

* TC(X) is a number which measures discontinuity of the process of motion planning in the configuration space X .*

* TC(X) * is the minimal number k such that there are k different “motion planning rules”, each define on an open subset of X \times X so that each rule is continuous in the source and the target configurations.

### What is motion planning?

in short, motion planning is finding a path between two points with allowable motions. for more precisely definition, we can point to “Robot Motion Planning” paper, by J.Kuffner and H.Choset:

**Motion Planning Problem**

* A = robot with p degrees of freedom in 2-D or 3-D*

* CB = set of obstacles*

*A configuration q is legal if it does not cause the robot to intersect the obstacles*

*Given start and goal configurations ( q_{start} and q_{goal} ), find a continuous sequence of legal configurations from q_{start} to q_{goal} .*

Again in M.Farber’s paper we read;

*The motion planning problem consists of constructing a program or a device, which takes pairs of configurations (A, B) \in X \times X as an input and produces as an output a continuous path in X , which starts at A and ends at B .*

*Here A is the initial configuration, and B is the final (desired) configuration of the system.*

*We assume below that the configuration space X is **path-connected**, which means that for any pair of points of X there exists a continuous path in X connecting them.*

*The motion planning problem can be formalized as follows. Let PX denote the space of all continuous paths γ: [0, 1] → X in X . We denote by π: PX → X \times X the map associating to any path γ \in PX the pair of its initial and end points π(γ ) =(γ (0), γ (1)) . Equip the path space PX with** compact-open topology**. Rephrasing the above definition we see that the problem of motion planning in X consists of finding a function s: X × X → PX such that the composition π \circ s = id is the identity map. In other words, s must be a section of π .*

*Continuity of motion planning is an important natural requirement. Absence of continuity will result in the instability of behavior.*

Last paraghraph is so important and we must check the continuity of * s * for different space.

## Definition of Topological Complexity by M.Farber

*Given a path-connected topological space X , we define the topological complexity of the motion planning in X as the minimal number TC(X) = k , such that the Cartesian product X \times X may be covered by k k open subsets*

* X \times X = U_{1}, U_{2}, \ldots,U_{k} *

* such that for any i = 1, 2, \ldots , k there exists a continuous motion planning s_{i} : U_{i} → PX, π \circ s_{i} = id over U_{i} . If no such k exists we will set TC(X)= \infty .*