Robot motion planning, weights of cohomology classes, and cohomology operations
HTML articles powered by AMS MathViewer
- by Michael Farber and Mark Grant PDF
- Proc. Amer. Math. Soc. 136 (2008), 3339-3349 Request permission
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
- Octav Cornea, Gregory Lupton, John Oprea, and Daniel Tanré, Lusternik-Schnirelmann category, Mathematical Surveys and Monographs, vol. 103, American Mathematical Society, Providence, RI, 2003. MR 1990857, DOI 10.1090/surv/103
- Edward Fadell and Sufian Husseini, Category weight and Steenrod operations, Bol. Soc. Mat. Mexicana (2) 37 (1992), no. 1-2, 151–161. Papers in honor of José Adem (Spanish). MR 1317569, DOI 10.1016/0165-1765(91)90092-y
- Michael Farber, Topological complexity of motion planning, Discrete Comput. Geom. 29 (2003), no. 2, 211–221. MR 1957228, DOI 10.1007/s00454-002-0760-9
- Michael Farber, Instabilities of robot motion, Topology Appl. 140 (2004), no. 2-3, 245–266. MR 2074919, DOI 10.1016/j.topol.2003.07.011
- Michael Farber, Topology of robot motion planning, Morse theoretic methods in nonlinear analysis and in symplectic topology, NATO Sci. Ser. II Math. Phys. Chem., vol. 217, Springer, Dordrecht, 2006, pp. 185–230. MR 2276952, DOI 10.1007/1-4020-4266-3_{0}5
- Michael Farber and Mark Grant, Symmetric motion planning, Topology and robotics, Contemp. Math., vol. 438, Amer. Math. Soc., Providence, RI, 2007, pp. 85–104. MR 2359031, DOI 10.1090/conm/438/08447
- Michael Farber, Serge Tabachnikov, and Sergey Yuzvinsky, Topological robotics: motion planning in projective spaces, Int. Math. Res. Not. 34 (2003), 1853–1870. MR 1988783, DOI 10.1155/S1073792803210035
- Jesús González, Topological robotics in lens spaces, Math. Proc. Cambridge Philos. Soc. 139 (2005), no. 3, 469–485. MR 2177172, DOI 10.1017/S030500410500873X
- Jesús González and Leticia Zárate, BP-theoretic instabilities to the motion planning problem in 4-torsion lens spaces, Osaka J. Math. 43 (2006), no. 3, 581–596. MR 2283410
- Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. MR 1867354
- Robert E. Mosher and Martin C. Tangora, Cohomology operations and applications in homotopy theory, Harper & Row, Publishers, New York-London, 1968. MR 0226634
- Yuli B. Rudyak, On category weight and its applications, Topology 38 (1999), no. 1, 37–55. MR 1644063, DOI 10.1016/S0040-9383(97)00101-8
- A. S. Schwarz, The genus of a fiber space, Amer. Math. Soc. Transl. (2) 55 (1966), 49–140.
- Edwin H. Spanier, Algebraic topology, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0210112
Additional Information
- Michael Farber
- Affiliation: Department of Mathematical Sciences, Durham University, South Road, Durham DH1 3LE, England
- Email: michael.farber@durham.ac.uk
- Mark Grant
- Affiliation: Department of Mathematical Sciences, Durham University, South Road, Durham DH1 3LE, England
- MR Author ID: 794577
- Email: mark.grant@durham.ac.uk
- 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
- © Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 136 (2008), 3339-3349
- MSC (2000): Primary 55M99; Secondary 68T40
- DOI: https://doi.org/10.1090/S0002-9939-08-09529-4
- MathSciNet review: 2407101