Topology of Parametrized Motion Planning Algorithms

Abstract

We introduce and study a new concept of parametrized topological complexity: a topological invariant motivated by the motion planning problem of robotics. In the parametrized setting, a motion planning algorithm has a high degree of universality and flexibility and can function under a variety of external conditions (such as positions of obstacles). We explicitly compute the parametrized topological complexity of obstacle-avoiding collision-free motion of many particles (robots) in 3-dimensional space. Our results show that the parametrized topological complexity can be significantly higher than the standard (nonparametrized) invariant.