Boids - Modeling And Understanding Emergent Behavior

Boids: Modeling and Understanding emergent behavior

Sudeep Pillai [email protected]

Background • Natural and often seen, yet so intriguing o o

Discrete birds, but an overall fluidic motion Magnificent synchronized behaviors

• Each bird dependent on each other o o o o

Based on local perception, they control themselves No awareness of global perspective Seems like a distributed control Is it intentional??

Intentional flocking • Formations o

Classic “Flying V” formation –

Reduce overall drag force as compared to flying alone

–

Upwash produces free lift allowing lower angle of attack Lead bird – Two flanking birds dissipate downwash

–

The “Flying V” formation • Reduced Energy expenditure o

Greater number cause further reduction in induced drag –

– – – –

Birds towards the middle gain considerable advantage Flanking birds gain free lift through upwash Reduced induced drag for birds being flanked Research – 70% more flight time, reduced heart rates Lead bird – Two flanking birds dissipate downwash

• Communication & Cooperation o

Mutual cooperation – Flock Rotations   

Evolved over time Efficient flying formation thereby increasing flight time Distribution of responsibility within flock during rotations

More reasons to flocking • Protection from predators o o

o

Statistically improved survival of gene pool from attacks Each creature has knowledge of its local perception Cry signals for predator warning increases reaction time

• Improved foraging o

Larger effective search patterns

• Advantages for social and mating activities

Emergent behavior • Formation of efficient flying order o o

o o o

Reduced Energy expenditure Effective communication among flock Improved knowledge and avoidance of predator Improved foraging Increased social and mating activities

• Emergence - Complex global behavior (flocking) arising from simple local interaction

Modeling emergent behavior • Do we model emergence in behavior or the result of emergence (i.e. flocking) ? Relatively trivial (using current technology) to create a model that simulates flocking (boids) o Less trivial to model emergence and tracing the path towards flocking o

• Accomplishing •

•

the former leads us to understanding the latter the latter is difficult, and very specific

Modeling boids • Basics o

Separation, Alignment, Cohesion

• Slight modifications o

o o

(In decreasing order of precedence)

Collision Avoidance – avoid collision with nearby flockmates Velocity Matching – match velocity with nearby flockmates Flock Centering – stay close to nearby flockmates

• Additional modifications Tendency towards goal, Limiting flock speed, Bounding workspace, Perching, Obstacle avoidance, Boid neighborhood o

The Algorithm flock_init_positions()

Main instance

Structure b (boids) FOR EACH BOID b b.position =25* [2*rand-1; 2*rand-1;2* rand-1]; b.velocity = [0;0;0]; END

Flock_init_positions () LOOP flock_draw_boids() flock_move() END LOOP

Rule 1 : Seperation PROCEDURE rule1(boid bJ) Vector c = 0; FOR EACH BOID b IF b != bJ THEN IF |b.position - bJ.position| < 100 THEN c = c - (b.position - bJ.position) END IF END IF END RETURN c  v1 END PROCEDURE

Rule 2: Velocity Matching PROCEDURE rule2(boid bJ) Vector pvJ FOR EACH BOID b IF b != bJ THEN pvJ = pvJ + b.velocity END IF END pvJ = pvJ / N-1 RETURN (pvJ - bJ.velocity) / 8  v2 END PROCEDURE

Moving boids – flock_move() PROCEDURE move_all_boids_to_new_positions() Vector v1, v2, v3 Boid b FOR EACH BOID b v1 = rule1(b) v2 = rule2(b) v3 = rule3(b) ….. ….. ….. b.velocity = b.velocity + v1 + v2 + v3 + …. b.position = b.position + b.velocity END END PROCEDURE

Rule 3: Flock centering PROCEDURE rule3(boid bJ) Vector pcJ FOR EACH BOID b IF b != bJ && |b.position - bj.position| < 8 THEN pcJ = pcJ + b.position END IF END pcJ = pcJ / N-1 RETURN (pcJ - bJ.position) / 100  v3 END PROCEDURE

The Algorithm (2) – Further additions Moving boids – flock_move() PROCEDURE move_all_boids_to_new_positions() Vector v1, v2, v3 Boid b FOR EACH BOID b v1 = rule1(b) v2 = rule2(b) v3 = rule3(b) ….. ….. ….. b.velocity = b.velocity + v1 + v2 + v3 + …. b.position = b.position + b.velocity END END PROCEDURE

Tendency towards goal – flock_tendency() PROCEDURE tend_to_goal(Boid b) Vector goal RETURN (goal - b.position) / 100  v4 END PROCEDURE

Predator interaction Same procedure as tendency towards goal, except a negative effect. Return –v (from tend_to_goal)  v6

Workspace bound – flock bound() PROCEDURE bound_position(Boid b) Integer Xmin, Xmax, Ymin…… Vector v IF b.position.x < Xmin THEN v.x = 10 ELSE IF b.position.x > Xmax THEN v.x = -10 END IF ….. .... Return v  v5 END PROCEDURE

FLOCK LEARNING Fitness functions being iteratively manipulated based on behavior needs FOR EACH BOID b v1 = c1*rule1(b) v2 = c2*rule2(b) v3 = c3*rule3(b) ….. b.velocity = b.velocity + v1 + v2 + v3 + …. b.position = b.position + b.velocity END

Limiting Speed – flock_limitvel() PROCEDURE limit_velocity(Boid b) Integer vlim Vector v IF norm(b.velocity) > vlim THEN b.velocity = (b.velocity/|b.velocity|*vlim) END IF END PROCEDURE

Other possibilities • Anti-flocking o o

Dispersion of flock due to predator Negating flock centering almost solves the problem

• Other behaviors Negating separation – Boids run into each other o Negating velocity matching – Boids have semi-chaotic oscillations o

• Different permutations of different behaviors with different fitness functions not necessarily modeling flocks realistically

Optimization • Trial and error and manual tweaking of parameters using GAs o o

Flocks can be tuned to exhibit interesting behavior Practical application may be limited

• Particle Swarm Optimization (PSO) o o

o

Shares evolutionary computation techniques such as GA Unlike GA, it has no evolution operators (crossover, mutation) Strategy 

  

Initialized with random group Closest bird to food leads the flock Solution to the optimization is a single bird, not a group Each bird‟s fitness is re-evaluated and optimized

Simulation

Future work • Modeling from the perspective of the bird o o

o

Model effects of other birds that are in its view (local) Model effects of aerodynamics (CFD) Does it support the “Flying V formation”?

• Implementing highway traffic based on distributed behavior control o

o o

Simple to implement Highly reliable Energy efficient

My thoughts • Several models and techniques have been developed o o

Some based on the behavior of flocks Some based on optimizing a specific task

• Similar to how we think of evolution, have flocks „emerged‟ completely? Flocking in groups can be beneficial, as is evident. Are we in a transitional phase? Or will they „emerge‟ further to optimize flocking behavior? o Can we predict of any possible optimizations they may possibly undertake? o