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.
Also, I co-authored one paper presented at the
18th Australian Joint Conference on Artificial Intelligence
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
- If it starts with "sim", it is a simulated run, performed in the Saphira robotic simulator. E.g. sim_star_noError.run
- If it starts with "real" it was performed in the real world. E.g. real_star.run
The second part of the file name is the environment it was performed in. Four environments were
- The third optional part of the name is "noError", which if present states that all odometric errors were disabled for the test run. This is obviously only possible in a simulated environment.
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
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
. It also has it's own web site, which you can access
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
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
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)|
|CSIS_robot_runs.zip||Computer Science Building|
Generating Voronoi DiagramsSince 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 corresponds to yValues, 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