"Both of them were perfectly familiar with
the inner structure of all settlements.
Ei knew as well as Jo, where to find those rooms from
the corridor leading to the recharger module which are equal to
the substance of Leonardo. The passageway going there
opens at the fourtieth meter of the corridor.
But this corridor here was less than ten meters long. Jo felt that
contradictions surpass his resistivity."
Robots having human-like or exceeded intelligence feel at home on the pages of science fiction books. Reality is far from that, although we heard many times in the last couple of decades that in the near future robots will take up remarkable part of our tasks.
Where are these intelligent structures, who are not necessarily smarter than us, but are still able to execute monotone, fatiguing, easily solvable duties? When machines will do the cleaning, the ironing, the repairing, or drive cars instead of humans?
The frequently heard answer since the sixties mentions ten years, but this date have not been reached yet. The problem is multifold. Among the tasks are worth mentioning the creation of fast processors, efficient energy supplies, the elaboration of movement patterns comparable in quality to evolved human behaviour complex but not obviously in a human-like manner, image processing, cognition of the environment, acceptable fast learning capability, efficient and harmless problem solving, probably speech recognition, and processing of natural languages. This article focuses on one unavoidable property of these future intelligent mobile robots, the property of navigation, explaining the relevant difficulties of the subject.
Imagine that you are left in the middle of an unknown city with a pencil and a piece of paper without a city map and the task of getting acquainted with the environment. Walking around you note the relation of buildings to you and to each other. You attempt to attach your position to the starting point and the already known map elements. That is to say coordinates of the elements of the map depend on your position, and you position yourselves with the usage of the map, you navigate. A robot has to cope with this kind of chicken-egg problem, what results a fairly exact map only after a long period of time.
Beyond simultaneous localization and mapping (SLAM), as it is called in the literature, other problems also arise.
Reflection of the environment perceived by your sensors is not exactly accurate and you make mistake in your motion as well. Or else you could tell the distance of a house precisely at first glance and you would never stumble. The same applies to robots: radars, cameras can be mistaken, bumpy terrain or even the edge of a carpet may cause troubles. This fact naturally renders more difficult the building of maps. Furthermore measurement errors accumulate, so after travelling long distances without a reference point position estimation diverges seriously. Mounting GPS to every robot would be costly though. Figure 3 shows how the map of a closed-loop corridor in the size of 20x60 meters is biased by the accumulating noise.
Another problem stems from high dimensionality of the environment. We, humans naturally use information genetically wired into us, or gathered in the learning process of maturation: sensations are assembled to a consistent system, otherwise elements of the environment can be transformed to houses, cars, trees, fences. Furthermore the purpose of these objects and relations among them are well-known what still can aid the development of the map.
So robots have to be prepared in a human programming process to convert the few million color pixels of a video camera to more complex structures helping navigation. For instance Figure 4 shows an ordinary room, and Figure 5 indicates a robot interpreted image of the same room, a three-dimensional occupancy map of the environment.
For fruitful navigation accurate map is unavoidable. Increasing the resolution means a growth of computational demand. Furthermore growth can be exponential with a topological map, where relations among objects are stored.
If, for the sake of efficiency, the robot uses only scarce information then it could run into the problem of data association. This trouble may arise when the robot cannot determine if two places - probably from different viewpoints - are equal. For example walking around in circular corridor it is hard to find the starting point.
Successful everyday robots have to surmount to another important obstacle. Their working field continuously changes: people are walking around, rooms are altering, nature is evolving. These transformations have to be mirrored on the map, that is to say time is a new dimension of the solution.
If a robot can deal with all the above mentioned problems, we still have not reached the niveau presented in the science fiction literature. A universal robot must work in real time, efficiently, without harm, in general, probably unknown environment.
The level of research and technology can be characterized by two famous events of the year. NASA Mars robots performed very well after their landing, but with the aid of an army of researchers, which means that the condition of autonomous task solving is completed only partially. Another interesting, yet less successful experiment was the DARPA Grand Challenge in Mojave desert, where self-supporting robots had to travel 150 miles in 10 hours for 1 million dollars. The best performing vehicle from Pittsburg University had to give up at 5% of the track going off course and having a wheel caught fire.
It is clear that described problems have not been solved yet at an acceptable level even with tremendous effort to supersed human work. Accordingly we have to take out the dustbin for a while.
Article content copyright © Richard Szabo, 2004.
All content copyright © 1998-2007, Generation5 unless otherwise noted.