Robotic Surveillance Based on the Meeting Time of Random Walks
This work addresses robotic surveillance strategies by improving theoretical bounds and enabling optimization, though it is incremental as it builds on existing random walk models.
The paper tackles the problem of analyzing and minimizing the expected meeting time between pursuer and evader robots performing random walks on digraphs, providing the first closed-form expression for this time and using it to formulate optimization problems that show effectiveness in basic case studies.
This paper analyzes the meeting time between a pair of pursuer and evader performing random walks on digraphs. The existing bounds on the meeting time usually work only for certain classes of walks and cannot be used to formulate optimization problems and design robotic strategies. First, by analyzing multiple random walks on a common graph as a single random walk on the Kronecker product graph, we provide the first closed-form expression for the expected meeting time in terms of the transition matrices of the moving agents. This novel expression leads to necessary and sufficient conditions for the meeting time to be finite and to insightful graph-theoretic interpretations. Second, based on the closed-form expression, we setup and study the minimization problem for the expected capture time for a pursuer/evader pair. We report theoretical and numerical results on basic case studies to show the effectiveness of the design.