Collision Free Motion Planning on Graphs

A topological theory initiated in [4,5] uses methods of algebraic topology to estimate numerically the character of instabilities arising in motion planning algorithms. The present paper studies random motion planning algorithms and reveals how the topology of the robot’s configuration space influences their structure. We prof that the topological complexity of motion planning TC(X) coinsides with the minimal n such that there exist an n-valued random motion planning algorithm for the system; here X the configuration space. We study in detail the problem of collision free motion of several objects in the graph Γ. We describe an explicit motion planning algorithm for this problem. We prove that if Γ is a tree and if the number of objects is large enough, then the topological complexity of this motion planning problem equals 2m(Γ)+1 where m(Γ) is the number of the essential vertices of Γ. It turns out (in contrast with the results on the collision free control of many objects in space [7]) that the topological complexity is independent of the number of particles.

Authors and Affiliations

1. University of Durham, Durham DH1 3LE, UK

   Michael Farber

Reprints and permissions

Policies and ethics