H. David Mathias
Annie S. Wu
Skip Abstract Section
Abstract
In this work, we investigate the application of a multi-objective genetic algorithm to the problem of task allocation in a self-organizing, decentralized, threshold-based swarm. We use a multi-objective genetic algorithm to evolve response thresholds for a simulated swarm engaged in dynamic task allocation problems: two-dimensional and three-dimensional collective tracking. We show that evolved thresholds not only outperform uniformly distributed thresholds and dynamic thresholds but achieve nearly optimal performance on a variety of tracking problem instances (target paths). More importantly, we demonstrate that thresholds evolved for some problem instances generalize to all other problem instances, eliminating the need to evolve new thresholds for each problem instance to be solved. We analyze the properties that allow these paths to serve as universal training instances and show that they are quite natural.
After a priori evolution, the response thresholds in our system are static. The problem instances solved by the swarms are highly dynamic, with schedules of task demands that change over time with significant differences in rate and magnitude of change. That the swarm is able to achieve nearly optimal results refutes the common assumption that a swarm must be dynamic to perform well in a dynamic environment.
- . 2020. Assessing a swarm-GAP based solution for the task allocation problem in dynamic scenarios. Expert Syst. Appl. 152 (2020), 113437.Google Scholar
Cross Ref
- . 2008. Evolution of signaling in a multi-robot system: Categorization and communication. Adaptive Behavior 16, 1 (2008), 5–26.Google ScholarCross Ref
- . 1958. Requisite variety and its implications for the control of complex systems. Cybernetica 1, 2 (1958), 83–99.Google Scholar
- . 2017. Evolutionary optimization of self-assembly in a swarm of bio-micro-robots. In Proceedings of the Genetic and Evolutionary Computation Conference. 59–66.Google ScholarDigital Library
- . 2003. Evolving mobile robots able to display collective behaviors. Artif. Life 9, 3 (2003), 255–267.Google ScholarDigital Library
- . 2007. Self-organized coordinated motion in groups of physically connected robots. IEEE Trans. Syst. Man Cybernet. B: Cybernet. 37, 1 (2007), 224–239.Google ScholarDigital Library
- . 2008. Evolution of adaptive population control in multi-agent systems. In Proceedings of the 2nd IEEE International Conference on Self-Adaptive and Self-Organizing Systems.Google ScholarDigital Library
- . 1992. Distributed robotic systems and swarm intelligence. J. Robot. Soc. Jpn. 10, 4 (1992), 31–37.Google Scholar
- . 1996. Quantitiate study of the fixed threshold model for the regulation of division of labor in insect societies. Proc. Roy. Soc. Lond.: Biol. Sci. 263, 1376 (1996), 1565–1569.Google ScholarCross Ref
- . 1998. Fixed response thresholds and the regulation of division of labor in insect societies. Bull. Math. Biol. 60 (1998), 753–807.Google ScholarCross Ref
- . 2012. Costs and benefits of behavioral specialization. Robot. Auton. Syst. 60, 11 (2012), 1408–1420.Google ScholarDigital Library
- . 2011. On the impact of variation on self-organizing systems. In Proceedings of the 5th IEEE International Conference Self-Adaptive and Self-Organizing Systems.Google ScholarDigital Library
- . 2000. Dynamic scheduling and division of labor in social insects. Adapt. Behav. 8, 2 (2000), 83–96.Google ScholarCross Ref
- . 2016. Adaptive foraging for simulated and real robotic swarms: The dynamical response threshold approach. Swarm Intell. 10, 1 (2016), 1–31.Google ScholarCross Ref
- . 2013. Task allocation for a robotic swarm based on an adaptive response threshold model. In Proceedings of the 13th International Conference on Control, Automation, and Systems. 259–266.Google ScholarCross Ref
- . 2002. Distributed coordination of resources via wasp-like agents. In Lecture Notes in Artificial Intelligence, Vol. 2564. 71–80.Google Scholar
- . 2008. Parameter estimation and optimal control of swarm-robotic systems: A case study in distributed task allocation. In Proceedings of the IEEE International Conference on Robotics and Automation. 3302–3307.Google ScholarCross Ref
- . 2013. Response threshold models and stochastic learning automata for self-coordination of heterogeneous multi-task distribution in multi-robot systems. Robot. Auton. Syst. 61, 7 (2013), 714–720.Google ScholarCross Ref
- . 2015. Self-organizing techniques to improve the decentralized multi-task distribution in multi-robot systems. Neurocomputing 163 (2015), 47–55.Google ScholarDigital Library
- . 2019. The emergence of division of labor in a structured response threshold model. Physica A 517, C (2019), 153–162.Google ScholarCross Ref
- . 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6, 2 (2002), 182–197.Google ScholarDigital Library
- . 2004. Evolving self-organizing behaviors for a swarm-bot. Auton. Robots 17 (2004), 223–245.Google ScholarDigital Library
- Miguel Duarte, Sancho Oliveira, and Anders Christensen. 2009. An ant based algorithm for task allocation in large-scale and dynamic multiagent scenarios. In Proceedings of the Genetic and Evolutionary Computation Conference. 73–80.Google Scholar
- . 2012. Evolution of self-organized division of labor in a response threshold model. Behav. Ecol. Sociobiol. 66 (2012), 947–957.Google ScholarCross Ref
- . 2016a. Evolution of collective behaviors for a real swarm of aquatic surface robots. PLoS One 11, 3 (2016).Google ScholarCross Ref
- . 2016b. Hybrid control for a real swarm robotics system in an intruder detection task. In Proceedings of the European Conference on the Applications of Evolutionary Computation. 213–230.Google ScholarCross Ref
- Miguel Duarte, Sancho Oliveira, and Anders Christensen. 2014. Hybrid control for large swarms of aquatic drones. In Proceedings of the 14th International Conference on the Synthesis and Simulation of Living Systems. 785–792.Google Scholar
- . 2015. Evolution of self-organized task specialization in robot swarms. PLOS Comput. Biol. 11, 8 (2015).Google ScholarCross Ref
- . 2007. A swarm based approximated algorithm to the extended generalized assignment problem (E-GAP). In Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems. 1–3.Google ScholarDigital Library
- . 2018. How swarm size during evolution imacts the behavior, generalizability, and brain connectivity of animats performing a spatial navigation task. In Proceedings of the Genetic and Evolutionary Computation Conference. 77–84.Google ScholarDigital Library
- . 1993. What makes a problem hard for a genetic algorithm? Some anomalous results and their explanation. Mach. Learn. 13 (1993), 285–319.Google ScholarDigital Library
- . 2012. DEAP: Evolutionary algorithms made easy. J. Mach. Learn. Res. 13 (July 2012), 2171–2175.Google ScholarDigital Library
- . 2002. Emergent polyethism as a consequence of increase colony size in insect societies. J. Theor. Biol. 215, 3 (2002), 363–373.Google ScholarCross Ref
- Harry Goldingay and Jort van Mourik. 2013. The effect of load on agent-based algorithms for distributed task allocation. Inf. Sci. 222 (2013), 66–80.Google ScholarDigital Library
- . 2012. Task-switching costs promote the evolution of division of labor and shifts in individuality. Proc. Natl. Acad. Sci. U.S.A. 109, 34 (2012), 13686–13691.Google ScholarCross Ref
- . 2010. Evolution of division of labor in genetically homogeneous groups. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’10).Google Scholar
- . 2013. Generic behaviour similarity measures for evolutionary swarm robotics. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’13). 199–206.Google ScholarDigital Library
- . 2013. Evolution of swarm robotics systems with novelty search. Swarm Intell. 7 (2013), 115–144.Google ScholarCross Ref
- . 2008. Evolution of solitary and group transport behaviors for autonomous robots capable of self-assembling. Adapt. Behav. 16, 5 (2008), 285–305.Google ScholarDigital Library
- . 2020. Multi-agent coalition formation by an efficient genetic algorithm with heuristic initialization and repair strategy. Swarm Evol. Comput. 55 (2020).Google ScholarCross Ref
- . 2018. Evolution of a functionally diverse swarm via a novel decentralised quality-diversity algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference. 101–108.Google ScholarDigital Library
- . 2009. Evolved swarming without positioning information: An application in aerial communication relay. Auton. Robots 26 (2009), 21–32.Google ScholarDigital Library
- . 2013. Colony-size effects on task organization in the harvester ant Pogonomymex californicus. Insect. Soc. 60, 2 (2013), 191–201.Google ScholarCross Ref
- . 2011. Division of labor increases with colony size in the harvester ant pogonomyrmex californicus. Behav. Ecol. 22, 5 (2011), 960–966.Google ScholarCross Ref
- . 2017. Evolving collective driving behaviors. In Proceedings of the 16th International Conference on Autonomous Agents and MultiAgent Systems. 1573–1574.Google Scholar
- . 1986. The evolution of the organization of work in social insects. Monit. Zool. Ital. 20, 2 (1986), 119–133.Google Scholar
- . 2014. Interindividual variability in social insects—Proximate causes and ultimate consequences. Biol. Rev. 89, 3 (2014), 671–687.Google ScholarCross Ref
- . 2006. A comparative study of market-based and threshold-based task allocation. In Distributed Autonomous Robotics Systems 7. 91–101.Google Scholar
- . 2016. Modeling multi-robot task allocation with limited information as global game. Swarm Intell. 10 (2016), 147–160.Google ScholarCross Ref
- . 2018. Specialization vs. re-specialization: Effects of hebbian learning in a dynamic environment. In Proceedings of the 31st Florida Artificial Intelligence Research Society (FLAIRS’18). 354–359.Google Scholar
- . 2020. Respecializing swarms by forgetting reinforced thresholds. Swarm Intelligence 14 (2020), 171–204.Google ScholarCross Ref
- . 2003. Do ants paint trucks better than chickens? Market versus response threshold for distributed dynamic scheduling. In Proceedings of the Congress on Evolutionary Computation. 1431–1439.Google ScholarCross Ref
- . 2000a. The call of duty: Self-organised task allocation in a population of up to twelve mobile robots. Robot. Auton. Syst. 30, 1–2 (2000), 65–84.Google ScholarCross Ref
- . 2000b. Ant-like task allocation and recruitment in cooperative robots. Nature 406 (2000), 992–995.Google ScholarCross Ref
- . 2006. Division of labor in a group of robotics inspired by ants’ foraging behavior. ACM Trans. Auton. Adapt. Syst. 1, 1 (2006), 4–25.Google ScholarDigital Library
- . 2004. Improvement in collective performance with experience in ants. Behav. Ecol. Sociobiol. 56 (2004), 523–529.Google ScholarCross Ref
- . 2019. Adaptive approach to regulate task distribution in swarm robotic systems. Swarm Evol. Comput. 44 (2019), 1108–1118.Google ScholarCross Ref
- . 2020. Task allocation into a foraging task with a series of subtasks in swarm robotic system. IEEE Access 8 (2020), 107549–107561.Google ScholarCross Ref
- . 2004. Dynamic polyethism and competition for tasks in threshold reinforcement models of social insects. Adapt. Behav. 12, 3-4 (2004), 251–262.Google ScholarDigital Library
- . 2015. Collective homeostasis and time-resolved models of self-organised task allocation. In Proceedings of the 9th EAI Int’l Conf Bio-inspired Info & Comm Tech. 469–478.Google Scholar
- . 2015. Evolutionary inheritance mechanisms for multi-criteria decision making in multi-agent systems. In Proceedings of the Genetic and Evolutionary Computation Conference. 65–72.Google Scholar
- . 1996. Painting trucks at general motors: The effectiveness of a complexity-based approach. In Embracing Complexity: Exploring the Application of Complex Adaptive Systems to Business. 53–58.Google Scholar
- . 2006. Multi-objective Evolutionary Optimization of agent-based models: An application to emergency response planning. In Proceedings of the 2nd International Conference on Computational Intelligence. 224–230.Google Scholar
- . 2019. Designing emergent swarm behaviors usign behavior trees and grammatical evolution. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems. 2138–2140.Google ScholarDigital Library
- . 2018. GEESE: Gramatical evolution algorithm for evolution of swarm behaviors. In Proceedings of the Genetic and Evolutionary Computation Conference. 999–1006.Google ScholarDigital Library
- Marta Niccolini, Mario Innocenti, and Lorenzo Pollini. 2010. Multiple UAV task assignment using descriptor functions. In Proceedings of the 18th IFAC Symposium on Automatic Control in Aerospace. 93–98.Google Scholar
- . 2009. Neuro-evolution methods for gathering and collective construction. In Proceedings of the 10th European Conference on Artificial Life. 111–119.Google Scholar
- . 2012a. Evolving team behaviors with specialization. Genet. Program. Evolv. Mach. 13 (2012), 493–536.Google ScholarDigital Library
- . 2012b. Evolving behavioral specialization in robot teams to solve a collective construction task. Swarm Evol. Comput. 2 (2012), 25–38.Google ScholarCross Ref
- . 2005. An Insect-based Algorithm for the Dynamic Task Allocation Problem.
Technical Report . IRIDIA.Google Scholar - . 2006. Biasing coevolutionary search for optimal multiagent behaviors. IEEE Trans. Evol. Comput. 10, 6 (2006), 629–645.Google ScholarDigital Library
- Bao Pang, Chengjin Zhang, Yong Song, and Hongling Wang. 2017. Seld-organized task allocation in swarm robotics foraging based on dynamical response threshold approach. In Proceedings of the 18th International Conference on Advanced Robotics. 256–261.Google Scholar
- . 2008. On the design of neuro-controllers for individual and social learning behaviour in autonomous robots: An evolutionary approach. Connect. Sci. 20, 2–3 (2008), 211–230.Google ScholarDigital Library
- . 2004. Evaluation of adaptive nature inspired task allocation against alternative decentralised multiagent strategies. In Proceedings of the Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Vol. 3242. 982–990.Google Scholar
- . 2007. Individual experience alone can generate lasting division of labor in ants. Curr. Biol. 17, 15 (2007), 1308–1312.Google ScholarCross Ref
- . 2012. Variation as an element in multi-agent control for target tracking. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. 834–841.Google Scholar
- . 2018. Automatic synthesis of swarm behavioural rules from their atomic components. In Proceedings of the Genetic and Evolutionary Computation Conference. 133–140.Google ScholarDigital Library
- . 2018. Solving task allocation problem in multi unmanned aerial vehicles systems using swarm intelligence. Eng. Appl. Artif. Intell. 72 (2018), 10–20.Google ScholarDigital Library
- . 2007. Aggregation in swarm robotic systems: Evolution and probabilistic control. Turk. J. Electr. Eng. Comput. Sci. 15 (2007), 199–225.Google Scholar
- . 2008. Evolving coordinated group behaviours through maximisation of mean mutual information. Swarm Intell. 2 (2008), 73–95.Google ScholarCross Ref
- . 2011. Self-organised path formation in a swarm of robots. Swarm Intell. 5 (2011), 97–119.Google ScholarCross Ref
- . 2017. An investigation of environmental influence on the benefits of adaptation mechanisms in evolutionary swarm robotics. In Proceedings of the Genetic and Evolutionary Computation Conference. 155–162.Google ScholarDigital Library
- . 1998. Response threshold reinforcement and division of labour in insect societies. Proc. Roy. Soc. B 265, 1393 (1998), 327–332.Google ScholarCross Ref
- . 1991. Task differentiation in polistes wasp colonies: A model for self-organizing groups of robots. In Proceedings of the 1st International Conference on Simulation of Adaptive Behavior: From Animals to Animats. 346–355.Google ScholarCross Ref
- . 2003. Evolving aggregation behaviors in a swarm of robots. In Proceedings of the European Conference on Artificial Life. 865–874.Google ScholarCross Ref
- . 2006. Cooperative hole avoidance in a swarm-bot. Robot. Auton. Syst. 54, 2 (2006), 97–103.Google ScholarCross Ref
- . 2014. Evolutionary swarm robotics: Genetic diversity, task allocation and task switching. In Proceedings of the 9th International Conference on Swarm Intelligence (ANTS’14). 148–160.Google ScholarCross Ref
- . 2019. Evolving intrinsic motivations for altruistic behavior. In Proceedings of the 18th International Conference Autonomous Agents and MultiAgent Systems. 683–692.Google ScholarDigital Library
- . 2004. The control of nest climate in bumblebee (\( {B}ombus \)terrestris) colonies: Interindividual variability and self reinforcement in fanning response. Behav. Ecol. 15, 1 (2004), 120–128.Google ScholarCross Ref
- . 2019. Reconsidering response threshold models – short-term response patterns in thermoregulating bumblebees. Behav. Ecol. Sociobiol. 73, Article 112 (2019).Google ScholarCross Ref
- . 2020. Dynamic response thresholds: Heterogeneous ranges allow specialization while mitigating convergence to sink states. In Proceedings of the 12th International Conference on Swarm Intelligence. 107–120.Google ScholarCross Ref
- . 2020. Effects of response threshold distribution on dynamic division of labor in decentralized swarms. In Proceedings of the 33rd International Florida Artificial Intelligence Research Society Conference.Google Scholar
- . 2021. Collective Control as a Decentralized Task Allocation Testbed.
Technical Report CS-TR-21-01. University of Central Florida.Google Scholar - . 2018. Inter-agent variation improves dynamic decentralized task allocation. In Proceedings of the 31st International Florida Artificial Intelligence Research Society Conference. 366–369.Google Scholar
- . 2013. Evolution of self-interested agents: An experimental study. In Proceedings of the 7th International Workshop on Multi-disciplinary Trends in AI. 329–340.Google ScholarDigital Library
- . 2011. Genetic algorithm aided optimization of hierarchical multiagent system organization. In Proceedings of the 10th International Conference Autonomous Agents and MultiAgent Systems. 1169–1170.Google Scholar
Index Terms
- Analysis of Evolved Response Thresholds for Decentralized Dynamic Task Allocation
Index terms have been assigned to the content through auto-classification.
Recommendations
Evolved response thresholds generalize across problem instances for a deterministic-response multiagent system
GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference CompanionIn this work, we use a multiobjective genetic algorithm to evolve agent response thresholds for a decentralized swarm and demonstrate that swarms with evolved thresholds outperform swarms with thresholds set using other methods. In addition, we provide ...
Evolving Secret Sharing: Dynamic Thresholds and Robustness
Theory of CryptographyAbstractThreshold secret sharing schemes enable a dealer to share a secret among n parties such that only subsets of parties of cardinality at least can reconstruct the secret. Komargodski, Naor and Yogev (TCC 2016-B) proposed an efficient scheme ...
Globally evolved dynamic bee colony optimization
KES'11: Proceedings of the 15th international conference on Knowledge-based and intelligent information and engineering systems - Volume Part IBee colony optimization (BCO) is one of swarm intelligence algorithms that evolve static and locally. It performs slow improvement and tends to reach a local solution. In this paper, three modifications for the BCO are proposed, i.e. global evolution ...
Comments