AAAI Publications, Third Annual Symposium on Combinatorial Search

Font Size: 
On the Scaling Behavior of HDA*
Akihiro Kishimoto, Alex Fukunaga, Adi Botea

Last modified: 2010-08-25


HDA* is a simple, parallelization of A* where work is asynchronously distributed among the nodes by a global hash function. Using up to 1024 cores on a large distributed memory cluster, we evaluate HDA* for a domain-independent planner as well an application-specific 24-puzzle solver. We show that HDA* scales fairly well on a large cluster using up to 1024 cores. Our analysis of the scaling behavior shows that on a cluster of multicore nodes, using only a subset of the available cores and leaving some cores idle can, surprisingly, lead to better results.


A* algorithm; parallel search; HDA*

Full Text: PDF