Visibility-based pursuitĝ€"evasion with bounded speed

Benjamín Tovar, Steven M Lavalle

Research output: Contribution to journalArticle

Abstract

In this paper we present a study on the visibility-based pursuitĝ€" evasion problem in which bounds on the speeds of the pursuer and evader are given. In this setting, the pursuer tries to find the evader inside a simply connected polygonal environment, and the evader in turn tries to avoid detection. The focus of the paper is to develop a characterization of the set of possible evader positions as a function of time (the reachable sets). This characterization is more complex than the unbounded-speed case, because it no longer depends only on the combinatorial changes in the visibility region of the pursuer. The characterization presented can be used as a filter to keep track of the possible evader's position as a pursuer moves in the environment, or it can be used to guide the construction of the pursuer search strategy. This search algorithm is at least as powerful as a complete algorithm for the unbounded-speed case, and with the knowledge of speed bounds, generates solutions for environments that were unsolvable previously. Given that numerical methods are needed to compute the reachable sets, we also present a conservative approximation which can be computed with a closed formula.

Original languageEnglish (US)
Pages (from-to)1350-1360
Number of pages11
JournalInternational Journal of Robotics Research
Volume27
Issue number11-12
DOIs
StatePublished - Nov 1 2008

Keywords

  • Bounded-speed
  • Mobile robots
  • Pursuit-evasion
  • Visibility

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Mechanical Engineering
  • Electrical and Electronic Engineering
  • Artificial Intelligence
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Visibility-based pursuitĝ€"evasion with bounded speed'. Together they form a unique fingerprint.

  • Cite this