An art gallery approach to ensuring that landmarks are distinguishable

Lawrence H. Erickson, Steven M Lavalle

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

Abstract

How many different classes of partially distinguishable landmarks are needed to ensure that a robot can always see a landmark without simultaneously seeing two of the same class? To study this, we introduce the chromatic art gallery problem. A guard set S ⊂ P is a set of points in a polygon P such that for all p ∈ P, there exists an s ∈ S such that s and p are mutually visible. Suppose that two members of a finite guard set S ⊂ P must be given different colors if their visible regions overlap. What is the minimum number of colors required to color any guard set (not necessarily a minimal guard set) of a polygon P? We call this number, χG(P), the chromatic guard number of P. We believe this problem has never been examined before, and it has potential applications to robotics, surveillance, sensor networks, and other areas. We show that for any spiral polygon Pspi, χG(Pspi) ≤ 2, and for any staircase polygon (strictly monotone orthogonal polygon) Psta, χG(Psta) ≤ 3. For lower bounds, we construct a polygon with 4k vertices that requires k colors. We also show that for any positive integer k, there exists a monotone polygon Mk with 3k2 vertices such that χG(Mk) ≥ k, and for any odd integer k, there exists an orthogonal polygon Rk with 4k2 + 10k + 10 vertices such that χG(Rk) ≥ k.

Original languageEnglish (US)
Title of host publicationRobotics
Subtitle of host publicationScience and Systems VII
EditorsHugh Durrant-Whyte, Pieter Abbeel, Nicholas Roy
PublisherMIT Press Journals
Pages81-88
Number of pages8
ISBN (Print)9780262517799
StatePublished - Jan 1 2012
EventInternational Conference on Robotics Science and Systems, RSS 2011 - Los Angeles, United States
Duration: Jun 27 2011Jul 1 2011

Publication series

NameRobotics: Science and Systems
Volume7
ISSN (Print)2330-7668
ISSN (Electronic)2330-765X

Other

OtherInternational Conference on Robotics Science and Systems, RSS 2011
CountryUnited States
CityLos Angeles
Period6/27/117/1/11

    Fingerprint

ASJC Scopus subject areas

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

Cite this

Erickson, L. H., & Lavalle, S. M. (2012). An art gallery approach to ensuring that landmarks are distinguishable. In H. Durrant-Whyte, P. Abbeel, & N. Roy (Eds.), Robotics: Science and Systems VII (pp. 81-88). (Robotics: Science and Systems; Vol. 7). MIT Press Journals.