Robotics: Science and Systems VII

An Art Gallery Approach to Ensuring that Landmarks are Distinguishable

Lawrence Erickson, Steven LaValle

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 guardset $S \subset P$ is a set of points in a polygon $P$ such that for all $p \in P$, there exists an $s \in S$ such that $s$ and $p$ are mutually visible. Suppose that two members of a finite guard set $S \subset 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, $\chi_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 $P_{spi}, \chi_G(P_{spi}) \leq 2$, and for any staircase polygon (strictly monotone orthogonal polygon) $P_{sta}, \chi_G(P_{sta}) \leq 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 $M_k$ with $ 3k^ 2$ vertices such that $\chi_G(M_k) \geq k$, and for any odd integer $k$, there exists an orthogonal polygon $ R _ k $ with $ 4k ^ 2 + 10k + 10$ vertices such that $ \ chi _ G(R _ k) \geq k$.

Download:

Bibtex:

  
@INPROCEEDINGS{Erickson-RSS-11, 
    AUTHOR    = {Lawrence Erickson AND Steven LaValle}, 
    TITLE     = {An Art Gallery Approach to Ensuring that Landmarks are Distinguishable}, 
    BOOKTITLE = {Proceedings of Robotics: Science and Systems}, 
    YEAR      = {2011}, 
    ADDRESS   = {Los Angeles, CA, USA}, 
    MONTH     = {June},
    DOI       = {10.15607/RSS.2011.VII.011} 
}