Mapping and Pursuit-Evasion strategies for a simple wall-following robot

Max Katsev; Anna Yershova; Benjamn Tovar; Robert Ghrist; Steven M. Lavalle

doi:10.1109/TRO.2010.2095570

Mapping and Pursuit-Evasion strategies for a simple wall-following robot

Max Katsev, Anna Yershova, Benjamn Tovar, Robert Ghrist, Steven M. Lavalle

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

Abstract

This paper defines and analyzes a simple robot with local sensors that moves in an unknown polygonal environment. The robot can execute wall-following motions and can traverse the interior of the environment only when following parallel to an edge. The robot has no global sensors that would allow precise mapping or localization. Special information spaces are introduced for this particular model. Using these, strategies are presented to solve several tasks: 1) counting vertices, 2) computing the path winding number, 3) learning a combinatorial map, which is called the cut ordering, that encodes partial geometric information, and 4) solving pursuit-evasion problems.

Original language	English (US)
Article number	5685659
Pages (from-to)	113-128
Number of pages	16
Journal	IEEE Transactions on Robotics
Volume	27
Issue number	1
DOIs	https://doi.org/10.1109/TRO.2010.2095570
State	Published - Feb 2011

Keywords

Exploration
information spaces
minimal sensing
pursuit evasion
simultaneous localization and mapping (SLAM)

ASJC Scopus subject areas

Control and Systems Engineering
Computer Science Applications
Electrical and Electronic Engineering

Access to Document

10.1109/TRO.2010.2095570

Fingerprint Dive into the research topics of 'Mapping and Pursuit-Evasion strategies for a simple wall-following robot'. Together they form a unique fingerprint.

Cite this

@article{5c2169c1fb684f65a3188df8eae5aad0,

title = "Mapping and Pursuit-Evasion strategies for a simple wall-following robot",

abstract = "This paper defines and analyzes a simple robot with local sensors that moves in an unknown polygonal environment. The robot can execute wall-following motions and can traverse the interior of the environment only when following parallel to an edge. The robot has no global sensors that would allow precise mapping or localization. Special information spaces are introduced for this particular model. Using these, strategies are presented to solve several tasks: 1) counting vertices, 2) computing the path winding number, 3) learning a combinatorial map, which is called the cut ordering, that encodes partial geometric information, and 4) solving pursuit-evasion problems.",

keywords = "Exploration, information spaces, minimal sensing, pursuit evasion, simultaneous localization and mapping (SLAM)",

author = "Max Katsev and Anna Yershova and Benjamn Tovar and Robert Ghrist and Lavalle, {Steven M.}",

note = "Funding Information: Manuscript received February 18, 2010; revised September 5, 2010. Date of publication January 13, 2011; date of current version February 9, 2011. This paper was recommended for publication by Associate Editor C. Stachniss and Editor L. Parker upon evaluation of the reviewers{\textquoteright} comments. This work was supported in part by the National Science Foundation under Grant 0904501 (IIS Robotics) and Grant 1035345 (Cyberphysical Systems), in part by the Defense Advanced Research Projects Agency under Grant HR0011-05-1-0008 (Sensor Topology and Minimal Planning), and in part by the Multidisciplinary University Research Initiative/Office of Naval Research under Grant N00014-09-1-1052.",

year = "2011",

month = feb,

doi = "10.1109/TRO.2010.2095570",

language = "English (US)",

volume = "27",

pages = "113--128",

journal = "IEEE Transactions on Robotics",

issn = "1552-3098",

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

number = "1",

}

TY - JOUR

T1 - Mapping and Pursuit-Evasion strategies for a simple wall-following robot

AU - Katsev, Max

AU - Yershova, Anna

AU - Tovar, Benjamn

AU - Ghrist, Robert

AU - Lavalle, Steven M.

N1 - Funding Information: Manuscript received February 18, 2010; revised September 5, 2010. Date of publication January 13, 2011; date of current version February 9, 2011. This paper was recommended for publication by Associate Editor C. Stachniss and Editor L. Parker upon evaluation of the reviewers’ comments. This work was supported in part by the National Science Foundation under Grant 0904501 (IIS Robotics) and Grant 1035345 (Cyberphysical Systems), in part by the Defense Advanced Research Projects Agency under Grant HR0011-05-1-0008 (Sensor Topology and Minimal Planning), and in part by the Multidisciplinary University Research Initiative/Office of Naval Research under Grant N00014-09-1-1052.

PY - 2011/2

Y1 - 2011/2

N2 - This paper defines and analyzes a simple robot with local sensors that moves in an unknown polygonal environment. The robot can execute wall-following motions and can traverse the interior of the environment only when following parallel to an edge. The robot has no global sensors that would allow precise mapping or localization. Special information spaces are introduced for this particular model. Using these, strategies are presented to solve several tasks: 1) counting vertices, 2) computing the path winding number, 3) learning a combinatorial map, which is called the cut ordering, that encodes partial geometric information, and 4) solving pursuit-evasion problems.

AB - This paper defines and analyzes a simple robot with local sensors that moves in an unknown polygonal environment. The robot can execute wall-following motions and can traverse the interior of the environment only when following parallel to an edge. The robot has no global sensors that would allow precise mapping or localization. Special information spaces are introduced for this particular model. Using these, strategies are presented to solve several tasks: 1) counting vertices, 2) computing the path winding number, 3) learning a combinatorial map, which is called the cut ordering, that encodes partial geometric information, and 4) solving pursuit-evasion problems.

KW - Exploration

KW - information spaces

KW - minimal sensing

KW - pursuit evasion

KW - simultaneous localization and mapping (SLAM)

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

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

U2 - 10.1109/TRO.2010.2095570

DO - 10.1109/TRO.2010.2095570

M3 - Article

AN - SCOPUS:79951579654

VL - 27

SP - 113

EP - 128

JO - IEEE Transactions on Robotics

JF - IEEE Transactions on Robotics

SN - 1552-3098

IS - 1

M1 - 5685659

ER -

Mapping and Pursuit-Evasion strategies for a simple wall-following robot

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Cite this