SAFI-SAMGHABADI, MARJAN (2013) Collision-free motions of round robots on metric graphs. Doctoral thesis, Durham University.
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.
|Item Type:||Thesis (Doctoral)|
|Award:||Doctor of Philosophy|
|Faculty and Department:||Faculty of Science > Mathematical Sciences, Department of|
|Copyright:||Copyright of this thesis is held by the author|
|Deposited On:||11 Sep 2013 10:13|