Navigation is of major importance for autonomous agents. Any truly autonomous agent must be capable of relocating to important places in its environment by its own means, i.e., its sensors and actuators. Traditional approaches to the navigation problem are based on the concept of a world model, and start with the assumption that accurate maps are the necessary and sufficient means for robust and reliable navigation. All instantiations of this approach suffer from several problems. First, they require enormous computational and memory resources. Second they fail to act in real-time. Third, they make inappropriate assumptions about the availability of information about the environment. And fourth, they lack the robustness required in the real world.
The shift in paradigm, from symbol-processing AI to ``Embodied AI'', also affect the navigation strategies. The main focus has been shifted from accurate, metric representations of the environment to topological maps, that only code for ``important places'' in the environment and relate these places by notions of order, proximity, or instructions for the transition between them.
This idea is very appealing, since it eliminates the problem of dealing with movement uncertainty in mobile agents. The new approach regards homing as the basic navigation ability. The main problem now, is in finding robust, reliable and simple strategies that will enable the agent to navigate between important locations in the environment. A very promising direction for solving this problem is in looking at the navigation strategies employed by biological agents.
Biological agents are impressive navigators. Especially ants and bees are able to carry out incredible navigational tasks, despite their tiny bodies and their limited computational and memory resources. A desert ant, for example, can return home unfailingly after searching for food in places hundreds of meters away, and a honeybee can home reliably after flying to a food source located several kilometers away. A number of experiments performed with insects have unraveled important properties of the navigation strategies that they use. It is known, for example, that ants and bees use skylight patterns as a compass to determine the direction in which they travel. Bees measure how far they have traveled by integrating, over time, the image motion (optical flow) that they experience. Ants measure distance traveled by similar means, as well as through counting steps (proprioception). By continously monitoring compass and distance information, an insect searching for food is able to keep track of the distance and direction to its nest. In addition to this path integration mechanism, insects use visual landmarks.
Landmarks play an important role in guiding the insect home very precisely when it is near its goal. Recent experimental work is beginning to unravel details about the visual landmark navigation strategies of bees and ants.
The main objective of this research is to explore the potential of employing biological findings for the design of autonomous agents. While doing that, we will not only gain a better understanding of how these strategies are employed by natural agents, but we will also be able to build agents capable of robust navigation in real-world conditions.
My working hypothesis is that an accurate model of the environment isn't necessary to achieve robust navigation when the ability of the agent to interact with its environment, i.e., by simply moving, is explored. Rather than starting from the traditional AI assumption about the necessity of a world model and focusing on the construction of accurate maps, we focus on parsimonious mechanisms for navigation that are thought to be employed by natural agents. The two main navigational strategies I investigate are path integration employing a skylight compass and visual homing by using landmark information.
For path integration to work, both directional (compass) and distance information must be available. Of main importance is compass information, since the precision of the compass has an important influence on the precision of path integration. Traditionally, path-integration has been done by mainly relying on either to proprioception (wheel encoders) or inertial navigation systems. Both methods suffer from non-systematic drifts either as a function of distance covered or as a function of time that makes the application of these methods problematic for long distance navigation.
Visual homing has attracted a lot of attention recently. In contrast to the often used map-based methods, it doesn't require a detailed description of the environment. In its basic form, this method requires that the agent stores some information about the appearance of the visual scene at the vicinity of an important location and when it wants to visit this location again it compares what it currently sees with the stored information in order to derive the direction it has to move.
Long range navigation: Coupled mechanisms for path-integration and visual piloting can be used for long range navigation. Initial experiments in experimental setups with artificial landmarks suggest that a combination of such mechanisms is enough to guide the agent to the target location. The system can be based on the snapshot model where multiple ``snapshots'' could be used to connect different locations in the environment. This method can be used for navigation in both outdoor as well as in office environments.
This research proposes a multidisciplinary approach (see figure) involving the fields of AI, robotics and biology to meet the following specific objectives:
1. A biorobotic agent capable of skylight navigation. This includes, designing and implementing a polarization vision system in hardware, embedding this system in a mobile robot, and testing alternative models for extracting compass information from the polarization pattern of the sky (polarized light compass). The final goal is to integrate the polarized light compass in a path integration system that will be used in complex navigation tasks.
2. Visual landmark navigation. The task is to provide a systematic study of models for visual landmark navigation (e.g. snapshot model), that will help us to identify their limitations and propose solutions to cope with these limitations. The resulting model will be implemented in an autonomous agent equipped with panoramic, insect-like vision and will be tested in the field. The final goal is to provide a new, more parsimonious model of visual landmark navigation.
3. A design and an implementation of an agent architecture that incorporates means for adaptivity and integration of the various navigation strategies. Adaptivity is of major importance, since the agents will have to cope with dynamically changing real-world conditions. Integration of the various strategies will be an important step towards a complete agent.
4. A set of general principles for the design of navigating agents. The exploration of the navigation strategies is very important for developing concepts about navigation mechanisms in general and exploring their potential applicability in industrial/planetary-exploration settings.
The main concept underlying this approach is the use of multiple, simple navigation strategies, that are employed in parallel, instead of relying on a single one. This is in contrast with traditional AI approaches that are based on a central representation of the environment.