Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-18T15:38:26.185Z Has data issue: false hasContentIssue false
  • English
  • Français

Immune-inspired search strategies for robot swarms

Published online by Cambridge University Press:  11 July 2016

G. M. Fricke ,
J. P. Hecker ,
J. L. Cannon  and
M. E. Moses
G. M. Fricke*
Affiliation:
Department of Computer Science, The University of New Mexico, Albuquerque, USA. E-mails: [email protected], [email protected]
J. P. Hecker
Affiliation:
Department of Computer Science, The University of New Mexico, Albuquerque, USA. E-mails: [email protected], [email protected]
J. L. Cannon
Affiliation:
Department of Molecular Genetics and Microbiology, The University of New Mexico, Albuquerque, USA. E-mail: [email protected] Department of Pathology, The University of New Mexico, Albuquerque, USA
M. E. Moses
Affiliation:
Department of Computer Science, The University of New Mexico, Albuquerque, USA. E-mails: [email protected], [email protected] Department of Biology, The University of New Mexico, Albuquerque, USA Santa Fe Institute, Santa Fe, USA
*
*Corresponding author. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Summary

Detection of targets distributed randomly in space is a task common to both robotic and biological systems. Lévy search has previously been used to characterize T cell search in the immune system. We use a robot swarm to evaluate the effectiveness of a Lévy search strategy and map the relationship between search parameters and target configurations. We show that the fractal dimension of the Lévy search which optimizes search efficiency depends strongly on the distribution of targets but only weakly on the number of agents involved in search. Lévy search can therefore be tuned to the target configuration while also being scalable. Implementing search behaviors observed in T cells in a robot swarm provides an effective, adaptable, and scalable swarm robotic search strategy. Additionally, the adaptability and scalability of Lévy search may explain why Lévy-like movement has been observed in T cells in multiple immunological contexts.

Keywords

Lévy searchRobot searchRobot swarmLymph nodesT cell searchSwarm roboticsLevy walkT cellsDistributed search
Type
Articles
Information
Robotica , Volume 34 , Issue 8 , August 2016 , pp. 1791 - 1810
Copyright
Copyright © Cambridge University Press 2016 

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

1. Acar, E. U., Choset, H., Zhang, Y. and Schervish, M., “Path planning for robotic demining: Robust sensor-based coverage of unstructured environments and probabilistic methods,” Int. J. Robot. Res. 22 (7–8), 441–466 (2003).Google Scholar
2. Ackley, D. H., Cannon, D. C. and Williams, L. R., “A movable architecture for robust spatial computing,” Comput. J. bxs129, Oxford University Press (Oct 11, 2012).Google Scholar
3. Alberts, B., Johnson, A., Lewis, J., Raff, M., Roberts, K. and Walter, P., Molecular Biology of the Cell, 4th ed. (Garland Science, New York, 2002).Google Scholar
4. Ariotti, S., Beltman, J. B., Chodaczek, G., Hoekstra, M. E., van Beek, A. E., Gomez-Eerland, R., Ritsma, L., van Rheenen, J., Marée, A. F. M. and Zal, T., “Tissue-resident memory CD8+ T cells continuously patrol skin epithelia to quickly recognize local antigen,” Proc. Natl. Acad. Sci. 109 (48), 19739–19744 (2012).Google Scholar
5. Banerjee, S., Levin, D., Moses, M., Koster, F. and Forrest, S., “The Value of Inflammatory Signals in Adaptive Immune Responses,” In: Artificial Immune Systems (Liò, P., Nicosia, G. and Stibor, T., eds.) (Springer, 2011) pp. 1–14.Google Scholar
6. Banigan, E. J., Harris, T. H., Christian, D. A., Hunter, C. A., Liu, A. J. and Asquith, B., “Heterogeneous CD8+ T cell migration in the lymph node in the absence of inflammation revealed by quantitative migration analysis,” PLoS Comput. Biol. 11 (2), e1004058–e1004058 (2015).CrossRefGoogle Scholar
7. Bartumeus, F., d ALuz, M. G. E., Viswanathan, G. M. and Catalan, J., “Animal search strategies: A quantitative random-walk analysis,” Ecology 86 (11), 3078–3087 (2005).Google Scholar
8. Beal, J., “Superdiffusive dispersion and mixing of swarms,” ACM Trans. Auton. Adapt. Syst. (TAAS) 10 (2), 10 (2015).Google Scholar
9. Bénichou, O., Loverdo, C., Moreau, M. and Voituriez, R., “Intermittent search strategies,” Rev. Mod. Phys. 83 (1), 81 (2011).Google Scholar
10. Birk, A. and Carpin, S., “Rescue robotics - a crucial milestone on the road to autonomous systems,” Adv. Robot. 20 (5), 595–605 (2006).Google Scholar
11. Brambilla, M., Ferrante, E., Birattari, M. and Dorigo, M., “Swarm robotics: A review from the swarm engineering perspective,” Swarm Intell. 7 (1), 1–41 (2013).Google Scholar
12. Celli, S., Day, M., Müller, A. J., Molina-Paris, C., Lythe, G. and Bousso, P., “How many dendritic cells are required to initiate a T-cell response?” Blood 120 (19), 3945–3948 (2012).Google Scholar
13. De Boer, R. J., Oprea, M., Antia, R., Murali-Krishna, K., Ahmed, R. and Perelson, A. S., “Recruitment times, proliferation, and apoptosis rates during the CD8+ T-cell response to lymphocytic choriomeningitis virus,” J. Virology 75 (22), 10663–10669 (2001).Google Scholar
14. Donovan, G. M. and Lythe, G., “T-cell movement on the reticular network,” J. Theor. Biol. 295, 59–67 (2012).CrossRefGoogle ScholarPubMed
15. Edwards, A. M., “Overturning conclusions of Lévy flight movement patterns by fishing boats and foraging animals,” Ecology 92 (6), 1247–1257 (2011).Google Scholar
16. Fink, W., Dohm, J. M., Tarbell, M. A., Hare, T. M. and Baker, V. R., “Next-generation robotic planetary reconnaissance missions: A paradigm shift,” Planet. Space Sci. 53 (14), 1419–1426 (2005).Google Scholar
17. Fricke, G. M., Asperti-Boursin, F., Hecker, J., Cannon, J. and Moses, M., “From Microbiology to Microcontrollers: Robot Search Patterns Inspired by T Cell Movement,” In: Advances in Artificial Life, ECAL, (Liò, P., Miglino, O., Nicosia, G., Nolfi, S. and Pavone, M., eds.) vol. 12 (Sep 2, 2013) pp. 1009–1016.Google Scholar
18. Fricke, G. M., Letendre, K. A., Moses, M. E. and Cannon, J. L., “Persistence and adaptation in immunity: T cells balance the extent and thoroughness of search,” PLoS Comput. Biol. 12 (3), e1004818 (2016).Google Scholar
19. Fricke, G. M. and Thomas, J. L., “Receptor aggregation by intermembrane interactions: A Monte Carlo study,” Biophys. Chem. 119 (2), 205–211 (2006).Google Scholar
20. Gérard, A., Patino-Lopez, G., Beemiller, P., Nambiar, R., Ben-Aissa, K., Liu, Y., Totah, F. J., Tyska, M. J., Shaw, S. and Krummel, M. F., “Detection of rare antigen-presenting cells through T cell-intrinsic meandering motility, mediated by Myo1g,” Cell 158 (3), 492–505 (2014).Google Scholar
21. Groom, J. R., Richmond, J., Murooka, T. T., Sorensen, E. W., Sung, J. H., Bankert, K., von Andrian, U. H., Moon, J. J., Mempel, T. R. and Luster, A. D., “CXCR3 chemokine receptor-ligand interactions in the lymph node optimize CD4+ T helper 1 cell differentiation,” Immunity 37 (6), 1091–1103 (2012).CrossRefGoogle ScholarPubMed
22. Harris, T. H., Banigan, E. J., Christian, D. A., Konradt, C., Wojno, E. D. T., Norose, K. and, Wilson, E. H., John, B., Weninger, W., Luster, A. D. and Others “Generalized Lévy walks and the role of chemokines in migration of effector CD8+ T cells,” Nature 486 (7404), 545–548 (2012).CrossRefGoogle ScholarPubMed
23. Hecker, J. P. and Moses, M. E., “Beyond pheromones: Evolving error-tolerant, flexible, and scalable ant-inspired robot swarms,” Swarm Intell. 9 (1), 43–70 (2015).Google Scholar
24. Hecker, J. P., Stolleis, K., Swenson, B., Letendre, K. and Moses, M. E., “Evolving Error Tolerance in Biologically-Inspired iAnt Robots,” Proceedings of the 12th European Conference on the Synthesis and Simulation of Living Systems (Advances in Artificial Life, ECAL 2013) (Liò, P., Miglino, O., Nicosia, G., Nolfi, S. and Pavone, M., eds.) The MIT Press, Cambridge Mass (2013) pp. 1025–1032.Google Scholar
25. Hogg, R. V. and Ledolter, J., Engineering Statistics (Macmillan Pub Co, London, England, 1987).Google Scholar
26. Hu, H., Oyekan, J. and Gu, D., “A School of Robotic Fish for Pollution Detection in Port,” In: Biologically Inspired Robotics (Liu, Y. and Sun, D., eds.) Springer Berlin Heidelberg (2011) pp. 85–104.Google Scholar
27. Hughes, B. D. Random Walks and Random Environments (Clarendon Press Oxford, 1996).Google Scholar
28. Humphreys, T. E., Ledvina, B. M., Psiaki, M. L., O'Hanlon, B. W. and Kintner, P. M. Jr, “Assessing the Spoofing Threat: Development of a Portable GPS Civilian Spoofer,” Proceedings of the ION GNSS International Technical Meeting of the Satellite Division, vol. 55, Springer-Verlag, Springer (2008) p. 56.Google Scholar
29. Humphries, N. E., Weimerskirch, H., Queiroz, N., Southall, E. J. and Sims, D. W., “Foraging success of biological Lévy flights recorded in situ,” Proc. Natl. Acad. Sci. 109 (19), 7169–7174 (2012).Google Scholar
30. Jain, A. K. and Dubes, R. C., “Algorithms for Clustering Data, vol. 6 (Prentice Hall, Englewood Cliffs, 1988).Google Scholar
31. James, A., Plank, M. J. and Edwards, A. M., “Assessing Lévy walks as models of animal foraging,” J. R. Soc. Interface 8 (62), 1233–1247 (2011).Google Scholar
32. Katada, Y., Nishiguchi, A., Moriwaki, K. and Watakabe, R., “Swarm Robotic Network Using Lévy Flight in Target Detection Problem,” In Proceedings of The 1st International Symposium on Swarm Behavior and Bio-Inspired Robotics (SWARM2015), Springer, Japan (2015) pp. 310–315.Google Scholar
33. Keeter, M., Moore, D., Muller, R., Nieters, E., Flenner, J., Martonosi, S. E., Bertozzi, A. L., Percus, A. G. and Levy, R., “Cooperative search with autonomous vehicles in a 3d aquatic testbed,” In American Control Conference (ACC), IEEE (2012) pp. 3154–3160.Google Scholar
34. Larralde, H., Trunfio, P., Havlin, S., Stanley, H. E. and Weiss, G. H., “Territory covered by N diffusing particles,” Nature 355 (6359), 423–426 (1992).CrossRefGoogle Scholar
35. Lerman, K. and Galstyan, A., “Mathematical model of foraging in a group of robots: Effect of interference,” Autonomous Robots 13, no. 2 (Springer US, 2002) pp. 127–141.Google Scholar
36. Linderman, J. J., Riggs, T., Pande, M., Miller, M., Marino, S. and Kirschner, D. E., “Characterizing the dynamics of CD4+ T cell priming within a lymph node,” J. Immunology 184 (6), 2873–2885 (2010).Google Scholar
37. Lindquist, R. L., Shakhar, G., Dudziak, D., Wardemann, H., Eisenreich, T., Dustin, M. L. and Nussenzweig, M. C., “Visualizing dendritic cell networks in vivo ,” Nature immunology 5 (12), 1243–1250 (2004).Google Scholar
38. Liu, W., Winfield, A. F. T. and Sa, J., “Modelling Swarm Robotic Systems: A Case Study in Collective Foraging,” Towards Autonomous Robotic Systems (TAROS 07) (2007) pp. 25–32.Google Scholar
39. Love, J., Amai, W., Blada, T., Little, C., Neely, J. and Buerger, S., “The Sandia Architecture for Heterogeneous Unmanned System Control (SAHUC),” Proceedings of the SPIE 9464, Ground/Air Multisensor Interoperability, Integration, and Networking for Persistent ISR VI. International Society for Optics and Photonics, SPIE (2015) pp. 94640E-94640E.Google Scholar
40. Maier, D. and Kleiner, A., “Improved GPS Sensor Model for Mobile Robots in Urban Terrain,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), IEEE (2010) pp. 4385–4390.Google Scholar
41. Mandelbrot, B. B. The Fractal Geometry of Nature, vol. 173 (W. H. Freeman and Company, Macmillan, 1983).Google Scholar
42. Mårell, A., Ball, J. P. and Hofgaard, A., “Foraging and movement paths of female reindeer: Insights from fractal analysis, correlated random walks, and Lévy flights,” Can. J. Zoology 80 (5), 854–865 (2002).Google Scholar
43. Méndez, V., Campos, D. and Bartumeus, F., Stochastic Foundations in Movement Ecology: Anomalous Diffusion, Front Propagation and Random Searches (Springer Science & Business Media, Springer-Verlag Berlin Heidelberg, 2013).Google Scholar
44. Miller, M. J., Hejazi, A. S., Wei, S. H., Cahalan, M. D. and Parker, I., “T cell repertoire scanning is promoted by dynamic dendritic cell behavior and random T cell motility in the lymph node,” Proc. Natl. Acad. Sci. USA 101 (4), 998–1003 (2004).Google Scholar
45. Mirsky, H. P., Miller, M. J., Linderman, J. J. and Kirschner, D. E., “Systems biology approaches for understanding cellular mechanisms of immunity in lymph nodes during infection,” J. Theor. Biol. 287, 160–170 (2011).Google Scholar
46. Montgomery, D. C. Design and Analysis of Experiments, 8th ed. (John Wiley & Sons, 2012).Google Scholar
47. Nurzaman, S. G., Matsumoto, Y., Nakamura, Y., Koizumi, S. and Ishiguro, H., “Yuragi-Based Adaptive Searching Behavior in Mobile Robot: From Bacterial Chemotaxis to Lévy Walk,” IEEE International Conference on Robotics and Biomimetics, 2008, ROBIO 2008, IEEE (2009) pp. 806–811.Google Scholar
48. Nurzaman, S. G., Matsumoto, Y., Nakamura, Y., Shirai, K., Koizumi, S. and Ishiguro, H., “From Levy to Brownian: A computational model based on biological fluctuation,” PloS one 6 (2), e16168 (2011).CrossRefGoogle ScholarPubMed
49. Parker, L., “Path planning and motion coordination in multiple mobile robot teams,” In: Encyclopedia of Complexity and System Science (Meyers, R. A., ed.), Springer, Heidelberg (2009).Google Scholar
50. Potdar, A. A., Jeon, J., Weaver, A. M. and Cummings, P. T., “Cell Migration Paths of Epithelial Cells Resemble Lévy Modulated Correlated Random Walk Pattern,” Proceedings of the 2008 Annual Meeting of the American Institute of Chemical Engineers (2008) https://aiche.confex.com/aiche/2008/techprogram/P127058.HTM.Google Scholar
51. Raichlen, D. A., Wood, B. M., Gordon, A. D., Mabulla, A. Z. P., Marlowe, F. W. and Pontzer, H., “Evidence of Lévy walk foraging patterns in human huntergatherers,” Proc. Natl. Acad. Sci. 111 (2), 728–733 (2014).Google Scholar
52. Ramsey, S., “NASA Awards Grant to Manage Swarmathon Challenge (press release) (2015).Google Scholar
53. Raposo, E. P., Bartumeus, F., D ALuz, M. G. E., Ribeiro-Neto, P. J., Souza, T. A. and Viswanathan, G. M., “How landscape heterogeneity frames optimal diffusivity in searching processes,” PLoS Comput. Biol. 7 (11), e1002233 (2011).Google Scholar
54. Sahin, E., “Swarm Robotics: From Sources of Inspiration to Domains of Application,” In: Swarm Robotics (Şahin, E. and Spears, W. M., eds.) (Springer, 2005) pp. 10–20.Google Scholar
55. Seshadri, V. and West, B. J., “Fractal dimensionality of Lévy processes,” Proc. Natl. Acad. Sci. USA 79 (14), 4501 (1982).Google Scholar
56. Shlesinger, M. F. and Klafter, J., “Lévy Walks versus Lévy Flights” In: On Growth and Form (Stanley, H. E. and Ostrowsky, N., eds.) (Springer, 1986) pp. 279–283.Google Scholar
57. Stephens, D. W. and Krebs, J. R., Foraging Theory (Princeton University Press, Princeton, New Jersey, 1986).Google Scholar
58. Stolleis, K. A., Hecker, J. P., Montague, G., Leucht, K. and Moses, M. E., “Evolving Autonomous Charging Behavior in a Robot Swarm,” Proceedings of Earth & Space 2016 Engineering for Extreme Environments, Elsevier (2016a).Google Scholar
59. Stolleis, K. A., Hecker, J. P. and Moses, M. E., “The Ant and the Trap: Evolution of Ant-Inspired Obstacle Avoidance in a Multi-Agent System,” Proceedings of Earth & Space 2016 Engineering for Extreme Environments, Elsevier (2016b).Google Scholar
60. Stone, L. D., Theory of Optimal Search (Academic Press, New York, 1975).Google Scholar
61. Sung, J. H., Zhang, H., Moseman, E. A., Alvarez, D., Iannacone, M., Henrickson, S. E., Juan, C., Groom, J. R., Luster, A. D. and von Andrian, U. H., “Chemokine guidance of central memory T cells is critical for antiviral recall responses in lymph nodes,” Cell 150 (6), 1249–1263 (2012).Google Scholar
62. Sutantyo, D., Levi, P., Moslinger, C. and Read, M., “Collective-Adaptive Lévy Flight for Underwater Multi-Robot Exploration,” Proceedings of the IEEE International Conference on Mechatronics and Automation (ICMA), IEEE (2013) pp. 456–462.Google Scholar
63. Sutantyo, D. K., Kernbach, S., Levi, P. and Nepomnyashchikh, V. A., “Multi-Robot Searching Algorithm Using Lévy Flight and Artificial Potential Field,” Proceedings of the IEEE International Workshop on Safety Security and Rescue Robotics (SSRR), IEEE (2010) pp. 1–6.Google Scholar
64. Tamura, K. and Naruse, K., “Unsmooth Field Sweeping by Balistic Random Walk of Multiple Robots in Unsmooth Terrain,” Soft Computing and Intelligent Systems (SCIS), 2014 Joint 7th International Conference on and Advanced Intelligent Systems (ISIS), 15th International Symposium on, IEEE (2014) pp. 585–589.Google Scholar
65. Taylor, L. R., “Aggregation, variance and the mean,” Nature 189, 732–735 (Mar. 4, 1961).Google Scholar
66. Textor, J., Henrickson, S. E., Mandl, J. N., von Andrian, U. H., Westermann, J., de Boer, R. J. and Beltman, J. B., “Random migration and signal integration promote rapid and robust T cell recruitment,” PLoS Comput. Biol. 10 (8), e1003752.Google Scholar
67. United States Department of Defense “Global Positioning System Standard Positioning Service Performance Standard,” SPSGPS, 4th ed. (2008) pp. 9–15. United States Department of Defense http://www.gps.gov/technical/ps/2008-SPS-performance-standard.pdf.Google Scholar
68. Van Dartel, M., Postma, E., van den Herik, J. and de Croon, G., “Macroscopic analysis of robot foraging behaviour,” Connect. Sci. 16 (3), 169–181 (2004).Google Scholar
69. Viswanathan, G. M., Afanasyev, V., Buldyrev, S. V., Murphy, E. J., Prince, P. A. and Stanley, H. E., “Lévy flight search patterns of wandering albatrosses,” Nature 381 (6581), 413–415 (1996).Google Scholar
70. Viswanathan, G. M., Buldyrev, S. V., Havlin, S., D ALuz, M. G. E., Raposo, E. P. and Stanley, H. E., “Optimizing the success of random searches,” Nature 401 (6756), 911–914 (1999).Google Scholar
71. Von Neumann, J., “The general and logical theory of automata,” Cerebral Mech. Behav. 1, 1–41 (1951).Google Scholar
72. Weber, T. R., “An Analysis of Lemmings: A Swarming Approach to Mine Countermeasures in the VSW/SZ/BZ,” Technical report, DTIC Document (1995).Google Scholar
73. Winfield, A. F. T., “Foraging Robots,” In: Encyclopedia of Complexity and Systems Science (Meyers, R. A., ed.) (Springer, New York, 2009) pp. 3682–3700.Google Scholar
74. Winfield, A. F. T., Harper, C. J. and Nembrini, J., “Towards Dependable Swarms and a New Discipline of Swarm Engineering,” In: Swarm Robotics (Şahin, E. and Spear, W. M., eds.) (Springer, 2005) pp. 126–142.Google Scholar
75. Zhang, J., Leiderman, K., Pfeiffer, J. R., Wilson, B. S., Oliver, J. M. and Steinberg, S. L., “Characterizing the topography of membrane receptors and signaling molecules from spatial patterns obtained using nanometer-scale electron-dense probes and electron microscopy,” Micron 37 (1), 14–34 (2006).Google Scholar