Abstract
Multi-robot task allocation and coalition formation are critical challenges in robotics, essential for applications such as disaster response, search and rescue, environmental monitoring, exploration and mapping, surveillance and security, logistics, agriculture, military operations and healthcare. Therefore, it is essential to address these challenges and develop optimal solutions for implementing these concepts in real-world scenarios to effectively execute the previously mentioned applications. Hence, this paper presents a comprehensive survey and comparative analysis of different approaches for allocating tasks to multiple robots and forming coalitions to accomplish these tasks efficiently. The paper first provides a systematic categorization of the existing methods into four different groups namely behavior-based, market-based, optimization-based, and learning-based methods. Next, it analyzes the trade-off between different objectives, including minimizing task completion time, maximizing resource utilization, and balancing workload among robots. The paper also explores the impact of robot heterogeneity, task dependencies, and communication constraints on the performance of various algorithms. Furthermore, it discusses the challenges of dynamic task allocation and coalition formation in response to changes in the environment or robot failures.
Accordingly, the paper presents a comprehensive comparative study of the surveyed approaches, highlighting their substantial features including limitations and suitability for different application scenarios. As such, the paper identifies promising research directions, including the integration of machine learning techniques and the development of hybrid algorithms. Through this systematic analysis, the main aim is to provide researchers with a comprehensive understanding of the state-of-the-art in multi-robot task allocation and coalition formation, enabling them to select the most appropriate approach for their specific requirements.
