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.