| Multi-robot systems are expected to perform faster than their single-robot counterpart in different areas of robotics such as exploration, localization and mapping. For exploration, a faster task completion is only one of the advantages of using multi-robot systems. Among other benefits are better reliability, increased robustness and improved efficiency. Coordination of the movement of the robots is required in order to attain those benefits.;As such, a fundamental problem in multi-robot exploration is to know how the robots should coordinate their movements inside the environment in order to perform the exploration process either faster or more efficiently. In this work, we propose two coordination algorithms that address two of the constraints imposed on multi-robot systems: exploration time and total traversed distance. We characterize their behavior mathematically and find out their performance in time and distance.;We consider the situation of multiple robots exploring a structured environment, modeled as a graph, from a single starting vertex. The graph is initially unknown; the existence of edges becomes known only when a robot sees one end of the edge from a vertex, and the other end of the edge becomes known only when the robot actually follows that edge. This models an environment of sites with passages between them, where the passages are opaque: from either end it is not clear where the passage goes.;The mathematical analysis allows us to obtain the main properties of the algorithms and the bounds of the exploration time. In order to compare the efficiency of the algorithms in time and traversed distance, we derive three criteria of performance for multi-robot systems.;In the last part of this thesis we study the effects of the number of robots in the exploration process. Given the fact that the exploration time cannot be reduced indefinitely, even when the number of robots is increased infinitely, we perform an analysis in order to obtain the limit on the number of robots that produces the maximum reduction in the exploration time. |
