Scalable Parallel Best-First Search for Optimal Sequential Planning
Date
2009
Authors
Kishimoto, Akihiro
Fukunaga, Alex
Botea, Adi
Journal Title
Journal ISSN
Volume Title
Publisher
AAAI Press
Abstract
Large-scale, parallel clusters composed of commodity processors are increasingly available, enabling the use of vast processing capabilities and distributed RAM to solve hard search problems. We investigate parallel algorithms for optimal sequential planning, with an emphasis on exploiting distributed memory computing clusters. In particular, we focus on an approach which distributes and schedules work among processors based on a hash function of the search state. We use this approach to parallelize the A* algorithm in the optimal sequential version of the Fast Downward planner. The scaling behavior of the algorithm is evaluated experimentally on clusters using up to 128 processors, a significant increase compared to previous work in parallelizing planners. We show that this approach scales well, allowing us to effectively utilize the large amount of distributed memory to optimally solve problems which require hundreds of gigabytes of RAM to solve. We also show that this approach scales well for a single, shared-memory multicore machine.
Description
Keywords
Keywords: Best first search; Commodity processors; Computing clusters; Distributed Memory; Multi-core machines; Optimal sequential; Parallel clusters; Parallelizing; Processing capability; Scaling behavior; Search problem; Shared memories; Hash functions; Optimizat
Citation
Collections
Source
Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling
Type
Conference paper
Book Title
Entity type
Access Statement
License Rights
DOI
Restricted until
2037-12-31