Robovis, 2005
The Robovis project was developed as a final project for Scientific Visualization and Virtual Reality lectures at the University of Amsterdam, Netherlands.
The following text is a part of the final report, available for download.
Introduction
During the last years robotics experiences its new boom. Autonomous mobile robots are getting to our everyday lives. From vacuum cleaners through grass cutters to fully autonomous car-like vehicles (DARPA Grand Challenge by U. S. Army, ELROB by German Bundeswehr).
These robots may either simply react to the environment, as in case of simple vacuum cleaners, or they can be provided with, or build itself, a map. In the second case it is crucial for the robot to know, where it is. Due to imperfection of the sensors and the inaccurate movement of the robot, errors in position prediction and/or calculation can accumulate quite easily and dangerously.
This is the point where Mr. Dieter Fox from University of Germany introduced the Markov probabilistic approach. It has been, however, observed, that the suggested technique is too computationally expensive and cannot be used for on-line navigation in the real environment.
The improvement in the form of the Monte Carlo localization (MCL) was suggested soon afterwards at Carnegie Mellon University and University of Bonn.
Both ideas are based on the fact, that the robot's position calculation may be based only on the previous position and the performed movement. It is not dependent on the situations more in the past. This is so called Markov assumption.
Both algorithms consists of two phases:
- prediction
- correction
During the prediction phase the probabilistic distribution for being at any point is changed according to the performed movement. Because it is known, that the robot has inaccurate actuators, this update has a form of Gaussian distribution.
During the correction phase the distribution is corrected according to the actual sensory input. Again the Gaussian noise on the sensors is expected.
The importance of the visualization
The Monte Carlo localization uses thousands of samples, that are moved and filtered according to the probabilistic movement and sensory model.
Because the Monte Carlo localization was introduced very soon after the original Markov localization, the visualization of the complete grid did not have a time to be developed.
Thanks to the samples nature of MCL the only visualization technique that is widely used is drawing the samples in the map.
Such an approach requires from the user to extract the probability from the density of the points by himself. This is not only highly inaccurate, but it may also be almost impossible, when there is a small area with too many occluding samples.
It also lacks the support for visualization of the probability distribution over the direction. And obviously the direction of the robot is a vital part of the robot navigation.
Video description
As one of the results of the project the video (divx5 codec) was obtained.
The simulated environment is the playground of the Eurobot 2006 international robotic competition. The holes in the ground are omitted.
There is a robot, almost transparent brown box, moving on the playground. For its localization it uses three distance sensors, displayed as light blue lines (left forward, forward, right forward). They are simulated as sensors with gaussian noise with the variance of 20% of the real distance to the obstacle (so they are almost useless for longer distances).
The robot calculates the probability distribution not only over the position, but also over the direction. Both in discrete value, but this is nicely hidden by the visualization.
The most striking shape is the red hill. It displays the probability of positions. The higher the probability, the higher and more red the hill.
The probabilities of directions are visualized by the rain cloud. These are the dark blue lines above the red hill. They start above the point of the ground, they belong to, point in the direction, they talk about, and their length is proportional to the probability of this direction.