Navigation problem

The Navigation Problem is one of the unsolved problems of computer science and robotics. The problem is in creating an algorithm that would be able to find its way around a room, or a maze - dealing with obstacles that may be in the way.

Origins of the problem

The problem stems from the fact that algorithm design is solution oriented, and since the way to the target may be blocked, there is no guarantee that a solution exists, and therefore it would be impossible to create a general algorithm let alone prove its universal validity.

Interesting alternatives to solving the problem are suggested by the following, if only obliquely. The main thrust is that coping, or "muddling through" would be the solution to the Navigation problem. However, this solution cannot be proved to work. As such, it may be considered a heuristic.

• Hubert Dreyfus
• Being and Time
• Coping
• Navigation research

External links

• Neural Information Processing Systems
• Jacob T. Schwartz and Micha Sharir, Algorithmic Motion Planning in Robotics, Handbook of theoretical computer science (ed. J. van Leeuwen), Elsevier, 1990, pp. 391-430.
• Many articles referred by http://citeseer.ifi.unizh.ch/context/52914/0
  • http://citeseer.ifi.unizh.ch/impacttaskforce96application.html
  • http://citeseer.ifi.unizh.ch/155925.html
  • http://citeseer.ifi.unizh.ch/164761.html
  • http://citeseer.ifi.unizh.ch/259432.html
  • http://citeseer.ifi.unizh.ch/albers97exploring.html
  • http://citeseer.ifi.unizh.ch/rao93robot.html
  • http://citeseer.ifi.unizh.ch/475748.html
• http://citeseer.ist.psu.edu/208930.html
• http://www.ics.forth.gr/~foka/phd.html
• Robot Navigation in Unknown Terrains: Introductory Survey of Non-Heuristic Algorithms (1993)
• Motion Planning for Car-like Robots using a Probabilistic Learning Approach (1995)
• A search to continue:
• Another search to continue
• A bibliography

See also

Motion planning - These two arcitles (the one just mentioned and the one you are reading) may need merging!