At the forefront of Artificial Intelligence
  Home Articles Reviews Interviews JDK Glossary Features Discussion Search
Home » Articles » Robotics » Navigation

Difficulties of Robot Navigation

"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."
Péter Zsoldos: Counterpoint


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?

Qrio -- a hero of our time
Figure 1: Qrio — a hero of our time ([1])


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.

Navigation research environment
Figure 2: Navigation research environment ([2])


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.

Role of noise
Figure 3: Role of noise ([3])


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.

An experimental environment
Figure 4: An experimental environment ([4])
Robot perspective
Figure 5: Robot perspective ([4])


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.

A Grand Challenge contestant in trouble
Figure 6: A Grand Challenge contestant in trouble ([5])


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.

References

  1. http://www.androidworld.com/qrio1.jpeg
  2. Hanspeter A. Mallot and Matthias O. Franz and Bernhard Scholkopf and Heinrich H. Bulthoff. The View-Graph Approach to Visual Navigation and Spatial Memory. In ICANN, pages 751-756, 1997. url: citeseer.ist.psu.edu/mallot97viewgraph.html
  3. S. Thrun. Learning Metric-Topological Maps for Indoor Mobile Robot Navigation. Artificial Intelligence, 99(1): 21-71, 1998. url: citeseer.nj.nec.com/thrun98learning.html
  4. M. C. Martin: http://www.frc.ri.cmu.edu/~hpm/talks/ARPA.MARS.reports.00/Martin.Slides.0005
  5. T. Abate: http://www.sfgate.com/cgi-bin/article.cgi?f=/c/a/2004/03/14/ROBOT.TMP

Submitted: 08/08/2004

Article content copyright © Richard Szabo, 2004.
 Article Toolbar
Print
BibTeX entry

Search

Latest News
- The Latest (03/04/2012)
- Generation5 10-year Anniversary (03/09/2008)
- New Generation5 Design! (09/04/2007)
- Happy New Year 2007 (02/01/2007)
- Where has Generation5 Gone?! (04/11/2005)

What's New?
- Back-propagation using the Generation5 JDK (07/04/2008)
- Hough Transforms (02/01/2008)
- Kohonen-based Image Analysis using the Generation5 JDK (11/12/2007)
- Modelling Bacterium using the JDK (19/03/2007)
- Modelling Bacterium using the JDK (19/03/2007)


All content copyright © 1998-2007, Generation5 unless otherwise noted.
- Privacy Policy - Legal - Terms of Use -