  A topological theory initiated recently by the author 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 prove that the topological complexity of
motion planning TC(X) coincides with the minimal n such that there exists an
n-valued random motion planning algorithm for the system; here $X$ denotes the
configuration space. We study in detail the problem of collision free motion of
several objects on a graph G. We describe an explicit motion planning algorithm
for this problem. We prove that if G is a tree and if the number of objects is
large enough, then the topological complexity of this motion planning problem
equals 2m(G)+1 where m(G) is the number of the essential vertices of G. It
turns out (in contrast with the results on the collision free control of many
objects in space obtained earlier jointly with S. Yuzvinsky) that the
topological complexity is independent of the number of particles.
