Scalable Parallel Best-First Search for Optimal Sequential Planning
| dc.contributor.author | Kishimoto, Akihiro | |
| dc.contributor.author | Fukunaga, Alex | |
| dc.contributor.author | Botea, Adi | |
| dc.coverage.spatial | Thessaloniki Greece | |
| dc.date.accessioned | 2015-12-07T22:41:44Z | |
| dc.date.created | September 19-23 2009 | |
| dc.date.issued | 2009 | |
| dc.date.updated | 2016-02-24T11:13:54Z | |
| dc.description.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. | |
| dc.identifier.isbn | 9781577354062 | |
| dc.identifier.uri | http://hdl.handle.net/1885/24451 | |
| dc.publisher | AAAI Press | |
| dc.relation.ispartofseries | International conference on Automated planning and scheduling (ICAPS 2009) | |
| dc.source | Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling | |
| dc.subject | 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 | |
| dc.title | Scalable Parallel Best-First Search for Optimal Sequential Planning | |
| dc.type | Conference paper | |
| local.contributor.affiliation | Kishimoto, Akihiro, Tokyo Institute of Technology | |
| local.contributor.affiliation | Fukunaga, Alex, Tokyo Institute of Technology | |
| local.contributor.affiliation | Botea, Adi , College of Engineering and Computer Science, ANU | |
| local.contributor.authoremail | repository.admin@anu.edu.au | |
| local.contributor.authoruid | Botea, Adi , u1814829 | |
| local.description.embargo | 2037-12-31 | |
| local.description.notes | Imported from ARIES | |
| local.description.refereed | Yes | |
| local.identifier.absfor | 080199 - Artificial Intelligence and Image Processing not elsewhere classified | |
| local.identifier.absfor | 080105 - Expert Systems | |
| local.identifier.ariespublication | u4607519xPUB32 | |
| local.identifier.scopusID | 2-s2.0-78650608544 | |
| local.identifier.uidSubmittedBy | u4607519 | |
| local.type.status | Published Version |