Transcript Behaviors22c196F03_1

Behavior
Autonomous Characters
 Acknowledgement
Much of this material is taken from the work of Craig
Reynolds. He maintains a web pages including a rich
source of material of steering behavior and the
consumate source on flocking.
Also see:
Steering Behaviors For Autonomous Characters
by Craig Reynolds
Autonomous Characters
 Self-Directed
characters
"puppets that pull their own strings" -Ann Marion

Situated
Live in a world shared by other entities

Embodied
Physical manifestation (virtual)

Reactive
instinctive, driven by stimulus
 Improvisation,
life-like behavior
Emergent Behavior
 The appearance of consistent global behavior
from a set of local rules enforcing independent
constraints.
 Emergent group behavior is the appearance of
coordinated collective behavior of many
individuals from individual behaviors based on
independent, local interactions.
Emergent Misbehavior?
 Permits modular development of complex
behaviors
 Hard to predict interactions among rules
•
•
Sometimes surprising and undesirable behaviors
appear in new circumstances or when new rules are
added.
Hard to debug.
Three-Tier Hierarchy
 Action
selection
goals and strategies
“What to do”
 Steering
guidance / motion control
“How to do it”
 Locomotion
movement generation
“Getting it done”
Cowboy Analogy
 Action
selection
Trail boss: “Fetch that stray.”
 Steering
Cowboy: “Giddy-up, that away.”
 Locomotion
Horse
“Wilbur!”
Flocks in Film
 1987: Stanley and Stella in: Breaking the Ice, (short)
Director: Larry Malone, Producer: Symbolics, Inc.
 1988: Behave, (short)
Produced and directed by Rebecca Allen
 1989: The Little Death, (short)
Director: Matt Elson, Producer: Symbolics, Inc.
 1992: Batman Returns, (feature)
Director: Tim Burton, Producer: Warner Brothers
 1993: Cliffhanger, (feature)
Director: Renny Harlin, Producer: Carolco.
 1994: The Lion King, (feature)
Director: Allers / Minkoff, Producer: Disney.
Flocks in Film
 1996: From Dusk Till Dawn, (feature)
Director: Robert Rodriguez, Producer: Miramax
 1996: The Hunchback of Notre Dame, (feature)
Director: Trousdale / Wise, Producer: Disney.
 1997: Hercules, (feature)
Director: Clements / Musker, Producer: Disney.
 1997: Spawn, (feature)
Director: Dipp₫, Producer: Disney.
 1997: Starship Troopers, (feature)
Director: Verhoeven, Producer: Tristar Pictures.
 1998: Mulan, (feature)
Director: Bancroft/Cook, Producer: Disney.
Flocks in Film
 1998: Antz, (feature)
Director: Darnell/Guterman/Johnson, Producer: DreamWorks/PDI.
 1998: A Bugs Life, (feature)
Director: Lasseter/Stanton, Producer: Disney/Pixar.
 1998: The Prince of Egypt, (feature)
Director: Chapman/Hickner/Wells, Producer: DreamWorks.
 1999: Star Wars: Episode I--The Phantom Menace, (feature)
Director: Lucas, Producer: Lucasfilm.
 2000: Lord of the Rings: the Fellowship of the Ring (feature)
Director: Jackson, Producer: New Line Cinema.
Motor Control
 Steering Force
Integrate to determine acceleration


Thrust – determines speed
Lateral Steering Force – determines direction
Boid Object Representation

Point Mass Vehicle
Mass
 Position
 Velocity
 Orientation
 Constrained to align with velocity

 Force
and Speed Limits
(No moment of intertia)
Euler Integration
acceleration = steering_force / mass
velocity = velocity + acceleration
position = position + velocity
Seeking and Fleeing
 Aim towards target
Desired_velocity = Kp (position – target)
Steering = desired_velocity – velocity
Seeking and Fleeing
Applet (Reynolds)
Pursuing and Avoiding
 Target is another moving object
 Predict target’s future position
 Scale prediction time, T, based on distance to object, Dc
T=Dc
Pursuing and
avoiding applet
(Reynolds)
More Behaviors
 Evasion
Like flee, but predict pursuer’s movement
 Arrival
Like seek, but step at target
Applet (Reynolds)
 Obstacle Avoidance
1. Repulsive force
2. Aim to boundary
3. Adjust velocity to be perpendicular to surface
normal
Flocking Behaviors
 Interactions among
members of a group
 Local neighborhood
Separation: Boid Avoidance
Alignment
Aggregation
Leader Following
 Based on arrival
 Target is behind leader
 Clear leader’s front
 Separation avoids
crowding
 Applet (Reynolds)
Arbitration of Competing Demands
1. State Machines


Context dependent selection
Problem: combinatorial explosion
2. Winner Take All


Choose highest priority goal
Problems: dithering, fairness, and tunnel vision
3. Blending


Combine output (e.g. sum, average, min, …)
Problem: combination may satisfy no one
Flocking Demos
 Flocking Applet (Craig Reynolds)
 Fish Schooling (Steve Hughes)
 Beach House (Ishihama Yoshiaki )
For more demos see Reynolds “Boids in Java”
Do People Flock?
Social psychologist’s
report the people tend
to travel as singles or
in groups of size 2 to
5.
“Controlling Steering Behavior for Small Groups of
Pedestrians in Virtual Urban Environments”
Terry Hostetler, Phd dissertation, 2002
Characteristics of Small Groups
 Proximity
 Coupled Behavior
 Common Purpose
 Relationship Between
Members
Moving Formations
 Pairs:
Side by side
 Triples: Triangular shape
Stationary Formations
Moving pair approaches
stationary triple
Stationary quintuple formed
Locomotion Model for Walking
 Two Parameters
 Acceleration



Increase/reduce walking speed
Combination of step length and step rate
Turn


Adjust orientation
Heading direction for forward walking
Action Space
Accelerate
Turn Left
Accelerate
No Turn
Accelerate
Turn Right
Coast
Turn Left
Coast
No Turn
Coast
Turn Right
Decelerate
Turn Left
Decelerate
No Turn
Decelerate
Turn Right
Distributed Preference Voting
 Seek best compromise through democratic voting
 Delegation of voters: Constraint Proxies
 Proxies vote on every possible value of control variable
 (Weighed) votes are tallied
“Some citizens are more equal than others”
(Who said life was fair?)
 Winning cell represents best compromise
Bias towards incumbents to reduce dithering
(Now this is REAL politics)
Vote Tabulation
Pursuit
Point
Tracking
Inertia
1.0
Maintain
Target
Velocity
Avoid Peds
Maintain
Formation
1.0
Avoid
Obstacles
1.0
4.0
Centering
2.0
5.0
2.0
Electioneer
Winning Cell
A Group of Two Following a Path
Pursuit Point
Tracking
-1.0 -1.0 +1.0
-1.0 -1.0 +1.0
-1.0 -1.0 +1.0
Maintain
Formation
+1.0 +1.0 +1.0
-1.0 -1.0 -1.0
-1.0 -1.0 -1.0
walkway
axis
pursuit
point

1.0
2.0
+1.0 +1.0 +3.0
-3.0 -3.0 -1.0
-3.0 -3.0 -3.0
Election for ped 1

ped 1
Winning vote =
Accelerate/Turn Right

ped 2
Avoiding an Obstacle -- Trajectory
walkway axis
walkway axis
ped 1
ped 2
Small look-ahead distance
ped 1
ped 2
Large look-ahead distance
Interaction Between Pairs -- 1
Interaction Between Pairs -- 2
Interaction Between Pairs -- 3
Motion Control Through Optimization
 Space-Time Constraints
a great place to start is the Witkin and Kass SIGGRAPH paper
Spacetime Constraints
Andrew Witkin and Michael Kass,
SIGGRAPH, V. 22, N. 4, pp. 159-168, 1988.
(See me for class notes)
Legged Motion
 Statically Stable Walking
 Dynamically Stable Running
Legged robots that balance
by Marc H. Raibert (1986)
ISBN:0-262-18117-7
Also: Legged Robots
by Marc Raibert, CACM, V. 6, N. 29, pp. 499-514
June 1986,
(See me for class notes)