The Group-Based Distributed Auction Algorithms for Multi-Robot Task Assignment

In recent years, the optimization of multi-robot systems for tasks such as delivery of goods has gained significant attention in the field of robotics. This paper presents a detailed comparative analysis of central and distributed algorithms, focusing on how the Distributed Auction Algorithm (DAA) can be effectively applied to address the multi-robot minimum time problem. The central algorithms traditionally considered for such tasks are often limited by the need for a central coordinator, which can become a bottleneck both in terms of computational requirements and as a single point of failure. Conversely, distributed algorithms, like the DAA, allow for decision-making to be spread across the network of robots, potentially increasing robustness and scalability. Our study involves extensive simulations and real-world experiments to evaluate the performance of both algorithmic paradigms. We have meticulously recorded the total time taken by a fleet of robots to deliver goods to a predetermined location, as well as the average computation time required by each algorithm. The results are displayed in tabular form, facilitating a direct comparison across different metrics. The findings confirm that the DAA not only reduces the total delivery time but also demonstrates a significant improvement in computation efficiency. This paper not only substantiates the effectiveness of the Distributed Auction Algorithm through empirical evidence but also discusses the theoretical underpinnings that contribute to its superior performance. By highlighting the trade-offs between central and distributed approaches, we aim to provide insights that will guide the development of more efficient algorithms for multi-robot systems in similar applications.