## Crowd Simulation

### Intro to steering algorithms Presented By
Glen Berseth
University of British Columbia

### What is steering

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

### Hitman: Absolution

Uses Boids algorithm [Craig W. Reynolds, 1987]

### Where are they used?

• 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

### Why do we want steering algorithms?

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

### Outline: how to make good steering algorithms

1. The steering problem
2. Some popular steering algorithms
3. Issues with the disk model
4. How can we compare steering algorithms
5. What's next?

### What kinds of behaviour do we see in crowds?

1. Flocking
2. Lane forming
3. The Vortex
4. Compression waves
5. More?

### Steering Model

1. Sliding particle
2. Configuration state $$q = \langle x, y, \dot{x}, \dot{y} \rangle$$
3. Commonly internal to the steering model
1. Preferred Velocity $$v_{pref}$$
2. max speed $$v_{max}$$
3. radius $$r$$
4. neighbours $$a_{0} \ldots a_{n}$$
5. waypoints $$p_{0} \ldots p_{m}$$ ### Simulation loop?

1. Steering decision can be even simpler than simulation loop
2. $$\langle x, y, \dot{x}, \dot{y} \rangle' = steeringAlgorithm(\langle x, y, \dot{x}, \dot{y} \rangle, \Delta t)$$ ### Example Steering algorithms

Anyone used a steering algorithm before?

### Social Forces / HIDAC

• Obstacle repulsion forces [Helbing et al. 2000, Pelechano et al. 2007]

#### Agent repulsion force #### Net force #### Agent Comfort zone

• Repulsive when agents almost collide ### Continuum crowds [Treuille et al. 2006]

#### Key ideas

• 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

### Reciprical Velocity Obstacles (RVO) • Keep velocity outside of Velocity Obstacle

[van den Berg et al. 2008]

### Smooth (RVO) • Velocity is average of velocity outside of obstacle and desired.

### Multi-agent descision (RVO) • Choose best velocity outside of union on RVOs

### Plan, Predict, React (PPR)

#### Short term planning [Singh et al. 2011] #### React #### Demo ### Issues with Disk model

1. Foot Skating
2. Does not capture rigid body
3. Limbs can intersect
4. People are not circular

### Footstep based [Singh et all 11] [Singh et al. 2011]

### Awesome! Now which one works the best??

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

### SteerBench

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

[Singh et al. 2009]

### ScenarioSpace: [Kapadia et al 11]

1. Construct a subspace of possible scenarios
2. What should this subspace consist of?
3. More difficult scenarios
• • Reference agent
• Force interaction
4. Better metrics for comparison
• Coverage
• Time quality
• Distance Quality

### Now we can evaluate steering algorithms, so what?

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

### SteerFit: Steering algorithm parameter fitting

1. Each steering algorithm models the steering problem well
2. Each algorithm has a number of parameters
3. How do they affect the algorithms behaviour?
4. Can we improve the algorithms?

[Berseth et al. 2013]

### Optimization framework

1. We optimize the parameters ($$v$$) of a steering algorithm ($$A_{v}$$)
2. Over a test set $$T$$ (representative set)
3. For a user defined objective $$ƒ$$
4. Important issue: do the optimized parameters generalize?

### Behavioural Objectives

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

### Formulate an optimization

• 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})$$

### SteerFit Findings Relative percent improvement over default

### These Results are good but what do we really want?

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

### SteerFit Findings (Entropy)

• 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 vs Pareto Optimal

• Uses weighted combinations of objectives
• Does not optimize
• Pareto Optimal Front
• More principled method
• Computes trade-offs of multiple objectives

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

### Pareto Optimial Front  ORCA Social Forces
• NGSA-II

### Weight mapping ### Dicussion

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

### Architecture optimization

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

[Berseth et al. 2015]

### Parameterized scenario (Scenario Subspace)

• 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}$$

### Crowd Flow

• $$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$$

### Formulate Optimization

• 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

• 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

### Flow analysis    ORCA PPR Social Forces

### Results

optimization results