Large-Scale Near-Optimal Decentralised Information Gathering with Multiple Mobile Robots
Timothy Patten, Robert Fitch, Salah Sukkarieh · UTS ePRESS (University of Technology Sydney) · 2013
Information gathering at large spatial scales can be addressed with teams of decentralised robots. Many existing methods search over a limited time horizon and do not provide strong performance guarantees. Near-optimal methods that exploit submodular objective functions have been proposed, given a fixed time budget. We propose a revised problem formulation that seeks to near-optimally maximise information gain quickly. We present a novel, near-optimal polynomial-time decentralised algorithm for multiple robots and analyse the expected path length with respect to the number of robots, the size of the area, and the number of observations. Our approach is based on area partitioning and is practically beneficial in that it allows for superlinear speedup in the time required to maximise the submodular objective function, is decentralised, and is easy to implement. We show extensive simulation results that compare the performance of our algorithm to existing sequential allocation methods.