Title: Configuration Spaces and Robot Motion Planning Algorithms,
Abstract: The paper surveys topological problems relevant to the motion planning
problem of robotics and includes some new results and constructions. First we
analyse the notion of topological complexity of configuration spaces which is
responsible for discontinuities in algorithms for robot navigation. Then we
present explicit motion planning algorithms for coordinated collision free
control of many particles moving in Euclidean spaces or on graphs. These
algorithms are optimal in the sense that they have minimal number of regions of
continuity. Moreover, we describe in full detail the topology of configuration
spaces of two particles on a tree and use it to construct some top-dimensional
cohomology classes in configuration spaces of n particles on a tree.