Algorithms for distributed and mobile sensing

Sensing remote, complex and large environments is an important task that arises in diverse applications including planetary exploration, monitoring forest fires and the surveillance of large factories. Currently, automation of such sensing tasks in complex environments is achieved either by deploying many stationary sensors to the environment, or by mounting a sensor on a mobile device and using the device to sense the environment. The Eighties and Nineties witnessed tremendous advances in both distributed and mobile sensing technologies. To take advantage of these technologies, it is crucial to design algorithms to perform sensing tasks in an autonomous fashion. In this dissertation, we study four fundamental sensing problems that arise in sensing complex environments with distributed and mobile systems. For mobile sensing systems we study exploration and pursuit-evasion problems. In the exploration problem, the goal is to design a strategy for a mobile robot so that the robot sees every point in an unknown environment as quickly as possible. In the pursuit-evasion problem, the goal is to design a strategy for a pursuer to capture an adversarial evader. For distributed sensing systems we study placement and assignment problems. In the placement problem, the goal is to place sensors to an environment so that every point in the environment is in the range of at least one sensor. The assignment problem deals with the issue of assigning targets to sensors in a network, so that overall error in estimating the position of the targets is minimized. We present algorithms to perform these sensing tasks in an efficient fashion. Performance guarantees of the algorithms are mathematically proven and evaluated by simulations