Transcript Flocking and Group Behavior

Flocking and Group Behavior
Brian Salomon
Papers
• Reynolds, C.W. Flocks, Herds, and Schools:
A Distributed Behavioral Model. Computer
Graphics, 21(2):25-34,1987.
• Tu, X., and Terzopoulos, D. Artificial Fishes:
Physics, Locomotion, Perception, Behavior. In
Computer Graphics: Proceedings of
SIGGRAPH 94, 43--50, 1994.
Reynolds
Birds
Motivation
• Flocks are interesting because
– Overall fluid movement from discrete actors
– Emergent Behavior
• Purpose
– Higher level animation
– Automatic constraint satisfaction
Boids
• Bird-oid
• Oriented particles
• Rendered as a geometric shape
• Independent computation: “distributed”
Movement
• Coordinate System travels with boid
y
z
x
• Intermittent translation and rotation about X and Y, not
a real flight model, no notion of lift, gravity
• Speed may not exceed certain limit through viscous
damping, acceleration may not exceed fraction of max
speed.
• Banking, keeps negative Y pointing in direction of
acceleration (including gravity)
Flocking
• Reason for flocking
– Predator protection
– Finding food
– Mating opportunities
• Flocking in nature is scalable
– Schools of fish 17 miles long with millions of
fish
– Implies O(1) complexity
Simulated Flocking
• Three behaviors
– Collision Avoidance (other boids and
obstacles)
– Velocity Matching
– Flock Centering (move towards
centroid of neighbors)
• Algorithm is O(N2). More on this
later.
Diagrams from Craig Reynolds’ boids page
Behaviors
• Each behavior produces a normalized
vector and an importance [0,1]
• Strict priority order as opposed to
averaging
• Once magnitude is used up subsequent
behaviors have no say
Simulated Flocking, cont’d
Flocks may split when obstacle
encountered, but may not rejoin
– Not realistic (more like fish in murky water)
– Actual birds use long range vision:
Rate of propagation of maneuvers can be as high as
3 times startle reaction time
Perception
• Complete knowledge led to unrealistic behavior.
Flocking requires locality.
• Boid surrounded by a zone (sphere) of
sensitivity. Specified by two parameters, radius
and exponent (1/rn falloff up to rmax).
• Found n=1 was unnatural but n=2 worked well.
Vague notion of gravity vs spring, seems like
hackery
Scripting, “Going Z for the Winter”
• Want more control
• Add a point of attraction or direction of
movement
– Can be position dependent
– Can only apply to certain boids
– Can change over time
Environmental Obstacles
• Don’t want simple repulsion because it is OK
to be near obstacles, just don’t want to fly at
them.
• Algorithm:
– Look along Z for obstacles
– If found find nearest silhouette point and add 1 body
length, use this radial vector for collision avoidance
• Works for obstacles that are spheres, cylinders,
planes, boxes
Complexity
Described algorithm is O(N2) but:
– Treating each boid as a separate computer
changes complexity to O(N)
– Could use spatial decomposition to achieve
O(1)
Results
Some Applets:
http://www.red3d.com/cwr/boids/
http://members.ozemail.com.au/~dcrombie/project/applet.html
Tu and Terzopoulos
Fish
Motivation
• Schooling and other behaviors
– Eating
– Wandering
– Mating
• Memory
• More accurate Perception
• Physically based motion
Fish Model
• 23 Nodes, 91 Springs, 12 Contractible Springs
diagram from the paper
Physical Simulation
xi(t)=[xi(t), yi(t), zi(t)] v(t)=dx/dt a(t)=d2x/dt2
Si,j ~ spring between nodes i and j
li,j ~ resting length
ci,j ~ spring constant
fsi,j ~ force from spring Si,j on node i, fsj,i= -fsi,j
ri,j=xj(t)-xi(t)
ei,j=|ri,j|-li,j
fsi,j=ci,jei,j(t)ri,j/|ri,j|
Physical Simulation, cont’d
mi(d2xi/dt2) + i(dxi/dt) – wi=fwi
fwi ~ external forces
wi ~ sum of spring forces
Sparse Matrix, integrated using Implicit
Euler.
External Forces for Swimming
• When fish swings tail left to right water is
displaced. Moving water applies force to tail
proportional to volume of water displaced.
• Instantaneous force is proportional to
-∫s(n·v)nds
s ~ surface
v ~ relative velocity of surface to water
n ~ surface normal
• Approximate by triangulating surface with
vertices at nodes. Use f=min(0, -A(n·v)n) and
give 1/3 force to each node of triangle. A =
triangle area.
Muscles
• Contract resting length (li,j from previous
slide) up to lmini,j
• To swim contract one side while relaxing
other in periodic manner
• To turn contract one side sharply and
then slowly relax
• There are three muscle sections with four
muscles each. Swimming uses front two
groups, turning uses back two.
Motor Controllers
• According to Paper only 3 motor controllers (Swim,
Turn-Left, Turn-Right).
– move muscles by specifying amplitude and frequency for two
muscle sections to generate muscle movements described on
previous slide
– For Swim empirically found maximum speed parameters and
specify rest in terms of max
– For turn found params for 30 °,45 °,60 °,90° turn. Interp for
turns in between these values. Multiple turns for greater than
90° .
• But, next section talks about using pectoral fins for
braking, rising, etc. No mention of how this fits into the
controllers. Presumably these are used by the swim
controller.
Perception
• Vision
– Cyclopean
– solid angle of 300
– Lookup properties of visible objects.
– Access to shading information
– Average whole picture for “light” perception
– Effective radius determined by murkiness
• Temperature
Mental State
Three functions determine the mental state
of a fish
• Hunger:
H(t) = min[1-ne(t)R(∆tH)/,1]
– ne(t) ~ amount of food eaten
– R(x) = 1 – p0x
po ~ rate of digestion
– ∆tH ~ time since last meal
–  ~ appetite
Mental State, cont’d
• Libido
L(t) = min[s(∆tL)(1-H(t)), 1]
– s(x) = p1x
p1 ~ libido constant
– H is hunger from previous slide
– ∆tH ~ time since last mating
• Fear
F(t) = min[Do/di(t), 1]
– Do = 100
– di(t) = distance to visible predator i
diagram from paper
Intentions
Focuser selects target of intention if necessary
Behavior
• Intentions generate behaviors
• Behaviors use muscle controllers
• Behaviors:
–
–
–
–
–
–
–
–
avoiding-static-obstacle
avoiding-fish
eating-food
mating
leaving
wandering
escaping
schooling
• Some have sub-behaviors (chase-target sub-behavior of
eating-food)
Schooling
Results
http://mrl.nyu.edu/~dt/animat-vision/
Questions/Comments?