Synchronizing navigation algorithms for crowd simulation via topological strategies
Wouter van Toll, Julien Pettré
Computers & Graphics, vol. 89, pp. 24-37, 2020.
Resources:
Journal website page - Inria HAL page - Full paper (PDF)
Preceding conference publication:
Connecting Global and Local Agent Navigation via Topology
Wouter van Toll, Julien Pettré
In 12th ACM SIGGRAPH Conference on Motion, Interaction and Games, pp. 33:1-33:10, 2019.
Resources:
ACM Digital Library page - Inria HAL page - Full paper (PDF)
(This is the abstract of the extended journal version of this article.)
We present a novel topology-driven method for enhancing the navigation behavior of agents in virtual environments and crowds. In agent-based crowd simulations, each agent combines multiple navigation algorithms for path planning, collision avoidance, and more. This may lead to undesired motion whenever the algorithms disagree on how an agent should pass an obstacle or another agent.
In this paper, we argue that all navigation algorithms yield a strategy: a set of decisions to pass obstacles and agents along the left or right. We show how to extract such a strategy from a (global) path and from a (local) velocity. Next, we propose a general way for an agent to resolve conflicts between the strategies of its algorithms. For example, an agent may re-plan its global path when collision avoidance suggests a detour. As such, we bridge conceptual gaps between algorithms, and we synchronize their results in a fundamentally new way. Experiments with an example implementation show that our strategy concept can improve the behavior of agents while preserving real-time performance. It can be applied to many agent-based simulations, regardless of their specific navigation algorithms. The concept is also suitable for explicitly sending agents in particular directions, e.g. to simulate signage.
@article{vanToll2020-NavigationTopology,
author = {van Toll, W. and Pettr\'e, J.},
title = {Synchronizing navigation algorithms for crowd simulation via topological strategies},
booktitle = {Computers \& Graphics},
year = {2020},
volume = {89},
pages = {24--37}
}
@inproceedings{vanToll2019-NavigationTopology,
author = {van Toll, W. and Pettr\'e, J.},
title = {Connecting Global and Local Agent Navigation via Topology},
booktitle = {Proceedings of the 12th ACM SIGGRAPH Conference on Motion, Interaction and Games},
year = {2019},
pages = {33:1--33:10}
}