Techniques are provided for discovery and monitoring of an environment using a plurality of robots. A plurality of robots navigate an environment by determining a navigation buffer for each of the robots; and allowing each of the robots to navigate within the environment while maintaining a substantially minimum distance from other robots, wherein the substantially minimum distance corresponds to the navigation buffer, and wherein a size of each of the navigation buffers is reduced over time based on a percentage of the environment that remains to be navigated. The robots can also navigate an environment by obtaining a discretization of the environment to a plurality of discrete regions; and determining a next unvisited discrete region for one of the plurality of robots to explore in the exemplary environment using a breadth-first search. The plurality of discrete regions can be, for example, a plurality of real or virtual tiles.