Robotics: Science and Systems VII

An Art Gallery Approach to Ensuring that Landmarks are Distinguishable

Lawrence Erickson, Steven LaValle


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$.



    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}