Topological Complexity of Motion Planning

By Michael Farber. Discrete & Computational Geometry, 2001

467 citations recorded by the source corpus.

Abstract. In this paper we study a notion of topological complexity TC(X) for the motion planning problem. TC(X) is a number which measures discontinuity of the process of motion planning in the configuration space X . More precisely, TC(X) is the minimal number k such that there are k different "motion planning rules," each defined on an open subset of X× X , so that each rule is continuous in the source and target configurations. We use methods of algebraic topology (the Lusternik—Schnirelman theory) to study the topological complexity TC(X) . We give an upper bound for TC(X) (in terms of the dimension of the configuration space X ) and also a lower bound (in terms of the structure of the cohomology algebra of X ). We explicitly compute the topological complexity of motion planning for a number of configuration spaces: spheres, two-dimensional surfaces, products of spheres. In particular, we completely calculate the topological complexity of the problem of motion planning for a robot arm in the absence of obstacles.

Subfields: Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/72c0c7ea2dbb3d339ef9d44d0b5adde99778d382

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Yuli B. Rudyak
2. Jesús González
3. Steven M. LaValle
4. Norio Iwase
5. D. Tamaki
6. Michihiro Sakai
7. I. Basabe

In Computer Vision and Pattern Recognition

1. Yuli B. Rudyak
2. Jesús González
3. Steven M. LaValle
4. Norio Iwase
5. D. Tamaki
6. Michihiro Sakai
7. I. Basabe
8. Sertac Karaman

In Mathematical Physics

1. Yuli B. Rudyak
2. Jesús González
3. Steven M. LaValle
4. Norio Iwase
5. D. Tamaki
6. Michihiro Sakai
7. I. Basabe

Citations in the corpus

• Planning algorithms (2006, background): “In [327], the topological complexity of C-spaces is studied by characterizing the minimum number of regions needed to cover C × C by defining a continuous path function over each region.”
• Higher topological complexity and its symmetrization (2010, methodology): “S/ have been computed in [9, Corollary 18] and [5], respectively.”
• Topological complexity is a fibrewise L–S category (2012, background): “7 of [2] must be replaced with “T C(B)” and the resulting inequality should be presented in the following form: Zπ(B) ≤ wgtπ(B) ≤ Mwgt B B(d(B)) ≤ T C (B)−1 ≤ catlenBB(d(B)) ≤ Cat B B(d(B)).”