An Auction-Based Task Allocation Algorithm in Heterogeneous Multi-Robot System
Today, robots are facing dynamic, real-time, complex adversarial, and stochastic work environment. It’s of great significance to research on task allocation problem in multi-robot system. In this paper, we propose a dynamic auction method for differentiated tasks under cost rigidities (DAMCR) which can find the optimal result in a static auction between robots and tasks. Then we analyze the optimality of DAMCR. Considering the dynamics of the system, we propose a partition-based task allocation adjustment method via distributed approach. To verify the effectiveness of the proposed scheme, we compare it with other task allocation methods based on classic Hungarian algorithm. In the experiments, we analyze the impact of the number of tasks and robots on the running time and robustness of the methods. The results suggest that our solution outperforms others, that is, robots can accomplish tasks faster and more effectively.
KeywordsTask allocation Auction Multi-robot system Dynamics
This work was supported by the National Nature Science Foundation of China under Grant 61170201, Grant 61070133, and Grant 61472344, in part by the Innovation Foundation for graduate students of Jiangsu Province under Grant CXLX12 0916, in part by the Natural Science Foundation of the Jiangsu Higher Education Institutions under Grant 14KJB520041, in part by the Advanced Joint Research Project of Technology Department of Jiangsu Province under Grant BY201506106 and Grant BY2015061-08, and in part by the Yangzhou Science and Technology under Grant YZ2017288 and Yangzhou University Jiangdu High-end Equipment Engineering Technology Research Institute Open Project under Grant YDJD201707.
- 6.Jiang, L., & Zhang, R. (2011). An autonomous task allocation for multi-robot system. Journal of Computational Information Systems, 7(11), 3747–3753.Google Scholar
- 11.Wang, L., Liu, M., & Meng, M. Q. H. (2017). A hierarchical auction-based mechanism for real-time resource allocation in cloud robotic systems. IEEE Transactions on Cybernetics, 47(2), 473–484.Google Scholar