Collision-free motions of round robots on metric graphs

Abstract

In this thesis, we study the path-connectivity problem of configuration spaces of two robots that move without collisions on a connected metric graph. The robots are modelled as metric balls of positive radii. In other words, we wish to find the number of path-connected components of such a configuration space. Finding a solution to this problem will help us to understand which configurations can be reached from any chosen configuration.

In order to solve the above problem, we show that any collision-free motion of two robots can be replaced by a finite sequence of elementary motions. As a corollary, we reduce the path-connectivity problem for a 2-dimensional configuration space to the same problem for a simple 1-dimensional subgraph (the configuration skeleton) of the space.