07. – 12. Dezember 2003, Dagstuhl Seminar 03501

Robot Navigation


Rudolf Fleischer (Fudan University – Shanghai, CN)
Rolf Klein (Universität Bonn, DE)
Alejandro Lopez-Ortiz (University of Waterloo, CA)

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team


Dagstuhl's Impact: Dokumente verfügbar


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.

Related Dagstuhl Seminar


Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.