Copyright © 2014 by Intelligent Systems Laboratory, Computer Science Department, Technion - Israel Institute of Technology, Haifa 3200003, Israel. All rights reserved


TheGrue.org

MARS Flock

f11V-Shape Flocking

Carried out Elad Leibovitz and Danny Albocher.
Guided by Noam Gordon.
Supervised by Prof. Alfred M. Bruckstein.

In this project, we investigate the properties of a flock of birds in the fimiliar V formation. We study the considerations a single bird applies while finding its place in the formation. We use these presumable considerations to implement an algorithm for a single bird in the flock, and examine the outcome under various assumptions when putting several birds together. In order to imitate reality as much as possible, each bird is unaware of its friends' decisions, and is unable to communicate with them. There is no "centeral brain" controlling all birds, and each has to make a decision using very limited and noisy sensors.

 

HARDWARE 

The algorithm is implemented on Lego Mindstorm. Therefore, our inputs from the enviroment and movement capabilities are limited to the following:

Light Sensor - providing us with an integer number, indicating amount of light sensed.
Odometer - a unit that measures rotation cycles.
Engines.
Mini light-bulb system.
As described in the document (link below) we build our robots using the above items, and a "brain" system (the Mindstorm RCX unit) programmed in C. The robot vision system is based on a rotating light sensor, and mini light bulb system, trackable by other robots, as shown in the image below:

Image 1 - Lego Robot

  

THE ALGORITHM

Limited to the above inputs, we are able to map the space around the robot into slices, and measure light in each slice. However, we are not able to get a good estimation of the distance between two robots. Therefore, our algorithm can not be strongly based on distances between robots.

We summarize the algorithm here according to our understanding of the birds consideration, with the limitations mentioned above. The robot scans his inviroment and finds the closest robot to follow. However, in order to create and maintain the V formation, the robot examines the location of this robot, and acts as follows:

Image 2 - The different decision zones

 

  • The first area, very close to the robot, and in a small angle in front of it (Image 2) is the dangerous zone, and simply moving forward might result in collision. The robot tries to avoid having another robot there, by turning away from it and slowing down.
  • The second area, not in immediate course to collision is the view blocked zone, and having a robot there should be avoided. This is done by speeding up a bit.
  • The third area, at approximately 45 degrees from the robot's front is the good zone, and having a robot there helps improve aerodynamic efficiency and does not block the view. Maintaining this possition is wanted.
  • The fourth area, mostly at the sides and hardly in front of the robot is the unhelpful zone. Having a robot there does not helps improve aerodynamic efficiency and therefore the robot should slow down to let his friend enter his good zone.

Additional information and details can be found in the project document below.

 

LEGO IMPLEMENTATION

Image 3 - Robot FlockThe algorithm is finally implemented using the Lego Mindstorm set. It required some tuning but eventually we came out with fine results, as can be seen in the following videos:

 

 

 

 

 

 

 

 

SOURCES

The project document can be found here (MS doc, 4.6MB, Hebrew).

The NetLogo source code can be found here.

The C source code for the Lego RCX unit, can be found here.