Distributed map-making and navigation in dynamic environments

Abstract

We present an implemented distributed map-making algorithm based on an online generation of an approximation to the generalized Voronoi graph of the robots' environment. Using sonar sensors, a team of mobile robots constructs maps which are topological and relatively sparse, and hence are well suited to basic path-planning approaches. The maps also contain metric data which could be used to detect changes in a dynamic environment automatically. The implementation addresses robot interactions that occur during mapping; the map merge algorithm is simple and uses a robust metric to produce reliable combined maps. A corresponding navigation algorithm which uses these maps has proven reliable in dynamic environments, i.e. when the world has changed since the map was made.