This page contains source code, videos, and experimental data for our publications on incrementally updatable distance maps, Voronoi diagrams, and C-space obstacle maps.

Publications

B. Lau, C. Sprunk, and W. Burgard
Efficient Grid-Based Spatial Representations for Robot Navigation in Dynamic Environments
Robotics and Autonomous Systems, 61 (10), 2013, pp. 1116-1130, Elsevier

B. Lau, C. Sprunk, and W. Burgard
Incremental Updates of Configuration Space Representations for Non-Circular Mobile Robots with 2D, 2.5D, or 3D Obstacle Models
European Conference on Mobile Robotics (ECMR), Örebro, Sweden, 2011

B. Lau, C. Sprunk, and W. Burgard
Improved Updating of Euclidean Distance Maps and Voronoi Diagrams
IEEE International Conference on Intelligent RObots and Systems (IROS), Taipei, Taiwan, 2010

Key Properties

• Efficient algorithms to update distance maps and Voronoi diagrams (IROS 2010)
• Efficient algorithms to update configuration space obstacle maps (ECMR 2011)
• Combination of both methods to compute c-space distance maps and Voronoi diagrams (ECMR 2011)
• Extension to 3D distance maps (RAS 2012, to appear)
• All methods consider true Euclidean distances rather than step counts
• Voronoi lines are thin and well connected
• 4-connected Voronoi diagrams to prevent erroneous connections
• More details in the papers...

Open-source library / ROS package

• C++ library, no 3rd-party libraries required
• BSD licence, but please cite our paper if you use it in scientific publications
• Download stand-alone library at spatialrepresentations_r638.zip

Experimental data (2D only)

• Logs (for dynamic environments): FR079 FR101
• Maps (initialization for dynamic environments): FR079 FR101 Factory
• Logs (for SLAM): intel_labs fr_campus

Progression of Wavefronts During the Updates