Distributed Markov Chain-Based Strategies for Multi-Agent Robotic Surveillance

Abstract

Markov chains have been increasingly used to define persistent robotic surveillance schemes. Motivations for this design choice include their easy implementation, unpredictable surveillance patterns, and their well-studied mathematical background. However, applying previous results to scenarios with multiple agents can significantly increase the dimension of the problem, leading to intractable algorithms. In this work we analyze the hitting time minimization problem for multiple agents moving over a finite graph. We exploit the structure of this problem to propose a tractable algorithm to design Markov chains to cover the graph with multiple interacting agents. Using mathematical analysis, we provide guarantees for the convergence of our proposed solution. Also, through numerical simulations, we show the performance of our approach compared to the current state of art in multi-agent scenarios.