Robotics/Navigation/Mapping

To find routes efficiently a robot has to know it's surroundings. Maps can be very handy for this. Either the robot has the memory and tools for it and draws its own map, gets its map in advance or get a partial map (e.g. only walls) and adds the other obstacles to it itself.

• Getting the map in advance works fine in a static environment.
• The partial map is a more efficient approach as it already contains all the static parts of the world.
• Working from scratch is the best approach when the robot is often placed in new environments.

Drawing a map has 2 major issues:

• Not all elements in the surroundings are stationary. Most sensors are too limited to measure directly if the obstacle is a wall, a chair or a person. A method for solving this issue is to use a "score" for each obstacle measured. Add to the score if the object is detected again when the robot passes the same location.
• Localization isn't perfect. Small accumulating errors can make it hard to determine the exact location of the robot and therefor can make it hard to find where a detected obstacle has to be noted on the map. One solution to this problem is Simultaneous Localization and Mapping (SLAM), which corrects the location of detected objects based on the estimated error of the robots location.

A third minor issue is memory. On a robot build without a computer memory is limited and storing an entire map can be next to impossible. If you have the memory the map can be stored in different ways:

• 2D array: Easy and fast to access, very wasteful with memory.
• linked list: slower to use, more efficient with memory.
• Quadtree: faster than linked list, much harder to implement, very efficient with memory.

Implementing these structures on a PC is reasonably easy, however constructing them in a limited environment as a microcontroller is a serious challenge.