Hostname: page-component-745bb68f8f-grxwn Total loading time: 0 Render date: 2025-01-07T13:33:14.609Z Has data issue: false hasContentIssue false
  • English
  • Français

Adaptable and stable decentralized task allocation for hierarchical domains

Part of: Adaptive Learning Agents 2019

Published online by Cambridge University Press:  04 June 2020

Vera A. Kazakova Open the ORCID record for Vera A. Kazakova [Opens in a new window]  and
Gita R. Sukthankar
Vera A. Kazakova
Affiliation:
Intelligent Agents Laboratory, University of Central Florida, Orlando, FL, USA e-mails: [email protected], [email protected]
Gita R. Sukthankar
Affiliation:
Intelligent Agents Laboratory, University of Central Florida, Orlando, FL, USA e-mails: [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Many real-world domains can benefit from adaptable decentralized task allocation through emergent specialization, especially in large teams of non-communicating agents. We begin with an existing bio-inspired response threshold reinforcement approach for decentralized task allocation and extend it to handle hierarchical task domains. We test the extension on self-deployment of a large team of non-communicating agents to patrolling a hierarchically defined set of areas. Results show near-ideal performance across all areas, while minimizing wasteful task switching through the development of specializations and subsequent respecializations when area demands change. A genetic algorithm is then used to evolve even more adaptable and stable task allocation behavior, by incorporating weight and power coefficients into agents’ response threshold reinforcement action probability calculations.

Type
Research Article
Information
The Knowledge Engineering Review , Volume 35 , 2020 , e26
Copyright
© Cambridge University Press, 2020

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Agmon, N., Urieli, D. & Stone, P. 2011. Multiagent patrol generalized to complex environmental conditions. In Proceedings of the Twenty-Fifth Conference on Artificial Intelligence (AAAI 2011).Google Scholar
Almeida, A., Ramalho, G., Santana, H., Tedesco, P., Menezes, T., Corruble, V. & Chevaleyre, Y. 2004. Recent advances on multi-agent patrolling. In Advances in Artificial Intelligence – SBIA 2004, Bazzan, A. L. C. & Labidi, S. (eds). Springer Berlin Heidelberg, 474–483. ISBN: 978-3-540-28645-5.Google Scholar
Baker, J. E. 1985. Adaptive selection methods for genetic algorithms. In Proceedings of an International Conference on Genetic Algorithms and Their applications, Hillsdale, New Jersey, 101–111.Google Scholar
Berman, S., Halasz, A., Kumar, V. & Pratt, S. 2007. Bio-inspired group behaviors for the deployment of a swarm of robots to multiple destinations. In Proceedings 2007 IEEE International Conference on Robotics and Automation, 2318–2323.Google Scholar
Campbell, A. & Wu, A. S. 2011. Multi-agent role allocation: Issues, approaches, and multiple perspectives. Autonomous Agents and Multi-Agent Systems 22(2), 317–355.CrossRefGoogle Scholar
Campos, M., Bonabeau, E., Theraulaz, G. & Deneubourg, J.-L. 2000. Dynamic scheduling and division of labor in social insects. Adaptive Behavior 8(2), 83–95.CrossRefGoogle Scholar
Chu, H. N., Glad, A., Simonin, O., Sempe, F., Drogoul, A. & Charpillet, F. 2007. Swarm approaches for the patrolling problem, information propagation vs. pheromone evaporation. In 19th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2007, 1, 442–449. 2007.Google Scholar
Cicirello, V. A. & Smith, S. F. 2004. Wasp-like agents for distributed factory coordination. Autonomous Agents and Multi-Agent Systems 8(3), 237–266. ISSN: 1573-7454.CrossRefGoogle Scholar
De Jong, K. A. 2006. Evolutionary Computation: A Unified Approach, MIT Press, Cambridge, MA, USA.CrossRefGoogle Scholar
dos Santos, F. & Bazzan, A. L. 2009. An ant based algorithm for task allocation in largescale and dynamic multiagent scenarios. In Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, 73–80. ACM.CrossRefGoogle Scholar
dos Santos, F. & Bazzan, A. L. 2011. Towards efficient multiagent task allocation in the robocup rescue: a biologically-inspired approach. Autonomous Agents and Multi-Agent Systems 22(3), 465–486.CrossRefGoogle Scholar
dos Santos, D. S. & Bazzan, A. L. 2012. Distributed clustering for group formation and task allocation in multiagent systems: a swarm intelligence approach. Applied Soft Computing 12(8), 2123–2131. ISSN: 1568-4946.CrossRefGoogle Scholar
Ducatelle, F., Förster, A., Di Caro, G. A. & Gambardella, L. M. 2009. New task allocation methods for robotic swarms. In 9th IEEE/RAS Conference on Autonomous Robot Systems and Competitions.Google Scholar
Farinelli, A., Iocchi, L., Nardi, D. & Ziparo, V. A. 2006. Assignment of dynamically perceived tasks by token passing in multirobot systems. Proceedings of the IEEE 94(7), 1271–1288.CrossRefGoogle Scholar
Ghizzioli, R., Nouyan, S., Birattari, M. & Dorigo, M. 2005. An Ant-Based Algorithm for the Heterogeneous Dynamic Task Allocation Problem, Institut de Recherches Interdisciplinaires et de Développements en Intelligence Artificielle (IRIDIA), Technical Report TR/IRIDIA/2005-005.Google Scholar
Halász, A., Hsieh, M. A., Berman, S. & Kumar, V. 2007. Dynamic redistribution of a swarm of robots among multiple sites. In IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2007, 2320–2325. IEEE.CrossRefGoogle Scholar
Hsieh, M. A., Halász, Á., Berman, S. & Kumar, V. 2008. Biologically inspired redistribution of a swarm of robots among multiple sites. Swarm Intelligence 2(2–4), 121–141.CrossRefGoogle Scholar
Hsieh, M. A., Halász, Á., Cubuk, E. D., Schoenholz, S. & Martinoli, A. 2009. Specialization as an optimal strategy under varying external conditions. In IEEE International Conference on Robotics and Automation, ICRA 2009, 1941–1946.Google Scholar
Kanakia, A., Touri, B. & Correll, N. 2016. Modeling multi-robot task allocation with limited information as global game. Swarm Intelligence 10(2), 147–160.CrossRefGoogle Scholar
Kazakova, V. A., Wu, A. S. & Rahman, T. S. 2013. Cluster energy optimizing genetic algorithm. In Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, 1317–1324. ACM.CrossRefGoogle Scholar
Kazakova, V. A. & Wu, A. S. 2018. Specialization vs. re-specialization: Effects of hebbian learning in a dynamic environment. In Florida Artificial Intelligence Research Society Conference FLAIRS-31.Google Scholar
Kira, Z. & Arkin, R. C. 2004. Forgetting bad behavior: memory for case-based navigation. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS), 4, 3145–3152.Google Scholar
Li, L., Martinoli, A. & Abu-Mostafa, Y. S. 2002. Emergent specialization in swarm systems. In International Conference on Intelligent Data Engineering and Automated Learning, 261–266. Springer.CrossRefGoogle Scholar
Liu, W., Winfield, A. F., Sa, J., Chen, J. & Dou, L. 2007. Towards energy optimization: emergent task allocation in a swarm of foraging robots. Adaptive Behavior 15(3), 289–305.CrossRefGoogle Scholar
Ma, H., Li, J., Kumar, T. & Koenig, S. 2017. Lifelong multi-agent path finding for online pickup and delivery tasks. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems, 837–845.Google Scholar
Mavrovouniotis, M., Li, C. & Yang, S. 2017. A survey of swarm intelligence for dynamic optimization: algorithms and applications. Swarm and Evolutionary Computation 33, 1–17.CrossRefGoogle Scholar
McIntire, M., Nunes, E. & Gini, M. 2016. Iterated multi-robot auctions for precedenceconstrained task scheduling. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, International Foundation for Autonomous Agents and Multiagent Systems, 1078–1086.Google Scholar
Merkle, D. & Middendorf, M. 2004. Dynamic polyethism and competition for tasks in threshold reinforcement models of social insects. Adaptive Behavior 12(3–4), 251–262.CrossRefGoogle Scholar
Murciano, A., del R. MillÁn, J. & Zamora, J.Specialization in multi-agent systems through learning. Biological Cybernetics 76(5), 375–382. ISSN: 1432-0770.CrossRefGoogle Scholar
Nitschke, G., Schut, M. & Eiben, A. 2008. Emergent specialization in biologically inspired collective behavior systems. In Intelligent Complex Adaptive Systems, 215–253. IGI Global.CrossRefGoogle Scholar
Nouyan, S. 2002. Agent-based approach to dynamic task allocation. In International Workshop on Ant Algorithms, 28–39. Springer.CrossRefGoogle Scholar
Nouyan, S., Ghizzioli, R., Birattari, M. & Dorigo, M. 2005. An insect-based algorithm for the dynamic task allocation problem. KI 19(4), 25–31.Google Scholar
Nunes, E., McIntire, M. & Gini, M. 2016. Decentralized allocation of tasks with temporal and precedence constraints to a team of robots. In IEEE International Conference on Simulation, Modeling, and Programming for Autonomous Robots (SIMPAR), 197–202. IEEE.CrossRefGoogle Scholar
Ono, N. & Fukumoto, K. 1996. Multi-agent reinforcement learning: a modular approach. In Second International Conference on Multiagent Systems, 252–258.Google Scholar
Portugal, D. & Rocha, R. 2011. A survey on multi-robot patrolling algorithms. In Doctoral Conference on Computing, Electrical and Industrial Systems, 139–146. Springer.CrossRefGoogle Scholar
Price, R. & Tiño, P. 2004. Evaluation of adaptive nature inspired task allocation against alternate decentralised multiagent strategies. In International Conference on Parallel Problem Solving from Nature, 982–990. Springer.CrossRefGoogle Scholar
Ragusa, V. R., Mathias, H. D., Kazakova, V. A. & Wu, A. S. 2017. Enhanced genetic path planning for autonomous flight. In Proceedings of the Genetic and Evolutionary Computation Conference, ACM, 2017, pp. 1208–1215.Google Scholar
Román, J. A., Rodríguez, S. & Corchado, J. M. 2014. Improving intelligent systems: specialization. In International Conference on Practical Applications of Agents and Multi-Agent Systems, 378–385. Springer.CrossRefGoogle Scholar
Schwarzrock, J., Zacarias, I., Bazzan, A. L., de Araujo Fernandes, R. Q., Moreira, L. H. & de Freitas, E. P. 2018. Solving task allocation problem in multi unmanned aerial vehicles systems using swarm intelligence. Engineering Applications of Artificial Intelligence 72, 10–20.CrossRefGoogle Scholar
Stanley, K. O. & Miikkulainen, R. 2002. Evolving neural networks through augmenting topologies. Evolutionary Computation 10(2), 99–127.CrossRefGoogle ScholarPubMed
Theraulaz, G., Bonabeau, E. & Deneubourg, J.-L. 1998. Response threshold reinforcement and division of labour in insect societies. Proceedings of the Royal Society of London B 265, 327–332.CrossRefGoogle Scholar
van Lon, R. R. & Holvoet, T. 2017. When do agents outperform centralized algorithms? Autonomous Agents and Multi-Agent Systems 31(6), 1578–1609.CrossRefGoogle Scholar
Villacorta, P. J., Pelta, D. A. & Lamata, M. T. 2013. Forgetting as a way to avoid deception in a repeated imitation game. Autonomous Agents and Multi-Agent Systems 27(3), 329–354.CrossRefGoogle Scholar
Wawerla, J. & Vaughan, R. T. 2010. A fast and frugal method for team-task allocation in a multi-robot transportation system. In ICRA, 1432–1437.Google Scholar
Wu, A. S. & Kazakova, V. A. 2017. Effects of task consideration order on decentralized task allocation using time-variant response thresholds. In Florida Artificial Intelligence Research Society Conference FLAIRS-30, 466–471.Google Scholar
Zhang, Z., Long, K., Wang, J. & Dressler, F. 2014. On swarm intelligence inspired self-organized networking: its bionic mechanisms, designing principles and optimization approaches. IEEE Communications Surveys & Tutorials 16(1), 513–537.CrossRefGoogle Scholar
Zheng, X. & Koenig, S. 2011. Generalized reaction functions for solving complex-task allocation problems. IJCAI Proceedings-International Joint Conference on Artificial Intelligence, 22, 478.Google Scholar