Multi Robot Exploration and Task Allocation through a Two-layer Architecture and Genetic Algorithm

Multi-robot systems are preferable for tasks that are inherently distributed in space, time, or functionality. For the problems that can be decomposed into independent subproblems, using a multi-robot system offers a potential for reducing the overall task completion time. For effective employment of multi robot systems, it is necessary to properly implement Task Allocation, which is an NP-hard problem. In this paper, a two-layer architecture for exploring and covering an unknown environment by multiple heterogeneous robots is developed. At the first layer of the architecture, the Multi-SRT algorithm is developed for exploration and covering of the environment and the Multi-Tangent-Bug is used for online path planning and obstacle avoidance in a distributed manner. In the second layer, by means of a centralized approach, a Fast Genetic Algorithm (FGA) is proposed for solving the multi-robot task allocation problem. Performing each task enhances the utility of the system, and completing all tasks is the ultimate goal of the system. For evaluating the efficiency of the FGA, a number of scenarios were run and the results were compared to NSGA-II algorithm. Simulation results showed the reliability of the developed architecture at the first layer and the precision and quality of the task allocation at the second layer.