M.Sc Student | Amir Michael |
---|---|

Subject | Probabilistic Pursuits on Graphs |

Department | Department of Computer Science |

Supervisor | Professor Alfred Bruckstein |

Full Thesis text |

We consider discrete dynamical
systems of "ant-like" agents engaged in a sequence of pursuits on a
graph environment. The agents emerge one by one at equal time intervals from a
source vertex *s* and pursue each other by greedily attempting to close
the distance to their immediate predecessor, the agent that emerged just before
them from *s*, until they arrive at the destination point *t*. Such
pursuits have been investigated before in the continuous setting and in
discrete time when the underlying environment is a regular grid. In both these
settings the agents' walks provably converge to a shortest path from *s*
to *t*. Furthermore, assuming a certain natural probability distribution
over the move choices of the agents on the grid (in case there are multiple
shortest paths between an agent and its predecessor), the walks converge to the
uniform distribution over all shortest paths from *s* to *t* - and so
the agents' locations are on average very close to the straight line from *s*
to *t*.

In this work we consider the
evolution of agent walks over a general finite graph environment *G*. Our
model is a natural generalization of the pursuit rule proposed for the case of
the grid. The main results are as follows. We show that "convergence"
to the shortest paths in the sense of previous work extends to all
pseudo-modular graphs (i.e. graphs in which every three pairwise intersecting
disks have a nonempty intersection), and also to environments obtained by
taking graph products, generalizing previous results in two different ways. We
show that convergence to the shortest paths is also obtained by chordal graphs
(i.e. graphs in which all cycles of four or more vertices have a chord), and
discuss some further positive and negative results for planar graphs. In the
most general case, convergence to the shortest paths is not guaranteed, and the
agents may get stuck on sets of recurrent, non-optimal walks from *s* to *t*.
However, we show that the limiting distributions of the agents' walks will
always be uniform distributions over some set of walks of equal length.