Publishing house Radiotekhnika

"Publishing house Radiotekhnika":
scientific and technical literature.
Books and journals of publishing houses: IPRZHR, RS-PRESS, SCIENCE-PRESS

Тел.: +7 (495) 625-9241


A hybrid method for using external and internal memory in heuristic search for automated planning


Yu.M. Blokhin - Assistent, National Research Nuclear University “MEPhI” (Moscow)

In this paper some aspects of implementation of heuristic search methods for automated planning are discussed. Automated planning is used in wide range of application, including integrated expert systems construction automation. This paper describes a method to use of both external and internal memory during a single search session in heuristic search in large-scale problems. The work is primarily focused on designing special data structures, which can be used with classical heuristic search algorithms without algorithm modifications. The main idea is to perform cached disk access with virtual memory approach. There are three special designed data structures – for search priority queue, for duplication detection processing and for search graph storage. Priority queue and graph storage use only serial access, thus they do not affect overall search speed. The most complex structure used for duplication detection, and when a cache is overflowed, some pages are kicked and flushed to a hard disk drive. We evaluate our approach on Sliding Puzzle, Tower of Hanoi, Rubik's Cube and classical planning (or STRIPS planning from Internation Planning Competition domains) problems. A* search algorithm and admissible heuristics are used in all our experiments. The solver timeline statistics (such as search speed and progress) are plotted for different search properties. We perform experiments on both magnetic and solid disks and compare results. Analyzing the results, conclusions are made, that our proposed approach can be efficiently used for small-middle sized problems on weak machines, with limited operation memory, because it guarntees, that the plan will be found even if all the memory is con-sumed.

  1. Ry'bina G.V., Bloxin Ju.M. Metody' i sredstva intellektual'nogo planirovaniya: primenenie dlya upravleniya proczessami postroeniya integrirovanny'x e'kspertny'x sistem // Iskusstvenny'j intellekt i prinyatie resheniй. 2015. № 1. S. 75–93.
  2. Bloxin Ju.M., Shaxraman'yan A.M., Mozzhuxin D.A. Primenenie intellektual'nogo planirovshhika kompleksa AT-TEXNOLOGIJa dlya obrabotki biznes-informaczii v sisteme Lement Pro // Informaczionno-izmeritel'ny'e i upravlyayushhie sistemy'. 2016. T. 14. № 8. S.19–25.
  3. Ry'bina G.V., Bloxin Ju.M., Danyakin I.D. Intellektual'naya texnologiya postroeniya integrirovanny'x e'kspertny'x sistem // Informaczionno-izmeritel'ny'e i upravlyayushhie sistemy'. 2015. № 1. S. 3–19.
  4. Ry'bina G.V. Teoriya i texnologiya postroeniya integrirovanny'x e'kspertny'x sistem. Monografiya. M.: Nauchtexlitizdat. 2008. 482 s.
  5. Korf R.E. Depth-first Iterative-Deepening: An Optimal Admissible Tree Search // Artificial Intelligence 27. 1985. P. 97–109.
  6. Edelkamp S., Jabbar S., Schrodl S. External A* // KI, Springer. 2004. P. 226–240.
  7. Woelfel P. Maintaining external memory efficient hash tables // Daz, J., Jansen, K., Rolim, J. D. P., & Zwick, U. (Eds.), APPROX-RANDOM, V. 4110 of Lecture Notes in Computer Science. Springer. 2006. P. 508–519.
  8. Edelkamp S., Jabbar S. Cost-optimal external planning // National Conference on Artificial Intelligence (AAAI), AAAI Press, 2006. P. 821–826.
  9. Dai P.M., Weld D.S. Domain-independent, automatic partitioning for probabilistic planning // IJCAI 2009. P. 1677–1683.
  10. Edelkamp S., Sulewski D. Flash-efficient ltl-model checking with minimal counterexamples // Software Engineering and Formal Methods, 2008. SEFM ’08. Sixth IEEE International Conference. P. 73–82.
  11. Korf R.E. Best-first frontier search with delayed duplicate detection // Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence. 2004. July 25–29. San Jose, California, USA. P. 650–657.
  12. Korf R.E., Felner A. Recent progress in heuristic search: A case study of the four-peg towers of hanoi problem // IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6–12, 2007. P. 2324–2329.
  13. Nau D.S. Current trends in automated planning // AI Magazine. 2007. V. 28. № 4. P. 43–58.
  14. Kruse R.L., Ryba A.J. Data structures and program design in C++. Prentice Hall, Upper Saddle River, New Jersey. 1998.
  15. Myrvold W., Ruskey F. Ranking and unranking permutations in linear time // Information Processing Letters. 2000(79). P. 281–284.
  16. Mulholland J. Lecture 20. rubiks cube: The fundamental theorem of cubology // Permutation Puzzles: A Mathematical Perspective. 2013.
  17. Bryce D., Kambhampati S. A tutorial on planning graph based reachability heuristics // AI Magazine, 2007, V. 28. № 1. P. 47–83.
  18. Gerevini A., Haslum P., Long D. et al. Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners // Artif. Intell. 2009. V. 173. № 5–6. P. 619–668.
June 24, 2020
May 29, 2020

© Издательство «РАДИОТЕХНИКА», 2004-2017            Тел.: (495) 625-9241                   Designed by [SWAP]Studio