SteerPlex: Estimating Scenario Complexity for Simulated Crowds
Glen Berseth^{1}, Mubbasir Kapadia^{2} and Petros Faloutsos^{1}
^{1}York University ^{2}Disney 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.
[Kapadia et al. 2011]
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
[Kapadia et al. 2011]
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
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