Topological complexity of configuration spaces for robot motion planning

Abstract

En este trabajo, estudiaremos el concepto de Complejidad Topológica (TC) de espacios de configuraciones para el movimiento planificado de robots. TC es un número entero positivo que mide las discontinuidades en el proceso de movimiento planificado en el espacio de configuraciones X (el conjunto de posibles posiciones del robot). En [6], Michael Farber determinó cotas superiores para TC en términos de la dimensión y de la Categoría de Lusternik–Schnirelman del espacio de configuraciones X; además, proporcionó una cota inferior trabajando con la cohomología del espacio de configuraciones. Con estas herramientas, es posible calcular TC para esferas de cualquier dimensión n y, en general, de cualquier superficie bidimensional cerrada, compacta, orientable y de género g. En particular, el producto de m esferas de dimensión n, puede considerarse como un brazo de robot con m articulaciones, el cual puede moverse en n dimensiones; el cálculo de TC para ese caso, también es proporcionado en [6]. Posteriormente en [8], se estudia el caso de espacios reales proyectivos de dimensión n, RPn, donde se proporciona una clasificación de TC para tales espacios y, en ciertos casos particulares, el cálculo es explícito. Se introducen otros conceptos que son de gran utilidad. De hecho, uno de los resultados más importantes es que el cálculo de TCpRPnq, coincide con el problema clásico de inmersión de espacios reales proyectivos. Proporcionaremos una sólida justificación de todos los resultados mencionados en [6] y [8], además de varios ejemplos de casos particulares, que permitirán al lector comprender con mayor precisión lo que determina la teoría.

In this work, we study the concept of Topological Complexity pTCq of configuration spaces for robot motion planning. TC is a positive integer which measures discontinuity of the process of motion planning in the configuration space X (the set of possible positions of the robot). In [6], Michael Farber gave upper bounds for TC in terms of the dimension and of the Lusternik–Schinerlman Category of the configuration space X; he also provided a lower bound working with the cohomology of the configuration space. With these tools, it is possible to calculate TC for spheres of any dimension n and, in general, for any 2–dimensional closed, compact, orientable surface of genus g. In particular, the product of m spheres of dimension n, can be seen like a robot arm with m articulations which moves in n dimensions. The calculation of TC for this case, is also given in [6]. Later in [8], the case of real projective spaces of dimension n, RPn, is studied, and a classification of TC for these spaces is provided and, in particular cases, the calculation is explicit. Other useful concepts are introduced. In fact, one of the most important results is that the calculation of TCpRPnq, coincides with the classical immersion problem of real projective spaces. We will provide a solid justification for all results mentioned in [6] and [8], as well as several examples of specific cases, which allow the reader to understand more precisely what the theory determines.