Advertisement

An Auction-Based Task Allocation Algorithm in Heterogeneous Multi-Robot System

  • Jieke Shi
  • Zhou Yang
  • Junwu ZhuEmail author
Conference paper
Part of the EAI/Springer Innovations in Communication and Computing book series (EAISICC)

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.

Keywords

Task allocation Auction Multi-robot system Dynamics 

Notes

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.

References

  1. 1.
    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.CrossRefGoogle Scholar
  2. 2.
    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.CrossRefGoogle Scholar
  3. 3.
    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.CrossRefGoogle Scholar
  4. 4.
    Garg, R., & Kapoor, S. (2006). Auction algorithms for market equilibrium. Mathematics of Operations Research, 31(4), 714–729.MathSciNetCrossRefGoogle Scholar
  5. 5.
    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.CrossRefGoogle Scholar
  6. 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
  7. 7.
    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.CrossRefGoogle Scholar
  8. 8.
    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.CrossRefGoogle Scholar
  9. 9.
    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.CrossRefGoogle Scholar
  10. 10.
    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–146CrossRefGoogle Scholar
  11. 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

Copyright information

© Springer Nature Switzerland AG 2020

Authors and Affiliations

  1. 1.College of Information EngineeringYangzhou UniversityYangzhouChina
  2. 2.Department of Computer ScienceUniversity of GuelphGuelphCanada

Personalised recommendations