# How does a robot efficiently store a map it makes?

From what I understand, you can create a map using sensors and storing values in an array. For example, the array can have 0's for places not visited, and 1's for places visited, or 0's for open spaces and 1's for occupied spaces, etc.

The map I'm thinking of making will have about 1000 x 2000 members. This means I need an array of 2 million members. That seems like a lot. If I have eight attributes about each member (like temperature, light level, sound level, etc.), then I have 16 million pieces of information to capture.

Is this correct, or is there a better way to create a map for a robot using software?

• Consider packing your data. Don't use a whole byte/word for something that doesn’t need it. Those 0 and 1 can be packed 8 to a byte - quite a saving. Temperature - realistically, no more range than -10 to +40 C . A range or 50 can be packed into 6 bits (you might get it down to 5). How many light levels? You can probably get away with only a few bits. There will be a minor performance hit, but bit bit-wise & shift operations are usually efficient. Alternatively, you can just add a multi-gB SSD – Mawg says reinstate Monica Apr 21 '15 at 6:43

It really really depends on the kind of map. If you want a map that is a 2-D grid of boolean values, then it depends on how sparse the map is expected to be.

If you want to keep all boolean values, you would need at least N * M * S bits (assuming the map is N by M and each location has S sensor readings), which for your numbers translate to ~2MB of data. If your microcontroller doesn't have this much space, then that's a bad approach.

However, all is not lost! Usually the environment has some feature you can take advantage of. For example, if the environment is not full of obstacles, you don't need to memorize all the empty spaces, right? Or if there is an area closed by obstacles, you don't to keep track of what's inside it, since you can't get there anyway.

That said, perhaps the approach with the least amount of memory would be to model your environment by a set of closed polygons. As you explore the world, you refine the polygons, but not with extreme details, to reduce the memory footprint. All algorithms would then work with polygons (e.g. collision detection) rather than bitmaps which is possibly also less costly, so it could be a win for everyone!

This Wikipedia article may help, where topological frameworks are hinted at, and the thereby linked Map Database Management which could also provide some insight.

• Do you know of any examples showing how a polygon-based map is stored? Is this also stored in an array? – Alligator May 19 '14 at 15:34
• I don't know of any particular implementation you could use. But effectively it could be a set of points, stored in array if you want, or a Quad tree or any other data structure based on your usage, and a set of lists of indices to those points, showing a closed polygon traversed in anticlockwise for example. – Shahbaz May 19 '14 at 16:06

The world is always bigger than the robot's memory can hold (it's bigger than your memory can hold, too).

There are 2 ways to reduce the space that you need. The first is to consider whether you need to pre-allocate the storage space, and the second is to consider what kind of compression you can use.

Pre-allocating space makes sense if you already have values for those 8 attributes at every square, or if the robot's job is to visit all 2 million squares and measure them. However, if the robot is just going to visit a small portion of the total squares then you might be able to store the data in something like a quadtree instead. (There are many other structures that take advantage of sparse data sets, and I won't list them here.)

Compression can help if you can't avoid pre-allocating the space. For example, you could store the state of visited squares as bits instead of bytes to get 8:1 compression with minimal effort. For the attributes of the spaces, do you need exact values? Can you exploit patterns in the data to save on storage space (think of GIF, JPEG, and other 2D compression schemes).

Look at papers and projects at universities on how others have done this. Unfortunately most of this is not as transferable from robot to robot as one would initially imagine. There is a lot that will be custom to your robot.

That being said, here's what I did...

What I was doing for mine was a graph of 1" squares representing the room.
To "fill in" a square I incremented the value of it by 1. To "clear" it I decremented it by 2, to min of 0. I then filled in squares as IR and Ultrasonic detectors detected them. I cleared them as the squares would be seen to be clear. This handled transient obstacles OK, but it walked about as the sensors and their precision did not match the grid well.

This also depends as Shahbaz stated on resources for storage/processing power, etc.

• Good method but the question is about how to store the data. So in your case, which data type is used to store the squares? – Demetris May 20 '14 at 22:08
• Sorry, I got busy and hadn't got back... I used a signed byte for each point. – Matt M Jun 3 '14 at 18:46

Are you just using a microcontroller? Do you have the option of strapping a laptop to it?

I use Octomap to store my robot's maps (with the robotic operating system): http://octomap.github.io/

It is the best method I have found to store rich robot sensory data in an efficient way. There is a good PDF explaining how it works:

www.first-mm.eu/files/hornung13auro.pdf

I'm pretty sure you could apply the same principles to a raw embedded robot.

Since the robot is unlikely to visit all the locations you have a sparse data set that you can most simply store in a hash table. You would have to think of a good way of hashing the x and y locations together. You need a function hash(x,y) and feed that into a hash table.