Advertisement

Automated Creation of Pattern Database Search Heuristics

  • Stefan Edelkamp
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4428)

Abstract

Pattern databases are dictionaries for heuristic estimates storing state-to-goal distances in state space abstractions. Their effectiveness is sensitive to the selection of the underlying patterns. Especially for multiple and additive pattern databases, the manual selection of patterns that leads to good exploration results is involved.

For automating the selection process, greedy bin-packing has been suggested. This paper proposes genetic algorithms to optimize its output. Patterns are encoded as binary strings and optimized using an objective function that predicts the heuristic search tree size based on the distribution of heuristic values in abstract space.

To reduce the memory requirements we construct the pattern databases symbolically. Experiments in heuristic search planning indicate that the total search efforts can be reduced significantly.

Keywords

Genetic Algorithm Model Check Heuristic Search Heuristic Estimate Heuristic Search Algorithm 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Ball, T., Majumdar, R., Millstein, T.D., Rajamani, S.K.: Automatic predicate abstraction of c programs. In: SIGPLAN Conference on Programming Language Design and Implementation, pp. 203–213 (2001)Google Scholar
  2. 2.
    Brie, A.H., Morignot, P.: Genetic planning using variable length chromosomes. In: ICAPS, pp. 320–329 (2005)Google Scholar
  3. 3.
    Bryant, R.E.: Symbolic manipulation of boolean functions using a graphical representation. In: ACM/IEEE Design Automation Conference, pp. 688–694 (1985)Google Scholar
  4. 4.
    Clarke, E.M., Grumberg, O., Long, D.: Model checking and abstraction. ACM Transactions on Programming Languages and Systems 16(5), 1512–1542 (1994)CrossRefGoogle Scholar
  5. 5.
    Culberson, J.C., Schaeffer, J.: Pattern databases. Computational Intelligence 14(4), 318–334 (1998)CrossRefMathSciNetGoogle Scholar
  6. 6.
    Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge (2005)Google Scholar
  7. 7.
    Edelkamp, S.: Planning with pattern databases. In: ECP, pp. 13–24 (2001)Google Scholar
  8. 8.
    Edelkamp, S.: Symbolic pattern databases in heuristic search planning. In: AIPS, pp. 274–293 (2002)Google Scholar
  9. 9.
    Edelkamp, S.: Taming numbers and durations in the model checking integrated planning system. Journal of Artificial Intelligence Research 20, 195–238 (2003)zbMATHGoogle Scholar
  10. 10.
    Edelkamp, S.: External symbolic heuristic search with pattern databases. In: ICAPS, pp. 51–60 (2005)Google Scholar
  11. 11.
    Edelkamp, S., Lluch-Lafuente, A.: Abstraction in directed model checking. In: ICAPS-Workshop on Connecting Planning Theory with Practice (2004)Google Scholar
  12. 12.
    Edelkamp, S., Reffel, F.: OBDDs in heuristic search. In: KI, pp. 81–92 (1998)Google Scholar
  13. 13.
    Felner, A., Alder, A.: Solving the 24 puzzle with instance dependent pattern databases. In: Zucker, J.-D., Saitta, L. (eds.) SARA 2005. LNCS (LNAI), vol. 3607, pp. 248–260. Springer, Heidelberg (2005)Google Scholar
  14. 14.
    Felner, A., Meshulam, R., Holte, R.C., Korf, R.E.: Compressing pattern databases. In: AAAI, pp. 638–643 (2004)Google Scholar
  15. 15.
    Felner, A., Zahavi, U., Schaeffer, J., Holte, R.: Dual lookups in pattern databases. In: IJCAI, pp. 103–108 (2005)Google Scholar
  16. 16.
    Fikes, R., Nilsson, N.: STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence 2, 189–208 (1971)zbMATHCrossRefGoogle Scholar
  17. 17.
    Gaschnig, J.: A problem similarity approach to devising heuristics: First results. In: IJCAI, pp. 434–441 (1979)Google Scholar
  18. 18.
    Godefroid, P., Khurshid, S.: Exploring very large state spaces using genetic algorithms. STTT 6(2), 117–127 (2004)CrossRefGoogle Scholar
  19. 19.
    Hansen, E.A., Zhou, R., Feng, Z.: Symbolic heuristic search using decision diagrams. In: Koenig, S., Holte, R.C. (eds.) SARA 2002. LNCS (LNAI), vol. 2371, Springer, Heidelberg (2002)CrossRefGoogle Scholar
  20. 20.
    Hansson, O., Mayer, A., Valtora, M.: A new result on the complexity of heuristic estimates for the A* algorithm (research note). Artificial Intelligence 55, 129–143 (1992)zbMATHCrossRefMathSciNetGoogle Scholar
  21. 21.
    Haslum, P., Bonet, B., Geffner, H.: New admissible heuristics for domain-independent planning. In: AAAI, pp. 1163–1168 (2005)Google Scholar
  22. 22.
    Haslum, P., Geffner, H.: Admissible heuristics for optimal planning. pp. 140–149 (2000)Google Scholar
  23. 23.
    Helmert, M.: A planning heuristic based on causal graph analysis. In: ICAPS, pp. 161–170 (2004)Google Scholar
  24. 24.
    Hernádvölgyi, I.T.: Automatically Generated Lower Bounds for Search. PhD thesis, University of Ottawa (2003)Google Scholar
  25. 25.
    Hoffmann, J., Nebel, B.: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research 14, 253–302 (2001)zbMATHGoogle Scholar
  26. 26.
    Holland, J.: Adaption in Natural and Artificial Systems. PhD thesis, University of Michigan (1975)Google Scholar
  27. 27.
    Holte, R.C., Grajkowski, J., Tanner, B.: Hierarchical heuristic search revisited. In: Zucker, J.-D., Saitta, L. (eds.) SARA 2005. LNCS (LNAI), vol. 3607, pp. 121–133. Springer, Heidelberg (2005)Google Scholar
  28. 28.
    Holte, R.C., Hernádvögyi, I.T.: A space-time tradeoff for memory-based heuristics. In: AAAI (1999)Google Scholar
  29. 29.
    Holte, R.C., Newton, J., Felner, A., Meshulam, R., Furcy, D.: Multiple pattern databases. In: ICAPS, pp. 122–131 (2004)Google Scholar
  30. 30.
    Holte, R.C., Perez, M.B., Zimmer, R.M., Donald, A.J.: Hierarchical A*: Searching abstraction hierarchies. In: AAAI, pp. 530–535 (1996)Google Scholar
  31. 31.
    Jensen, R.M., Bryant, R.E., Veloso, M.M.: SetA*: An efficient BDD-based heuristic search algorithm. In: AAAI, pp. 668–673 (2002)Google Scholar
  32. 32.
    Junghanns, A.: Pushing the Limits: New Developments in Single-Agent Search. PhD thesis, University of Alberta (1999)Google Scholar
  33. 33.
    Klein, D., Manning, C.: A* parsing: Fast exact Viterbi parse selection. In: Human Language Technology Conference of North American Chapter of the Association for Computational Linguistics (2003)Google Scholar
  34. 34.
    Knoblock, C.A.: Automatically generating abstractions for planning. Artificial Intelligence 68(2), 243–302 (1994)zbMATHCrossRefGoogle Scholar
  35. 35.
    Korf, R.E.: Finding optimal solutions to Rubik’s Cube using pattern databases. In: AAAI, pp. 700–705 (1997)Google Scholar
  36. 36.
    Korf, R.E., Felner, A.: Chips Challenging Champions: Games, Computers and Artificial Intelligence. In: chapter Disjoint Pattern Database Heuristics, pp. 13–26. Elsevier, Amsterdam (2002)Google Scholar
  37. 37.
    Korf, R.E., Reid, M., Edelkamp, S.: Time Complexity of Iterative-Deepening-A*. Artificial Intelligence 129(1-2), 199–218 (2001)zbMATHCrossRefMathSciNetGoogle Scholar
  38. 38.
    Korf, R.E., Zhang, W., Thayer, I., Hohwald, H.: Frontier search. Journal of the ACM 52(5), 715–748 (2005)CrossRefMathSciNetGoogle Scholar
  39. 39.
    Kupferschmid, S., Hoffmann, J., Dierks, H., Behrmann, G.: Adapting an ai planning heuristic for directed model checking. In: Valmari, A. (ed.) Model Checking Software. LNCS, vol. 3925, Springer, Heidelberg (2006)CrossRefGoogle Scholar
  40. 40.
    Mostow, J., Prieditis, A.E.: Discovering admissible heuristics by abstracting and optimizing. In: IJCAI, pp. 701 – 707 (1989)Google Scholar
  41. 41.
    Muslea, I.: A general-propose AI planning system based on genetic programming. In: Genetic Programming Conference (Late Breaking Papers), pp. 157–164 (1997)Google Scholar
  42. 42.
    Pearl, J.: Heuristics. Addison-Wesley, London (1985)Google Scholar
  43. 43.
    Qian, K., Nymeyer, A.: Heuristic search algorithms based on symbolic data structures. In: ACAI, pp. 966–979 (2003)Google Scholar
  44. 44.
    Qian, K., Nymeyer, A.: Guided invariant model checking based on abstraction and symbolic pattern databases. In: Jensen, K., Podelski, A. (eds.) TACAS 2004. LNCS, vol. 2988, pp. 497–511. Springer, Heidelberg (2004)Google Scholar
  45. 45.
    Graf, S., Saidi, H.: Construction of abstract state graphs with PVS. In: Grumberg, O. (ed.) CAV 1997. LNCS, vol. 1254, pp. 72–83. Springer, Heidelberg (1997)Google Scholar
  46. 46.
    Schroedl, S.: An improved search algorithm for optimal multiple sequence alignment. Journal of Artificial Intelligence Research 23, 587–623 (2005)zbMATHMathSciNetGoogle Scholar
  47. 47.
    Silver, D.: Cooperative pathfinding. In: Conference on Artificial Intelligence and Interactive Digital Entertainment, pp. 117–122 (2005)Google Scholar
  48. 48.
    Spector, L.: Genetic programming and AI planning systems. In: AAAI, pp. 1329–1334 (1994)Google Scholar
  49. 49.
    Valtorta, M.: A result on the computational complexity of heuristic estimates for the A* algorithm. Information Sciences 34, 48–59 (1984)CrossRefMathSciNetGoogle Scholar
  50. 50.
    Wall, M.: GAlib – A C++ Library of Genetic Algorithm Components. Massachusetts Institute of Technology (2005)Google Scholar
  51. 51.
    Westerberg, H., Levine, J.: Optimising plans using genetic programming. In: ECP, page Poster (2001)Google Scholar
  52. 52.
    Zhou, R., Hansen, E.: Space-efficient memory-based heuristics. In: AAAI, pp. 677–682 (2004)Google Scholar
  53. 53.
    Zhou, R., Hansen, E.: External-memory pattern databases using structured duplicate detection. In: AAAI (2005)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2007

Authors and Affiliations

  • Stefan Edelkamp
    • 1
  1. 1.Computer Science Department, University of Dortmund 

Personalised recommendations