Optimizing Coalition Formation Strategies for Scalable Multi-Robot Task Allocation: A Comprehensive Survey of Methods and Mechanisms

摘要

In practical applications, the utilization of multi-robot systems (MRS) is extensive and spans various domains such as search and rescue operations, mining operations, agricultural tasks, and warehouse management. The surge in demand for MRS has prompted extensive exploration of Multi-Robot Task Allocation (MRTA). Researchers have devised a range of methodologies to tackle MRTA problems, aiming to achieve optimal solutions, yet there remains room for further enhancements in this field. Among the complex challenges in MRTA, the identification of an optimal coalition formation (CF) solution stands out as one of the (Nondeterministic Polynomial) NP-hard problems. CF pertains to the effective coordination and grouping of agents or robots for efficient task execution, achieved through optimal task allocation. In this context, this paper delivers a succinct overview of dynamic task allocation and CF strategies. It conducts a comprehensive examination of diverse strategies employed for MRTA. The analysis encompasses the advantages, disadvantages, and comparative assessments of these strategies with a focus on CF. Furthermore, this study introduces a novel classification system for prominent task allocation methods and compares these methods with simulation analysis. The fidelity and effectiveness of the proposed CF approach are substantiated through comparative assessments and simulation studies.