Multi-robot exploration in task allocation problem

Task allocation is an important problem in multi-robot system which can be defined with different setup for different application, i.e. coverage, surveillance and mining mission in static or dynamic scenarios. Our focus in this paper is exploring environment to accomplish tasks distributed over the environment by minimizing overall cost of the system. This problem is defined as a NP-Hard problem, thus will be more challenging in larger environments containing many robots and tasks. To solve multi-robot task allocation in very large environment we propose a new deployment-based framework. Our proposal divided the problem into two sub-problems: region partitioning and routing problem. This decomposition eases considering our problem specification in multi-robot system which are not easily considerable in other approaches, i.e distribution of the tasks or robots' initial position. Load balancing is done globally by deploying robots in a proper location of the environment and assigning sub-regions among them. Sub-regions contains set of points, where the goal is visiting all the points individually by one of the robots. On the other hand, after deploying the robots, routing techniques can be simply applied to find shortest and safest paths for every robots. To search for solutions in this NP-hard problem, two methods are built on a tailor-made multi-objective scheme of Genetic Algorithm (GA) with a different setup and search operators, and a reinforcement learning approach. Simulation results testify the performance of our methods in comparison to existing ones.

Automated summary

In this paper, a new deployment-based framework is proposed to solve the task allocation problem in a multi-robot system, which divides the problem into region partitioning and routing problems to achieve global load balancing and minimize system cost. Two methods based on a tailor-made multi-objective Genetic Algorithm and reinforcement learning approach are proposed to search for solutions in this NP-hard problem, with simulation results showing improved performance compared to existing methods.