Navigation among visually connected sets of partially distinguishable landmarks

Lawrence H. Erickson, Steven M Lavalle

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

Abstract

A robot navigates in a polygonal region populated by a set of partially distinguishable landmarks. The robot's motion primitives consist of actions of the form "drive toward a landmark of class x". To effectively navigate, the robot must always be able to see a landmark. Also, if the robot sees two landmarks of the same class, its motion primitives become ambiguous. Finally, if the robot wishes to navigate from landmark s0 to landmark sgoal with a simple graph search algorithm, then there must be a sequence of landmarks [s0, s1, s2,..., s k = sgoal], in which landmark si is visible from si-1. Given these three conditions, how many landmark classes are required for navigation in a given polygon P? We call this minimum number of landmark classes the connected landmark class number, denoted χCL(P). We study this problem for the monotone polygons, an important family of polygons that are frequently generated as intermediate steps in other decomposition algorithms. We demonstrate that for all odd k, there exists a monotone polygon Mk with 3/4 (k2 + 2k + 1) vertices such that χCL(P) ≥ k. We also demonstrate that for any n-vertex monotone polygon P, χCL(P) ≤ n/3 + 12.

Original languageEnglish (US)
Title of host publication2012 IEEE International Conference on Robotics and Automation, ICRA 2012
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4829-4835
Number of pages7
ISBN (Print)9781467314039
DOIs
StatePublished - Jan 1 2012
Event 2012 IEEE International Conference on Robotics and Automation, ICRA 2012 - Saint Paul, MN, United States
Duration: May 14 2012May 18 2012

Publication series

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

Other

Other 2012 IEEE International Conference on Robotics and Automation, ICRA 2012
CountryUnited States
CitySaint Paul, MN
Period5/14/125/18/12

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Navigation among visually connected sets of partially distinguishable landmarks'. Together they form a unique fingerprint.

Cite this