Fleet size of multi-robot systems for exploration of structured environments

The fleet size of a multi-robot system is an important parameter to be considered for real robotics applications since it will determine the cost and the time of execution of any given task. Unfortunately, it is a topic that has received little attention in the robotics literature. The study of the fleet size will allow for the design and implementation of more effective techniques and coordination methods for multi-robot systems. In this paper we study the effects of the fleet size on the time of exploration of a structured environment. We present an analysis that allows us to specify the maximum fleet size that provides the maximum reduction on the exploration time when the structured environment is modeled as a tree. The analysis is applied to the Multi-Robot Depth First Search (MR-DFS) algorithm that allows for maximum parallelism when an exploration process starts from a single point. The analysis provides an expression for the average time of exploration of a tree and for the maximum number of robots that produces a significant reduction on the exploration time.