TOWARDS A DISTRIBUTED SOLUTION TO MULTI-ROBOT TASK ALLOCATION PROBLEM WITH ENERGETIC AND SPATIOTEMPORAL CONSTRAINTS
This paper tackles the Multi-Robot Task Allocation problem. It consists of two distinct sets: a set of tasks (requiring resources), and a set of robots (offering resources). Then, the tasks are allocated to robots while optimizing a certain objective function subject to some constraints; e.g., allocating the maximum number of tasks, minimizing the distances traveled by the robots, etc. Previous works mainly optimized the temporal and spatial constraints, but no work focused on energetic constraints. Our main contribution is the introduction of energetic constraints on multi-robot task allocation problems. In addition, we propose an allocation method based on parallel distributed guided genetic algorithms and compare it to two state-of-the-art algorithms. The performed simulations and obtained results show the effectiveness and scalability of our solution, even in the case of a large number of robots and tasks. We believe that our contribution is applicable in many contemporary areas of research such as smart cities and related topics.
A multi-robot system (MRS) is a set of robots that are designed to communicate and cooperate with each other in order to achieve some common goals. In the last decades, MRSs have been used to solve many real-world problems such as smart security, the search and rescue of victims, environmental monitoring,and health-care. In an MRS, we usually face some challenging problems like task allocation, coalition formation, object detection and tracking, communication relay, and self-organization. In this paper, we deal with the task allocation problem. The Multi-Robot Task Allocation problem (MRTA) is informally defined as follows: “given two sets of robots and tasks, the purpose is to allocate tasks to robots while optimizing some criteria (i.e., objective function) under several constraints”. The problem is known to be N P-hard; solving it in an optimal way is a great challenge, especially when heterogeneous robots, complex tasks, and dynamic environments should be considered. In order to understand the MRTA problem, the following sections will give some useful defnitions.
We dealt with MRTA problems that considered spatial, temporal, and energetic constraints. A distributed solution based on parallel distributed guided genetic algorithms is proposed for allocating tasks to some group of robots. Six objective functions that express spatial temporal and energetic constraints have been proposed and extensively discussed. A well-known mathematical formulation of MRTA problems is modified, and two equations that express energetic constraints have been proposed and explained. Finally, we compared our solution to the two state-of-the-art solutions described in. The simulation result of our solution outperforms this pair of approaches in terms of completion time. In the case when we utilized ten robots, our solution improved the completion time of the two methods by 50 and 67%, respectively. In the future, we plan to use real robots to assess the performance of our solution.
American Journal of Computer Science and Engineering Survey