An algorithm question about SLAM

edit

Frankly speaking, I think you have to read a whole lot more to get a better idea of the problem.

A couple links from amazon (in no particular order: just easily spotted and cheap) Introduction-Autonomous-Mobile-Intelligent-Robotics

FastSLAM-Scalable-Simultaneous-Localization-Robotics

Now onto your specific question. Every entity that has no navigate an environment has to accomplish multiple tasks:

• path finding
• obstacle avoidance
• map construction
• localization

PATH FINDING

There are a number of algorithms (from the well known A* and D* to the most esoteric ones) but these all depend on the way you represent the navigation map (which may be different from say the real-time map, or the obstacle map: you may have different resolution maps for different tasks).

The simplest theory is this: your map is a connected graph, the algorithm tries to find the shortest path between two nodes. This way the hardest part, the one that determines where a node effectively is, is moved outside the path planning and into the map construction.

The key point here being what and where is a node. The amount of nodes heavily depends on the algorithm for the path planning: some algorithms have very short expansions (meaning they wander very short distances from nodes, trying to stay near them) so you need lots of nodes to cover the environment (grid maps are often used here), other algorithms have much wider expansions, so you can have fewer nodes representing the area (voronoi expansions and medial axis can be used when you can wander far from nodes).

OBSTACLE AVOIDANCE

The task of avoiding obstacles may be complicated ad-libitum. Meaning you can go from bumpers (like the first Roombas) up to multiple stereo-cameras and laser range finders (like the autonomous cars developed by Google or for the Darpa Urban Challenge <-check it out!)

For most applications a laser ranger (Hokuyo and SICK are the most famous manufacturers) is the default choice: such a sensor gives you a distance reading across a circular sector up to 270°, with resolutions up to 0.25°, at frequencies up 40Hz and distances up 80 m.

The key point though is how you process your data. In fact you have to decide how you categorize an obstacle -meaning how you determine what sequence of data is effectively an obstacle, and what properties an obstacle can have- and after that how this categorization affects the path planning and/or map building.

The simplest (but still working) obstacle avoidance is the VFH(+ or *) method: this is the simplest method still doing some kind of data coalescence. Otherwise an even simpler method would be: get as far away from the nearest obstacle.

More sophisticated methods involve determining some characteristics of the obstacle (like dimensions, shape, orientation) and placing it in the map, to allow the planner to plan a path around the obstacle. But again this depends on the kind and resolution of the map: for example if your planning algorithm runs on a low resolution grid map, you may even not put obstacles in ... (more)