Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Innerhalb dieser Seite:
Externe Seiten:
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp

Dagstuhl-Seminar 03501

Robot Navigation

( 07. Dec – 12. Dec, 2003 )

(zum Vergrößern in der Bildmitte klicken)

Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:


  • Searching with an autonomous robot - Fekete, Sandor, P.; Klein, Rolf; Nüchter, Andreas - University : 2004. - CD-ROM.


Autonomous robots are supposed to perform well, even without complete information about their environment. Frequently occurring subtasks include

  • to search an environment for a goal,
  • to explore an unknown environment, and
  • to determine their own position, given a map.

Depending on the type of the robot's sensors, and on its a priori knowledge about the environment or the position of the target, these - and other - tasks give rise to a variety of on-line navigation problems.

A solution for a problem P consists of a strategy S that solves correctly all instances of P. It is called competitive with factor c if it solves each instance p of P at a cost not bigger than c times the cost of solving p optimally (for example, we would compare the length of the robot's path from the start to the goal against the length of the shortest such path that exists in the given environment).

Given a navigation problem P, two questions arise. Can P be solved by a competitive strategy with a constant factor c? And, if so, what is the competitive complexity of problem P, that is, the smallest possible factor c? These questions are mostly of theoretical nature. They can be studied independently of the more technical problems in robotics, like systems design, fusion of sensor data, or dealing with inaccuracies. But we hold that gaining a better understanding of these navigation problems is not only an interesting theoretical challenge; it might also provide solid ground work for the development of future robots.

Due to their particular nature, on-line navigation problems have been studied independently by researchers in three scientific communities: by some more theoretically-oriented electrical engineers in robotics, by people in on-line analysis, and by computational geometers. This is reflected by the corresponding Dagstuhl seminars. But in none of these seminars have on-line navigation problems received the attention they deserve. In this seminar, we brought together leading experts of all three groups. We reviewed and discussed the state of the art, and we tried to identify important problems of common interest.

25 researchers with affiliations in Canada (3), Germany (9), Hong Kong (2), Israel (3), the Netherlands (4), Slovenia (1), and the USA (3) participated in the meeting. Seven participants were graduate students or postdocs. Four keynote speakers, Rudolf Fleischer, Vladimir Lumelsky, David Mount, and Mark Overmars, gave one-hour survey talks. The remaining 19 presentations given by participants of the meeting covered a wide range of topics, ranging from robot path planning, search and exploration problems, to algorithmic issues in practical robotics. In an evening session we discussed important open problems.

As usual, Schloss Dagstuhl proved to be an excellent place to hold a great meeting, so we would not only like to thank the participants of the seminar for making this a very successful event but also the Dagstuhl staff for providing a friendly and stimulating working environment.

  • Andrej Brodnik (University of Primorska, SI) [dblp]
  • Wolfram Burgard (Universität Freiburg, DE) [dblp]
  • Sándor Fekete (TU Braunschweig, DE) [dblp]
  • Rudolf Fleischer (Fudan University - Shanghai, CN) [dblp]
  • Yoav Gabriely (Technion - Haifa, IL)
  • Shmuel Gal (Haifa University, IL)
  • Roland Geraerts (Utrecht University, NL) [dblp]
  • Frank Hoffmann (FU Berlin, DE)
  • Christian Icking (FernUniversität in Hagen, DE)
  • Arno Kamphuis (Utrecht University, NL)
  • Rolf Klein (Universität Bonn, DE) [dblp]
  • Klaus Kriegel (FU Berlin, DE)
  • Elmar Langetepe (Universität Bonn, DE)
  • Alejandro Lopez-Ortiz (University of Waterloo, CA) [dblp]
  • Vladimir J. Lumelsky (University of Wisconsin - Madison, US)
  • David M. Mount (University of Maryland - College Park, US) [dblp]
  • Ian Munro (University of Waterloo, CA) [dblp]
  • Hartmut Noltemeier (Universität Würzburg, DE)
  • Andreas Nüchter (Universität Osnabrück, DE)
  • Mark Overmars (Utrecht University, NL)
  • Kirk Pruhs (University of Pittsburgh, US) [dblp]
  • Elon Rimon (Technion - Haifa, IL)
  • Jörg-Rüdiger Sack (Carleton University - Ottawa, CA) [dblp]
  • Gerhard Trippen (HKUST - Kowloon, HK)
  • Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]

Verwandte Seminare
  • Dagstuhl-Seminar 06421: Robot Navigation (2006-10-15 - 2006-10-20) (Details)