Localisation and Map Building Questions

This is a good step.

The items below are not definative, but they are from my reading and thoughts on the subject.

I can think of a couple of ways, the efficiency of each depends on the environment.

1. Wall following: follow the walls building the map that way until you've got the walls mapped out, then venture into the center.
2. Wallbanging (my personal favorite): go until you have to avoid an obstacle. Then go off in a random direction. Keep a timestamp on each location so that if you are in a givne area too long, you use a different algorithm to get you out of there.
3. Longest distance: find the longest distance the robot can travel. Go that way addihg to the map. When you stop at a wall or other obstacle, recalculate the longest distance again, avoiding the previous path.

#1 should get you the outline first, #2 is better at the center, and #3 is probably best for environments with few obstacles.

If you are using an occupancy grid, then when the grid has been sufficiently built and the outline is all done, then the map has been created.

You may want to look at David Lee's book: _The Map-Building and Exploration Strategies of a Simple Sonar-Equipped Mobile Robot_

He discusses a number of algorithms and how well they work for him.

-- D. Jay Newman

1) flood fill (lees algorithm) searching for unexplored cells. When you find an unexplored cell in your search, you back track through the flood to find your robot in the grid. You then follow the steps it required to get to robot (in reverse order). These steps will be "n,s,e,w, ne, nw, se, sw" so you need to send these steps to a subroutine which will follow those steps, IE turn in the correct direction, and then travel the distance that a cell in your occupancy grid represents.

google keyboards: "occupancy grid" "moravec"

2) localization: search in surrounding cells in X radius from robots location. find out what percent have been unexplored. If this percent is low (IE, most have been explored) then you can go to your "localize" subroutine.

as you move your robot, you increase the diameter of a circle surrounding the robot. This represents the possible locations of the robot due to error in your encoders. "the robot could be anywhere in this circle"

The cells in the grid are the cells you test in your localization software. compare a current sonar scan (local occupancy grid) to the data in the robots map (global occupancy grid.) You overlay the grids and count the matches. Cycle through all cells in the "possible locations circle" and store the number of matches between global/local for each cell in that circle.

When you are done testing each cell in the circle, you pick the cell that has the highest number of matches between global/local grids. This is where your robot is at according to localization software.

I have tons of drawings, graphics, charts, diagrams, psuedo code, and step by step explanation on how to explore, "normalize" sonar data, and localize your robot that I created while I was coding my software.

Rich