Proceedings:
Book One
Volume
Issue:
Proceedings of the International Conference on Automated Planning and Scheduling, 27
Track:
Main Track
Downloads:
Abstract:
Multipath Generalized Adaptive A* (MPGAA*) is an A*-based incremental search algorithm for dynamic terrain that can outperform D* for the (realistic) case of limited visibility ranges. A first contribution of this paper is a brief analysis studying why MPGAA* has poor performance for extended visibility ranges, which concludes that MPGAA* carries out an excessive number of heuristic updates. Our second contribution is a method to reduce the number of heuristic updates that preserves optimality. Finally, a third contribution is a variant of MPGAA*, MPGAA*-back, which we show outperforms MPGAA* and D* on a wide range of dynamic grid pathfinding scenarios, and visibility ranges.
DOI:
10.1609/icaps.v27i1.13834
ICAPS
Proceedings of the International Conference on Automated Planning and Scheduling, 27