Motion Planning and Control of a Swarm of Boids in a 3-Dimensional Space

Authors: Bibhya Sharma, Jito Vanualailai, Jai Raj

Abstract:

In this paper, we propose a solution to the motion planning and control problem for a swarm of three-dimensional boids. The swarm exhibit collective emergent behaviors within the vicinity of the workspace. The capability of biological systems to autonomously maneuver, track and pursue evasive targets in a cluttered environment is vastly superior to any engineered system. It is considered an emergent behavior arising from simple rules that are followed by individuals and may not involve any central coordination. A generalized, yet scalable algorithm for attraction to the centroid and inter-individual swarm avoidance is proposed. We present a set of new continuous time-invariant velocity control laws, formulated via the Lyapunov-based control scheme for target attraction and collision avoidance. The controllers provide a collision-free trajectory. The control laws proposed in this paper also ensures practical stability of the system. The effectiveness of the control laws is demonstrated via computer simulations.

Keywords: Swarm, Practical stability, Motion planning.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1090508

References:

[1] A. Okubo. Diffusion and Ecological problems: Mathematical Models. Springer - Verla, New York, 1980.
[2] C. Blum and D. Merkle. Swarm Intelligence: Introduction and Applications. Springer - Verlag Berlin Heidelberg, Germany, 2008.
[3] E. Bonebeau. Swarm Intelligence: From Natural to Artificial Sytems. Oxford University Press, New York, 1999.
[4] A. Martinoli, K. Easton, and W. Agassounon. Modeling swarm robotic systems: A case study in collaborative distributed manipulation. International Journal of Robotics Research, 23(4):415–436, 2004. Special Issue on Experimental Robotics, P. Dario and B. Siciliano, editors. Invited paper.
[5] L. Edelstein-Keshet. Mathematical models of swarming and social aggregation. In Procs. 2001 International Symposium on Nonlinear Theory and Its Applications, pages 1–7, Miyagi, Japan, October-November 2001.
[6] E. Forgoston and I. B. Schwartz. Delay-induced instabilities in self-propelling swarms. Phys. Rev. E, 77(3):035203, Mar 2008.
[7] M. Dorigo, L.M. Gambardella, M. Birattari, A. Martinoli, R. Poli, and T. Stützle. Ant Colony Optimization and Swarm Intelligence: 5th International Workshop, ANTS 2006, Brussels, Belgium, September 4-7, 2006, Proceedings, volume 4150. Springer, 2006.
[8] Q.K. Pan, M. Fatih Tasgetiren, and Y.C. Liang. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. Computers & Operations Research, 35(9):2807–2839, 2008.
[9] J. Raj, B. Sharma, J. Vanualailai, and S. Singh. Swarm navigation in a complex environment. In International Conference on Mathematical, Computational and Statistical Sciences, and Engineering, WASET, Phuket, Thailand, Issue 72, pages 1157 – 1163, December 2012.
[10] G.J. Gelderblom, G. Cremers, M. de Wilt, W. Kortekaas, A. Thielmann, K. Cuhls, A. Sachinopoulou, and I. Korhonen. The opinions expressed in this study are those of the authors and do not necessarily reflect the views of the european commission. 2008.
[11] C. W. Reynolds. Flocks, herds, and schools: A distributed behavioral model, in computer graphics. In Proceedings of the 14th annual conference on Computer graphics and interactive techniques, pages 25–34, New York, USA, 1987.
[12] C. W. Reynolds. Steering behaviors for autonomous characters. In Proceedings of Game Developers Conference, pages 763–782, Miller Freeman Game Group, San Francisco, California, USA, 1999.
[13] B. Sharma, J. Vanualailai, and A. Prasad. Formation control of a swarm of mobile manipulators. Rocky Mountain Journal of Mathematics, 41(3):909–940, 2011.
[14] H. G. Tanner, A. Jadbabaie, and G. J. Pappas. Stable flocking of mobile agents, part I: fixed topology. volume 2, pages 2010–2015, 2003.
[15] A. Mogilner, L. Edelstein-Keshet, L. Bent, and A. Spiros. Mutual interactions, potentials, and individual distance in a social aggregation. Journal of Mathematical Biology, 47:353–389, 2003.
[16] V. Gazi and K.M. Passino. Stability analysis of social foraging swarms. In IEEE Transactions on Systems, Man and Cybernetics - Part B, volume 34(1), pages 539–557, 2004.
[17] V. Lakshmikantham, S. Leela, and A. A. Martynyuk. Practical Stability of Nonlinear Systems. World Scientific, Singapore, 1990.
[18] E. W. Justh and P. S. Krishnaprasad. Equilibria and steering laws for planar formations. Systems & Control Letters, 52(1):25 – 38, 2004.
[19] David S. Morgan and Ira B. Schwartz. Dynamic coordinated control laws in multiple agent models. Physics Letters A, 340(1-4):121 – 131, 2005.
[20] V. Lakshmikantham, V. M. Matrosov, and S. Sivasundaram. Vector Lyapunov Functions and Stability Analysis of Nonlinear Systems. Kluwer Academic, Dordrecht / Boston / London, 1991.