Student Feature - Maxfield Comstock

By Invited Student Contributor
Print

headingfig

I am currently a PhD student studying Computational Science and Engineering (CSE) at the Georgia Institute of Technology, advised by Dr. Elizabeth Cherry. Prior to entering this PhD program, I worked as a software engineer in the healthcare industry. I received my undergraduate degree in Mathematics and Computer Science from Harvey Mudd College.

At the moment, my primary research focus is the study of the dynamics of large starling flocks known as murmurations. These flocks exhibit complex dynamic behavior such as wave propagation, coordinated turns, and consistent geometric patterns of tens of thousands of individuals, although the behavior required for individual birds to create such incredible group dynamics is still not well understood.

Existing flocking models typically aim to reproduce three types of behavior [1]:

  • Cohesion: Birds within a certain distance try to stay together
  • Separation: Birds stay far enough apart to avoid collisions
  • Alignment: Birds try to move in the same direction as the others

Additionally, experimental studies have reported many properties of observed bird flocks which have been used to determine model parameters. [2], [3] While many mathematical models have been able to capture this general behavior, few simulations have been run with the necessary number of birds due to the computational cost of large flock sizes. Additionally, few models have attempted to explain or reproduce murmuration patterns.

To better understand how the actions of individual birds affect flock behavior as a whole, I have implemented a simulation that supports thousands of birds flocking with real-time visualization and interactive parameter tuning. The simulation currently supports several interaction models. Its performance is achieved by taking advantage of the graphics hardware present on all modern computers to perform updates and visualization in parallel using the WebGL graphics library, which allows the simulation to run even on modest hardware in a web browser by simply visiting a website. The use of WebGL for simulations was introduced to me by Abouzar Kaboudian, who demonstrated its effectiveness on a variety of dynamical systems models. [4]

fig1
Figure 1: An example of a small simulated flock. The simulation is in 3D, so birds that appear smaller are
farther away.

The two main flocking models used to describe interactions between birds are a declarative model and a potential function model. In the declarative model, each bird is given its own cost function which it attempts to minimize. [5] Goals such as flying alongside other birds, staying level to the ground, and avoiding collisions are encoded as terms in the cost function, and the birds accelerate at each time step in the way that they predict will minimize this cost function. This model is decentralized, so the birds ignore the effect their actions will have on other birds, which results in a completely parallel optimization step.

The potential function model imposes a force for each neighboring pair of birds based on a potential function, which is minimized when the birds are a certain distance apart. This model is computationally faster than the declarative function approach as it does not require an optimization process to be performed at each update step. On the other hand, it requires other goals, such as velocity alignment and obstacle avoidance, to be modeled as additional forces.

Another challenging aspect of this project is determining neighbor relationships between the birds. In real starling flocks, birds typically interact with the six or seven nearest birds within a few meters, and the simulation replicates this behavior. However, this step requires the pairwise distances between the birds to be computed so that each bird can identify these neighbors, a computation that scales quadratically with the flock size. By making careful use of the parallel performance provided by GPU program, the simulation is still able to run quickly while finding neighbors at each time step, but for large flocks this step remains the performance bottleneck.

As the long term goal of this project is to reproduce murmuration behavior, the next steps for this project are to experiment with changes to the model that may enable murmurations. Some examples of such features are a predator bird that other birds will try to avoid, different modes of bird behavior, and various choices of potential function. Predator birds in particular are theorized as a possible cause of murmuration behavior. [6] I also plan to add metrics to help determine how close the flock is to successful murmuration behavior, although this task is challenging because there is no concise definition of murmuration, and such metrics may be difficult to compute efficiently as the simulation runs.

I would like to thank Korana Burke for inviting me to contribute to this issue of Dynamical Systems Web Magazine.

References

[1] C. W. Reynolds, Flocks, herds and schools: A distributed behavioral model, in Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, 1987, pp. 25–34.

[2] M. Ballerini, N. Cabibbo, R. Candelier, et al., Empirical investigation of starling flocks: A benchmark study in collective animal behaviour, Animal behaviour, vol. 76, no. 1, pp. 201–215, 2008.

[3] A. Attanasi, A. Cavagna, L. Del Castello, et al., Information transfer and behavioural inertia in starling flocks, Nature Physics, vol. 10, no. 9, pp. 691–696, 2014.

[4] A. Kaboudian, E. M. Cherry, and F. H. Fenton, Large-scale interactive numerical experiments of chaos, solitons and fractals in real time via GPU in a web browser, Chaos, Solitons & Fractals, vol. 121, pp. 6– 29, 2019.

[5] U. Mehmood, N. Paoletti, D. Phan, et al., Declarative vs rule-based control for flocking dynamics, in Proceedings of the 33rd Annual ACM Symposium on Applied Computing, 2018, pp. 816–823.

[6] A. J. King and D. J. Sumpter, Murmurations, Current Biology, vol. 22, no. 4, R112–R114, 2012.

Documents to download

  • feature(.pdf, 107.83 KB) - 141 download(s)
Categories: Student Feature
Tags:

Please login or register to post comments.

Name:
Email:
Subject:
Message:
x