The last decade witnessed tremendous advances in distributed and mobile sensing technologies which has made it possible to deploy mobile robots and sensor networks in complex environments. To take advantage of these capabilities, it is crucial to design algorithms to perform high-level tasks in an autonomous fashion. A fundamental problem that arises in this context is pursuit-evasion. In a typical pursuit-evasion game, a pursuer tries to capture an evader who, in turn, actively tries to avoid capture. Practical applications of pursuit-evasion games include surveillance, search-and-rescue, collision avoidance and air traffic control. Designing pursuit strategies that incorporate visibility constraints in a complex environment is a major challenge.
In this talk, I will present pursuit strategies for two such games. In the first game, one or more hunters is seeking to capture an evading rabbit on a graph. At the beginning of each round, the rabbit tries to gather information about the location of the hunters. It can see the hunters only if they are located on adjacent nodes. The second game is played in a simply-connected polygon. The players can move one unit at a time and they can see each other if their view is not obstructed by the polygon.
For both games we will answer the following questions:
-
Given an environment, how many pursuers are needed to capture the evader?
-
Given k pursuers, what is the class of environments where k pursuers suffice for capture?
I will conclude the talk with an overview of solutions we have obtained to various other algorithmic problems in the area of distributed and mobile sensing.