For quite a number of years, researchers from various fields have studied problems motivated by Robot Navigation. On the theoretical side, a robot is faced with a number of algorithmic issues that are geometric in nature. This includes mapping a given environment, searching all possible locations in such an environment, or localizing the robot’s position on a given map; typically, available information is visibility-based, but motion-planning may also require the computation of a collison-free trajectory for a rigid body, if one exists. These geometric aspects are pursued in the field of Computational Geometry, where quite a bit of expertise has been developed, including deep results on visibility problems and motion planning.

Another crucial feature of robot navigation is that path-planning has to be performed without full knowledge of all necessary data; such information only becomes available during the course of the robot’s motion, requiring optmization with incomplete information. Complete knowledge of the scenario only becomes known after a strategy has been actually been applied. This means that in addition to the geometric issues described above, an algorithm has to protect against various possibilities (including faulty sensors or inaccurate data), instead of basing its decisions on a complete description of the tasks ahead. Problems of this type are studied in the field of Online Algorithms.

On the other hand, computer scientists and engineers from the field of Robotics who work with real robots have made tremendous progress in developing systems that can perform a multitude of practical tasks. These technical posibilities give rise to a number of scenarios that have been studied in theory for a number of years. Thus, practitioners can benefit from the expertise of theoreticians. On the other hand, actual real-world scenarios tend to impose requirements that are more or less different from the ones previously considered in theory; moreover, some novel capabilities give rise to additional theoretical questions that pose new and exciting challenges.

As the possibilities and the need for real breakthroughs increase, the demand and opportunities for close interaction between practitioners and theoreticians grows. This became apparent in the Open Problems Session which saw a very lively debate on how interaction between theory and practice is seen by the various communities and how it might be improved. The central question seemed to be what is the best or correct way to model real robots such that theorectical results become meaningful for practitioners.

A predecessor workshop took place December 7 to 12, 2003. An excellent example of a successful interaction between theoreticians and practitioners is the direct result of this workshop: The video “Searching with an autonomous robot” (available at the website http://videos.compgeom.org/socg04video/) is based on discussions between the theoreticians S´andor Fekete (TU Braunschweig) and Rolf Klein (Universit¨at Bonn), and the practitioner Andreas N¨uchter (Fraunhofer Institute for Autonomous Intelligent Systems), who met at this Dagstuhl workshop. Using the specifications of an existing autonomous robot, a new strategy was developed for optimally locating an object hidden behind a corner. Currently, further work on broad extensions of this scenario is in the planning, showing that theory meeting practive can lead to real breakthroughs. This fruitful contact has only become possible by the previous Dagstuhl workshop on Robot Navigation.

The workshop in 2006 brought together 31 researchers from 9 different countries. The 25 presentations, varying in length, covered a large variety of topics, including selected results from online algorithms, search problems and search games, self-localization, motion and path planning, mapping, and swarm navigation. Talks were spread over the week to allow for plenty of time for discussions between the talks, thus giving participants a chance to exchange problems and ideas. We are positive that many of them will lead to new results and publications.

As usual, Schloß 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.