SteerPlex: Estimating Scenario Complexity for Simulated Crowds

Glen Berseth¹, Mubbasir Kapadia² and Petros Faloutsos¹

¹York University
²Disney Research Zurich

Complexity of simulated worlds has increased dramatically in recent years

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

\( 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

Principal Component Analysis

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

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]

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

Thank You