Mecanismo de leilão descentralizado para atribuição de tarefas colaborativas em um sistemas multirrobô

Abstract

Multi-Robot Systems are receiving considerable attention during the last years due their efficiency in solving complex problems through task sharing and collaborative assignments. This class of systems have several different applications, ranging from daily to critical and highrisk activities, for example search and rescue of survivors in natural disaster scenarios and site vigilance. The efficiency of such systems relies on the quality of the task allocation among the agents. This works presents the development of a market-inspired solution by applying an auction mechanism to solve the multi-robot task allocation problem. The proposed system considers that each task requires one or more robot’s skills in order to be complete. Since each robot can only have one single skill, the robots must form coalitions to complete tasks that require multiple skills. The system is fully distributed and decentralized. The computation processing required to coordinate an auction is distributed among the robots in turns, in which each robot should perform an auction in its turn. The calculation for the bidding values is performed upon a set of factors that weight the importance of some characteristics of the system, such as task allocation and distance to the auctioned resource. The proposed system is verified through simulations in partially unknown search and rescue scenarios, where each robot is also equipped with sensing, mapping, frontier-based exploration, mission planning, navigation control and deviation mechanisms. The results are split in two parts. The first part isolates the auction mechanism to evaluate its performance by changing the number of robots, collaborative and individual tasks in two distinct scenarios. The second part validates the system as a whole, by integrating the auction mechanism with the remaining mechanisms. The results show that the performance is satisfactory, allowing the robots to cooperate in solving the task allocation problem. It is also indicated that the system performance can be configurable regarding some predefined constants that can be chosen. Lastly, the results also suggest that the proposed auction mechanism is scalable. However, further testing is required to confirm the scalability of the system.

Multi-Robot Systems are receiving considerable attention during the last years due their efficiency in solving complex problems through task sharing and collaborative assignments. This class of systems have several different applications, ranging from daily to critical and highrisk activities, for example search and rescue of survivors in natural disaster scenarios and site vigilance. The efficiency of such systems relies on the quality of the task allocation among the agents. This works presents the development of a market-inspired solution by applying an auction mechanism to solve the multi-robot task allocation problem. The proposed system considers that each task requires one or more robot’s skills in order to be complete. Since each robot can only have one single skill, the robots must form coalitions to complete tasks that require multiple skills. The system is fully distributed and decentralized. The computation processing required to coordinate an auction is distributed among the robots in turns, in which each robot should perform an auction in its turn. The calculation for the bidding values is performed upon a set of factors that weight the importance of some characteristics of the system, such as task allocation and distance to the auctioned resource. The proposed system is verified through simulations in partially unknown search and rescue scenarios, where each robot is also equipped with sensing, mapping, frontier-based exploration, mission planning, navigation control and deviation mechanisms. The results are split in two parts. The first part isolates the auction mechanism to evaluate its performance by changing the number of robots, collaborative and individual tasks in two distinct scenarios. The second part validates the system as a whole, by integrating the auction mechanism with the remaining mechanisms. The results show that the performance is satisfactory, allowing the robots to cooperate in solving the task allocation problem. It is also indicated that the system performance can be configurable regarding some predefined constants that can be chosen. Lastly, the results also suggest that the proposed auction mechanism is scalable. However, further testing is required to confirm the scalability of the system.