Adaptive Task Completion System for Multiple Robots under Task Quantity Variation

Abstract

With the change of population structure, integrating the robotic systems into logistics, healthcare, caregiving, and search-and-rescue operations has become an inevitable trend. This research develops a multi-robot adaptive task allocation and path finding system to address dynamic pickup-and-delivery problem in complex environment, considering both robot capacity and heterogeneity in capabilities. In contrast to other techniques without considering the dynamic task allocation, the proposed IAACO algorithm that is built on a two-layer framework claims high-quality solutions in rapid response to unpredicted task quantity variation. The first layer integrates methods of maximum weight matching, Voronoi Diagram classification and local optimization, to compute real-time allocation results in response to dynamic task changes. The second layer occurs in the task execution process, during which the system simultaneously employs an adaptive ant colony optimization algorithm for further optimization. Additionally, to provide the cost estimation during task assignment for each robot, this work also introduces the multi-robot path finding solved by the modified space-time A ${}^{*}$ to the system. In simulations, it is shown that IAACO improves the makespan and the total path length by up to 36% and 21% respectively, compared to the baseline algorithms. Finally, the experimental results are also delivered to validate the feasibility of the proposed methodology.