Article details

Research area
Natural language & AI

Annals of Mathematics and Artificial Intelligence


Regis Vincent, Dieter Fox, Jonothan Ko, Kurt Konolige, Benson Limketkai, Benoit Morisset, Charles Ortiz, Dirk Schulz, Benjamin Stewart

Distributed multi-robot exploration, mapping, and task allocation


We present an integrated approach to multi-robot exploration, mapping and searching suitable for large teams of robots operating in unknown areas lacking an existing supporting communications infrastructure. We present a set of algorithms that have been both implemented and experimentally verified on teams–of what we refer to asĀ Centibots–consisting of as many as 100 robots. The results that we present involve search tasks that can be divided into a mapping stage in which robots must jointly explore a large unknown area with the goal of generating a consistent map from the fragment, a search stage in which robots are deployed within the environment in order to systematically search for an object of interest, and a protection phase in which robots are distributed to track any intruders in the search area. During the first stage, the robots actively seek to verify their relative locations in order to ensure consistency when combining data into shared maps; they must also coordinate their exploration strategies so as to maximize the efficiency of exploration. In the second and third stages, robots allocate search tasks among themselves; since tasks are not defined a priori, the robots first produce a topological graph of the area of interest and then generate a set of tasks that reflect spatial and communication constraints. Our system was evaluated under extremely realistic real-world conditions. An outside evaluation team found the system to be highly efficient and robust.

Read/download now