ICRA 2011 Paper Abstract


Paper TuP210.2

Erickson, Lawrence H (University of Illinois at Urbana-Champaign), LaValle, Steven M (University of Illinois)

How Many Landmark Colors Are Needed to Avoid Confusion in a Polygon?

Scheduled for presentation during the Regular Sessions "Localization and Mapping IV" (TuP210), Tuesday, May 10, 2011, 15:40−15:55, Room 5E

2011 IEEE International Conference on Robotics and Automation, May 9-13, 2011, Shanghai International Conference Center, Shanghai, China

This information is tentative and subject to change. Compiled on March 30, 2020

Keywords Autonomous Navigation, Surveillance Systems, Mapping


Suppose that two members of a finite point guard set S within a polygon P must be given different colors if their visible regions overlap, and that every point in P is visible from some point in S. The chromatic art gallery problem asks for the minimum number of colors required to color any guard set (not necessarily a minimal guard set) of P.

We study two related problems. First, given a polygon P and a guard set S of P, can the members of S be efficiently and optimally colored so that no two members of S that have overlapping visibility regions have the same color? Second, given a polygon P and a set of candidate guard locations N, is it possible to efficiently and optimally choose the guard set S from N that requires the the minimum number of colors? We provide an algorithm that solves the first question in polynomial time, and demonstrate the NP-hardness of the second question. Both questions are motivated by common robot tasks such as mapping and surveillance.



Technical Content © IEEE Robotics & Automation Society

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2020 PaperCept, Inc.
Page generated 2020-03-30  00:21:19 PST  Terms of use