Large scale simultaneous localization and mapping for teams of mobile robots
Localization and mapping are core requirements for teams of mobile robots to cooperate autonomously in everyday environments. From emergency search and rescue, to precision agriculture and space exploration, there are many applications where it is advantageous to deploy teams of robots without relying on external localization or a priori maps, and instead using on board sensors only. This problem, called Simultaneous Localization And Mapping (SLAM) has been well studied for individual robots. While many single robot SLAM solutions have been adapted to teams of robots, highly centralized architectures are typically proposed that fail to address real world problems such as intermittent and lossy communications, and particularly in the case of large scale deployments. For robust deployments of autonomous teams of robots, a decentralized multi robot SLAM (MR SLAM) solution is required; one that allows teams of robots to operate for extended periods independent of a central server by sharing SLAM data and performing loop closures on board. Several decentralized architectures have been described in the literature, however none have demonstrated MR SLAM with the mapping fidelity required for both indoor and outdoor deployments at large scales. State of the art large scale MR SLAM systems have demonstrated up to 15 robots exploring a 500x500meter urban environment at the 2010 Multi Autonomous Ground robotic International Challenge (MAGIC) While these systems were centralized, their Decoupled Centralized Architectures (DCA) allowed individual robots brief periods of limited autonomy. Without the ability to share SLAM data or close loops on board, however, architectures like DCA are unable to provide teams of robots with extended operations or high level autonomy independent of a central server. This thesis contributes in three areas: 1) The design of a MR SLAM architecture that combines a novel hybrid decentralized pose graph SLAM technique with a unique submapbased approach; this architecture distributes pose graph optimization and global map building across all robots, enabling decentralized teams to operate autonomously for extended periods. 2) Highly parallelized algorithms that enable efficient global occupancy gridmap fusion and efficient submap correlations that generate multimodal constraints; together these algorithms allow the proposed architecture to be realized on commodity hardware. 3) Continuous Mode Blending Optimization (COMBO) a novel technique that enables pose graphs with multimodal constraints to be optimized using traditional nonlinear least squares; this allows complex environments and effects such as perceptual aliasing to be modeled more accurately. These contributions have been demonstrated on line at the MAGIC challenge, and more recently with three merged challenge datasets replayed in real time these are the largest multi robot datasets described in the literature, with heterogeneous teams of 10, 14 and 23 robots exploring over 3.1 km, 6.1 km and 8.3 km of total odometry, respectively. Results include global occupancy gridmap fusion at over 20Hz, with globally referenced mapping accuracies of 0.27m, 0.62m and 0.35m, without using Global Positioning System (GPS) sensors. The proposed submapping technique compresses sensor data approximately 50 fold, reducing communications bandwidth requirements to averages of 1.2KB/s, 2.2KB/s and 2.4KB/s. Submap constraints with multimodal Gaussian distributions are generated in real time and desirable convergence properties are demonstrated using COMBO. The total computation, storage and communications requirements are shown to scale linearly, enabling future deployments orders of magnitude larger. By distributing the MR SLAM back end so that all robots are able to build their own copies of the global gridmap, the proposed architecture enables teams of robots to operate autonomously without continuous communications to a centralized server. This distributed approach is highly scalable, since each robot includes the computational resources it requires to process its own sensor data and maintain its own registration to the global pose graph. The proposed hybrid decentralized and distributed MR SLAM architecture provides robust localization and mapping capabilities for large scale deployments of autonomous robots in real world conditions. This approach enables many applications where teams of robots need to cooperate in GPS denied environments, with imperfect communications and without a priori maps.