# Localisation and Map Building Questions

• posted

All, I've got my map modelling program working great, with guided help from me, and with the robot tracing around the boundary of the room (I'm controlling it) it makes a really good map of the environment. However...

That's not really much good as I was to be able to switch it on and send it off to make a map for itself. Which leads me onto these problems:

1) How should the robot move when building the map/what method are there for moving a robot in this phase? 2) How will it know when the map is sufficiently built and then prehaps revert to a localisation/map update algrothim.

The only vague lead I have is Lee's Algorithm, which I haven't been able to find out much about, most likely because I'm not typing in the right questions in the search engines. There's a lot of talk of using it, but not so much on how it's use/the algrothim itself.

Any techniques/references would be most useful, not just Lee's Alg but anything else which addresses the same issues.

Thanks

Mark

• posted

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

• posted

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.

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

PolyTech Forum website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.