Intelligent Agents Laboratory, University of Central Florida, Orlando, FL, USA e-mails: kazakova.cs@ucf.edu, gitars@eecs.ucf.edu"/>
Search
2020 Volume 35
Article Contents
RESEARCH ARTICLE   Open Access    

Adaptable and stable decentralized task allocation for hierarchical domains

More Information
  • 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.
  • 加载中
  • 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 Systems22(2), 317–355.

    Google Scholar

    Campos , M., Bonabeau , E., Theraulaz , G. & Deneubourg , J.-L.2000. Dynamic scheduling and division of labor in social insects. Adaptive Behavior8(2), 83–95.

    Google 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 Systems8(3), 237–266. ISSN: 1573-7454.

    Google Scholar

    De Jong , K. A.2006. Evolutionary Computation: A Unified Approach, MIT Press, Cambridge, MA, USA.

    Google 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.

    Google 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 Systems22(3), 465–486.

    Google 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 Computing12(8), 2123–2131. ISSN: 1568-4946.

    Google 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 IEEE94(7), 1271–1288.

    Google 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.

    Google Scholar

    Hsieh , M. A., Halász , Á., Berman , S. & Kumar , V.2008. Biologically inspired redistribution of a swarm of robots among multiple sites. Swarm Intelligence2(2–4), 121–141.

    Google 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 Intelligence10(2), 147–160.

    Google 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.

    Google 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.

    Google 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 Behavior15(3), 289–305.

    Google 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 Computation33, 1–17.

    Google 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 Behavior12(3–4), 251–262.

    Google Scholar

    Murciano , A., del R. MillÁn , J. & Zamora , J.Specialization in multi-agent systems through learning. Biological Cybernetics76(5), 375–382. ISSN: 1432-0770.

    Google 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.

    Google Scholar

    Nouyan , S.2002. Agent-based approach to dynamic task allocation. In International Workshop on Ant Algorithms, 28–39. Springer.

    Google 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.

    Google 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.

    Google 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.

    Google 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.

    Google 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 Intelligence72, 10–20.

    Google Scholar

    Stanley , K. O. & Miikkulainen , R.2002. Evolving neural networks through augmenting topologies. Evolutionary Computation10(2), 99–127.

    Google Scholar

    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 B265, 327–332.

    Google Scholar

    van Lon , R. R. & Holvoet , T.2017. When do agents outperform centralized algorithms?Autonomous Agents and Multi-Agent Systems31(6), 1578–1609.

    Google 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 Systems27(3), 329–354.

    Google 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 & Tutorials16(1), 513–537.

    Google 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

  • Cite this article

    Vera A. Kazakova, Gita R. Sukthankar. 2020. Adaptable and stable decentralized task allocation for hierarchical domains. The Knowledge Engineering Review 35(1), doi: 10.1017/S0269888920000235
    Vera A. Kazakova, Gita R. Sukthankar. 2020. Adaptable and stable decentralized task allocation for hierarchical domains. The Knowledge Engineering Review 35(1), doi: 10.1017/S0269888920000235

Article Metrics

Article views(51) PDF downloads(82)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Adaptable and stable decentralized task allocation for hierarchical domains

Abstract: 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.

    • © Cambridge University Press, 20202020Cambridge University Press
References (47)
  • About this article
    Cite this article
    Vera A. Kazakova, Gita R. Sukthankar. 2020. Adaptable and stable decentralized task allocation for hierarchical domains. The Knowledge Engineering Review 35(1), doi: 10.1017/S0269888920000235
    Vera A. Kazakova, Gita R. Sukthankar. 2020. Adaptable and stable decentralized task allocation for hierarchical domains. The Knowledge Engineering Review 35(1), doi: 10.1017/S0269888920000235
  • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return