Boids: Modeling And Understanding Emergent Behavior - Ee 594 Final Paper

Sudeep Pillai

Boids: Modeling and understanding emergent behavior Introduction Flocking of birds has always been a spectacle to all, especially to ornithologists. It has been one of the most intriguing, yet natural behaviors that I’ve ever encountered and it can be hard to explain it just from its movement. Its magnificence lies in its fluidic motion, but its complexity is noticed in its synchronized behavior. Each discrete bird behaves based on its local perception; however, it is amazing how their interactions produce an overall fluid-like unified motion. What’s more interesting is that such behaviors occur even when the bird does not have a global perspective of its goal or movement. Such splendors in life give rise to several questions in behavioral psychology, distributed behavior control and many other fields including complexity. In this paper, I would like to address the notion of ‘emergence’ that is pertinent to flocking. Using this generalized theory, I have attempted to understand the behavior of birds in flocks and their reason to flock. This in turn allowed me to simulate a rather simple yet reasonably realistic model of how birds flock. Implementing such a simulation framework has also compelled me to look into different algorithms that have already been implemented and those that I’ve learnt from this class. Motivation Birds, in general, have always puzzled me. I’m amazed by how birds can so intelligibly interact with each other to strategize an efficient flying formation that benefits the flock as a whole. Their intricate maneuverability and their spectacular flocking behavior can be quite startling to many people when they are used to seeing the common phenomenon of birds hitting windows. Nevertheless, if birds have ‘emerged’ over the past years to fabricate an ingenious flying strategy, then how did they possibly do this with a low level of intelligence? My interest in this topic gives me a better understanding of distributed behavior models and allows me to pursue my career in autonomous vehicles and intelligent highway traffic where this idea may be relevant. The ‘Science’ of Flocking Even though several scientists have tried to reason the need to flock, it still remains uncertain why most birds flock. One reason towards flocking pertains to the need of each individual bird to reduce the drag force that it experiences compared to if it were flying alone. During flight, vortices generated at the wingtips of each bird produce an upwash that can be beneficial to a second wing flying behind and slightly above the first. A bird flying in this upwash region gains free lift allowing it to reduce its angle of attack, thereby decreasing the drag induced during forward thrust. The birds that flanks a bird ahead of it gains an advantage as it needs lesser energy to fly, allowing it to fly for a longer distance. A common misunderstanding is that the bird that leads the flock is at most disadvantage. This is not true since the reduced downwash that is dissipated by the two birds that flank it helps reduce the induced drag that it experiences. Thus putting both interactions into perspective, birds towards the middle gain considerable overall advantage over the other birds in the flock. The idea that a “V formation” is produced from such interactions is quite acceptable as each bird gains benefit from one another thereby reducing the overall expenditure in energy. This interaction brings another problem into play that the flock tackles ever so beautifully. Since the bird leading the flock tires the quickest, they drop out of the lead position and fall further back into one of the

formation lines. Another bird from further back rapidly takes charge and fills in the position as the lead. This sense of responsibility and teamwork is essential to an efficient flock and captures the essence of flocking mentality towards an ‘optimum energy solution’ i.e. the classic “flying V” formation for the whole flock. This behavior dictates striking similarity to Nash’s equilibrium where an ‘optimum solution’ is that which benefits both the individual and the group as a whole. Other reasons for flocking include improved communication amongst other birds, improved foraging, increased protection from predators and better social and mating activities. Flocking: A truly evocative example of emergence A fluid-like unified motion of several discrete birds that act based on their corresponding local perception is intriguing to many in the fields of behavioral psychology, distributed behavioral modeling etc. What’s even more interesting is that such global maneuvers benefit not only the individual, but the flock as a whole. Such motivation towards a more ‘optimum solution’ i.e. flying formation is also critical to understanding their behavior particularly pertaining to emergence. A similarity that arises with the comparison of flocks with the Prisoner’s dilemma is also interesting to comment on. If the birds chose to ‘betray’ other flocks by moving towards the middle of the flock, they would be hurting other birds and in turn hurting themselves. The birds however, for some reason that is unknown, keep order and cooperate with each other to produce an emergent behavior that is far more intelligent than any single bird. Dilemma in Modeling In order to model flocking, I see two distinct questions at hand. Do we model how the birds ‘emerged’ into flocks or do we analyze how the birds interact in a flock to produce a realistic model? Each of these paths has completely different methodologies that that may be crucial at understanding the deep meaning of emergence at the flocking level. Even though the latter question is relatively more trivial than the former, it paves a path for a deeper understanding of modeling emergence in flocking behavior and thus I chose to take on this path. Modeling Boids Modeling boids (simulated flocks) can be as trivial as defining a few governing rules that each bird must follow, and see how they interact with several of their kind to produce a unified distributed behavior. The three governing rules of separation, adhesion and cohesion, as described by Craig Reynolds in his paper [1], only take into account certain aspects of the physical world. However, to make boids as realistic as possible, there can be several modifications and additions to this framework. Some of the modifications that have been implemented include collision avoidance, velocity matching and flock centering in their decreasing order of precedence. Furthermore, several other desired features such as tendency towards a goal, limiting flock speed, workspace bounds, boid neighborhood, perching and obstacle avoidance can be implemented rather easily to generate more life-like behavior. In my drive towards simulating a lifelike model to predict flock behavior, I have been successful in implementing the first three additions. A rigorous pseudo code explaining the algorithm I implemented and that plan to implement is shown in Appendix A. Further additions may require a more involved algorithm to accomplish certain desired tasks. Flock learning, where the birds vary the influence of each rule over the course of the simulation can produce unanticipated results that may be beneficial in some way or the other. Some of these unanticipated results such as anti-flocking result from negating the rule of flock centering in turn bring us to another critical

issue. Can we possibly have different permutations of such different behaviors with different ‘influence’ terms? Questions such as these are yet to be explained and I hope to continue working on them given that I finally built a framework for modeling boids. Future Work As was evident from the video of my simulation, there exists a fluidic flow even with a few simple rules that govern each of the boids. Given the current modeling framework, it is also possible to optimize these behaviors to produce better results catering to a particular need. A typical implementation is related to foraging for food based on the Ant Colony Optimization [2] techniques (ACO) that have been modeled after ant behavior. Another technique that is closely related to ACO is the Particle Swarm Optimization (PSO) that share similar evolutionary computation techniques with that of GAs. The PSO algorithm looks for a single solution i.e. ‘a single bird’ that is closest to the goal and optimizes the solution by requesting the bird to lead the flock. The fitness function that each bird has is re-evaluated at each time step and optimized to produce best results. Another possible solution to realistically modeling of flocks could involve modeling a 3D perspective view of each boid and calculating its effects due to other boids and physics. This method, apart from being relatively complex, can be fairly expensive to compute. However, an alternative to this solution that could be more feasible involves projecting each of the effects of the boid onto a plane that is normal to the heading vector of each boid. This relatively a non-trivial but feasible method that could take into account of aerodynamics and flocking behavior to predict the formations that we see often in real life. Conclusions Most of the existing models and techniques that have been developed are based on our perception of how flocks behave and interact, while some others based on optimizing certain tasks such as food foraging. However, there has not been one model that reasonably predicts the realistic behaviors of birds in flocks. Some of the questions and concerns I’ve put forward may be never dealt with, but it doesn’t stop us from asking ourselves the question, ‘Have flocks emerged completely?’ If not, then, is the “flying V” formation a transitional phase in emergence that took ever so long to perfect that it may take even longer to come up with a more optimum formation? The transitional phase in the emergence of a flock can also be related to Conway’s glider where the transition function described produces a sequence of changes in pattern over successive time-steps. Similar to Conway’s glider, in the case of boids or flocks, the possibility of a spatially coherent pattern cannot be easily determined due to its vast number of non-linear interactions. The possibilities are endless, and we model based on what we perceive. It requires a combination of experiment, birdwatching in this case, and theory to discover and explain regularities. This implies that birds may have evolved and ‘emerged’ over time, they may truly have developed an emergent behavior of higher order intelligence; but can they ‘emerge’ further to produce even higher orders of intelligence given the endless possibilities.

References [1] Reynolds, C. W., “Flocks, Herds, and Schools: A Distributed Behavioral Model” at SIGGRAPH ‘87 [2] Kennedy, J. and Eberhart,R.C, “Swarm Intelligence”, Morgan Kaufman Publishers, 1994