Optimal Allocation of Many Robot Guards for Sweep-Line Coverage

We study the problem of allocating many mobile robots for the execution of a pre-defined sweep schedule in a known two-dimensional environment, with applications toward search and rescue, coverage, surveillance, monitoring, pursuit- evasion, and so on. The mobile robots (or agents) are assumed to have one-dimensional sensing capability with probabilistic guarantees that deteriorate as the sensing distance increases. In solving such tasks, a time-parameterized distribution of robots along the sweep frontier must be computed, to minimize the number of robots used to achieve some desired coverage quality guarantee or to maximize the probabilistic guarantee for a given the number of robots. We propose a max-flow-based algorithm for solving the allocation task, which builds on a decomposition technique of the workspace as a generalization of the well- known boustrophedon decomposition. Our proposed algorithm has a very low polynomial running time and completes in under two seconds for polygonal environments with over 105 vertices. Simulation experiments are carried out on three realistic use cases with randomly generated obstacles of varying shapes, sizes, and spatial distributions, demonstrating our proposed method’s applicability and scalability. Introduction video: https://youtu.be/8taX92rzC5k.