Coverage, exploration and deployment by a mobile robot and communication network

We consider the problem of coverage and exploration of an unknown dynamic environment using a mobile robot. The environment is assumed to be large enough such that constant motion by the robot is needed to cover the environment. We present an efficient minimalist algorithm which assumes that global information is not available (neither a map, nor GPS). Our algorithm deploys a network of radio beacons which assists the robot in coverage. The network is also used by the robot for navigation. The deployed network can also be used for applications other than coverage (such as multi-robot task allocation). Simulation experiments are presented which show the collaboration between the deployed network and mobile robot for the tasks of coverage/exploration, network deployment and maintenance (repair), and mobile robot recovery (homing behavior). We discuss a theoretical basis for our algorithm on graphs and show the results of the simulated scenario experiments.