Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 8

Proceedings of the 2016 Federated Conference on Computer Science and Information Systems

A* Heuristic Based on a Hierarchical Space Model Extracted from Game Replays

,

DOI: http://dx.doi.org/10.15439/2016F104

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 21–30 ()

Full text

Abstract. The paper presents a new method of building a hierarchical model of the state space. The model is extracted fully automatically from game replays that store executed plan traces. It is used by a novel approach for estimating the distance between states in a state-space graph. The estimate is applied in the A* algorithm as a heuristic function to reduce the search space. The method was validated using the game Smart Blocks. It is a testbed environment for studying methods that benefit from game replay analysis. The proposed heuristic is dedicated to difficult classical planning problems, for which problem-specific or automated heuristics are difficult to obtain.

References

  1. R. Dechter and J. Pearl, “Generalized best-first search strategies and the optimality of A*,” J. ACM, vol. 32, no. 3, pp. 505–536, 1985. http://dx.doi.org/10.1145/3828.3830
  2. R. E. Fikes and N. J. Nilsson, “STRIPS: A new approach to the application of theorem proving to problem solving,” in Proceedings of the 2Nd International Joint Conference on Artificial Intelligence. Morgan Kaufmann Publishers Inc., 1971, pp. 608–620.
  3. X. Wang, “Learning by observation and practice: An incremental approach for planning operator acquisition,” in Proceedings of the 12th International Conference on Machine Learning. Morgan Kaufmann, 1995. doi: 10.1.1.36.7719 pp. 549–557.
  4. “Smart Blocks,” http://unity3ddev.net/smartblocks.
  5. S. M. LaValle, Planning Algorithms. Cambridge University Press, 2006. ISBN 0521862051
  6. D. Nau, M. Ghallab, and P. Traverso, Automated Planning: Theory & Practice. Morgan Kaufmann Publishers Inc., 2004. ISBN 1558608567
  7. D. M. Bourg and G. Seemann, AI for game developers. O’Reilly & Associates Inc., 2004. ISBN 0-596-00555-5
  8. D. Bryce and S. Kambhampati, “A tutorial on planning graph based reachability heuristics,” AI Magazine, vol. 28, no. 1, pp. 47–83, 2007.
  9. A. J. Champandard, “Planning in games: An overview and lessons learned,” http://aigamedev.com/open/review/planning-in-games/, 2013, accessed: 2015-11-11.
  10. J. Orkin, “Applying goal oriented action planning in games,” in AI Game Programming Wisdom 2. Charles River Media, 2002, pp. 217–229. [Online]. Available: http://web.media.mit.edu/~jorkin/GOAP_draft_AIWisdom2_2003.pdf
  11. A. Botea, M. Muller, and J. Schaeffer, “Near optimal hierarchical path-finding,” Journal of Game Development, vol. 1, pp. 7–28, 2004.
  12. L. Mosenlechner, N. Demmel, and M. Beetz, “Becoming action-aware through reasoning about logged plan execution traces,” in Intelligent Robots and Systems (IROS), 2010 IEEE/RSJ International Conference on, 2010. http://dx.doi.org/10.1109/IROS.2010.5650989. ISSN 2153-0858 pp. 2231–2236.
  13. I. Hulpuş, M. Fradinho, and C. Hayes, “On-the-Fly Adaptive Planning for Game-Based Learning,” in Case-Based Reasoning. Research and Development, ser. LNCS, I. Bichindaritz and S. Montani, Eds. Springer, 2010, vol. 6176, pp. 375–389.
  14. S. Sahasrabudhe and H. Munoz-Avila, “Mining cause-effect sequential patterns from action traces,” FLAIRS Conference, 2013. http://www.cse.lehigh.edu/~munoz/Publications/flairs04.pdf
  15. S. Breining, H. Kriegel, M. Schubert, and A. Züfle, “Action sequence mining,” Workshop on Machine Learning and Data Mining in Games, 2013. [Online]. Available: http://www-kd.iai.uni-bonn.de/dmlg11/program.html
  16. N. Nejati, P. Langley, and T. Konik, “Learning hierarchical task networks by observation,” in Proceedings of the 23rd International Conference on Machine Learning. ACM, 2006. http://dx.doi.org/10.1145/1143844.1143928. ISBN 1-59593-383-2 pp. 665–672.
  17. C. Hogg, H. Munoz-Avila, and U. Kuter, “Learning hierarchical task models from input traces,” Computational Intelligence, vol. 32, no. 1, pp. 3–48, 2016. http://dx.doi.org/10.1111/coin.12044
  18. H. Xu, B. T. R. Savarimuthu, A. Ghose, E. D. Morrison, Q. Cao, and Y. Shi, “Automatic BDI plan recognition from process execution logs and effect logs.” in Engineering Multi-Agent Systems, ser. LNCS, M. Cossentino, A. E. Fallah-Seghrouchni, and M. Winikoff, Eds., vol. 8245. Springer, 2013. http://dx.doi.org/10.1007/978-3-642-45343-4_15. ISBN 978-3-642-45342-7 pp. 274–291.
  19. G. Sukthankar and K. Sycara, “Robust and efficient plan recognition for dynamic multi-agent teams,” in Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, ser. AAMAS, vol. 3, 2008. ISBN 978-0-9817381-2-3 pp. 1383–1388.
  20. J. Hsieh, C. Sun, C. Wang, and C. Cheng, “Mining replays of real-time strategy games to learn player strategies,” Canadian Artificial Intelligence Conference, 2008. [Online]. Available: http: //gamelearninglab.nctu.edu.tw/ctsun/RTS%20player%20modeling.pdf
  21. B. Weber and M. Mateas, “A data mining approach to strategy prediction,” IEEE Symposium on Computational Intelligence and Games, 2009. [Online]. Available: http://alumni.soe.ucsc.edu/~bweber/pubs/cig_2009.pdf
  22. A. Botea, M. Muller, and J. Schaeffer, “Using abstraction for planning in Sokoban,” in Proceedings of the 3rd International Conference on Computers and Games. Springer, 2003. pp. 360–375.
  23. “Unity3D,” http://unity3d.com, accessed: 2015-11-11.
  24. T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson, Introduction to Algorithms, 2nd ed. MIT Press and McGraw-Hill, 2001. ISBN 0070131511
  25. M. Woolridge and M. J. Wooldridge, Introduction to Multiagent Systems. John Wiley & Sons, Inc., 2001. ISBN 978-0470519462
  26. “Wargus,” http://wargus.sourceforge.net, accessed: 2015-11-11.
  27. “BWAPI,” http://bwapi.github.io, accessed: 2015-11-11.
  28. “RoboCup,” http://www.robocup.org, accessed: 2015-11-11.
  29. S. J. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 2nd ed. Pearson Education, 2003. ISBN 0137903952
  30. R. Baeza-Yates, “A fast set intersection algorithm for sorted sequences,” in Combinatorial Pattern Matching, ser. LNCS, S. Sahinalp, S. Muthukrishnan, and U. Dogrusoz, Eds. Springer, 2004, vol. 3109, pp. 400–408. ISBN 978-3-540-22341-2
  31. J. Seipp, F. Pommerening, G. Roger, and M. Helmert, “Correlation complexity of classical planning domains,” in Proceedings of the 8th Workshop on Heuristics and Search for Domain-independent Planning (HSDIP), 2016, pp. 12–20. http://icaps16.icaps-conference.org/proceedings/hsdip16.pdf
  32. R. Liang, “A survey of heuristics for domain-independent planning,” Journal of Software, vol. 7, pp. 2099–2106, 2012. http://dx.doi.org/10.4304/jsw.7.9.2099-2106
  33. R. Wille, Formal Concept Analysis: Foundations and Applications. Springer, 2005, ch. Formal Concept Analysis as Mathematical Theory of Concepts and Concept Hierarchies, pp. 1–33. ISBN 978-3-540-31881-1
  34. S. O. Kuznetsov and S. A. Obiedkov, Algorithms for the Construction of Concept Lattices and Their Diagram Graphs. Springer, 2001, pp. 289–300. ISBN 978-3-540-44794-8