1York University 2Disney Research Zurich
Hitman Absolution
|
|
|
How can we objectively conclude which one is more difficult to solve?
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
We randomly construct scenarios with the following constraints
[Kapadia et al. 2011]
Reference agent reaches its goal without collisions and number of collision is less than the number of agents
Ratio of distance traveled to optimal distance to reach goal, penalizing deviation from staic optimal path
Average time spent computing steering decision for an agent
[Kapadia et al. 2011]
A scenario \( s \) consists of two sets:
$$ s = \langle \mathbb{O}, \mathbb{A} \rangle $$ |
|
Each agent is a tuple of {position, desired velocity, initial facing direction and target position}
|
Obstacle groupsObstacles are grouped together into clusters that consist of any overlaping or touching static obstacles |
|
Space-time pathsPaths are computed for each agent that consist of points in both space and time from initial position to target |
\( f_{og} \)
\( f_{i} \)
The light blue circles describe the area of expected interaction \( \epsilon_{d} \). The blue stars are expected interactions points in space-time
\( f_{i}^{ref} \)
The orange stars are expected space-time interactions points with the reference agent
\( 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 \)
\( f_{ci}^{ref} \)
We do the same for the reference agent
\( f_{open} \)
The area of the box that bounds all interactions points minus the area of the obstacles in that box.
|
|
|
|
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}) \)
|
We weight each feature proportion to the variance calculated from the PCA analysis of the features
\( 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}) \)
|
$$ 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]
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 |
$$ f_{comp} = 43.8 $$
|
$$ f_{comp} = 1042.70 $$
|
$$ f_{comp} = 9080.54 $$
|