Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Booth, K. E., Nejat, G., & Beck, J. C. (2016). A constraint programming approach to multi-robot task allocation and scheduling in retirement homes. In International Conference on Principles and Practice of Constraint Programming (pp. 539–555). Berlin: Springer.
Das, G. P., McGinnity, T. M., Coleman, S. A., & Behera, L. (2015). A distributed task allocation algorithm for a multi-robot system in healthcare facilities. Journal of Intelligent & Robotic Systems, 80(1), 33–58.
Elango, M., Nachiappan, S., & Tiwari, M. K. (2011). Balancing task allocation in multi-robot systems using k-means clustering and auction based mechanisms. Expert Systems with Applications, 38(6), 6486–6491.
Garg, R., & Kapoor, S. (2006). Auction algorithms for market equilibrium. Mathematics of Operations Research, 31(4), 714–729.
Hooshangi, N., & Alesheikh, A. A. (2017). Agent-based task allocation under uncertainties in disaster environments: An approach to interval uncertainty. International Journal of Disaster Risk Reduction, 24, 160–171.
Jiang, L., & Zhang, R. (2011). An autonomous task allocation for multi-robot system. Journal of Computational Information Systems, 7(11), 3747–3753.
Liu, Y., Yang, J., Zheng, Y., Wu, Z., & Yao, M. (2013). Multi-robot coordination in complex environment with task and communication constraints. International Journal of Advanced Robotic Systems, 10(5), 229.
Lu, L., Yu, J., Zhu, Y., & Li, M. (2018). A double auction mechanism to bridge users’ task requirements and providers’ resources in two-sided cloud markets. IEEE Transactions on Parallel and Distributed Systems, 29(4), 720–733.
Ponda, S. S., Johnson, L. B., & How, J. P. (2012). Distributed chance-constrained task allocation for autonomous multi-agent teams. In: American Control Conference (ACC), 2012 (pp. 4528–4533). Piscataway: IEEE.
Tang, J., Zhu, K., Guo, H., Gong, C., Liao, C., & Zhang, S. (2018). Using auction-based task allocation scheme for simulation optimization of search and rescue in disaster relief. Simulation Modelling Practice and Theory, 82, 132–146
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.
Acknowledgements
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.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Shi, J., Yang, Z., Zhu, J. (2020). An Auction-Based Task Allocation Algorithm in Heterogeneous Multi-Robot System. In: Lu, H., Yujie, L. (eds) 2nd EAI International Conference on Robotic Sensor Networks. EAI/Springer Innovations in Communication and Computing. Springer, Cham. https://doi.org/10.1007/978-3-030-17763-8_14
Download citation
DOI: https://doi.org/10.1007/978-3-030-17763-8_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-17762-1
Online ISBN: 978-3-030-17763-8
eBook Packages: EngineeringEngineering (R0)