Occupancy grid rasterization in large environments for teams of robots

We introduce a method for efficiently rasterizing large occupancy grids. Efficient Maximum Likelihood Estimation (MLE) of robot trajectories has been shown to be highly scalable using sparse SLAM algorithms such as SqrtSAM, but unfortunately such approaches don't directly provide a rasterized grid map. We harness these existing SLAM methods to compute maximum likelihood (ML) robot trajectories and introduce a new efficient algorithm to rasterize a dynamic occupancy grid. We propose a spatially-aware data structure that enables the cost of a map update to be proportional to the impact of any loop closures, resulting in better average case performance than naive methods. Furthermore, we show how redundant sensor data can be exploited to improve map quality and speed up rasterization. We evaluate our method using several data sets collected using a team of 14 autonomous robots and show success in mixed indoor-outdoor urban environments as large as 220m × 170m, with 0.1m resolution.