| We introduce distributed algorithms that enable groups of robots to monitor environmental fields such as temperature, chemical concentration, or radiation intensity. The robots autonomously patrol the environment, measure it, estimate it, and coordinate their actions with other nearby robots. Our algorithms enable large groups of robots to measure complicated environments because each individual's memory and communication requirements remain constant as the number of robots, the number of measurements, and the complexity of the environmental model increases.;We first examine an average consensus-based environmental monitoring method. Using average consensus algorithms, which allow the robots to estimate the average of their individual inputs in a decentralized manner, the robots implement decentralized Kalman filters to estimate the environment. The faster the average consensus algorithm converges, the less overall communication required to implement the decentralized Kalman filter. We present an average consensus design process that creates estimators that converge quickly over a range of networks. Our simulation results indicate that the performance of the average consensus estimators we design remains relatively constant over a variety of network topologies.;Next, we develop a method that allows the robots to identify their Voronoi neighbors from inter-robot distance measurements, without assigning coordinates to neighboring robots. Knowledge of the Voronoi neighbor relation can improve existing distributed algorithms (such as average consensus or localization) by allowing robots to maintain network connectivity while processing information from only a subset of their neighbors. We prove the correctness of the algorithm when the measurements are exact. We also validate the algorithm through simulation using an empirical measurement model based on XBee received signal strength indicator (RSSI) data.;Finally, we develop a distributed environmental monitoring system where each robot estimates the field only over its own Voronoi cell. No individual robot stores or communicates a complete description of the field; therefore, in contrast to the average consensus- based approach, each robot's memory and communication requirements remain fixed as the complexity of the environment increases. The robots first deploy themselves, moving so that their Voronoi cells have roughly equal area and long edges. The Voronoi regions become elements in a finite element mesh. The deployment step ensures that each robot has similar memory and communication requirements and that the resulting finite element problem is well conditioned. After establishing their regions, the robots use a distributed optimization method to determine their estimate and uncertainty within their region. Robots patrol their region to reduce their uncertainty. A query system allows a human operator to determine the value of the field at any location by contacting any robot. The algorithm is evaluated through simulation and a comparison with existing methods in the literature. |
