Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

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

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Availability of data and material

For this study, we have used benchmark planning problems from the International Planning Competition (IPC), which are available in the public domain. The source of the dataset is cited in the paper. The problems from real-world applications are available upon request.

Code availability

The code is available on request.

Notes

  1. http://www.icaps-conference.org/index.php/Main/Competitions.

  2. https://www.icaps-conference.org/competitions/.

References

  1. Arredondo RLG, Sanchez R, Berrones A (2014) Introducing simulated annealing in partial order planning. In: 2014 13th Mexican International Conference on Artificial Intelligence. pp 190–196. https://doi.org/10.1109/MICAI.2014.35

  2. Ángel Bello F, Álvarez A, Pacheco J, Martínez I (2011) A single machine scheduling problem with availability constraints and sequence-dependent setup costs. Appl Math Model 35(4):2041–2050. https://doi.org/10.1016/j.apm.2010.11.017

    Article  MathSciNet  MATH  Google Scholar 

  3. Burns E, Lemons S, Ruml W, Zhou R (2010) Best-first heuristic search for multicore machines. Artif Intell Res 39:689–743. https://doi.org/10.1613/jair.3094

    Article  MathSciNet  MATH  Google Scholar 

  4. Bylander T (1994) The computational complexity of propositional strips planning. Artif Intell 69(1):165–204. https://doi.org/10.1016/0004-3702(94)90081-7

    Article  MathSciNet  MATH  Google Scholar 

  5. Coles AI (2007) Heuristics and metaheuristics in forward-chaining planning. Ph.D. thesis, University of Strathclyde

  6. Elizalde-Ramírez F, Nigenda RS, Martínez-Salazar IA, Ríos-Solís YA (2019) Travel plans in public transit networks using artificial intelligence planning models. Appl Artif Intell 33(5):440–461. https://doi.org/10.1080/08839514.2019.1582859

    Article  Google Scholar 

  7. Evett M, Hendler J, Mahanti A, Nau D (1995) Pra*: Massively parallel heuristic search. J Parallel Distrib Comput 25(2):133–143. https://doi.org/10.1006/jpdc.1995.1036

    Article  Google Scholar 

  8. Fox M, Long D (2003) Pddl2.1: An extension to PDDL for expressing temporal planning domains. J Artif Int Res 20(1):61–124. https://doi.org/10.1613/jair.1129

    Article  MATH  Google Scholar 

  9. Gerevini A, Saetti A, Serina I (2003) Planning through stochastic local search and temporal action graphs in LPG. Artif Intell Res 20:239–290. https://doi.org/10.1613/jair.1183

    Article  MATH  Google Scholar 

  10. Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4(2):100–107. https://doi.org/10.1109/TSSC.1968.300136

    Article  Google Scholar 

  11. Helmert M (2006) The fast downward planning system. J Artif Intell Res 26:191–246. https://doi.org/10.1613/jair.1705

    Article  MATH  Google Scholar 

  12. Hoffmann J, Edelkamp S, Thiébaux S, Englert R, dos Santos Liporace F, Trüg S (2006) Engineering benchmarks for planning: the domains used in the deterministic part of IPC-4. J Artif Intell Res 26(1):453–541. https://doi.org/10.1613/jair.1982

    Article  MATH  Google Scholar 

  13. Hoffmann J, Nebel B (2001) The FF planning system: fast plan generation through heuristic search. J Artif Intell Res 14:253–302. https://doi.org/10.1613/jair.855

    Article  MATH  Google Scholar 

  14. Jinnai Y, Fukunaga A (2016) Abstract zobrist hashing: an efficient work distribution method for parallel best-first search. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI). pp 717–723. http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13081

  15. Jinnai Y, Fukunaga A (2016) Automated creation of efficient work distribution functions for parallel best-first search. In: Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling (ICAPS). pp 184–192. http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13081

  16. Jinnai Y, Fukunaga A (2017) On hash-based work distribution methods for parallel best-first search. J Artif Intell Res 60:491–548. https://doi.org/10.1613/jair.5225

    Article  MathSciNet  MATH  Google Scholar 

  17. Kishimoto A, Fukunaga A, Botea A (2013) Evaluation of a simple, scalable, parallel best-first search strategy. Artif Intell 195:222–248. https://doi.org/10.1016/j.artint.2012.10.007

    Article  MathSciNet  MATH  Google Scholar 

  18. Korf RE (1985) Depth-first iterative-deepening: an optimal admissible tree search. Artif Intell 27(1):97–109. https://doi.org/10.1016/0004-3702(85)90084-0

    Article  MathSciNet  MATH  Google Scholar 

  19. Kuroiwa R, Fukunaga A (2019) On the pathological search behavior of distributed greedy best-first search. In: Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling. pp 255–263. https://www.aaai.org/ojs/index.php/ICAPS/article/download/3485/3353

  20. Kuroiwa R, Fukunaga A (2020) Analyzing and avoiding pathological behavior in parallel best-first search. In: Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling. pp 175–183. https://ojs.aaai.org//index.php/ICAPS/article/view/6659

  21. Nau D, Ghallab M, Traverso P (2004) Automated planning: theory and practice. Morgan Kaufmann Publishers Inc., San Francisco

    MATH  Google Scholar 

  22. Nguyen X, Kambhampati S, Nigenda RS (2002) Planning graph as the basis for deriving heuristics for plan synthesis by state space and CSP search. Artif Intell 135(1):73–123. https://doi.org/10.1016/S0004-3702(01)00158-8

    Article  MATH  Google Scholar 

  23. Romein JW, Bal HE, Schaeffer J, Plaat A (2002) A performance analysis of transposition-table-driven work scheduling in distributed search. IEEE Trans Parallel Distrib Syst 13(5):447–459. https://doi.org/10.1109/TPDS.2002.1003855

    Article  Google Scholar 

  24. Romein JW, Plaat A, Bal HE, Schaeffer J (1999) Transposition table driven work scheduling in distributed search. In: Proceedings of AAAI/IAAI. pp 725–731. https://www.aaai.org/Papers/AAAI/1999/AAAI99-103.pdf

  25. Russell S, Norvig P (2020) Artificial intelligence: a modern approach, 4th edn. Pearson, London

    MATH  Google Scholar 

  26. Schütt T, Reinefeld A, Maier R (2013) Mr-search: massively parallel heuristic search. Concurr Comput Pract Exp 25(1):40–54. https://doi.org/10.1002/cpe.1833

    Article  Google Scholar 

  27. Seipp J, Röger G (2018) Fast downward stone soup 2018 (planner abstract). In: Ninth International Planning Competition (IPC 2018). https://ipc2018-classical.bitbucket.io/planner-abstracts/team45.pdf

  28. Shleyfman A, Katz M, Helmert M, Sievers S, Wehrle M (2015) Heuristics and symmetries in classical planning. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015). pp 3371–3377. http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/download/9635/9767

  29. Vidal V (2004) A lookahead strategy for heuristic search planning. In: Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling. pp 150–160. https://aaai.org/Papers/ICAPS/2004/ICAPS04-020.pdf

  30. Vidal V, Bordeaux L, Hamadi Y (2010) Adaptive k-parallel best-first search: a simple but efficient algorithm for multi-core domain-independent planning. In: Proceedings of the Third Annual Symposium on Combinatorial Seach (SOC-10). pp 100–107

Download references

Acknowledgements

We thank SUPE reviewers for many constructive comments of the proposed work.

Funding

Part of this study has been made possible via a funding of project BigGraphs of LABEX CIMI 2020, Toulouse and UANL PAICYT Grant IT1838-21.

Author information

Authors and Affiliations

  1. LAAS-CNRS, CNRS, Université de Toulouse, Toulouse, France

    Didier El Baz & Bilal Fakih

  2. Facultad de Ingeniería Mecánica y Eléctrica, Universidad Autónoma de Nuevo León, San Nicolás de los Garza, Nuevo León, Mexico

    Romeo Sanchez Nigenda

  3. Universidad Autónoma de Nuevo León, San Nicolás de los Garza, Mexico

    Vincent Boyer

Authors
  1. Didier El Baz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bilal Fakih
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Romeo Sanchez Nigenda
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Vincent Boyer
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors have contributed to the study and have read and approved the final manuscript.

Corresponding author

Correspondence to Romeo Sanchez Nigenda.

Ethics declarations

Conflict of interest

The authors declare that they have no conflicts of interest.

Ethics approval

Not applicable.

Consent to participate

All authors agree to participate in the study.

Consent to publication

All authors agree to publication.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

El Baz, D., Fakih, B., Sanchez Nigenda, R. et al. Parallel best-first search algorithms for planning problems on multi-core processors. J Supercomput 78, 3122–3151 (2022). https://doi.org/10.1007/s11227-021-03986-z

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-021-03986-z

Keywords

Search

Navigation