DP-SLAM
Austin Eliazar and Ronald Parr


Welcome to the DP-SLAM web page. DP-SLAM aims to achieve truly simultaneous localization and mapping without landmarks. While DP-SLAM is compatible with techniques that correct maps when a loop is closed, we have found that DP-SLAM is accurate enough that no special loop closing techniques are required in most cases.   DP-SLAM makes only a single pass over the sensor data.

DP-SLAM works by maintaining a joint probability distribution over maps and robot poses using a particle filter. This allows DP-SLAM to maintain uncertainty about the map over multiple time steps until ambiguities can be resolved. This prevents errors in the map from accumulating over time.

More about DP-SLAM:



How DP-SLAM Works

DP-SLAM uses a particle filter to maintain a joint probability distribution over maps and robot positions.  This would be expensive without some clever data structures since it would require a complete copy of the entire occupancy grid for every particle, and would require making copies of the maps during the resampling phase of the particle filter.  The figure below conceptually shows an ancestry of particles and map updates, with leaves of the ancestry tree pointing to maps.  (Think of each red dot in the ancestry tree as a sampled robot position and the black lines around the red dot as the new observations associated with the current robot position.  The gray lines show piece of the map inherited from the previous particle.)


Notice that all maps in this example will agree with the initial observation.  The two leftmost maps will agree on the observations made by the left child of the root, while the two rightmost maps will agree with the observations made by the right child of the root.  It would be a waste of memory and time to store and repeatedly copy these map sections every time a particle is resampled.  Instead, we use a single occupancy grid which stores an observation tree at each square.  As shown below, each particle inserts its observations into the global grid.  These are stored as a balanced tree, indexed on a unique ID assigned to each particle.

The computer science part of the DP-SLAM project involves the algorithms and analysis to show that these data structures can be maintained efficiently.  Please see the documents section for more details. 

Documents

The original DP-SLAM paper (DP-SLAM 1.0) was presented at IJCAI 03 and was based upon an assumption that the environment behaved deterministically with respect to the robot's laser range finder.  The original paper is available here.

Since the original paper was published, we have improved our algorithm and our analysis.  We also developed a novel model of how the laser penetrates space, which enables us to achieve a more robust algorithm that produces maps of extraordinary accuracy using probabilistic occupancy.  We refer to these improvements together as  DP-SLAM 2.0.

Our latest development with DP-SLAM now permits run time that is linear in all relevant parameters of the problem.  For P particles and area A swept out by the laser, the run time is O(AP) per iteration of the particle filter.  This is the same complexity per particle as pure localization!  We have also implemented a hierarchical approach that combats drift in our particle filter.  Our NIPS 05 paper on these improvements is available.

Austin Eliazar's doctoral dissertation is now available.

Sample Output

We have run DP-SLAM on two building environments.  The first is from the second floor the Duke University Computer Science Department, i.e., the second floor of the D-Wing of the LSRC building.  The second is from a long stretch of the second floor of the C-Wing of LSRC (pharmacology).   Clicking on the maps below will bring you to a web page with detailed on the performance of DP-SLAM (both versions) in each domain. We include results with different algorithm parameters and log files.

The maps shown below are at a tiny fraction of the actual map resolution.  Please click on the maps to see the full resolution, highly detailed versions.



D Wing
(Click for Details)
C Wing
(Click for Details)


Dieter Fox and Dirk Haehnel were kind enough to provide us with a quite large data set from Wean hall at CMU.  This one actually contains several loops, only one of which is show in our draft paper.



 
Wean Hall
(Click for Details)



Code 

We are pleased to make a version 0.1.1 release of the DP-SLAM code available to the research community.  This version has been developed and tested under Linux.  It can be used "live" on an iRobot with a laser range finder.  Otherwise, it can be used to process a log file.  It should be fairly straightforward to modify this code to work with log files in different formats or to operate "live" on different platforms.

Please note that your use of this code is subject to the following conditions
This Program is provided by Duke University and the authors as a service to the research community. It is provided without cost or restrictions, except for the User's acknowledgment that the Program is provided on an "As Is" basis and User understands that Duke University and the authors make no express or implied warranty of any kind.  Duke University and the authors specifically disclaim any implied warranty or merchantability or fitness for a particular purpose, and make no representations or warranties that the Program will not infringe the intellectual property rights of others. The User agrees to indemnify and hold harmless Duke University and the authors from and against any and all liability arising out of User's use of the Program.

If you agree to these conditions, you may download: dpslam0.1.1.tar.gz

Old Version:  dpslam0.1.tar.gz


Acknowledgments

We are grateful for the support of the National Science Foundation, the Alfred P. Sloan Foundation, and SAIC for this project.