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

Farber, Michael; Grant, Mark

doi:10.1090/S0002-9939-08-09529-4

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