Fekete, Sándor ;
Schmidt, Christiane
Polygon Exploration with Discrete Vision
Abstract
With the advent of autonomous robots with two- and
three-dimensional scanning capabilities, classical visibility-based
exploration methods from computational geometry have gained in
practical importance. However, real-life laser scanning of useful
accuracy does not allow the robot to scan continuously while in
motion; instead, it has to stop each time it surveys its
environment. This requirement was studied by Fekete, Klein and
N"uchter for the subproblem of looking around a corner, but until
now has not been considered for whole polygonal regions.
We give the first comprehensive algorithmic study for this important
algorithmic problem that combines stationary art gallery-type
aspects with watchman-type issues in an online scenario. We show
that there is a lower bound of $Omega(sqrt{n})$ on the competitive
ratio in an orthogonal polygon with holes; we also demonstrate that
even for orthoconvex polygons, a competitive strategy can only be
achieved for limited aspect ratio $A$, i.e., for a given lower bound
on the size of an edge. Our main result is an $O(log
A)$-competitive strategy for simple rectilinear polygons, which is
best possible up to constants.
BibTeX - Entry
@InProceedings{fekete_et_al:DSP:2007:871,
author = {S{\'a}ndor Fekete and Christiane Schmidt},
title = {Polygon Exploration with Discrete Vision},
booktitle = {Robot Navigation},
year = {2007},
editor = {S{\'a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
number = {06421},
series = {Dagstuhl Seminar Proceedings},
ISSN = {1862-4405},
publisher = {Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2007/871},
annote = {Keywords: Searching, scan cost, visibility problems, watchman problems, online searching, competitive strategies, autonomous mobile robots.}
}
Keywords: |
|
Searching, scan cost, visibility problems, watchman problems, online searching, competitive strategies, autonomous mobile robots. |
Seminar: |
|
06421 - Robot Navigation
|
Issue date: |
|
2007 |
Date of publication: |
|
07.02.2007 |
07.02.2007