8
$\begingroup$

I'm starting to work on topological complexity of configuration spaces.

Articles say that this field has applications in robotic and control theory. One of the important articles belongs to Michael Farber

My questions are :
1) How topological complexity can help to robotic and control theory?
2) Does there exist any applied problems in robotic or control or other subjects that have been solved by notion of Topological complexity?

Thanks

$\endgroup$

2 Answers 2

9
$\begingroup$

Since this is my main area of research, let me attempt an answer (which inevitably got quite long!). The short answer is that I do not know of any specific instances where topological complexity has been used to solve robotics problems, but I know that roboticists are interested in the concept, and am hopeful that such instances may occur in the future.

Let me start by saying that, in addition to the nice survey article by Farber you link to, you should also be familiar with his original papers on the subject, which perhaps provide a bit more motivation than the survey article:

Michael Farber, MR 1957228 Topological complexity of motion planning, Discrete Comput. Geom. 29 (2003), no. 2, 211--221.

Michael Farber, MR 2074919 Instabilities of robot motion, Topology Appl. 140 (2004), no. 2-3, 245--266.

Let me briefly recall the main definition and attempt to explain why a roboticist should be interested. Let $X$ be a path-connected space, which we view as the configuration space of some mechanical system. A motion planner in $X$ is a section $s:X\times X\to X^I$ of the free path fibration $$ \pi: X^I\to X\times X,\qquad \pi(\gamma) = (\gamma(0),\gamma(1)) $$ which evaluates a path at its pair of initial and final points. Hence it is a rule for how to get from $A$ to $B$, such as is required for the robot to perform tasks.

It turns out that a continuous motion planner in $X$ exists if and only if $X$ is contractible (an easy exercise in homotopy theory). Therefore motion planners usually have discontinuities forced upon them by the topology of the configuration space.

Now, the roboticist may seek to minimize such instabilities, to produce motion planners which are optimally elegant, or robust to noise. One way to do this would be to find a minimal partition of the domain $X\times X$ into smaller pieces, on each of which we have a continuous motion planner. This motivates the following:

Definition: The topological complexity of $X$, denoted $TC(X)$, is the minimal integer $k$ such that $X\times X=U_0\cup U_1\cdots \cup U_k$ for some open sets $U_i\subseteq X\times X$, on each of which there exists a continuous local section $s_i:U_i\to X^I$ of the free path fibration.

Here we give the definition in terms of open covers of $X\times X$; Farber shows that this is equivalent to finding a partition of $X\times X$ into nice pieces (say, ENRs). We have also normalized so that $TC(*)=0$, as is customary in a lot of the newer papers on the subject.

It turns out that $TC$ is a homotopy invariant, and therefore interesting to algebraic topologists. It is closely related to more classical invariants, such as the Lusternik-Schnirelmann category and the immersion dimension of real projective spaces. Obtaining good estimates can involve large chunks of classical algebraic topology, including cohomology algebras and operations, obstruction theory, and (most recently) Hopf invariants. It is an instance of a more general concept called the sectional category of a fibration, originally defined and studied by Albert Schwarz under the name genus.

Returning to your actual questions: Another way to estimate $TC(X)$ from above would be to exhibit an actual motion planner with the fewest possible domains of continuity. This is one way in which the study of $TC$ by mathematicians could benefit the robotics community: by producing motion planners which are "topologically optimal" for configuration spaces of interest.

Of course, Farber's approach only takes into account the topology of $X$, and not its geometry. In applications, one might be interested in finding paths between configurations which minimize the distance or energy. There is a recent article by Zbigniew Błaszczyk and José Carrasquel which attempts to reconcile this with Farber's approach.

You may also be interested in recent work of Petar Pavesic, which investigates topological complexity of the forward kinematic map. This is perhaps closer to applications, as it is concerned with finding a path from a given configuration to a given pose of the end-effector (of, say, a robot arm).

$\endgroup$
1
  • $\begingroup$ Thank you very much for your information and suggestions, they are useful for my goals. $\endgroup$
    – Mojtaba
    Aug 4, 2016 at 17:05
3
$\begingroup$

(EDITED)

It's a bit late to answer this. However, I have spent around a year working on this topic as an undergraduate and it was my dissertation's topic so I hope I can make my own tiny contribution. Topological Complexity can help you to understand the Gimbal Lock, which is strongly related to the incident happened in some of the Apollo Moon missions:

The explanation from the point of view of topological complexity goes as follows:

The configuration space of the spacecraft is (topologically): $$X \colon = \mathbb{R}^3 \times SO(3)$$

and $TC(X)=4$ since $X$ is homotopy equivalent to $SO(3)$ and $TC(SO(3))=4$. The key to prove the last fact is a result proved by Michael Farber (thanks to Mark Grant for pointing out a previous mistake here) which says that if $X$ is a topological group, then the L-S category of $X$ and it's topological complexity are equal. (If you want I can send you the full proofs of all this facts -in Spanish-)

You can also use Topological Complexity to deal with robot arms in factories and so on....but I don't want to write a book as an answer.

Hope that this answers, at least partially, some of your questions.

Don't hesitate to ask for details or more information if you wish!

--------------------------EDIT-------------------------

The way I relate gimbal lock to TC is as follows.

First of all, gimbal lock is the loss of control of an airplane or spacecraft. And when restricted to drones, we see it as an overturning. As you know better than me, $TC$ measures the stability of motion planning algorithms, and if $TC(X)$ is grater than one, then the motion planning algorithms over $X$ are unstable.

Moreover, the configuration space of the drone is homotopy equivalent to $SO(3)$. And the motion planner needs to check periodically the inclination of the drone (which is alterated due to exterior circumstances -a storm or wind in case of a dron flying close to the land-) and considering the inclination that it should have, to correct it by changing the path in $P(SO(3))=SO(3)^{I}$. The problem about $TC(SO(3))=4$ is that there is no continuous global section of the path fibration, and as a consequence, given a small change in the inlination of the drone, the algorithm can produce a completely wrong path. I have made some pictures to illustrate this.

In the first picture we see the drone, (it is supposed to have suffered a small perturbation despite of I have pictured it very big in order to produce a better drawing). It should correct its inclination by rotating clockwise direction. However, due to the instabilities caused by $TC(SO(3))=4$ it rotates the other way around and it overturns, which means we have lost it since it can not recover from that position.

I hope that this could help a bit. Feel free to criticize the ''arguments'' or ''explanations'' written above since they are just the way an undergraduate thought about gimbal lock and are far from rigorous or even serious.

$\endgroup$
2
  • 1
    $\begingroup$ Could you say a bit more about how TC can be used to understand gimbal lock? Also, the result that you mentioned about TC(G) is due to Michael Farber, not me! $\endgroup$
    – Mark Grant
    Nov 12, 2016 at 11:57
  • $\begingroup$ Hi @MarkGrant First of all, you are right, that result is due to Farber, not you. I have made a mistake since the first time I saw that result was in one of your presentations. That being said, I will edit the answer to add details. $\endgroup$
    – D1811994
    Nov 13, 2016 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.