Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Data structure to store a map while doing it with SLAM

I'm studying robotics at the university and I have to implement on my own SLAM algorithm. To do it I will use ROS Melodic, Gazebo 9.1.0 and C++.

I have a doubt about what data structure I have to use to store the map (and what I'm going to store it, but this is another story).

I have thought to represent the map as a 2D grid and robot's start location is (0,0). But I don't know where exactly is the robot on the world that I have to map. It could be at the top left corner, at the middle of the world, or in any other unknonw location inside the world.

Each cell of the grid will be 1x1 meters. I will use a laser to know where are the obstacles. Using current robot's location, I will set to 1 on all the cells that represent an obstacle. For example, it laser detects an obstacle at 2 meters in front of the robot, I will set to 1 the cell at (0,2).

Using a vector, or a 2D matrix, here is a problem, because, vector and matrices indices start at 0, and there could be more room behind the robot to map. And that room will have an obstacle at (-1,-3).

On this data structure, I will need to store the cells that have an obstacle and the cells that I know they are free.

Which kind of data structure will I have to use?


The process to store the map will be the following:

  1. Robot starts at (0,0) cell. It will detect the obstacles and store them in the map.
  2. Robot moves to (1,0) cell. And again, detect and store the obstacles in the map.
  3. Continue moving to free cells and storing the obstacles it founds.

the robot will detect the obstacles that are in front of him and to the sides, but never behind it.

My problem comes when the robot detects an obstacle on a negative cell (like (0,-1). I don't know how to store that obstacle if I have previously stored only the obstacle on "positive" cells. So, maybe the "offset", it is not a solution here (or maybe I'm wrong).