December 7 – 12 , 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)

For support, please contact

Dagstuhl Service Team


List of Participants
Dagstuhl's Impact: Documents available


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


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.