Probabilistic pursuits on graphs

DOI10.1016/J.TCS.2019.08.001MaRDI QIDQ2330128zbMATH OpenOpenAlexFDO

Authors Michael Amir, Alfred M. Bruckstein

Publication date 18 October 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.08107

zbMATH Keywords

chain pursuitsgrid geometrygridsmulti-agent pursuitsprobabilistic multi-agent systemspseudo-modular graphs

Mathematics Subject Classification ID

Random walks on graphs (05C81) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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$. We study 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, 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.

Recommendations

• Probabilistic optimization in graph-problems
• scientific article; zbMATH DE number 4101220
• Probabilistic Bigraphs
• scientific article; zbMATH DE number 4205985
• Vertex-pursuit in random directed acyclic graphs
• Graph searching games and probabilistic methods
• Probabilistic Pursuits on the Grid
• scientific article; zbMATH DE number 4055347
• Probabilistic combinatorial optimization problems on graphs: A new domain in operational research

Cites work

• Algorithmic graph theory and perfect graphs
• Ant local search and its efficient adaptation to graph colouring
• Handbook of product graphs
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 3214278 (Why is no real title available?)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Markov chains and stochastic stability
• Metric graph theory and geometry: a survey
• On rigid circuit graphs
• Probabilistic Pursuits on the Grid
• Pseudo-modular graphs
• Slicing an ear using prune-and-search
• The game of cops and robbers on graphs
• The role of information in the cop-robber game
• Why the ant trails look so straight and nice

Cited in

(2)

• Quantitative asymptotics of graphical projection pursuit
• Probabilistic Pursuits on the Grid

This page was built for publication: Probabilistic pursuits on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2330128)