A complete pursuit-evasion algorithm for two pursuers using beam detection

Borislav H. Simov; Steven M. LaValle; Giora Slutzki

doi:10.1109/ROBOT.2002.1013427

A complete pursuit-evasion algorithm for two pursuers using beam detection

Borislav H. Simov, Steven M. LaValle, Giora Slutzki

Research output: Contribution to journal › Article › peer-review

Abstract

We present an algorithm for a pair of pursuers, each with one rotating beam (flashlight, laser or a camera), searching for an unpredictable, moving target in a 2D environment (simple polygon). Given a polygon with n edges, the algorithm decides in time O(n⁴ whether it can be cleared by the pursuers, and if so, constructs a search schedule. The pursuers are allowed to move on the boundary and in the interior of the polygon. They are not required to maintain mutual visibility throughout the pursuit.

Original language	English (US)
Pages (from-to)	618-623
Number of pages	6
Journal	Proceedings - IEEE International Conference on Robotics and Automation
Volume	1
DOIs	https://doi.org/10.1109/ROBOT.2002.1013427
State	Published - May 2002

ASJC Scopus subject areas

Software
Control and Systems Engineering
Artificial Intelligence
Electrical and Electronic Engineering

Online availability

10.1109/ROBOT.2002.1013427

Library availability

Discover UIUC Full Text

Cite this

@article{05b3f3a7b1994f99a592fea530c2cec5,

title = "A complete pursuit-evasion algorithm for two pursuers using beam detection",

abstract = "We present an algorithm for a pair of pursuers, each with one rotating beam (flashlight, laser or a camera), searching for an unpredictable, moving target in a 2D environment (simple polygon). Given a polygon with n edges, the algorithm decides in time O(n4 whether it can be cleared by the pursuers, and if so, constructs a search schedule. The pursuers are allowed to move on the boundary and in the interior of the polygon. They are not required to maintain mutual visibility throughout the pursuit.",

author = "Simov, {Borislav H.} and LaValle, {Steven M.} and Giora Slutzki",

year = "2002",

month = may,

doi = "10.1109/ROBOT.2002.1013427",

language = "English (US)",

volume = "1",

pages = "618--623",

journal = "Proceedings - IEEE International Conference on Robotics and Automation",

issn = "1050-4729",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - A complete pursuit-evasion algorithm for two pursuers using beam detection

AU - Simov, Borislav H.

AU - LaValle, Steven M.

AU - Slutzki, Giora

PY - 2002/5

Y1 - 2002/5

N2 - We present an algorithm for a pair of pursuers, each with one rotating beam (flashlight, laser or a camera), searching for an unpredictable, moving target in a 2D environment (simple polygon). Given a polygon with n edges, the algorithm decides in time O(n4 whether it can be cleared by the pursuers, and if so, constructs a search schedule. The pursuers are allowed to move on the boundary and in the interior of the polygon. They are not required to maintain mutual visibility throughout the pursuit.

AB - We present an algorithm for a pair of pursuers, each with one rotating beam (flashlight, laser or a camera), searching for an unpredictable, moving target in a 2D environment (simple polygon). Given a polygon with n edges, the algorithm decides in time O(n4 whether it can be cleared by the pursuers, and if so, constructs a search schedule. The pursuers are allowed to move on the boundary and in the interior of the polygon. They are not required to maintain mutual visibility throughout the pursuit.

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

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

U2 - 10.1109/ROBOT.2002.1013427

DO - 10.1109/ROBOT.2002.1013427

M3 - Article

AN - SCOPUS:0036056261

SN - 1050-4729

VL - 1

SP - 618

EP - 623

JO - Proceedings - IEEE International Conference on Robotics and Automation

JF - Proceedings - IEEE International Conference on Robotics and Automation

ER -

A complete pursuit-evasion algorithm for two pursuers using beam detection

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this