Topological complexity of motion planning

Farber, M.

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 X2 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.

Citation

Farber, M. (2003). Topological complexity of motion planning. Discrete & Computational Geometry, 29(2), 211-221. https://doi.org/10.1007/s00454-002-0760-9

• Journal Article Type: Article
• Publication Date: Jan 1, 2003
• Deposit Date: Apr 26, 2007
• Journal: Discrete and Computational Geometry
• Print ISSN: 0179-5376
• Electronic ISSN: 1432-0444
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 29
• Issue: 2
• Pages: 211-221
• DOI: https://doi.org/10.1007/s00454-002-0760-9