Visibility-based pursuit-evasion in an unknown planar environment

Shai Sachs, Steven M Lavalle, Stjepan Rajko

Research output: Contribution to journalReview article

Abstract

We address an on-line version of the visibility-based pursuit-evasion problem. We take a minimalist approach in modeling the capabilities of a pursuer robot. A point pursuer moves in an unknown, simply-connected, piecewise-smooth planar environment, and is given the task of locating any unpredictable, moving evaders that have unbounded speed. The evaders are assumed to be points that move continuously. To solve the problem, the pursuer must for each target have an unobstructed view of it at some time during execution. The pursuer is equipped with a range sensor that measures the direction of depth discontinuities, but cannot provide precise depth measurements. All pursuer control is specified either in terms of this sensor or wall-following movements. The pursuer does not have localization capability or perfect control. We present a complete algorithm that enables the limited pursuer to clear the same environments that a pursuer with a complete map, perfect localization, and perfect control can clear (under certain general position assumptions). Theoretical guarantees that the evaders will be found are provided. The resulting algorithm to compute this strategy has been implemented in simulation. Results are shown for several examples. The approach is efficient and simple enough to be useful towards the development of real robot systems that perform visual searching.

Original languageEnglish (US)
Pages (from-to)3-26
Number of pages24
JournalInternational Journal of Robotics Research
Volume23
Issue number1
DOIs
StatePublished - Dec 1 2004

Fingerprint

Pursuit-evasion
Visibility
Unknown
Robot
Perfect Map
Robots
Sensor
Sensors
Execution Time
Discontinuity
Target
Modeling
Range of data
Simulation

Keywords

  • Bug algorithms
  • On-line algorithms
  • Pursuit-evasion
  • Sensing uncertainty
  • Sensor-based planning
  • Surveillance
  • Visibility

ASJC Scopus subject areas

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

Cite this

Visibility-based pursuit-evasion in an unknown planar environment. / Sachs, Shai; Lavalle, Steven M; Rajko, Stjepan.

In: International Journal of Robotics Research, Vol. 23, No. 1, 01.12.2004, p. 3-26.

Research output: Contribution to journalReview article

@article{56da59191a5a4de29a836c435f79a388,
title = "Visibility-based pursuit-evasion in an unknown planar environment",
abstract = "We address an on-line version of the visibility-based pursuit-evasion problem. We take a minimalist approach in modeling the capabilities of a pursuer robot. A point pursuer moves in an unknown, simply-connected, piecewise-smooth planar environment, and is given the task of locating any unpredictable, moving evaders that have unbounded speed. The evaders are assumed to be points that move continuously. To solve the problem, the pursuer must for each target have an unobstructed view of it at some time during execution. The pursuer is equipped with a range sensor that measures the direction of depth discontinuities, but cannot provide precise depth measurements. All pursuer control is specified either in terms of this sensor or wall-following movements. The pursuer does not have localization capability or perfect control. We present a complete algorithm that enables the limited pursuer to clear the same environments that a pursuer with a complete map, perfect localization, and perfect control can clear (under certain general position assumptions). Theoretical guarantees that the evaders will be found are provided. The resulting algorithm to compute this strategy has been implemented in simulation. Results are shown for several examples. The approach is efficient and simple enough to be useful towards the development of real robot systems that perform visual searching.",
keywords = "Bug algorithms, On-line algorithms, Pursuit-evasion, Sensing uncertainty, Sensor-based planning, Surveillance, Visibility",
author = "Shai Sachs and Lavalle, {Steven M} and Stjepan Rajko",
year = "2004",
month = "12",
day = "1",
doi = "10.1177/0278364904039610",
language = "English (US)",
volume = "23",
pages = "3--26",
journal = "International Journal of Robotics Research",
issn = "0278-3649",
publisher = "SAGE Publications Inc.",
number = "1",

}

TY - JOUR

T1 - Visibility-based pursuit-evasion in an unknown planar environment

AU - Sachs, Shai

AU - Lavalle, Steven M

AU - Rajko, Stjepan

PY - 2004/12/1

Y1 - 2004/12/1

N2 - We address an on-line version of the visibility-based pursuit-evasion problem. We take a minimalist approach in modeling the capabilities of a pursuer robot. A point pursuer moves in an unknown, simply-connected, piecewise-smooth planar environment, and is given the task of locating any unpredictable, moving evaders that have unbounded speed. The evaders are assumed to be points that move continuously. To solve the problem, the pursuer must for each target have an unobstructed view of it at some time during execution. The pursuer is equipped with a range sensor that measures the direction of depth discontinuities, but cannot provide precise depth measurements. All pursuer control is specified either in terms of this sensor or wall-following movements. The pursuer does not have localization capability or perfect control. We present a complete algorithm that enables the limited pursuer to clear the same environments that a pursuer with a complete map, perfect localization, and perfect control can clear (under certain general position assumptions). Theoretical guarantees that the evaders will be found are provided. The resulting algorithm to compute this strategy has been implemented in simulation. Results are shown for several examples. The approach is efficient and simple enough to be useful towards the development of real robot systems that perform visual searching.

AB - We address an on-line version of the visibility-based pursuit-evasion problem. We take a minimalist approach in modeling the capabilities of a pursuer robot. A point pursuer moves in an unknown, simply-connected, piecewise-smooth planar environment, and is given the task of locating any unpredictable, moving evaders that have unbounded speed. The evaders are assumed to be points that move continuously. To solve the problem, the pursuer must for each target have an unobstructed view of it at some time during execution. The pursuer is equipped with a range sensor that measures the direction of depth discontinuities, but cannot provide precise depth measurements. All pursuer control is specified either in terms of this sensor or wall-following movements. The pursuer does not have localization capability or perfect control. We present a complete algorithm that enables the limited pursuer to clear the same environments that a pursuer with a complete map, perfect localization, and perfect control can clear (under certain general position assumptions). Theoretical guarantees that the evaders will be found are provided. The resulting algorithm to compute this strategy has been implemented in simulation. Results are shown for several examples. The approach is efficient and simple enough to be useful towards the development of real robot systems that perform visual searching.

KW - Bug algorithms

KW - On-line algorithms

KW - Pursuit-evasion

KW - Sensing uncertainty

KW - Sensor-based planning

KW - Surveillance

KW - Visibility

UR - http://www.scopus.com/inward/record.url?scp=29344471950&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=29344471950&partnerID=8YFLogxK

U2 - 10.1177/0278364904039610

DO - 10.1177/0278364904039610

M3 - Review article

AN - SCOPUS:29344471950

VL - 23

SP - 3

EP - 26

JO - International Journal of Robotics Research

JF - International Journal of Robotics Research

SN - 0278-3649

IS - 1

ER -