15th Biennial ASCE Conference on Engineering, Science, Construction, and Operations in Challenging Environments
The Ant and the Trap: Evolution of Ant-Inspired Obstacle Avoidance in a Multi-Agent Robotic System
Publication: Earth and Space 2016: Engineering for Extreme Environments
ABSTRACT
In this paper, we demonstrate that a simple robotic swarm can use a genetic algorithm (GA) to achieve autonomous navigation in highly cluttered environments. We also show the GA can evolve effective strategies for coping with random obstacle placements using a central place foraging algorithm (CPFA). The CPFA combines stochastic movements, insect-inspired obstacle avoidance, and simple communication among robots. We modify the CPFA by allowing simulated robots to communicate with stygmergic trails in CPFA-trails (CPFAT). Both the CPFA and CPFAT can evolve foraging strategies to collect resources in the presence of a high density of randomly placed obstacles. CPFAT additionally succeeds against a classic bug trap, where the CPFA fails. These methods are simple to implement, run in real-time, and need no global knowledge of the environment.
Get full access to this article
View all available purchase options and get full access to this chapter.
ACKNOWLEDGMENTS
The authors would like to thank members of the Biological Computation Lab (UNM), Dr. Lydia Tapia and Nick Malone from the Adaptive Motion Planning group (UNM) and Kurt Leucht, Cheryle Mako, Gil Montague, Matt Nugent and NASA/KSC Swamp Works for their time and input on this paper.
REFERENCES
Antich, J., Ortiz, A., and Minguez, J. (2009). “A bug-inspired algorithm for efficient anytime path planning” Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International Conference on, IEEE, 5407–5413.
Bailis, P., Nagpal, R., and Werfel, J. (2010). “Positional communication and private information in honeybee foraging models.” Swarm Intelligence, 263–274.
Beverly, B., McLendon, H., et al. (2009). “How site fidelity leads to individual differences in the foraging activity of harvester ants” Behavioral Ecology, 20(3), 633–638.
Brambilla, M., Ferrante, E., Birattari, M., and Dorigo, M. (2013). “Swarm robotics: a review from the swarm engineering perspective” Swarm Intelligence, 7(1), 1–41.
Buniyamin, N., Wan Ngah, W., Sariff, N., and Mohamad, Z. (2011). “A simple local path planning algorithm for autonomous mobile robots” International journal of systems applications, Engineering development, 5(2), 151–159.
Campo, A. and Dorigo, M. (2007). “Efficient multi-foraging in swarm robotics” Advances in Artificial Life, Springer, 696–705.
Chiang, C. H., Liu, J.-S., and Chou, Y.-S. (2009). “Comparing path length by boundary following fast matching method and bug algorithms for path planning” Opportunities and Challenges for Next-Generation Applied Intelligence, Springer, 303–309.
Crist, T. O. and Haefner, J. W. (1994). “Spatial model of movement and foraging in harvester ants (pogonomyrmex)(ii): the roles of environment and seed dispersion” Journal of Theoretical Biology, 166(3), 315–323.
Crowley, J. L. (1985). “Navigation for an intelligent mobile robot” Robotics and Automation, IEEE Journal of, 1(1), 31–41.
Denny, A. J., Wright, J., and Grief, B. (2001). “Foraging efficiency in the wood ant, formica rufa: is time of the essence in trail following?” Animal Behaviour, 62(1), 139–146.
Dorigo, M., Floreano, D., et al. (2011). “Swarmanoid: a novel concept for the study of heterogeneous robotic swarms” Report no., Technical Report TR/IRIDIA/2011-014, IRIDIA, Universite’ Libre de Bruxelles, Brussels, Belgium.
Dussutour, A., Nicolis, S. C., Shephard, G., Beekman, M., and Sumpter, D. J. (2009). “The role of multiple pheromones in food recruitment by ants” The Journal of Experimental Biology, 212(15), 2337–2348.
Flanagan, T. P., Letendre, K., Burnside, W. R., Fricke, G. M., and Moses, M. E. (2012). “Quantifying the effect of colony size and food distribution on harvester ant foraging” PloS one, 7(7), e39427.
Garnier, S., Tache, F., Combe, M., Grimal, A., and Theraulaz, G. (2007). “Alice in pheromone land: An experimental setup for the study of ant-like robots” Swarm Intelligence Symposium, 2007. SIS 2007. IEEE, IEEE, 37–44.
Goldberg, D. and Mataric, M. J. (2001). “Design and evaluation of robust behavior-based controllers for distributed multi-robot collection tasks” Robot teams: From diversity to polymorphism, Citeseer.
Hecker, J. P., Letendre, K., Stolleis, K., Washington, D., and Moses, M. E. (2012). “Formica ex machina: Ant swarm foraging from physical to virtual and back again” Swarm Intelligence: 8th International Conference, ANTS 2012, Springer Berlin Heidelberg, Berlin, DE, 252–259.
Hecker, J. P. and Moses, M. E. (2015). “Beyond pheromones: evolving error-tolerant, flexible, and scalable ant-inspired robot swarms” Swarm Intelligence, 9(1), 43–70.
Hoff, N. R., Sagoff, A., Wood, R. J., and Nagpal, R. (2010). “Two foraging algorithms for robot swarms using only local communication” Robotics and Biomimetics (ROBIO), 2010 IEEE International Conference on, IEEE, 123–130.
Holder, K. and Polis, G. (1987). “Optimal and central-place foraging theory applied to a desert harvester ant, pogonomyrmex californicus” Oecologia, 72(3), 440–448.
Jackson, D. E. and Ratnieks, F. L. (2006). “Communication in ants” Current biology, 16(15), R570–R574.
Johnson, A., Wiens, J., Milne, B., and Crist, T. (1992). “Animal movements and population dynamics in heterogeneous landscapes” Landscape ecology, 7(1), 63–75.
Kelly, I., Holland, O., and Melhuish, C. (2000). “Slugbot: A robotic predator in the natural world” Proceedings of the Fifth International Symposium on Artificial Life and Robotics for Human Welfare and Artificial Liferobotics, Citeseer, 470–475.
Krieger, M., Billeter, J., and Keller, L. (2000). “Ant-like task allocation and recruitment in cooperative robots” Nature, 406, 992–995.
LaValle, S. M. (2006). Planning algorithms. Cambridge university press.
LaValle, S. M. and Kuffner, J. J. (2001). “Randomized kinodynamic planning” The International Journal of Robotics Research, 20(5), 378–400.
LaValle, S. M. and Kuffner, J. J. Jr (2000). “Rapidly-exploring random trees: Progress and prospects.
Letendre, K. and Moses, M. E. (2013). “Synergy in ant foraging strategies: memory and communication alone and in combination” Proceedings of the 15th annual conference on Genetic and evolutionary computation, ACM, 41–48.
Liu, W., Winfield, A. F., and Sa, J. (2007). “Modelling swarm robotic systems: A case study in collective foraging” Towards Autonomous Robotic Systems (TAROS 07), 25–32.
Lumelsky, V. J. and Stepanov, A. A. (1987). “Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape” Algorithmica, 2(1-4), 403– 430.
Mataric, M. J. (1994). “Learning to behave socially” Third international conference on simulation of adaptive behavior, Vol. 617, Citeseer, 453–462.
Mayet, R., Roberz, J., Schmickl, T., and Crailsheim, K. (2010). “Antbots: A feasible visual emulation of pheromone trails for swarm robots” Swarm Intelligence, Springer, 84–94.
Mohan, Y. and Ponnambalam, S. (2009). “An extensive review of research in swarm robotics” World Congress on Nature Biologically Inspired Computing, IEEE, 140–145.
Moore, J. W. and Swerdling, M. (1971). “Conceptual design of a 1979 mars rover.
Ng, J. and Bräunl, T. (2007). “Performance comparison of bug navigation algorithms” Journal of Intelligent and Robotic Systems, 50(1), 73–84.
Payton, D., Daily, M., Estowski, R., Howard, M., and Lee, C. (2001). “Pheromone robotics” Autonomous Robots, 11(3), 319–324.
Paz Flanagan, T., Letendre, K., Burnside, W., Fricke, G. M., and Moses, M. (2011). “How ants turn information into food” Artificial Life (ALIFE), 2011 IEEE Symposium on, IEEE, 178–185.
Pugh, J. and Martinoli, A. (2007). “Inspiring and modeling multi-robot search with particle swarm optimization” Swarm Intelligence Symposium, 2007. SIS 2007. IEEE, IEEE, 332–339.
Reif, J. H. (1979). “Complexity of the mover’s problem and generalizations extended abstract” Proceedings of the 20th Annual IEEE Conference on Foundations of Computer Science, 421–427.
Russell, R. (1999). “Ant trails-an example for robots to follow?” Proceedings of the 1999 IEEE International Conference on Robotics and Automation, Vol. 4, IEEE, 2698–2703.
Schmickl, T. and Crailsheim, K. (2008). “Trophallaxis within a robotic swarm: bio-inspired communication among robots in a swarm” Autonomous Robots, 25(1), 171–188.
Steele Jr, F. and Thomas, G. (2007). “Directed stigmergy-based control for multi-robot systems” Proceedings of the ACM/IEEE international conference on Human-robot interaction, ACM, 223–230.
Sumpter, D. J. and Beekman, M. (2003). “From nonlinearity to optimality: pheromone trail foraging by ants.” Animal behaviour, 66(2), 273–280.
Thompson, A. M. (1977). “The navigation system of the jpl robot.
Washington, R., Golden, K., Bresina, J., Smith, D. E., Anderson, C., and Smith, T. (1999). “Autonomous rovers for mars exploration” Aerospace Conference, 1999. Proceedings. 1999 IEEE, Vol. 1, IEEE, 237–251.
Winfield, A. F. (2009). “Foraging robots” Encyclopedia of Complexity and Systems Science, Springer, 3682–3700.
Yershova, A., Jaillet, L., Siméon, T., and LaValle, S. M. (2005). “Dynamic-domain rrts: Efficient exploration by controlling the sampling domain” Robotics and Automation, 2005. ICRA 2005. Proceedings of the 2005 IEEE International Conference on, IEEE, 3856–3861.
Zhu, Y., Zhang, T., Song, J., and Li, X. (2010). “A new bug-type navigation algorithm considering practical implementation issues for mobile robots” Robotics and Biomimetics (ROBIO), 2010 IEEE International Conference on, IEEE, 531–536.
Zohaib, M., Pasha, M., Riaz, R., Javaid, N., Ilahi, M., and Khan, R. (2013a). “Control strategies for mobile robot with obstacle avoidance” arXiv preprint arXiv:1306.1144.
Zohaib, M., Pasha, S. M., Javaid, N., and Iqbal, J. (2013b). “Intelligent bug algorithm (iba): A novel strategy to navigate mobile robots autonomously” arXiv preprint arXiv:1312.4552.
Information & Authors
Information
Published In
Earth and Space 2016: Engineering for Extreme Environments
Pages: 675 - 687
Editors: Ramesh B. Malla, Ph.D., University of Connecticut, Juan H. Agui, Ph.D., NASA Glenn Research Center, and Paul J. van Susante, Ph.D, Michigan Technological University
ISBN (Online): 978-0-7844-7997-1
Copyright
© 2016 American Society of Civil Engineers.
History
Published in print: Dec 30, 2016
Published online: Jun 29, 2017
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.