Parallel strategies for best-first generalized planning

Abstract

In recent years, Artificial Intelligence (AI) has become the big trend in computer science, and many related areas are seeing renewed interest. One of these areas is Generalized Planning (GP), which studies the automated synthesis of algorithmicl ike solutions capable of solving multiple classical planning instances. Tightly coupled with the success of AI, there has been a steady increase in computational power thanks to multi-core CPUs and GPUs. This has encouraged active research in parallel programming, which is needed to use the full potential of current hardware. In this work, we explore parallelization strategies for tree-search algorithms. Furthermore, we propose one algorithm to parallelize Best-First Generalized Planning (BFGP), a heuristic search approach to GP. We show that our algorithm can scale linearly with the number of processors, but we also discuss some cases in which pathological behavior can cause performance degradation.Recentment, la Intel·ligència Artificial (IA) s’ha convertit en la gran moda de l’enginyeria informàtica, la qual cosa ha significat que moltes àrees relacionades estan veient un interès renovat. Una d’aquestes àrees és Generalized Planning (GP), que estudia la síntesi automatitzada de solucions algorítmiques capaces de resoldre múltiples instàncies de problemes de Classical Planning d’un mateix domini. L’èxit de la IA est`a molt lligat a l’increment en capacitat computacional proporcionat per processadors multinucli i GPUs. Això ha propiciat la recerca sobre programació paral·lela, necessària per extreure el màxim potencial dels ordinadors actuals. En aquest treball, explorem estratègies de paral·lelització d’algoritmes. de cerca d’arbres. A més a més, proposem un algoritme per paral·lelitzar Best-First Generalized Planning (BFGP), una estratègia basada en cerca heurística de GP. Tamb´e demostrem que el nostre algoritme pot escalar linearment amb el n´umero de processadors, i discutim alguns casos patol`ogics que podem causar una degradaci´o del rendiment. v