Homepage of Roland Geraerts

We study how we can automatically create a data structure that represents the walkable surfaces in such an environment, and how it can be updated dynamically and efficiently when it changes. We refer to this structure as a navigation mesh. This mesh enables efficient crowd simulation, which is our next topic of research. We study and develop a crowd simulation framework and its components, which ranges from global (AI) planning to local animation. We create models for realistic crowd behaviors, which includes studying how (groups of) people move and avoid collisions in such environments, based on agent profiles and semantics (such as terrain annotations).

Dynamically Pruned A* for Re-planning in Navigation Meshes

Different strategies are shown when a dynamic obstacle appears or disappears.

Abstract

Modern simulations feature crowds of AI-controlled agents moving through dynamic environments, with obstacles appearing or disappearing at run-time. A dynamic navigation mesh can represent the traversable space of such environments. The A* algorithm computes optimal paths through the dual graph of this mesh. When an obstacle is inserted or removed, the mesh changes and agents should re-plan their paths. Many existing re-planning algorithms are too memory-intensive for crowds, or they cannot easily be used on graphs that structurally change.

In this paper, we present Dynamically Pruned A* (DPA*), an extension of A* for re-planning optimal paths in dynamic navigation meshes. DPA* has similarities to adaptive algorithms that make the A* heuristic more informed based on previous queries. However, DPA* prunes the search using only the previous path and its relation to the dynamic event. We describe this relation using four scenarios; DPA* uses different rules in each scenario. Our algorithm is memory-friendly and robust against structural changes, which makes it suitable for crowds in dynamic navigation meshes. Experiments show that DPA* performs particularly well in large environments and when the dynamic event is visible to the agent. We integrate the algorithm into crowd simulation software to model large crowds in dynamic environments in real-time.

Reference

Wouter van Toll and Roland Geraerts. Dynamically Pruned A* for Re-planning in Navigation Meshes. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (Hamburg, Germany), pp. 2051-2057, 2015.
Wouter van Toll and Roland Geraerts. DPA*: Dynamically Pruned A* for Re-planning in Navigation Meshes. In ICT.OPEN 2016, ASCI track (Amersfoort, The Netherlands). This work received the Best Poster Award of the ASCI track. In addition, it received the Poster Award 3rd Prize of ICT.OPEN 2016.