Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Robot motion planning, weights of cohomology classes, and cohomology operations

Authors: Michael Farber and Mark Grant
Journal: Proc. Amer. Math. Soc. 136 (2008), 3339-3349
MSC (2000): Primary 55M99; Secondary 68T40
Published electronically: April 25, 2008
MathSciNet review: 2407101
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The complexity of algorithms solving the motion planning problem is measured by a homotopy invariant $ \mathrm{TC}(X)$ of the configuration space $ X$ of the system. Previously known lower bounds for $ \mathrm{TC}(X)$ use the structure of the cohomology algebra of $ X$. In this paper we show how cohomology operations can be used to sharpen these lower bounds for $ \mathrm{TC}(X)$. As an application of this technique we calculate explicitly the topological complexity of various lens spaces. The results of the paper were inspired by the work of E. Fadell and S. Husseini on weights of cohomology classes appearing in the classical lower bounds for the Lusternik-Schnirelmann category. In the appendix to this paper we give a very short proof of a generalized version of their result.

References [Enhancements On Off] (What's this?)

  • 1. O. Cornea, G. Lupton, J. Oprea, D. Tanré, Lusternik-Schnirelmann Category, AMS, 2003. MR 1990857 (2004e:55001)
  • 2. E. Fadell and S. Husseini, Category weight and Steenrod operations, Bol. Soc. Mat. Mexicana (2) 37 (1992), no. 1-2, 151-161. MR 1317569 (95m:55007)
  • 3. M. Farber, Topological complexity of motion planning, Discrete Comput. Geom. 29 (2003), 211-221. MR 1957228 (2004c:68132)
  • 4. M. Farber, Instabilities of robot motion, Topology Appl. 140 (2004), 245-266. MR 2074919 (2005g:68166)
  • 5. M. Farber, Topology of robot motion planning, Morse Theoretic Methods in Nonlinear Analysis and in Symplectic Topology (P. Biran et al. (eds.)), Springer, Dordrecht, 2006, 185-230. MR 2276952
  • 6. M. Farber and M. Grant, Symmetric Motion Planning, Contemp. Math., 438, Amer. Math. Soc., Providence, RI, 2007, pp. 85-104. MR 2359031
  • 7. M. Farber, S. Tabachnikov, S. Yuzvinsky, Topological robotics: Motion planning in projective spaces, International Mathematical Research Notices 34 (2003), 1853-1870. MR 1988783 (2004i:55005)
  • 8. J. González, Topological robotics in lens spaces, Math. Proc. Cambridge Philos. Soc. 139 (2005), no. 3, 469-485. MR 2177172 (2006f:55006)
  • 9. J. González, L. Zárate, BP-theoretic instabilities to the motion planning problem in 4-torsion lens spaces, Osaka J. Math. 43 (2006), 581-596. MR 2283410 (2007k:57056)
  • 10. A. Hatcher, Algebraic Topology, Cambridge Univ. Press, 2002. MR 1867354 (2002k:55001)
  • 11. R. E. Mosher, M. C. Tangora, Cohomology operations and applications in homotopy theory, Harper & Row Publishers, 1968. MR 0226634 (37:2223)
  • 12. Y. B. Rudyak, On category weight and its applications, Topology 38 (1999), no. 1, 37-55. MR 1644063 (99f:55007)
  • 13. A. S. Schwarz, The genus of a fiber space, Amer. Math. Soc. Transl. (2) 55 (1966), 49-140.
  • 14. E. Spanier, Algebraic Topology, McGraw-Hill, 1966. MR 0210112 (35:1007)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 55M99, 68T40

Retrieve articles in all journals with MSC (2000): 55M99, 68T40

Additional Information

Michael Farber
Affiliation: Department of Mathematical Sciences, Durham University, South Road, Durham DH1 3LE, England

Mark Grant
Affiliation: Department of Mathematical Sciences, Durham University, South Road, Durham DH1 3LE, England

Keywords: Topological complexity, weights of cohomology classes, category weight, cohomology operations, lens spaces.
Received by editor(s): April 23, 2007
Published electronically: April 25, 2008
Additional Notes: The authors were supported by a grant from the UK Engineering and Physical Sciences Research Council; the first author was also supported by a grant from the Royal Society.
Communicated by: Mikhail Shubin
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society