Topological Complexity

By | September 9, 2019

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 .

Leave a Reply

Your email address will not be published. Required fields are marked *