Parallel best-first search algorithms for planning problems on multi-core processors - LAAS-Réseaux et Communications Accéder directement au contenu
Article Dans Une Revue Journal of Supercomputing Année : 2022

Parallel best-first search algorithms for planning problems on multi-core processors

Résumé

The multiplication of computing cores in modern processor units permits revisiting the design of classical algorithms to improve computational performance in complex application domains. Artificial Intelligence planning is one of those applications where large search spaces require intelligent and more exhaustive search control. In this paper, parallel planning algorithms, derived from best-first search, are proposed for shared memory architectures. The parallel algorithms, based on the asynchronous work pool paradigm, maintain good thread occupancy in multi-core CPUs. All algorithms use one ordered global list of states stored in shared memory from where they select nodes for expansion. A parallel best-first search algorithm that develops new states with depth equal to one is proposed first. Then, we propose an extension of this parallel algorithm that features a diversification strategy in order to escape local minima. We study and analyse a set of computational experiments for problems that come from the International Planning Competition and real-world industry applications. The empirical evaluation shows that the parallel algorithms solve most of the domains efficiently without incurring higher solutions costs. In those problems with partial results, we highlight the potential shortcomings of the proposed approaches for promising future directions.
Fichier principal
Vignette du fichier
Planning.pdf (13.98 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03380578 , version 1 (15-10-2021)

Identifiants

Citer

Didier El Baz, Bilal Fakih, Romeo Sanchez Nigenda, Vincent Boyer. Parallel best-first search algorithms for planning problems on multi-core processors. Journal of Supercomputing, 2022, 78 (3), p. 3122-3151. ⟨10.1007/s11227-021-03986-z⟩. ⟨hal-03380578⟩
81 Consultations
34 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More