Transcript Local Dynamics Models for Crowd Simulation

Local Dynamics
Models for Crowd
Simulation
Yeh, Hengchin
Outline
Introduction
 Optimal Velocity Model
 Helbing’s Model and Extensions
 Rule Based and Others
 HiDAC in More Detail
 References

Introduction– Definition

Narrow
 Helbing’s
social forces.
Introduction– Definition

Narrow
 Helbing’s

social forces.
Broad
 Forces
 Change
of positions an velocities
 According to local environment
 Everything not Global (planning, navigation
and so on)
Introduction– Design flow

Observation
 Choose
the macroscopic phenomena you
want to reproduce.
Introduction– Design flow

Observation
 Choose
the macroscopic phenomena you
want to reproduce.

Design the form of (microscopic) forces.
 Highly
arbitrary and heuristic.
 Analogous to physics.
Introduction– Design flow

Observation
 Choose
the macroscopic phenomena you
want to reproduce.

Design the form of (microscopic) forces.
 Highly
arbitrary and heuristic.
 Analogous to physics.
Simulation
 Fix the problems.

Introduction - Examples

Domain
 Roadmaps
 Cellular
automata
 Continuous space
 etc.

Methods
 Particle
dynamics and potential field
 Rule based, eg. flocking
 Special, eg. RVO.
CA: Very popular in
Statistical Physics (eg.
Physica A), but not in
Graphics
1D-Optimal Velocity Model (OVM)

From Transportation Science
 1D

traffic flow.
Imaging driving on highway:
A
car will keep the maximum speed with
enough the distance to the next car.
 A car tries to run with optimal velocity
determined by the distance to the next car.
 Safety distance
1D-OVM

Formula
 a:
How “fast” the car
wants to accelerate
to the desired speed.
 V: optimal (desired)
speed.
 b, c: constants
Distance to the next car
tanh? Any monotonic increasing
function with upper/lower bounds
suffice.
1D-OVM
Demo
 Phenomena: Congestion, phase transition

 The
uniform flow becomes unstable when a <
2 V(L/N).
 Intuition: lag in response time magnifies
fluctuations.
2D-OVM

Similar ideas

For
 Only

attraction
θ
For
 Both
attraction and repulsion
2D-OVM

_
 Anything
that models
(approximates) the anisotropic
nature of human perception /
reaction.

For example:

Self driving force

Range of consideration
θ
2D-OVM

Similar phenomena
 Lane
formation in low
density.
 Congestion in high
density
Helbing’s Forces

[Helbing and Molnar 1995]


[Helbing et al. 2000]





“The paper”, published in Nature.
[Helbing et al. 2002]
[Lakoba and Kaup 2005]
[Helbing et al. 2005]
[Helbing et al. 2007]


Social force model for pedestrian dynamics
Crowd turbulence: the physics of crowd disasters
[Yu and Johansson 2007]

Modeling Crowd Turbulence by Many-Particle Simulation
Helbing 2000

Main equation
Add features or modify this equation.
 Example:

 HiDAC
 AERO
Self-Driven Force

First term
 Deviation
of current velocity from preferred velocity
 p: panic parameter; (in)dependence
 : preferred velocity; “own” velocity.

: average velocity within a radius around the
agent himself; “collective” velocity.
Self-Driven Force

First term
 Deviation
of current velocity from preferred velocity
 p: panic parameter; (in)dependence
 : preferred velocity; “own” velocity.

: average velocity within a radius around the
agent himself; “collective” velocity.

Compared to OVM
 No
distance dependence for preferred velocity.
 No concept of safety distance. Can be added.
Interactive Forces

Second Term
Interactive Forces

Social force:
 Baseline,
 A,
B, dij
almost in every paper
Interactive Forces

Pushing force:

Kernel

k, elasticity, spring constant
Interactive Forces

Frictional force – relative velocity

But no static friction, alternative
Agent-Obstacle
Force

Analogously

Or, again
Summary of Helbing 2000
The social force do not have a physical
source.
 Body force and sliding friction forces do.

 But
rather simple
 no ground friction
 no dynamic constraint

Details; Qualitative vs quantitative.
Summary of Helbing 2000

Phenomena
 Nick
talked about them
 Pressure buildup (Pressure discussed later)
 Clogging at bottleneck
 Jamming at widening
 Faster is slower
 Inefficient use of alternative exits (due to
panicking and herding)
Lakoba and Kaup 2005

Title: Modifications of the Helbing-MolnárFarkas-Vicsek Social Force Model for
Pedestrian Evolution
 HMFV
later on.
 Fix some counterintuitive results of HMFV,
 by changing numerical values;
 as well as modifying the model
Problem 1 of HMFV

Overlapping:
 HMFV
allows overlapping, it
NEEDS overlapping for
pushing forces and frictional
forces.
 But
no limit.
Overlapping

There should be a “core”
which is not penetratable.
Overlapping
There should be a “core”
which is not penetratable.
 Maximum overlapping or
squeezing

 Smax,
say, 20 % of the
radius.
 Collision Elimination
Methods for Handling Overlapping

HMFV: use high k in
In order to prevent overlapping 
makes humans very stiff springs or bouncy
balls.
 5cm  5000 N, or ~ 7G
 Problem:

Potential Barrier:
 for
 approaches
infinity as dij  Rij – 2 Smax
Potential Barrier

Numerically, Stiff equation
 Since
f
unbounded, very large.
 In order to be stable, (i.e. x not “blowing off”)
only very small time step can be used.

Runs forever.
 Implicit

integration is expensive too
Lakoba & Kaup – OEA
Overlap-Eliminating Algorithm
(OEA)
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
n= total number of pedestrians; count = 0;
While (overlapping occurs && count < n)
Find the most overlapped pedestrian pi.
If (pi intersects with the wall)
Move pi away from the wall
set vi,n  0; vi ,t stays the same.
make pi “stationary”
end if
Move all pj’s away from pi.
Set vj  vi
end while
OEA


Set vj  vi this only
works for uni-goal
system, such as egress.
Still no guarantee.


But probability very low.
Can we do better?

What if the only collision
free configuration is a
“packing” one?
 Finite packing? HARD
OEA time step

Determine the maximum allowable time
step by letting each pedestrian to move

No less than Smax.
 Can be even bigger if all (obstacles and
pedestrians) are at least d > Smax apart.
OEA time step

OEA is a physical
process. Need time.

Deduce the needed
time from change of
momentum and
feasible “force”.
time left for
other physical
processes
fOE

fOE

a free parameter, how
hard he can bounce
away from overlapping
objects.
 Related to skeleton
elasticity, c.f. k for
“muscle” elasticity.
Problem 2 of HMFV

Too small B
8
cm ~ 1.4G
 or say, 50 cm for
less then a weight of
a baseball.
 Consider walking
toward a wall.

Too bouncy.
 Oscillation
expected.
Density Effects of the Social Force

Since B is larger now
 need
to suppress the
social repulsion as the
person approaches a
dense crowd density is
high.
K0 =0.3
K1 >1
Normalized density
D0 diameter of pedestrian
Orientational Dependence of the
Social Force
Face-to-back: W1
 Give extra weight to
Face-to-face: W2

Orientational Dependence of the
Social Force
Face-to-back: W1
 Give extra weight to
Face-to-face: W2

Helbing ‘05


Add some more features
Impatience

: average speed into
the desired direction of
motion.
 Long
waiting times decrease
the actual velocity compared
to the desired one, which
increases the desired velocity
More features
Fluctuation
 Orientational effects

0.2
0.8
[Helbing ‘05] Interesting
Suggestions
[Helbing ‘05] Interesting
Suggestions
What is left in this lecture
 Examples
of method-specific local dynamics
in AERO
 in Autonomous Pedestrians [Shao and
Terzopoulos ‘05]

 HiDAC

in more details
following Nick’s lecture.
Local Dynamics in AERO
Local Dynamics in AERO

New face: Roadmap force
field
lk
p
Autonomous Pedestrians

Rule-based.
 local
rules
 A B D E F: collision
avoidance.
 C Modified Potential field. To
maintain separation in a
moving crowd.
Autonomous Pedestrians

Temporary Crowd:
 Moving
in similar directions
 Situated within a parabolic
region in front of H.
 ri repulsiveness
 di distance
fi
to Ci
di
HiDAC

Position for agent i is
Avoidance Forces
f & F: not force. but unit directional vector.
 Used to “direct” the speed (scalar).

Avoidance Forces





desired attractor (FiAt)
walls w (FwiWa)
obstacles k(FkiOb) and
other agents j (FjiOt)
trying to keep its previous direction of
movement to avoid abrupt changes in its
trajectory (FiTo[n −1]).
Avoiding Obstacles
Rectangle of influence


Perpendicular to dki
or nw
Tangent.
Avoiding Agents



Tangent
distance factor
orientation factor
Repulsion Force

Recall

Dimension: displacement
Use: directly move the agent out of the
overlapping situation
: 0.3 priorities between agents and walls or
obstacles.


Repulsion Force (Displacement)
Note




Unlike Helbing’s model. More like RVO.
Directly manipulate velocities. No real forces.
Speed never “blows off”. Decide directions
mostly.
Stops and waits: next page.
Resolving Shaking

Stopping rule:
 If
others push against you
and you are not panicking,
you stop.
 To avoid deadlock, a timer
is set.
 alpha becomes zero: can
change position only if
pushed by others.
Resolving Shaking

Waiting rule:
 If
another agent j
walking in the same
direction falls within
the disk.
 Timer too.
 Until the condition no
longer holds.
Pushing

Waiting rule:
 If
another agent j
walking in the same
direction falls within
the disk.
 Timer too.
 Until the condition no
longer holds.
Panic

High level:
 Communication

Low level
 crowd
density goes up.
 pushing occurs frequently.
…
References

OVM




Social Force






A. Nakayama and Y. Sugiyama. “Two-Dimensional Optimal Velocity Model for Pedestrians and Biological
Motion”. AIP Conference Proceedings 2003;661:107
A. Nakayama and Y. Sugiyama. “Group Formation of Organisms in 2-Dimensional OV Model.” Traffic and
Granular Flow ’03 2005;399-404
A. Nakayama, Katsuya Hasebe and Y. Sugiyama. “Instability of Pedestrian Flow and Phase Structure,”
Physical Review E 2005;71:036121
D. Helbing, I. Farkas, and T. Vicsek, "Simulating Dynamical Features of Escape Panic," cond-mat/0009448,
September 2000.
D. Helbing et al., "Self-Organized Pedestrian Crowd Dynamics: Experiments, Simulations, and Design
Solutions," Transportation Science, vol. 39, pp. 1-24, 2005.
T.I. Lakoba, D.J. Kaup, and N.M. Finkelstein, "Modifications of the Helbing-Molnar-Farkas-Vicsek Social
Force Model for Pedestrian Evolution," SIMULATION, vol. 81, pp. 339, 2005.
D. Helbing, A. Johansson, and H.Z. Al-Abideen, "Dynamics of crowd disasters: An empirical study," Physical
Review E, vol. 75, pp. 46109, 2007.
W. Yu and A. Johansson, "Modeling crowd turbulence by many-particle simulations," Physical Review E, vol.
76, pp. 46105, 2007.
Crowd Simulation in Graphics



W. Shao and D. Terzopoulos, "Autonomous pedestrians," Proceedings of the 2005 ACM
SIGGRAPH/Eurographics symposium on Computer animation, pp. 19-28, 2005.
N. Pelechano, J.M. Allbeck, and N.I. Badler, "Controlling individual agents in high-density crowd simulation,"
Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, pp. 99-108,
2007.
A. Sud et al, "Real-time navigation of independent agents using adaptive roadmaps," Proceedings of the
2007 ACM symposium on Virtual reality software and technology, pp. 99-106, 2007.