SteerPlex: Estimating Scenario Complexity for Simulated Crowds

Glen Berseth1, Mubbasir Kapadia2 and Petros Faloutsos1

1York University
2Disney Research Zurich

Complexity of simulated worlds has increased dramatically in recent years Hitman Absolution

Can we compute the complexity of a scenario before simulation?   How can we objectively conclude which one is more difficult to solve?

There are many mature solutions for dynamic navigation Egocentric PPR Footstep RVO [Kapadia et al, 09] [Singh et al, 09] [Singh et al, 11] [van den Berg et al, 08]

We use PPR, Egocentric and Footstep for this work

Related Work

• Environment verification methods [Perkins 2010; Penn 2001] focuse on the validation of a layout using metrics such as connectivity and visibility
• Our method focuses on the static analysis of environment configurations to extract meaningful features which quantify the complexity of dynamic crowd motion

Representative set of Scenarios

We randomly construct scenarios with the following constraints

• The reference agent (blue) is placed at the origin (0,0)
• The static path of each agent must intersect the reference agent’s static path.
• Each agent $$a \in \mathbb{A}$$ must have a valid static optimal path from its initial position to its target.
• The scenario is limited to a minimum of 3 and a maximum of 6 agents.

Simulation Metrics

Used to evaluate steering algorithms post-simulation

• Coverage $$c(A)$$:

Reference agent reaches its goal without collisions and number of collision is less than the number of agents

• Distance Quality $$q(A)$$:

Ratio of distance traveled to optimal distance to reach goal, penalizing deviation from staic optimal path

• Computational Performance $$p(A)$$:

Average time spent computing steering decision for an agent

Complexity formulation

Scenario Definition

 A scenario $$s$$ consists of two sets:   The static obstacles in the simulation $$\mathbb{O}$$ The agents in the simulation $$\mathbb{A}$$   $$s = \langle \mathbb{O}, \mathbb{A} \rangle$$ Each agent is a tuple of {position, desired velocity, initial facing direction and target position}

Scenario Annotation Obstacle groups

Obstacles are grouped together into clusters that consist of any overlaping or touching static obstacles Space-time paths

Paths are computed for each agent that consist of points in both space and time from initial position to target

Complexity features

Number of obstacle groups

$$f_{og}$$ Number of expected interactions

$$f_{i}$$ The light blue circles describe the area of expected interaction $$\epsilon_{d}$$. The blue stars are expected interactions points in space-time

Number of expected interactions with Reference Agent

$$f_{i}^{ref}$$ The orange stars are expected space-time interactions points with the reference agent

Space-Time co-located interactions and obstalces

$$f_{ci}, f_{o}$$ For each expected interaction we check for other interactions and obstalces in the radius of influence $$r_{inf}$$ and within a given time $$\epsilon_t$$

Space-Time co-located interactions and obstalces with reference agent

$$f_{ci}^{ref}$$ We do the same for the reference agent

Open space in area of expected interactions

$$f_{open}$$ The area of the box that bounds all interactions points minus the area of the obstacles in that box.

Experiments and Analysis

correlation analysis over representative set Features calculated from the Space-Time paths show correlation Almost every feature has negative correlation for every steering algorithm with respect to the evaluation metrics

Data clustering analysis

We use data clustering techniques to group scenarios together with similar feature values and compute the average metrics for these clusters $$f_{o}^{ref}$$  $$f_{i}$$ $$c(A^{ppr})$$ $$p(A^{ppr})$$ $$q(A^{ppr})$$ $$c(A^{ego})$$ $$p(A^{ego})$$ $$q(A^{ego})$$ $$c(A^{foot})$$ $$p(A^{foot})$$ $$q(A^{foot})$$ Feature combination and analysis

$$\mathbb{F} = \langle f_i, f_{i}^{ref}, f_{i}^{ref}, f_{o}, f_{o}^{ref}, f_{ci} , f_{ci}^{ref}, f_{open}, f_{og} \rangle$$
$$f_{comp} = \sum_{\forall f_i \in F} w_i f_i$$

Principal Component Analysis

We weight each feature proportion to the variance calculated from the PCA analysis of the features

Complexity Clustering Comparison $$f_{comp}$$ $$c(A^{ppr})$$ $$p(A^{ppr})$$ $$q(A^{ppr})$$ $$c(A^{ego})$$ $$p(A^{ego})$$ $$q(A^{ego})$$ $$c(A^{foot})$$ $$p(A^{foot})$$ $$q(A^{foot})$$ SteerBench analysis $$f_{comp} = 44,000$$ $$f_{comp} = 110,000$$ $$f_{comp} = 460,000$$

Decreasing the number of exits and width of the exit leads to increased expected interactions between agents

[Singh et al. 2009]

movingAI analysis

We perform the same analysis over a set of movingAI benchmarks [Sturtevant 2012] Egocentric Footstep PPR
 $$f_{comp}$$ $$number$$ $$of$$ $$collisions$$ $$c(A)$$ $$p(A)$$ $$q(A)$$ The complexity analysis appears to be more accurate on the movingAI benchmarks

Example scenarios $$f_{comp} = 43.8$$ $$f_{comp} = 1042.70$$ $$f_{comp} = 9080.54$$

Conclusions

• We can compare relative complexity between scenarios
• We have an understanding of what modifications can be done to alter the expected complexity of a scenario
• Having a good combination of features is important to remove bias from any subset of features when calculating the overall complexity

Limitations

• We do not capture the complexity of individual obstacle groups
• Agents traveling in groups can produce a high complexity score but many steering algorithms can solve these scenarios. However this should reflect in a lower computational performance score