אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

We consider a discrete system of "ant-like" agents which pursue each other on the vertices of a graph environment. Visually reminiscent of a trail of ants, 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 graph. In both these settings the agents' walks provably converge to a shortest path between s and 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. We study, more generally, the evolution of such systems over a general graph environment G. We will exhibit surprising connections to topology, convex geometry and graph theory. For example, if every three pairwise intersecting disks of G have a non-empty (shared) intersection, the agents' walks are guaranteed to converge to the uniform distribution over all shortest paths.