Presented By

Glen Berseth

University of British Columbia

- What you see in the movies
- Not big crowds of ambient/stationary people

I've fallen, and I can't get up! from Dave Fothergill vfx on Vimeo.

- Situationally aware agent (locally)
- Active collision avoidance
- Has a GOAL (target location)

Uses Boids algorithm [Craig W. Reynolds, 1987]

- Video Games (e.g. Hitman Absolution, Warhammer online)
- Some character animation systems (MiArmy, MASSIVE)
- Research and analysis (SteerSuite, Menge)
- Data Driven Crowd analysis (Machine learning)
- Some Films (World War Z, LOTR

- Want to be able to simulate crowds of people
- In some situations it is unrealistic to use people
- Expensive to pay that many people to work together
- Maybe the desired performance may be exaggerated or unsafe
- Used for navigation of robotic systems (better behaviour)
- Airplane boarding (saves money, pedAir)
- How to make a good crowd simulation algorithm?

- The steering problem
- Some popular steering algorithms
- Issues with the disk model
- How can we compare steering algorithms
- What's next?

- Flocking
- Lane forming
- The Vortex
- Compression waves
- More?

- Sliding particle
- Configuration state \(q = \langle x, y, \dot{x}, \dot{y} \rangle \)
- Commonly internal to the steering model
- Preferred Velocity \(v_{pref}\)
- max speed \(v_{max}\)
- radius \(r\)
- neighbours \(a_{0} \ldots a_{n}\)
- waypoints \(p_{0} \ldots p_{m}\)

- Steering decision can be even simpler than simulation loop
- \(\langle x, y, \dot{x}, \dot{y} \rangle' = steeringAlgorithm(\langle x, y, \dot{x}, \dot{y} \rangle, \Delta t)\)

Assume steering algorithm has access to all other agents

Anyone used a steering algorithm before?

- Obstacle repulsion forces

[Helbing et al. 2000, Pelechano et al. 2007]

- Repulsive when agents almost collide

[Treuille et al. 2006]

- Convert the crowd to a density field
- For each group:
- Construct the unit cost field C
- Construct the potential φ and it’s gradient ∇φ
- Update the agent locations
- Enforce the minimum distance between people

- Keep velocity outside of Velocity Obstacle

[van den Berg et al. 2008]

- Velocity is average of velocity outside of obstacle and desired.

- Choose best velocity outside of union on RVOs

[Singh et al. 2011]

- Foot Skating
- Does not capture rigid body
- Limbs can intersect
- People are not circular

[Singh et al. 2011]

- How do we even compare these things?
- Why do we want to compare them?
- Defining what is good motion is a BIG problem.
- Which disks looks more realistic?

- Suite of steering benchmarks
- Consist of common steering benchmarks and new ones
- set of metrics that are independant of steering approach
- number of colissions
- total acceleration, distance traveled, time spent and energy

[Singh et al. 2009]

- Construct a subspace of possible scenarios
- What should this subspace consist of?
- More difficult scenarios
- Reference agent
- Force interaction
- Better metrics for comparison
- Coverage
- Time quality
- Distance Quality

[Kapadia et al. 2011]

- What do we gain by this?
- What can we do with this information?

- Each steering algorithm models the steering problem well
- Each algorithm has a number of parameters
- How do they affect the algorithms behaviour?
- Can we improve the algorithms?

[Berseth et al. 2013]

- We optimize the parameters (\(v\)) of a steering algorithm (\(A_{v}\))
- Over a test set \(T\) (representative set)
- For a user defined objective \(ƒ\)
- Important issue: do the optimized parameters generalize?

- Deficiency \(d\): percentage of scenarios failed
- Distance Quality \(q^{d}\): ratio of optimal distance to actual distance
- Time quality \(q^{t}\): ratio of optimal time to actual time
- Effort Quality \(q^{e}\): ratio of optimal bio-mechanical energy to actual [Guy et al. 10]
- Computational Efficiency \(e\): ratio of max desired computational time to actual.

- Normalize Metrics
- \(\mathbb{M} = \langle d, q^{d}, q^{t}, q^{e}, e \rangle\)
- Weighted sum
- \(f(A_{v},\textbf{w}) = \sum\limits_{m_{i} \in \mathbb{M} } w_{i} \cdot m_{i} , \sum\limits_{w_{i} \in \textbf{w}} w_{i} = 1\)
- Minimization
- \( \textbf{v}^{*}_{\textbf{w}} = \arg \min_{\textbf{v} \in \mathbb{V} } f(A_{v},\textbf{w})\)

Relative percent improvement over default

- We want crowds to look like human crowds
- Ground Truth Similarity: Statistical similarity to recorded crowd data [Guy et al. 2012].

- For every set of weights we need to do an optimization?
- Can we compute a mapping from weights \(\mathbb{W}\) to parameters \(\mathbb{V}\)?

- Adaptive Sampling
- Uses weighted combinations of objectives
- Weighted combination is ad-hoc
- Does not optimize
- Pareto Optimal Front
- More principled method
- Computes trade-offs of multiple objectives

- Can’t improve one objective without reducing another
- Pareto Optimal Front
- Collection of Pareto Efficient points

ORCA | Social Forces |

- NGSA-II

- Optimize algorithms for combinations of objectives
- principled model of trade-offs between objectives

- Lets not optimize the crowd but the environment for the crowd
- Can we optimize parts of buildings for crowd flow?

[Berseth et al. 2015]

- A scenario \( s \) is a set of Obstacle and Agents ( \(s = \langle \textbf{O},\textbf{A} \rangle \))
- An obstacle \( o \) has a position \( \textbf{x} \) and geometry (circle or square)
- An agent \( a \) has a position \( \textbf{x}\), radius \( r \) and goal location \( \textbf{g} \)
- A Scenario subspace will define bounds on positions (agents or obstacles) \( \mathcal{S}_{sub} \)
- A scenario is created from \( \mathcal{S}_{sub} \) with parameters \( \textbf{p} \in \mathcal{P} \)

- $$ f(\textbf{p}) = \frac{ | A_c | |A|}{\sum_{a \in A_c} t_a} $$
- \(A_{c}\), number of agents that completed the scenario
- \(t_{a}\), Time to complete scenario for agent \(a\)

- penalize overlapping obstacles \(g(\textbf{p})\)
- \(g(\textbf{p}) = \sum\limits_{\forall (o_{1},o_{2}) \in O \times O } g_{o}(o_{1},o_{2}) \)
- $$ \textbf{p}^* = \arg \min_{\textbf{p} \in \mathcal{P}} (-f(\textbf{p}) + g(\textbf{p})) $$

- Path planning influences \(v_{pref}\)
- Path planning is usually based on some static discretization of the environment
- This results in very bad noise in the optimization
- Jaring discountinuities in flow wrt \(\textbf{p}\)
- Increased crowd congestion

ORCA | PPR | Social Forces |

optimization results

[Guy et al. 2013]

[Ricks et al. 2014]

- Starting to show that we are making good steering algorithms
- Still large barrier between crowd simulation and character simulation
- Physics is going to have to sneek in there somewhere
- More data, we need more data...