Dynamically Pruned A* for Re-planning in Navigation Meshes
Wouter van Toll, Roland Geraerts
In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2051-2057, 2015.
Resources:
Full text (pdf) - Presentation (pptx)
Also published as:
DPA*: Dynamically Pruned A* for Re-planning in Navigation Meshes
Wouter van Toll, Roland Geraerts
Presentation and poster in ICT.OPEN 2016, ASCI track.
- Received the Best Poster Award of the ASCI track.
- Received the Poster Award 3rd Prize of ICT.OPEN 2016.
Resources:
Extended abstract (pdf) - Poster (pdf) - Presentation (pptx)
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.
@inproceedings{vanToll2015-Replanning,
author = {van Toll, W.G. and Geraerts, R.},
title = {Dynamically {P}runed {A}* for Re-planning in Navigation Meshes},
booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
year = {2015},
pages = {2051--2057}
}