Exact Solutions for the Chromatic Art Gallery Problem

• Grant number: 12/24993-6
• Support Opportunities: Scholarships in Brazil - Master
• Start date: May 01, 2013
• End date: October 31, 2014
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Pedro Jussieu de Rezende
• Grantee: Mauricio Jose de Oliveira Zambon
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated scholarship(s): 13/25104-3 - The chromatic art gallery problem, BE.EP.MS

Abstract

Consider an application where a mobile robot (such as an industrial operator, or a mobile agent on a secure area) find itself in an environment whose floorplan has a boundary described as a simple polygon (possibly with holes). With the objective of guiding the robot, landmarks (or visual emitters) may be placed in this environment so that the robot can distinguish between them and perform motion actions based in their locations. Possible motions include: move in the direction of a landmark, move away from a landmark or move around it. For the purpose of formulating this problem, consider that the landmarks, distinguishable only by their colors, as well as the robot, are idealized as (zero dimensional) points. A motion instruction for the robot is unfeasible if it does not see any landmarks and ambiguous if it sees two landmarks of the same color simultaneously. We say that a landmark covers a point of the environment if a robot is capable of seeing that landmark while placed at that point. In this way, given an environment description, it becomes necessary to determine the position of landmarks that guarantee the coverage of all points in the environment, so that it is possible to color those landmarks in a way that no point will be covered by two ndmarksks of the same color. Furthermore, its desirable that the number of colors used be minimal.An alternative way of describing this problem is in the context of Art Gallery problems, which have been widely studied in the computational geometry literature. Consider a simple polygon P (possibly with holes) and a finite set of points (guards) R, contanined in P, which covers P. Obviously, |R| colors are sufficient to color the points of R, so that no point of P will be covered by two guards of the same color. A coloring of R with this property is called a valid coloring. The search for a minimal valid coloring is justified, in the aforementioned application context, given that the fewer the colors the robot has to identify, the more precise the classification of the landmarks will be, since, depending on illumination conditions and the quality of the robot's sensors, the more similiar shades there are, the greater the chance of misclassifications.Many interesting questions may be raised; the simplest one being: given P and R, determine a coloring with the fewest number of colors sufficient to color R in a valid way. Even more interesting is the problem: given P and a finite set of points of G, determine a covering R, subset of G, for P that allows for a valid coloring of least cardinality among all possible coverings from G. The latter is called the Chromatic Art Gallery Problem - CAGP.The main objective of the present research project is to find an exact solution for the CAGP, as well as for some of its variations. Since this problem was introduced in the literature only recently (2011), its complexity is still unknown. While some lower and upper bounds for very restricted classes of polygons are known, no exact or approximation algorithm have yet been devised. It is our aim to attain an exact algorithm through Integer Linear Programming models. Moreover, we intend to develop heuristics for choosing sets of guard candidates, for a comparative study.

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

ZAMBON, Mauricio Jose de Oliveira. Exact solutions for the Chromatic Art Gallery Problem. 2014. Master's Dissertation - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.