The Boids and the Bees

(Leadership and Decision-Making in Animal Groups on the Move)

V. Hunter Adams (vha3@cornell.edu)

Introduction

When a bee colony grows too large, it divides in two through a process called swarming ). The queen and approximately half of the workers leave to establish a new colony, while the remaining workers and a daughter queen remain at the original site. The departing bees come to rest on a nearby tree while a remarkably small number of scouts search for new nesting locations. Each reports the distance and direction to a candidate site by performing a waggle dance. At first, the scouts may be visiting and deliberating over more than ten candidate locations. Over a few days, however, the number of candidate locations will reduce. [1]

missing
A swarm of honeybees (figure from [1])

It is tempting to assume that all of the scouts reach an agreement (i.e. come to consensus) before the colony takes flight to be guided by the scouts to their new home. Tom Seeley of Cornell showed that this is not the case! Instead, the colony will take flight when the scouts have reached a quorum. That is, when a sufficient number of the scouts agree, not necessarily all the scouts. Despite the fact that the colony may take flight with dissenting opinions about the direction it should travel, the colony will collectively select the location that has the quorum-number of scouts voting for it. [1]

In this laboratory exercise, we will implement a modified version of the Boids algorithm to model bees in flight. Then, we will give a configurable number of those bees a preferred direction of travel as described in Effective leadership and decision-making in animal groups on the move by Couzin, Krause, Franks, and Levin. We will conduct experiments to determine how many scouts are required to steer the colony, and compare our results to Couzin et al's mathematical results and Seeley's field measurements. Graduate students will be asked to implement dynamic weighting in their biased groups (as described in the Couzin paper). They will be asked to demonstrate collective consensus in their swarm. This is all demonstrated in the video below.

You are challenged to create the largest swarm that you can manage, subject to the constraint that the swarm must animate at 30 fps. This will require that you think about optimized arithmetic, rearranging the algorithm, parallelization strategies, and overclocking (among other things!).

This laboratory exercise combines the results from two articles:

4760 students will create a system that enables them to replicate the results shown in Figs 1-2 of the Couzin paper. 5730 students will be able to replicate all results from that paper.

Key concepts: Boids algorithm, fixed point arithmetic, computer animation, optimization, VGA, UART

Demonstration

Reading

Experience shows that students prefer these webpages short. For that reason, plese find the reading and background materials on the webpages linked below. Please note that the information in these readings will be critical for completing the lab.

Mathematical background

  • Boids algorithm: Boids is an artificial life program that produces startlingly realistic simulations of the flocking behavior of birds. We will be using a modified version of this algorithm to model bees in flight.
  • Effective leadership and decision-making in animal groups on the move: This paper, by Couzin, Krause, Franks, and Levin, describes the mechanism by which a small minority of hive members can steer the collective. It also describes the mechanism by which the colony chooses among multiple candidate nesting locations.

Engineering background

  • VGA driver: You will not be asked to implement a VGA driver, you will use the one described on this webpage. You will need to modify it if you want to overclock the RP2040.
  • Fixed-point arithmetic: To generate the largest possible swarm, you want for your arithmetic to be as fast as possible. Floating point is too slow. Fixed-point arithmetic allows for you to use integer arithmetic (which is way faster than floating point, on this architecture) while maintaining fractional resolution.
  • RP2040 datasheet: Sections on DMA, UART, Multicore, Timers, PIO
  • RP2040 C SDK guide: Same sections as above

Biological background

Beyond this lab

  • Honeybee Democracy: A book by Professor Seeley that discusses honeybee behavior in fascinating detail.

Weekly Checkpoints

Note that these checkpoints are cumulative. In week 2, for example, you must have also completed all of the requirements from week 1.

Week 1

  • Starting from this example, get one boid flying around on the screen. I recommend the following parameters for the boids algorithm:

    turnfactor: 0.2
    visualRange: 40
    protectedRange: 8
    centeringfactor: 0.0005
    avoidfactor: 0.05
    matchingfactor: 0.05
    maxspeed: 6
    minspeed: 3
    maxbias: 0.01
    bias_increment: 0.00004
    default biasval: 0.001 (user-changeable, or updated dynamically)

  • The boid should have randomized initial position (within margins) and velocity (within min/max speed limits)
  • Your boid may be represented as a pixel (drawn using the drawPixel routing) or as a circle or rectangle. I think 2x2 rectangles look nice, and are less expensive than circles.
  • Your animation should update at a constant frame rate 30fps (see example linked in first bullet)
  • The VGA display (or a serial terminal) should show the number of boids, the frame rate, and elapsed time in seconds
  • Finishing a checkpoint does NOT mean you can leave lab early!

Week 2

  • At least 10 boids flocking. This is enough to show that the algorithm is working, but you do not need to have your code optimized by week two.
  • Through a serial interface, you must be able to change the boundary conditions from a box, to top/bottom wrapping with configurable width, to top/bottom and left/right wrapping (see the demo video above).

Week 3

Write a ProtoThreads C program which does the following:

  • At reset, the program spawns as many boids as it can while maintainting 30fps animation rate. The program will use the following parameters for the flock of boids:

    turnfactor: 0.2
    visualRange: 40
    protectedRange: 8
    centeringfactor: 0.0005
    avoidfactor: 0.05
    matchingfactor: 0.05
    maxspeed: 6
    minspeed: 3
    maxbias: 0.01
    bias_increment: 0.00004
    default biasval: 0.001 (user-changeable, or updated dynamically)

  • The boids should have randomized initial position (within margins) and velocity (within min/max speed limits)
  • The boids may be represented as pixels, circles, or rectangles, as long as they are visible.
  • Your animation should update at a constant frame rate 30fps
  • Through a serial interface, the user should be able to modify:
    • The boundary conditions (box, top/bottom wrapping with configurable width, top/bottom & left/right wrapping)
    • The number of boids in each biased subset
    • The strength of the bias for each subset
    • [5730 students only] Enable/disable dynamic updating for the bias strength of each subset

Lab Report

Your written lab report should include the sections mentioned in the policy page, and:

  • A few cool photographs of your flock/swarm
  • A brief discussion of the emergent behavior that you saw when you added a biased group to your swarm. Please connect these observations to the results in the Couzin paper.
  • A heavily commented listing of your code

References

  1. Couzin, Iain D., et al. "Effective leadership and decision-making in animal groups on the move." Nature 433.7025 (2005): 513-516.
  2. Seeley, Thomas D., P. Kirk Visscher, and Kevin M. Passino. "Group Decision Making in Honey Bee Swarms: When 10,000 bees go house hunting, how do they cooperatively choose their new nesting site?." American scientist 94.3 (2006): 220-229.