Instabilities of robot motion. (English) Zbl 1106.68107

Summary: Instabilities of robot motion are caused by topological reasons. In this paper we find a relation between the topological properties of a configuration space (the structure of its cohomology algebra) and the character of instabilities, which are unavoidable in any motion planning algorithm. More specifically, let \(X\) denote the space of all admissible configurations of a mechanical system. A motion planner is given by a splitting \(X \times X=F_1\cup F_2 \cup \ldots \cup F_k\) (where \(F_1, \ldots ,F_k\) are pairwise disjoint ENRs, see below) and by continuous maps \(s_j :F_j \to PX\), such that \(E \circ s_j=1_{F_j}\). Here \(PX\) denotes the space of all continuous paths in \(X\) (admissible motions of the system) and \(E :PX \to X \times X\) denotes the map which assigns to a path the pair of its initial-end points. Any motion planner determines an algorithm of motion planning for the system. In this paper we apply methods of algebraic topology to study the minimal number of sets \(F_j\) in any motion planner in \(X\). We also introduce a new notion of order of instability of a motion planner; it describes the number of essentially distinct motions which may occur as a result of small perturbations of the input data. We find the minimal order of instability, which may have motion planners on a given configuration space \(X\). We study a number of specific problems: motion of a rigid body in \(\mathbf R^3\), a robot arm, motion in \(\mathbf R^3\) in the presence of obstacles, and others.


68T40 Artificial intelligence for robotics
93C85 Automated systems (robots, etc.) in control theory
Full Text: DOI arXiv


[1] Dold, A., Lectures on Algebraic Topology (1972), Springer: Springer Berlin · Zbl 0234.55001
[2] Dubrovin, B.; Novikov, S. P.; Fomenko, A. T., Modern Geometry: Methods of the Homology Theory (1984) · Zbl 0582.55001
[3] Farber, M., Topological complexity of motion planning, Discrete Comput. Geom., 29, 211-221 (2003) · Zbl 1038.68130
[4] James, I. M., On category, in the sense of Lusternik-Schnirelman, Topology, 17, 331-348 (1978) · Zbl 0408.55008
[5] Kelley, J., General Topology (1957), New York
[6] Latombe, J.-C., Robot Motion Planning (1991), Kluwer Academic: Kluwer Academic Dordrecht
[7] Schwarz, A. S., The genus of a fiber space, Amer. Math. Sci. Transl., 55, 49-140 (1966)
[8] Sharir, M., Algorithmic motion planning, (Goldman, J.; O’Rourke, J., Handbook of Discrete and Computational Geometry (1997), CRC Press: CRC Press Boca Raton, FL) · Zbl 0925.93625
[9] Spanier, E., Algebraic Topology (1966) · Zbl 0145.43303
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.