ICRA 2011 Paper Abstract

Close

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

Abstract

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