What algorithm can I use for constructing a map of an explored area using a number of ultrasound sensors?

Question

Ultrasound sensors are incredibly cheap these days which makes them a popular choice for many hobbyist robotic applications, and I'd like to use a bunch of them (say 10) around a robot with an algorithm to build a rough map of an area (as the robot explores it.) I'm not interested in dealing with moving objects at this stage, just pinpointing stationary ones, and I'll be using GPS for location. I realise that other components such as a laser scanner would produce much more accurate results, however such devices are also astronomically more expensive.

Does an algorithm exist for this purpose?

Answer 1

The algorithms are essentially the same regardless of what sensors you are using.

The real issue, which Chris touched upon, is that SLAM is hard even with very good sensors.

I would consider GPS, wheel odometry, and an IMU to be necessary to even attempt slam with ultrasound.

If you are just looking for cheap localization I recommend taking a look at vision/kinect based slam as well. Both webcams and the kinect are very cheap and visual slam has come a long way.

The kinect is pretty much the holy grail in terms of sensor performance/cost as long as you are indoors.

Here is an example of a kinect on a robot plus a lot of math: http://www.youtube.com/watch?v=9Y4RQVpp-BY

Answer 2

There is a whole area of literature on this topic. The most general idea is that of Simultaneous Localization and Mapping (SLAM), where the robot must build a map at the same time as it locating itself in that map. Depending on how accurate you want your maps to be, you can attempt a simpler problem of creating an occupancy grid map, which assumes you know the location of the robot.

In general, GPS is pretty horrible, so generating an occupancy grid just using GPS as your primary location source will generate pretty fuzzy maps. However, it is possible to integrate GPS with acceleration, gyroscopes, compasses, cameras, wheel encoders and other sensors to approximate a good position in the world. Otherwise, you will need to look into a simple SLAM system to handle your problems.

A nice open-source package g2o, for so-called GraphSLAM, allows you to put in constraints like GPS and relative position to walls. It may not be an exact fit, but it is pretty general.

Answer 3

To do SLAM, you will need a relatively good estimate of position.

Robots that use laser scanners can make do with just odometry, because the data is relatively accurate, and the scanner data can be used to help localize in subsequent time steps.

Ultrasound sensors are very fuzzy, they generally have a direction fuzziness of 20+ degrees, and anything in the general direction will be detected.

Thus, they are of negligible help in helping to localize (except in very structured environments).

A GPS/IMU combination can be used to get reasonable localization. Of course, this depends on the scale of the robot, and if it is indoors, GPS may not be practical.

If you are able to carefully control wheel slippage, wheel odometry can significantly improve localization in the short term (although an absolute method of localization is preferred). Without an absolute reference (eg. GPS), even with a laser scanner, you will need to be able to solve the problem of "closing the loop".

Structured environments may have a lower accuracy requirement. For example, a maze-like environment with walls at regular square grid distances, where it is simple to detect the presence of a wall in each direction of a grid cell.