Avoiding Simulation: Computationally Approximating Multi-Robot Swarm Hitting Times

Abstract

We propose a novel way to estimate some properties of the motion of a swarm of robots which does not require carrying out extensive simulations. We leverage the large body of literature on graphs to compute estimates for properties like hitting time, cover time, centrality measures of different regions of an arena, etc. We do not aim to produce accurate physical models of robot behavior, but rather aim to produce estimates of major properties of the robot behavior in the presence of a swarm of robot obstacles using quick closed-form formulas. This would allow the swarm designer to explore a variety of scenarios quickly before advancing to the stage of expensive simulations for more accurate measurements. In this paper, we model the correlated random walk (CRW) of a robot on a discrete arena in discrete time, and then extend this simple model to include multiple robot obstacles. We show how several critical properties for the discrete model can be estimated rapidly using linear algebra tools from spectral graph theory.