Masters - Map Building with Mobile Robots

My masters is concerned with map building in sonar based robots. I am working with the Pioneer mobile robot, using the Saphira architecture, in the Computer Systems department of the University of Limerick, Ireland. The masters was begun in October 2001, and was completed in September 2003

To see my thesis in Microsoft Word format, click here .

To see my thesis in Adobe Acrobat format, click here .

Below are four papers I participated in authoring, two as primary author, which were presented at the proceedings of the 9th International Symposium on Artificial Life and Robotics (AROB) 2004, in Oita, Japan.

Linear Feature Prediction for Confidence Estimation of Sonar Readings in Map Building
A Quantitive evaluation of sonar models and mathematical update methods for Map Building with mobile robots
Developing a Benchmarking Framework for Map Building Paradigms
Developing a Statistical Baseline for Robot Pursuit and Evasion using a Real World Control Architecture

Also, I co-authored one paper presented at the 18th Australian Joint Conference on Artificial Intelligence

Benchmarking Sonar Based Occupancy Grid Mapping Techniques

Download a video of the robot in motion here .

Get a complete picture of the Star world environment described in my thesis here .

 

Sonar Data Files

I've made all my sonar data files available in a Zip file here. The file format is a custom one I've created. A C++ class for parsing this file format is included in the zip file here, as well as a PDF tutorial on how to use the file. Some of the sonar data files may be duplicated in that zip file.

All of these sonar data files can be processed by MapViewer to create maps.

The sonar data files have a specific naming scheme

Generated Maps

As an example of some of the maps created by my robots in various environments, using different sonar models and update procedures, here are some of the maps generated by my map building systems.

These maps are viewable using a Windows application I wrote, called Map Viewer, currently on version 1.5 which you can get here .

A newer version of the Map Viewer, version 1.6 Beta is now also available. This has better support for larger maps, and handles zooming in and out much better. It can also animate the creation of a path between two points, as well as allowing the user to customise how the path is generated. This is a Beta release, so may be slightly buggy. You can get it here . 

The latest release of Map Viewer, version 2.2, is far more advanced than all of the previous releases, with much more functionality and vastly improved usability.  It's development journal is located here .   .

Just unzip the map file, and open it with the Map Viewer application.

Click on the link in the MAP column to get the hand drawn ideal map for the relevant environment.

Map Real World or Simulated? Update Method Used Sonar Model Independant Information? Feature Prediction? File
AIC Simulated Bayesian Liklihood Ratio 2D Normal Distribution No No k97mod_sim_aic4_noErr_noPoseBuckets_noSpec.zip
AIC Simulated Bayesian Liklihood Ratio 2D Normal Distribution No Yes k97mod_sim_aic4_noErr_noPoseBuckets_Spec.zip
AIC Simulated Bayesian Liklihood Ratio 2D Normal Distribution Yes No k97mod_sim_aic4_noError_PoseBuckets_noSpec.zip
AIC Simulated Bayesian Liklihood Ratio 2D Normal Distribution Yes Yes k97mod_sim_aic4_noErr_Spec_poseBuckets.zip
Computer Science Building Simulated Bayesian 2D gaussian No No me88mod_sim_CSIS1stFloor1_noError_noPoseBuckets_noSpec.zip
Computer Science Building Simulated Bayesian 2D gaussian No Yes me88mod_sim_CSIS1stFloor1_noError_Spec_noPoseBuckets.zip
Computer Science Building Simulated Bayesian 2D gaussian Yes No me88mod_sim_CSIS1stFloor1_noError_PoseBuckets_noSpec.zip
Computer Science Building Simulated Bayesian 2D gaussian Yes Yes me88mod_sim_CSIS1stFloor1_noError_Spec_PoseBuckets.zip
Computer Science Building Real World Ad Hoc 2D gaussian No No me85_real_CSIS1stFloor_1.zip
Computer Science Building Real World Bayesian 2D gaussian No No me88_real_CSIS1stFloor_1.zip
Computer Science Building Real World Bayesian Liklihood Ratio 2D Normal Distribution Yes No k97_real_CSIS1stFloor_1_poseBuckets.zip
Computer Science Building Real World Bayesian Liklihood Ratio 2D Normal Distribution Yes Yes k97mod_real_CSIS1stFloor_1_poseBuckets_Spec.zip
Star World Real World Ad Hoc 2D gaussian No No me85_real_star1.zip
Star World Real World Ad Hoc 2D gaussian No Yes me85mod_real_star1_NoPoseBuckets_Spec.zip
Star World Real World Ad Hoc 2D gaussian Yes Yes me85mod_real_star1_poseBuckets_Spec.zip
Star World Real World Bayesian 2D gaussian No No me88_real_star1.zip
Star World Real World Bayesian 2D gaussian No Yes me88mod_real_star1_NoPoseBuckets_Spec.zip
Star World Real World Bayesian 2D gaussian Yes Yes me88mod_real_star1_poseBuckets_Spec.zip
Star World Real World Bayesian Liklihood Ratio 2D Normal Distribution Yes No k97_real_star1_poseBuckets.zip
Star World Real World Bayesian Liklihood Ratio 2D Normal Distribution Yes No k97mod_real_star1_poseBuckets_Spec.zip

 

Path Planning with the Map Viewer Application

The Map Viewer application also has a path planning mode, which can plan paths in a map using a highly modified version of the A-Star algorithm. To use this mode, click on the "To Path Mode" button.

 

Displaying a robot's path using the Map Viewer Application

The Map Viewer application has a third mode, RobotRun, which can be used to display the path taken by a robot. Either the entire path can be displayed, or it can be animated to show the the robot moving. The information about a run is stored in a file with the extension .run. This can be useful for such applications as displaying the path a robot took for a particular test run, or showing the results of a pursuit-and-evasion contest between two or more robots. Another interesting application is to display a complete game of robot soccer, for example the type used in the RoboCup competition.

These files are not compatible with MapViewer 2.x, only with versions up to 1.6b.

Each record in the file, stored in a simple text format, looks as follows:

Xposition Yposition AngleFacing

The X and Y values are stored in millimetres, with the AngleFacing (the direction the robot is facing) being stored in degrees. Currently the angle is not used in the program, but may be in future releases.

Each record in a .RUN file is considered to be the robot's position at a certain timestep, so each record represents a single timestep. Since frequent updates of the robot's position are generally required for real-time robot control (in my case 10 refreshes per second), the application can animate the run at a variety of speeds, with the default being 50 timesteps per second, which for me means 5 times normal speed. This can be changed using the "Timesteps/Sec" button.

Up to 25 simultaneous robot runs can be loaded at any one time, though they might become less clear when displaying the complete path, since they will ofthen overlap. When animating the robot run, it becomes much clearer, even with many robot runs loaded. Below are some example RobotRun files, for use with the Computer Science Building and AIC maps, though robot runs can be displayed with or without a map in the background (unlike the paths in the Path mode, which must be generated using a map).

File Map To Be Used With (Optional)
AIC_robot_runs.zip AIC
CSIS_robot_runs.zip Computer Science Building

 

Generating Voronoi Diagrams

Since the 1.6b release of MapViewer I've improved the Voronoi Diagram generation algorithm - it now runs much, much faster, and is more accurate. It is included in release 2.x of MapViewer. The algorithm is a modified version of Stephan Fortune's sweep line algorithm. Stephan very kindly put his algorithm on his website in C code. However, this merely printed information to the screen, and also suffers from severe memory leak issues. I've fixed these up, and encapsulated the code in a class, VoronoiDiagramGenerator. The two files are VoronoiDiagramGenerator.h and VoronoiDiagramGenerator.cpp.
Using the class is very simple. There are 3 public methods,

bool generateVoronoi(float *xValues, float *yValues, int numPoints, float minX, float maxX, float minY, float maxY, float minDist=0); This takes two float arrays with the occupied points in the map. Obviously enough, xValues[0] corresponds to yValues[0], and so on. numPoints specifies the size of the two arrays - the 2 arrays must of course be the same size. minX, minY, maxX, maxY specifies the bounding box around the map, so that any lines with less than 2 end points are clipped instead of extending to infinity, and are pretty self explanatory. minDist specifies the minimum distance that must be between two occupied points for an edge between them to be accepted. This is required, since the voronoi algorithm doesn't see occupied points as grid cells - just as infinitely small points. Therefore, if this is set to 0 it will place edges between adjacent occupied cells - note that this is the correct behaviour for pure voronoi algorithms. If you set it to sqrt(8) + 0.1 , then you'll be guaranteed that there will be at least one unoccupied cell between two cells since the distance between points (0,0) and (2,2) is sqrt(8).

void resetIterator()This must be called before you start iterating through the edges - it makes the internal pointer point to the head of the list.

bool getNext(float& x1, float& y1, float& x2, float& y2)This gets the next edge. The four parameters are passed by reference and are overwritten. The method returns true if an edge was returned, false if you've reached the end of the list.

A sample usage is provided in the file voronoi_main.cpp