Visibility analysis of landmark-based navigation

This thesis introduces and examines the chromatic art gallery problem. The chromatic art gallery problem asks for the minimum number of landmark classes required to ensure that every point in an input polygon sees at least one landmark but sees no more than one landmark of any particular class. The problem is motivated by partially distinguishable landmark-based navigation. A robot that navigates by landmarks must ensure that it always has one in view, or else it might reach a configuration where it has no bearings to use any of its motion primitives. Additionally, if the robot reaches a position where it can see two landmarks of the same class, its motion primitives become ambiguous. Because the number of landmark classes available for navigation is dependent on the discriminatory power of the robot's sensors, the chromatic art gallery problem relates the complexity of an environment to the sensors required to visually navigate in the environment. Existing research has generally not addressed this issue. This thesis provides upper and lower bounds on the number of landmark classes required for various types of polygons as a function of the number of polygon vertices and demonstrates the NP-hardness of determining whether 5 or more classes is necessary for an input polygon. Bounds and NP-hardness results are also given for a variant of the chromatic art gallery problem in which the visibility graph of the landmarks is required to be connected. The chromatic art gallery problem can be phrased in terms of a landmark placement problem combined with a graph coloring problem. The landmarks are placed such that each point in the polygon is visible from a landmark, and the restrictions on shared classes between landmarks is represented by a conflict graph. The vertex set of the conflict graph is the set of landmarks; two graph vertices are joined by an edge if the corresponding landmarks are visible from a common point. The goal is to find a set of landmarks that have a conflict graph with a minimal chromatic number. This thesis explores the structural properties of the conflict graphs by describing three necessary conditions for conflict graphs. Additional restrictions are determined for conflict graphs that arise in specific types of polygons. Beyond their use for the chromatic art gallery problem, these structural results are useful for error checking in surveillance algorithms.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Erickson, Lawrence

Contributors dc:contributor

• LaValle, Steven M.
• Erickson, Jeff G.
• Hoiem, Derek W.
• Isler, Volkan

• Robotics
• Art Gallery
• Visibility

Statement dc:rights

• Copyright 2014 Lawrence Erickson

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/49473

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/49473