Superdiffusive Dispersion and Mixing of Swarms

Abstract

A common swarm task is to disperse evenly through an environment from an initial tightly packed formation. Due to communication and sensing limitations, it is often necessary to execute this task with little or no communication between swarm members. Unfortunately, prior approaches based on repulsive forces or uniform random walks can often converge quite slowly. With an appropriate choice of random distribution, however, it is possible to generate optimal or near-optimal dispersion and mixing in swarms with zero communication. In particular, we discuss three extremely simple algorithms: reactive Levy walk, reactive ball dispersion, and purely reactive dispersion. All three algorithms vastly outperform prior approaches in both constrained and unconstrained environments, providing a range of options for trading off between aggressiveness and evenness in dispersion.

References

1. A. V. Chechkin, V. Y. Gonchar, and M. Szydlowski M. 2002. Fractional kinetics for relaxation and superdiffusion in a magnetic field. Physics of Plasmas 9, 78--88.
2. J. Beal. 2012. A tactical command approach to human control of vehicle swarms. In AAAI 2012 Fall Symposium on Human Control of Bio-Inspired Swarms. AAAI Press, 14--20.
3. J. Beal. 2013. Superdiffusive dispersion and mixing of swarms with reactive levy walks. In IEEE International Conference on Self-Adaptive and Self-Organizing Systems. IEEE Press, 141--148.
4. J. Beal and J. Bachrach. 2006. Infrastructure for engineered emergence in sensor/actuator networks. IEEE Intelligent Systems 21, 2, 10--19.
5. J. Beal, N. Correll, L. Urbina, and J. Bachrach. 2009. Behavior modes for randomized robotic coverage. In 2nd International Conference on Robot Communication and Coordination. IEEE Press, 1--6.
6. P. Becker-Kern, M. M. Meerschaert, and H.-P. Scheffler. 2004. Limit theorems for coupled continuous time random walks. Annals of Probability 32, 18, 730--756.
7. S. Benhamou. 2007. How many animals really do the Levy walk? Ecology 88, 8, 1962--1969.
8. D. Brockmann, L. Hufnagel, and T. Geisel. 2006. The scaling laws of human travel. Nature 439, 7075, 462--465.
9. D. Calitoiu. 2009. New search algorithm for randomly located objects: A non-cooperative agent based approach. In IEEE Symposium on Computational Intelligence for Security and Defense Applications (CISDA’09). IEEE Press, 1--6. DOI:http://dx.doi.org/10.1109/CISDA.2009.5356564
10. H. Choset. 2001. Coverage for robotics--A survey of recent results. Annals of Mathematics and Artificial Intelligence 31, 1--4, 113--126.
11. J. Eckert, H. Lichte, F. Dressler, and H. Frey. 2012. On the feasibility of mass-spring-relaxation for simple self-deployment. In 2012 IEEE 8th International Conference on Distributed Computing in Sensor Systems (DCOSS’12). IEEE Press, 203--208. DOI:http://dx.doi.org/10.1109/DCOSS.2012.14
12. A. M. Edwards. 2011. Overturning conclusions of Lévy flight movement patterns by fishing boats and foraging animals. Ecology 92, 6, 1247--1257.
13. N. Elhage and J. Beal. 2010. Laplacian-based consensus on spatial computers. In International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'10). 907--914.
14. A. Howard, M. J. Mataric, and G. S. Sukhatme. 2002. Mobile sensor network deployment using potential fields: A distributed, scalable solution to the area coverage problem. In International Symposium on Distributed Autonomous Robotic Systems. Springer, 299--308.
15. N. E. Humphries, N. Queiroz, J. R. M. Dyer, N. G. Pade, M. K. Musyl, K. M. Schaefer, D. W. Fuller, J. M. Brunnschweiler, T. K. Doyle, J. D. R. Houghton, G. C. Hays, C. S. Jones, L. R. Noble, V. J. Wearmouth, E. J Southall, and D. W. Sims. 2010. Environmental context explains Lévy and Brownian movement patterns of marine predators. Nature 465, 1066--1069.
16. M. Keeter, D. Moore, R. Muller, E. Nieters, J. Flenner, S. E. Martonosi, A. L. Bertozzi, A. G. Percus, and R. Levy. 2012. Cooperative search with autonomous vehicles in a 3D aquatic testbed. In 2012 American Control Conference (ACC’12). IEEE Press, 3154--3160.
17. M. Kotulski. 1995. Asymptotic distributions of continuous-time random walks: A probabilistic approach. Journal of Statistical Physics 81, 3--4, 777--792. DOI:http://dx.doi.org/10.1007/BF02179257
18. L. Ludwig and M. Gini. 2006. Robotic swarm dispersion using wireless intensity signals. In Distributed Autonomous Robotic Systems 7, M. Gini and R. Voyles (Eds.). Springer, Japan, 135--144. DOI:http://dx.doi.org/10.1007/4-431-35881-1_14
19. B. B. Mandelbrot. 1983. The Fractal Geometry of Nature. W. H. Freeman, New York.
20. E. Mathews, T. Graf, and K. S. S. B. Kulathunga. 2012. Biologically inspired swarm robotic network ensuring coverage and connectivity. In 2012 IEEE International Conference on Systems, Man, and Cybernetics (SMC’12). IEEE Press, 84--90. DOI:http://dx.doi.org/10.1109/ICSMC.2012.6377681
21. J. McLurkin and J. Smith. 2004. Distributed algorithms for dispersion in indoor environments using a swarm of autonomous mobile robots. In 7th International Symposium on Distributed Autonomous Robotic Systems (DARS’04). Springer, 399--408.
22. N. Mercadier, W. Guerin, M. Chevrollier, and R. Kaiser. 2009. Lévy flights of photons in hot atomic vapours. Nature Physics 5, 8, 602--605.
23. MIT Proto. 2012. MIT Proto. Software available at http://proto.bbn.com/.
24. J. Mullins, B. Meyer, and A. P. Hu. 2012. Collective robot navigation using diffusion limited aggregation. In Parallel Problem Solving from Nature (PPSN XII’12), C. A. Coello, V. Cutello, K. Deb, S. Forrest, G. Nicosia, and M. Pavone (Eds.). Lecture Notes in Computer Science, Vol. 7492. Springer, Berlin, 266--276. DOI:http://dx.doi.org/10.1007/978-3-642-32964-7_27
25. S. G. Nurzaman, Y. Matsumoto, Y. Nakamura, K. Shirai, S. Koizumi, and H. Ishiguro. 2010. An adaptive switching behavior between Levy and Brownian random search in a mobile robot based on biological fluctuation. In Intelligent Robots and Systems (IROS’10). IEEE Press, 1927--1934. DOI:http://dx.doi.org/10.1109/IROS.2010.5651671
26. J. Oyekan, H. Hu, and D. Gu. 2010. Exploiting bacterial swarms for optimal coverage of dynamic pollutant profiles. In 2010 IEEE International Conference on Robotics and Biomimetics (ROBIO’10), IEEE Press, 1692--1697. DOI:http://dx.doi.org/10.1109/ROBIO.2010.5723586
27. M. J. Plank and E. A. Codling. 2009. Sampling rate and misidentification of Lévy and non-Lévy movement paths. Ecology 90, 12, 3546--3553.
28. S. Poduri and G. S. Sukhatme. 2007. Latency analysis of coalescence in robot groups. In IEEE International Conference on Robotics and Automation (ICRA’07). IEEE Press, 3295--3300.
29. G. Ramos-Fernndez, J. L. Mateos, O. Miramontes, G. Cocho, H. Larralde, and B. Ayala-Orozco. 2004. Levy walk patterns in the foraging movements of spider monkeys (Ateles geoffroyi). Behavioral Ecology and Sociobiology 55, 3, 223--230.
30. I. Rhee, M. Shin, S. Hong, K. Lee, S. J. Kim, and S. Chong. 2011. On the Levy-walk nature of human mobility. IEEE/ACM Transactions on Networks 19, 3, 630--643. DOI:http://dx.doi.org/10.1109/TNET.2011.2120618
31. Russel Smith, et al. 2001 to 2010. Open Dynamics Engine (version 0.11). http://www.ode.org.
32. F. L. Schuster and M. Levandowsky. 1996. Chemosensory responses of Acanthamoeba castellani: Visual analysis of random movement and responses to chemical signals. Journal of Eukaryotic Microbiology 43, 150--158.
33. M. Shin, S. Hong, and I. Rhee. 2008. DTN routing strategies using optimal search patterns. In 3rd ACM Workshop on Challenged Networks (CHANTS’08). ACM, New York, NY, 27--32. DOI:http://dx.doi.org/10.1145/1409985.1409992
34. M. F. Shlesinger, B. J. West, and J. Klafter. 1987. Levy dynamics of enhanced diffusion: Application to turbulence. Physics Review Letters 58 11, 1100--1103. DOI:http://dx.doi.org/10.1103/PhysRevLett.58.1100
35. M. F. Shlesinger, G. M. Zaslavsky, and J. Klafter. 1993. Strange kinetics. Nature 363 (May), 31--37.
36. D. W. Sims, E. J. Southall, N. E. Humphries, G. C. Hays, C. J. A. Bradshaw, J. W. Pitchford, A. James, M. Z. Ahmed, A. S. Brierley, M. A. Hindell, D. Morritt, M. K. Musyl, D. Righton, E. L. C. Shepard, V. J. Wearmouth, R. P. Wilson, M. J. Witt, and J. D. Metcalfe. 2008. Scaling laws of marine predator search behaviour. Nature 451, 1098--1102.
37. G. M. Viswanathan, S. V. Buldyrev, Shlomo Havlin, M. G. E. da Luz, E. P. Raposo, and H. E. Stanley. 1999. Optimizing the success of random searches. Nature 401, 911--914.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles