Pursuit Evasion

From RSN
Revision as of 10:57, June 27, 2009 by Isler (talk | contribs)

Jump to: navigation, search

A Sensor Actuator Network (SAN) is a network of devices equipped with sensing, communication, actuation (e.g.: mobility) and computation capabilities. Many SAN automation tasks, such as surveillance and tracking, can be modeled as pursuit-evasion games. In a pursuit-evasion game, one or more pursuers try to capture an evader who, in turn, tries to avoid capture. This project will develop a theory of pursuit-evasion games taking place in complex environments among complex systems, such as SANs.


Pursuit strategies to be developed as a part of this project will provide robust solutions for a number of SAN automation tasks in emergency response, search and rescue, energy and environmental monitoring, and health care automation. In particular, their utility will be demonstrated on a prototype system for monitoring the elderly. More broadly, the results of this project will participate in the formation of the next generation of automation technologies by advancing the state-of-the-art in distributed sensing and decision making.


Pursuit-evasion games among complex systems are computationally hard in their most general form. Hence, we focus on instances that model SAN automation tasks. Specifically, this project involves

  1. the investigation of the effect of information available to the players on the outcome of pursuit-evasion games,
  2. the development of distributed pursuit strategies which efficiently reason about various forms of uncertainty, and
  3. the adaptation of these results to solve two ubiquitous sensor-actuator network automation tasks (tracking and surveillance) in a robust fashion.


Our previous contributions can be summarized as follows:

  • We started with a game that takes place on a graph. The players have only local visibility. We show that two pursuers can capture the evader on any graph (with high probability). We also present an algorithm which recognizes graphs on which a single pursuer suffices. [1]
  • Next, we studied a version where the game takes place in a simply-connected polygon. The pursuers have only line-of-sight visibility. We showed that a single pursuer can locate the evader (which can be arbitrarily faster than the pursuer) in any simply connected polygon with high probability. This game is known as the "visibility based pursuit-evasion game". If the pursuers are as fast as the evader, we show that they can in fact capture the evader. [2] (An applet that demonstrates this strategy)
  • We are currently working on designing pursuit-evasion strategies for more general systems. Recently, we have extended the pursuit strategy for finding the evader in a polygon to the case where the pursuer's motion is subject to polyhedral kinematic constraints. [3]
  • We have also studied a pursuit-evasion game where the players' motions are restricted to a roadmap. [4]

Full list of publications on pursuit-evasion games is available here.


  • The role of information in pursuit evasion: Graph theoretic models, Applied Algebraic Topology Seminar, IMA, June 2009. Video available through IMA
  • Pursuit-Evasion outreach: demonstration of a greedy pursuit strategy in an educational setting.
  • Turn-based pursuit evasion with localization: mobile robots query a vision system to obtain their coordinates.

This work is supported by the NSF grant Pursuit-Evasion Games with Complex Systems in Complex Environments