[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Development of a task-oriented, auction-based task allocation framework for a heterogeneous multirobot system

  • Published:
Sādhanā Aims and scope Submit manuscript

Abstract

A multirobot system has cooperative team of robots designed to enhance efficiency of its operations. One of the critically investigated problems of multirobot system is the multirobot task allocation (MRTA) issue. The main objective of MRTA is to assign tasks to the most suitable robot based on its functions and capability as well as availability. In this paper, a task-oriented, auction-based task allocation framework is presented and tested through simulations and real-world experiments. The developed framework consists of a novel heuristic-based task allocation algorithm and communication module. It is implemented in a multirobot system, allowing tasks to be dynamically assigned to the robots as they achieve given tasks. The implemented framework shows robustness in its flexibility to the task and environment requirements such as resource and energy requirements and size of the environment. The framework involved a task allocation algorithm, which consists of bid generation and bid selection process, and a TCP/IP-based client-server communication module. The results from both simulations and real-world experiments matched, producing optimum results in task allocation.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8
Figure 9
Figure 10
Figure 11
Figure 12
Figure 13
Figure 14
Figure 15
Figure 16
Figure 17
Figure 18

Similar content being viewed by others

References

  1. Alatartsev S, Stellmacher S and Ortmeier F 2015 Robotic Task Sequencing Problem: A Survey. Journal of Intelligent & Robotic Systems 80 (2): 279–298

    Article  Google Scholar 

  2. Nunes E, Manner M, Mitiche H and Gini M 2017 A taxonomy for task allocation problems with temporal and ordering constraints. Robotics and Autonomous Systems 90: 55–70

    Article  Google Scholar 

  3. Veloso N M and Nardi D 2006 Special Issue on Multirobot Systems. In: Proceedings of the IEEE, 94: pp. 1253–1253

  4. Cai L, Espinosa A P, Pranantha D and Gloria A D 2011 Multi-robot search and rescue team. In: Proceedings of 1 IEEE International Symposium on Safety, Security, and Rescue Robotics, pp. 296–301

  5. Hoshino S, Seki H, Naka Y and Ota J 2010 Multirobot Coordination for Flexible Batch Manufacturing Systems Experiencing Bottlenecks. IEEE Transactions on Automation Science and Engineering 7: 887–901

    Article  Google Scholar 

  6. Shkurti F, Xu A, Meghjani M, Higuera J C G, Girdhar Y, Giguere P, Dey B B, Li J, Kalmbach A, Prahacs C, Turgeon K, Rekleitis I and Dudek G 2012 Multi-domain monitoring of marine environments using a heterogeneous robot team. In: Proceedings of 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1747–1753

  7. Das G P, McGinnity T M, Coleman S A and Behera L 2015 A Distributed Task Allocation Algorithm for a Multi-Robot System in Healthcare Facilities. Journal of Intelligent & Robotic Systems 80: 33–58

    Article  Google Scholar 

  8. Jia X and Meng M Q H 2013 A survey and analysis of task allocation algorithms in multi-robot systems. In: Proceedings of 2013 IEEE International Conference on Robotics and Biomimetics (ROBIO), pp. 2280–2285

  9. Ayorkor K G, Anthony S and Bernardine D M 2013 A comprehensive taxonomy for multi-robot task allocation. The International Journal of Robotics Research 32: 1495–1512

    Article  Google Scholar 

  10. de Mendonça R M, Nedjah N and de Macedo Mourelle L 2016 Efficient distributed algorithm of dynamic task assignment for swarm robotics. Neurocomputing 172: 345–355

    Article  Google Scholar 

  11. Luo L, Chakraborty N, and Sycara K 2012 Competitive analysis of repeated greedy auction algorithm for online multi-robot task assignment. In: Proceedings of 2012 IEEE International Conference on Robotics and Automation, pp. 4792–4799

  12. Hatime H, Pendse R, and Watkins J M 2013 Comparative Study of Task Allocation Strategies in Multirobot Systems. IEEE Sensors Journal 13: 253–262

    Article  Google Scholar 

  13. Nam C and Shell D A 2015 Assignment Algorithms for Modeling Resource Contention in Multirobot Task Allocation. IEEE Transactions on Automation Science and Engineering 12: 889–900

    Article  Google Scholar 

  14. Chopra S, Notarstefano G, Rice M and Egerstedt M 2017 A Distributed Version of the Hungarian Method for Multirobot Assignment. IEEE Transactions on Robotics 33 (4): 932–947

    Article  Google Scholar 

  15. Butler Z and Hays J 2015 Task allocation for reconfigurable teams. Robotics and Autonomous Systems 68: 59–71

    Article  Google Scholar 

  16. de Lope J, Maravall D, and Quiñonez Y 2015 Self-organizing techniques to improve the decentralized multi-task distribution in multi-robot systems. Neurocomputing 163: 47–55

    Article  Google Scholar 

  17. Nagarajan T and Thondiyath A 2013 Heuristic based Task Allocation Algorithm for Multiple Robots Using Agents. Procedia Engineering 64: 844–853

    Article  Google Scholar 

  18. Jose K and Pratihar D K 2016 Task allocation and collision-free path planning of centralized multi-robots system for industrial plant inspection using heuristic methods. Robotics and Autonomous Systems 80: 34–42

    Article  Google Scholar 

  19. Elango M, Kanagaraj G and Ponnambalam S G 2013 Sandholm Algorithm with K-means Clustering Approach for Multi-robot Task Allocation. In: Proceedings of 4th International Conference, SEMCCO 2013, Chennai, India, December 19-21, 2013, Proceedings, Part II, Springer International Publishing pp. 14–22

  20. Żabińska M, Sośnicki T, Turek W and Cetnarowicz K 2013 Robot Task Allocation Using Signal Propagation Model. Procedia Computer Science 18: 1505–1514

    Article  Google Scholar 

  21. Kim Y and Matson E 2016 A Realistic Decision Making for Task Allocation in Heterogeneous Multi-agent Systems. Procedia Computer Science 94: 386–391

    Article  Google Scholar 

  22. Zhu Z, Tang B and Yuan J 2017 Multirobot task allocation based on an improved particle swarm optimization approach. International Journal of Advanced Robotic Systems 14(3, p. 172988141771031, 2017

  23. Parker J, Farinelli A and Gini M 2018 Lazy max-sum for allocation of tasks with growing costs. Robotics and Autonomous Systems 110: 44–56

    Article  Google Scholar 

  24. Botzheim J, Toda Y, Kubota N 2012 Bacterial memetic algorithm for simultaneous optimization of path planning and flow shop scheduling problems. Artificial Life and Robotics 17: 107–112

    Article  Google Scholar 

  25. Zhang Y and Meng M Q H 2013 Comparison of auction-based methods for task allocation problem in multi-robot systems. In: Proceedings of 2013 IEEE International Conference on Robotics and Biomimetics (ROBIO), pp. 2609-2613

  26. Das G P, McGinnity T M and Coleman S A 2014 Simultaneous allocations of multiple tightly-coupled multi-robot tasks to coalitions of heterogeneous robots. In: Proceedings of 2014 IEEE International Conference on Robotics and Biomimetics (ROBIO 2014), 2014, pp. 1198–1204

  27. Sarker M O F, Dahl T S, Arcaute E and Christensen K 2014 Local interactions over global broadcasts for improved task allocation in self-organized multi-robot systems. Robotics and Autonomous Systems 62: 1453–1462

    Article  Google Scholar 

  28. Binetti G, Naso D and Turchiano B 2013 Decentralized task allocation for surveillance systems with critical tasks. Robotics and Autonomous Systems 61: 1653–1664

    Article  Google Scholar 

  29. Luo L, Chakraborty N and Sycara K 2015 Provably-Good Distributed Algorithm for Constrained Multi-Robot Task Assignment for Grouped Tasks. IEEE Transactions on Robotics 31: 19–30

    Article  Google Scholar 

  30. Triguia S, Koubaa A, Cheikhrouhou O, Youssef H, Bennaceur H, Sriti M, and Javed Y 2014 A Distributed Market-based Algorithm for the Multi-robot Assignment Problem. Procedia Computer Science 32: 1108–1114

    Article  Google Scholar 

  31. Lee D H, Zaheer S A and Kim J H 2015 A Resource-Oriented, Decentralized Auction Algorithm for Multirobot Task Allocation. IEEE Transactions on Automation Science and Engineering 12: 1469–1481

    Article  Google Scholar 

  32. Lee D-H 2018 Resource-based task allocation for multi-robot systems. Robotic and Autonomous Systems. 103: 151–161

    Article  Google Scholar 

  33. Service T C, Sen S D and Adams J A 2014 A simultaneous descending auction for task allocation. In: Proceedings of 2014 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 379–384

  34. Cui Y, Wu X, Song J and Ma H 2016 A Dynamic Task Equilibrium Allocation Algorithm Based on Combinatorial Auctions. In: Proceedings of 8th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC), pp. 530–533

  35. Gürel U, Adar N and Parlaktuna O 2013 Priority-based task allocation in auction-based applications, In: Proceedings of 2013 IEEE INISTA, pp. 1–5

  36. Cao J, Li M, Wang Z, Li J and Wang H 2016 Multi-robot target hunting based on dynamic adjustment auction algorithm. In: Proceedings of 2016 IEEE International Conference on Mechatronics and Automation, pp. 211–216

  37. Tolmidis A T and Petrou L 2013 Multi-objective optimization for dynamic task allocation in a multi-robot system. Engineering Applications of Artificial Intelligence 26: 1458–1468

    Article  Google Scholar 

  38. Zhang K, Collins E G and Barbu A 2013 An Efficient Stochastic Clustering Auction for Heterogeneous Robotic Collaborative Teams. Journal of Intelligent & Robotic Systems 72: 541–558

    Article  Google Scholar 

  39. Akbarimajd A and Simzan G 2014 Application of Artificial Capital Market in Task Allocation in Multi-robot Foraging. International Journal of Computational Intelligence Systems 7 (3): 401–417

    Article  Google Scholar 

Download references

Acknowledgements

This research is funded by University Malaysia Pahang research grant (Project ID: RDU1803139).

Author information

Authors and Affiliations

  1. Core Consulting PLT, 50100, Kuala Lumpur, Malaysia

    TAN EIJYNE

  2. Immagine Sdn. Bhd., Jalan SS6/2, Level 3, Kelana Parkview Tower 1, 47301, Petaling Jaya, Selangor, Malaysia

    RISHWARAJ G

  3. Faculty of Manufacturing and Mechatronics Engineering Technology, University Malaysia Pahang, 26600, Pekan, Pahang, Malaysia

    PONNAMBALAM S G

Authors
  1. TAN EIJYNE
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. RISHWARAJ G
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. PONNAMBALAM S G
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to PONNAMBALAM S G.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

EIJYNE, T., G, R. & S G, P. Development of a task-oriented, auction-based task allocation framework for a heterogeneous multirobot system. Sādhanā 45, 115 (2020). https://doi.org/10.1007/s12046-020-01330-4

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s12046-020-01330-4

Keywords