Abstract

Navigation and steering in complex dynamically changing environments is a challenging research problem, and a fundamental aspect of immersive virtual worlds. While there exist a wide variety of approaches for navigation and steering, there is no definitive solution for evaluating and analyzing steering algorithms. Evaluating a steering algorithm involves three major challenges: (a) characterizing and generating the space of possible scenarios that the algorithm must solve, (b) defining evaluation criteria, and (c) defining a reference solution to serve as a basis for comparison. In this paper, we address these challenges to arrive at a definitive benchmarking solution for steering algorithms. First, we propose a representative sampling of the complete space of scenarios that a steering agent may encounter in dynamic situations. Second, we propose a new set of metrics and a statistically robust approach to determining the coverage and the quality of a steering algorithm in this space. We define reference values for each of the computed metrics to serve as a basis for comparison. Third, we provide users with the ability to specify constraints on the scenario space to generate subsets of scenarios (benchmarks) with specific properties. We use our method to objectively evaluate and compare five state of the art steering approaches, and one baseline reactive approach. These techniques represent centralized and decentralized approaches, different locomotion models, as well as reactive, predictive, and planning based techniques. Our proposed scoring mechanism can be used (a) to evaluate a single algorithm on a single scenario, (b) to compare the performance of an algorithm over different benchmarks, and (c) to compare different steering algorithms.

Related Articles

Scenario Space: Characterizing Coverage, Quality, and Failure of Steering Algorithms

Mubbasir Kapadia, Matthew Wang, Shawn Singh, Glenn Reinman and Petros Faloutsos

ACM SIGGRAPH Symposium on Computer Animation, August 2011
Bibtex

Improved Benchmarking for Steering Algorithms

Mubbasir Kapadia, Matthew Wang, Glenn Reinman and Petros Faloutsos

4th International Conference on Motion in Games, Novemeber 2011
Bibtex

Videos

Download here

Videos

Download here