On Probabilistic Pursuits on Grids and Graphs

We survey some models  of stochastic multi-agent interactions,

 involving  simple ant-like a(ge)nts  moving on grids,  or some general planar graph

 environments, leading to interesting results concerning the average number of visits

 to various sites and to connections between Euclidean and discrete geometry.

 We first describe a probabilistic pursuit model on the discrete grid, and show that a chain pursuit

 involving a sequence of agents  emerging at some starting point and ending at a fixed target location,

 converges to a Markov chain of shortest walks, and yields that the visit  frequency profile at each location

 defines with high precision a continuous straight line connecting the source and the destination in the Euclidean plane.  Subsequently we discuss some recent results on similar pursuits defined on different planar  graphs, and show that, under some interesting geometric conditions,  similar results hold.

 Finally we discuss some interaction that yield convergence to more complex geometric objects in the plane, and delineate a research program that uses interacting agents leaving pheromone trails in discretized environments to solve, with high precision,  a variety of  continuous geometric optimization problems.

 (the talk is be based on several papers co-authored with I. Wagner, C. Mallows, and M. Amir).