GP-rush: using genetic programming to evolve solvers for the rush hour puzzle

ABSTRACT

We evolve heuristics to guide IDA* search for the 6x6 and 8x8 versions of the Rush Hour puzzle, a PSPACE-Complete problem, for which no efficient solver has yet been reported. No effective heuristic functions are known for this domain, and--before applying any evolutionary thinking--we first devise several novel heuristic measures, which improve (non-evolutionary) search for some instances, but hinder search substantially for many other instances. We then turn to genetic programming (GP) and find that evolution proves immensely efficacious, managing to combine heuristics of such highly variable utility into composites that are nearly always beneficial, and far better than each separate component. GP is thus able to beat both the human player of the game and also the human designers of heuristics.

REFERENCES

• 1: Ricardo Aler , Daniel Borrafo , Pedro Isasi, Evolving Heuristics for Planning, Proceedings of the 7th International Conference on Evolutionary Programming VII, p.745-754, March 25-27, 1998
• 2: Ricardo Aler , Daniel Borrajo , Pedro Isasi, Learning to Solve Planning Problems Efficiently by Means of Genetic Programming, Evolutionary Computation, v.9 n.4, p.387-420, December 2001 [doi>10.1162/10636560152642841]
• 3: Ricardo Aler , Daniel Borrajo , Pedro Isasi, Using genetic programming to learn and improve control knowledge, Artificial Intelligence, v.141 n.1, p.29-56, October 2002 [doi>10.1016/S0004-3702(02)00246-1]
• 4: Daniel Borrajo , Manuela Veloso, Lazy Incremental Learning of Control Knowledge for EfficientlyObtaining Quality Plans, Artificial Intelligence Review, v.11 n.1-5, p.371-405, Feb. 1997 [doi>10.1023/A:1006549800144]
• 5: A. Botea, M. Muller, and J. Schaeffer. Using abstraction for planning in Sokoban. In CG: International Conference on Computers and Games. LNCS, 2003.
• 6: S. Collette, J.-F. Raskin, and F. Servais. On the symbolic computation of the hardest configurations of the Rush Hour game. In Proc. of the 5th International Conference on Computers and Games, LNCS 4630, pages 220--233. Springer-Verlag, 2006.
• 7: Joseph C. Culberson , Jonathan Schaeffer, Searching with Pattern Databases, Proceedings of the 11th Biennial Conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence, p.402-416, May 21-24, 1996
• 8: A. Felner, R. E. Korf, and S. Hanan. Additive pattern database heuristics. J. Artif. Intell. Res. (JAIR), 22:279--318, 2004.
• 9: H. Fernau, T. Hagerup, N. Nishimura, P. Ragde, and K. Reinhardt. On the parameterized complexity of the generalized Rush Hour puzzle. In Canadian Conference on Computational Geometry, pages 6--9, 2003.
• 10: Gary William Flake , Eric B. Baum, Rush Hour is PSAPCE-complete, or "Why you should generously tip parking lot attendants", Theoretical Computer Science, v.270 n.1-2, p.895-911, January [doi>10.1016/S0304-3975(01)00173-6]
• 11: P. W. Frey, Chess Skill in Man and Machine, Springer-Verlag New York, Inc., Secaucus, NJ, 1979
• 12: Othar Hansson , Andrew Mayer , Moti Yung, Criticizing solutions to relaxed models yields powerful admissible heuristics, Information Sciences: an International Journal, v.63 n.3, p.207-227, Sept. 15, 1992 [doi>10.1016/0020-0255(92)90070-O]
• 13: P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for heuristic determination of minimum path cost. IEEE Trans. on SSC, 4:100, 1968.
• 14: Robert Aubrey Hearn , Erik D. Demaine , Gerald J. Sussman, Games, puzzles, and computation, Massachusetts Institute of Technology, Cambridge, MA, 2006
• 15: Robert A. Hearn , Erik D. Demaine, PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation, Theoretical Computer Science, v.343 n.1-2, p.72-96, 10 October 2005 [doi>10.1016/j.tcs.2005.05.008]
• 16: A. Junghanns and J. Schaeffer. Sokoban: A challenging single-agent search problem. In IJCAI, pages 27--36. Universiteit, 1997.
• 17: Andreas Junghanns , Jonathan Schaeffer, Domain-Dependent Single-Agent Search Enhancements, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.570-577, July 31-August 06, 1999
• 18: Andreas Junghanns , Jonathan Schaeffer, Sokoban: improving the search with relevance cuts, Theoretical Computer Science, v.252 n.1-2, p.151-175, Feb. 6, 2001 [doi>10.1016/S0304-3975(00)00080-3]
• 19: G. Kendall, A. Parkes, and K. Spoerer. A survey of NP-complete puzzles. International Computer Games Association Journal (ICGA), 31:13--34, 2008.
• 20: Richard E. Korf, Depth-first iterative-deepening: an optimal admissible tree search, Artificial Intelligence, v.27 n.1, p.97-109, Sept. 1985 [doi>10.1016/0004-3702(85)90084-0]
• 21: Richard E. Korf, Macro-operators: a weak method for learning, Artificial Intelligence, v.26 n.1, p.35-77, April 1985 [doi>10.1016/0004-3702(85)90012-8]
• 22: R. E. Korf. Finding optimal solutions to rubik's cube using pattern databases. In AAAI/IAAI, pages 700--705, 1997.
• 23: Richard E. Korf , Ariel Felner, Disjoint pattern database heuristics, Artificial Intelligence, v.134 n.1-2, p.9-22, January 2002 [doi>10.1016/S0004-3702(01)00092-3]
• 24: John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
• 25: J. Levine and D. Humphreys. Learning action strategies for planning domains using genetic programming. In G. R. Raidl, J.-A. Meyer, M. Middendorf, S. Cagnoni, J. J. R. Cardalda, D. Corne, J. Gottlieb, A. Guillot, E. Hart, C. G. Johnson, and E. Marchiori, editors, EvoWorkshops, volume 2611 of Lecture Notes in Computer Science, pages 684--695. Springer, 2003.
• 26: David J. Montana, Strongly typed genetic programming, Evolutionary Computation, v.3 n.2, p.199-230, Summer 1995 [doi>10.1162/evco.1995.3.2.199]
• 27: J. Pearl. Heuristics. Addison-Wesley, Reading, Massachusetts, 1984.
• 28: Edwin P. D. Pednault, ADL: exploring the middle ground between STRIPS and the situation calculus, Proceedings of the first international conference on Principles of knowledge representation and reasoning, p.324-332, December 1989
• 29: A. Reinefeld , T. A. Marsland, Enhanced Iterative-Deepening Search, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.7, p.701-710, July 1994 [doi>10.1109/34.297950]
• 30: E. Robertson and I. Munro. NP-completeness, puzzles and games. Utilas Mathematica, 13:99--116, 1978.
• 31: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 32: F. Servais. Private communication.
• 33: L. A. Taylor and R. E. Korf. Pruning duplicate nodes in depth-first search. In AAAI, pages 756--761, 1993.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Design, Performance

Keywords:
genetic programming, heuristics, rush-hour puzzle, single-agent search