Volume

Dagstuhl Seminar Proceedings, Volume 6421

Publication Details

  • published at: 2007-02-07
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.06421.1
06421 Abstracts Collection – Robot Navigation

Authors: Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz

Abstract
From 15.10.06 to 20.10.06, the Dagstuhl Seminar 06421 ``Robot Navigation''generate automatically was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz. 06421 Abstracts Collection – Robot Navigation. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.06421.1,
  author =	{Fekete, S\'{a}ndor and Fleischer, Rudolf and Klein, Rolf and Lopez-Ortiz, Alejandro},
  title =	{{06421 Abstracts Collection – Robot Navigation}},
  booktitle =	{Robot Navigation},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.1},
  URN =		{urn:nbn:de:0030-drops-8890},
  doi =		{10.4230/DagSemProc.06421.1},
  annote =	{Keywords: Motion planning, robotics, computational geometry, online algorithms}
}
Document
DOI: 10.4230/DagSemProc.06421.2
06421 Executive Summary – Robot Navigation

Authors: Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz

Abstract
For quite a number of years, researchers from various fields have studied problems motivated by Robot Navigation. People in Online Algorithms have developed strategies that can deal with the inherent lack of information an autonomous robot encounters, as it sets out to perform a task in an unknown environment. Computational Geometers have obtained many results on the efficient planning of collision-free motions, and on visibility problems. Scientists and engineers in Robotics have perfected real robots to an astounding degree. Economic household robots and artificial pets are now available; more complex robots are able to carry out difficult search-and-rescue and exploration missions. The goal of this seminar is to bring together researchers from robotics, computational geometry, and online algorithms, in order to exchange problems and ideas, and to jointly work towards solutions. The following questions seem crucial. Given the advanced level of technical development, what are the strategic planning problems researchers in robotics need to solve in the next decade? How can real environments and robots be modeled, so that planning problems become tractable by algorithmic methods, and solutions are still significant for applications? In particular, what can be assumed about perception and motion accuracy? We are planning for plenary sessions where members of all groups can present their problems and recent work. In addition, there will be plenty of time for discussions.
Cite as

Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz. 06421 Executive Summary – Robot Navigation. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.06421.2,
  author =	{Fekete, S\'{a}ndor and Fleischer, Rudolf and Klein, Rolf and Lopez-Ortiz, Alejandro},
  title =	{{06421 Executive Summary – Robot Navigation}},
  booktitle =	{Robot Navigation},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.2},
  URN =		{urn:nbn:de:0030-drops-8720},
  doi =		{10.4230/DagSemProc.06421.2},
  annote =	{Keywords: Motion planning, robotics, computational geometry, online algorithms}
}
Document
DOI: 10.4230/DagSemProc.06421.3
6D SLAM with Cached kd-tree Search

Authors: Andreas Nüchter, Kai Lingemann, and Joachim Hertzberg

Abstract
6D SLAM (Simultaneous Localization and Mapping) or 6D Concurrent Localization and Mapping of mobile robots considers six degrees of freedom for the robot pose, namely, the x, y and z coordinates and the roll, yaw and pitch angles. In previous work we presented our scan matching based 6D SLAM approach, where scan matching is based on the well known iterative closest point (ICP) algorithm [Besl 1992]. Efficient implementations of this algorithm are a result of a fast computation of closest points. The usual approach, i.e., using kd-trees is extended in this paper. We describe a novel search stategy, that leads to significant speed-ups. Our mapping system is real-time capable, i.e., 3D maps are computed using the resources of the used Kurt3D robotic hardware.
Cite as

Andreas Nüchter, Kai Lingemann, and Joachim Hertzberg. 6D SLAM with Cached kd-tree Search. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{nuchter_et_al:DagSemProc.06421.3,
  author =	{N\"{u}chter, Andreas and Lingemann, Kai and Hertzberg, Joachim},
  title =	{{6D SLAM with Cached kd-tree Search}},
  booktitle =	{Robot Navigation},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.3},
  URN =		{urn:nbn:de:0030-drops-8705},
  doi =		{10.4230/DagSemProc.06421.3},
  annote =	{Keywords: SLAM, kd tree search}
}
Document
DOI: 10.4230/DagSemProc.06421.4
Adaptive Analysis of On-line Algorithms

Authors: Reza Dorrigiv and Alejandro Lopez-Ortiz

Abstract
On-line algorithms are usually analyzed using competitive analysis, in which the performance of on-line algorithm on a sequence is normalized by the performance of the optimal on-line algorithm on that sequence. In this paper we introduce adaptive/cooperative analysis as an alternative general framework for the analysis of on-line algorithms. This model gives promising results when applied to two well known on-line problems, paging and list update. The idea is to normalize the performance of an on-line algorithm by a measure other than the performance of the on-line optimal algorithm OPT. We show that in many instances the perform of OPT on a sequence is a coarse approximation of the difficulty or complexity of a given input. Using a finer, more natural measure we can separate paging and list update algorithms which were otherwise undistinguishable under the classical model. This createas a performance hierarchy of algorithms which better reflects the intuitive relative strengths between them. Lastly, we show that, surprisingly, certain randomized algorithms which are superior to MTF in the classical model are not so in the adaptive case. This confirms that the ability of the on-line adaptive algorithm to ignore pathological worst cases can lead to algorithms that are more efficient in practice.
Cite as

Reza Dorrigiv and Alejandro Lopez-Ortiz. Adaptive Analysis of On-line Algorithms. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{dorrigiv_et_al:DagSemProc.06421.4,
  author =	{Dorrigiv, Reza and Lopez-Ortiz, Alejandro},
  title =	{{Adaptive Analysis of On-line Algorithms}},
  booktitle =	{Robot Navigation},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.4},
  URN =		{urn:nbn:de:0030-drops-8696},
  doi =		{10.4230/DagSemProc.06421.4},
  annote =	{Keywords: On-line algorithms, paging, adaptive/cooperative analysis}
}
Document
DOI: 10.4230/DagSemProc.06421.5
Competitive Online Searching for a Ray in the Plane

Authors: Andrea Eubeler, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, and Gerhard Trippen

Abstract
We consider the problem of a searcher that looks, for example, for a lost flashlight in a dusty environment. The searcher finds the flashlight as soon as it crosses the ray emanating from the flashlight. In order to pick it up, the searcher moves to the origin of the light beam. We compare the length of the path of the searcher to the shortest path to the goal. First, we give a search strategy for a special case of the ray search---the window shopper problem---, where the ray we are looking for is perpendicular to a known ray. Our strategy achieves a competitive factor of $1.059ldots$, which is optimal. Then, we consider rays in arbitrary position in the plane. We present an online strategy that achieves a factor of $22.513ldots$, and give a lower bound of $2pi,e=17.079ldots$.
Cite as

Andrea Eubeler, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, and Gerhard Trippen. Competitive Online Searching for a Ray in the Plane. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{eubeler_et_al:DagSemProc.06421.5,
  author =	{Eubeler, Andrea and Fleischer, Rudolf and Kamphans, Tom and Klein, Rolf and Langetepe, Elmar and Trippen, Gerhard},
  title =	{{Competitive Online Searching for a Ray in the Plane}},
  booktitle =	{Robot Navigation},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.5},
  URN =		{urn:nbn:de:0030-drops-8687},
  doi =		{10.4230/DagSemProc.06421.5},
  annote =	{Keywords: Online motion planning, competitive analysis, ray search}
}
Document
DOI: 10.4230/DagSemProc.06421.6
Computing Shortest Safe Path amidst Growing Discs in the Plane

Authors: Jur van den Berg and Mark Overmars

Abstract
In this paper we discuss the problem of planning safe paths amidst unpredictably moving obstacles in the plane. Given the initial positions and the maximal velocities of the moving obstacles, the regions that are possibly not collision-free are modeled by discs that grow over time. We present an approach to compute the shortest path between two points in the plane that avoids these growing discs. The generated paths are thus guaranteed to be collision-free with respect to the moving obstacles while being executed. We created a fast implementation that is capable of planning paths amidst many growing discs within milliseconds.
Cite as

Jur van den Berg and Mark Overmars. Computing Shortest Safe Path amidst Growing Discs in the Plane. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{vandenberg_et_al:DagSemProc.06421.6,
  author =	{van den Berg, Jur and Overmars, Mark},
  title =	{{Computing Shortest Safe Path amidst Growing Discs in the Plane}},
  booktitle =	{Robot Navigation},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.6},
  URN =		{urn:nbn:de:0030-drops-8733},
  doi =		{10.4230/DagSemProc.06421.6},
  annote =	{Keywords: Path planning dynamic environments}
}
Document
DOI: 10.4230/DagSemProc.06421.7
Extracting Visibility Information by Following Walls

Authors: Anna Yershova, Benjamin Tovar, and Steven M. LaValle

Abstract
This paper presents an analysis of a simple robot model, called Bitbot. The Bitbot has limited capabilities; it can reliably follow walls and sense a contact with a wall. Although the Bitbot does not have a range sensor or a camera, it is able to acquire visibility information from the environment, which is then used to solve a pursuit-evasion task. Our developments are centered on the characterization of the information the Bitbot acquires. At any given moment, due to the sensing uncertainty, the robot does not know the current state. In general, uncertainty in the state is one of the central issues in robotics; the Bitbot model serves as an example of how the notion of information space naturally handles uncertainty. We show that state estimation with the Bitbot is a challenging problem, related to the well-known open problem of characterizing visibility graphs in computational geometry. However, state estimation becomes unnecessary to the achievement of the Bitbot's visibility tasks. We show how pursuit-evasion strategy is derived from a careful manipulation with histories of observations, and present analysis of the algorithm and experimental results.
Cite as

Anna Yershova, Benjamin Tovar, and Steven M. LaValle. Extracting Visibility Information by Following Walls. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{yershova_et_al:DagSemProc.06421.7,
  author =	{Yershova, Anna and Tovar, Benjamin and LaValle, Steven M.},
  title =	{{Extracting Visibility Information by Following Walls}},
  booktitle =	{Robot Navigation},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.7},
  URN =		{urn:nbn:de:0030-drops-8678},
  doi =		{10.4230/DagSemProc.06421.7},
  annote =	{Keywords: Planning, localization, pursuit evasion, visibility}
}
Document
DOI: 10.4230/DagSemProc.06421.8
Polygon Exploration with Discrete Vision

Authors: Sándor Fekete and Christiane Schmidt

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.
Cite as

Sándor Fekete and Christiane Schmidt. Polygon Exploration with Discrete Vision. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.06421.8,
  author =	{Fekete, S\'{a}ndor and Schmidt, Christiane},
  title =	{{Polygon Exploration with Discrete Vision}},
  booktitle =	{Robot Navigation},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.8},
  URN =		{urn:nbn:de:0030-drops-8714},
  doi =		{10.4230/DagSemProc.06421.8},
  annote =	{Keywords: Searching, scan cost, visibility problems, watchman problems, online searching, competitive strategies, autonomous mobile robots.}
}

Filters

  • Authors
  • D
  • Dorrigiv, Reza
  • E
  • Eubeler, Andrea
  • F
  • Fekete, Sándor
  • Fleischer, Rudolf
  • H
  • Hertzberg, Joachim
  • K
  • Kamphans, Tom
  • Klein, Rolf
  • L
  • Langetepe, Elmar
  • LaValle, Steven M.
  • Lingemann, Kai
  • Lopez-Ortiz, Alejandro
  • N
  • Nüchter, Andreas
  • O
  • Overmars, Mark
  • S
  • Schmidt, Christiane
  • T
  • Tovar, Benjamin
  • Trippen, Gerhard
  • V
  • van den Berg, Jur
  • Y
  • Yershova, Anna

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact