A complexity result for the pursuit-evasion game of maintaining visibility of a moving evader

Rafael Murrieta-Cid, Raul Monroy, Seth Hutchinson, Jean Paul Laumond

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper we consider the problem of maintaining visibility of a moving evader by a mobile robot, the pursuer, in an environment with obstacles. We simultaneously consider bounded speed for both players and a variable distance separating them. Unlike our previous efforts [11], we give special attention to the combinatorial problem that arises when searching for a solution through visiting several locations. We approach evader tracking by decomposing the environment into convex regions. We define two graphs: one is called the mutual visibility graph (MVG) and the other the accessibility graph (AG). The MVG provides a sufficient condition to maintain visibility of the evader while the AG defines possible regions to which either the pursuer or the evader may go to. The problem is framed as a non cooperative game. We establish the existence of a solution, based on a k - Min approach, for the following givens: the environment, the initial state of the evader and the pursuer, including their maximal speeds. We show that the problem of finding a solution to this game is NP-complete.

Original languageEnglish (US)
Title of host publication2008 IEEE International Conference on Robotics and Automation, ICRA 2008
Pages2657-2664
Number of pages8
DOIs
StatePublished - 2008
Event2008 IEEE International Conference on Robotics and Automation, ICRA 2008 - Pasadena, CA, United States
Duration: May 19 2008May 23 2008

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)1050-4729

Other

Other2008 IEEE International Conference on Robotics and Automation, ICRA 2008
Country/TerritoryUnited States
CityPasadena, CA
Period5/19/085/23/08

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'A complexity result for the pursuit-evasion game of maintaining visibility of a moving evader'. Together they form a unique fingerprint.

Cite this