Design of Stochastic Robotic Swarms for Target Performance Metrics in Boundary Coverage Tasks
This work addresses boundary coverage for applications like environmental monitoring and disaster response, but it is incremental as it builds on existing stochastic methods with new analytical tools.
The paper tackles the problem of designing stochastic robotic swarms for boundary coverage tasks by analyzing random robot configurations to compute statistical properties of communication and sensing networks, deriving formulas for network connectivity and sensor coverage using order statistics and random geometric graphs.
In this work, we analyze \textit{stochastic coverage schemes} (SCS) for robotic swarms in which the robots randomly attach to a one-dimensional boundary of interest using local communication and sensing, without relying on global position information or a map of the environment. Robotic swarms may be required to perform boundary coverage in a variety of applications, including environmental monitoring, collective transport, disaster response, and nanomedicine. We present a novel analytical approach to computing and designing the statistical properties of the communication and sensing networks that are formed by random robot configurations on a boundary. We are particularly interested in the event that a robot configuration forms a connected communication network or maintains continuous sensor coverage of the boundary. Using tools from order statistics, random geometric graphs, and computational geometry, we derive formulas for properties of the random graphs generated by robots that are independently and identically distributed along a boundary. We also develop order-of-magnitude estimates of these properties based on Poisson approximations and threshold functions. For cases where the SCS generates a uniform distribution of robots along the boundary, we apply our analytical results to develop a procedure for computing the robot population size, diameter, sensing range, or communication range that yields a random communication network or sensor network with desired properties.