A* Heuristic Based on a Hierarchical Space Model Extracted from Game Replays
Bartłomiej Józef Dzieńkowski, Urszula Markowska-Kaczmar
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 (2016)
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.
- 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
- 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.
- 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.
- “Smart Blocks,” http://unity3ddev.net/smartblocks.
- S. M. LaValle, Planning Algorithms. Cambridge University Press, 2006. ISBN 0521862051
- D. Nau, M. Ghallab, and P. Traverso, Automated Planning: Theory & Practice. Morgan Kaufmann Publishers Inc., 2004. ISBN 1558608567
- D. M. Bourg and G. Seemann, AI for game developers. O’Reilly & Associates Inc., 2004. ISBN 0-596-00555-5
- D. Bryce and S. Kambhampati, “A tutorial on planning graph based reachability heuristics,” AI Magazine, vol. 28, no. 1, pp. 47–83, 2007.
- A. J. Champandard, “Planning in games: An overview and lessons learned,” http://aigamedev.com/open/review/planning-in-games/, 2013, accessed: 2015-11-11.
- 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
- A. Botea, M. Muller, and J. Schaeffer, “Near optimal hierarchical path-finding,” Journal of Game Development, vol. 1, pp. 7–28, 2004.
- 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.
- 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.
- 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
- 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
- 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.
- 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
- 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.
- 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.
- 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
- 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
- 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.
- “Unity3D,” http://unity3d.com, accessed: 2015-11-11.
- 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
- M. Woolridge and M. J. Wooldridge, Introduction to Multiagent Systems. John Wiley & Sons, Inc., 2001. ISBN 978-0470519462
- “Wargus,” http://wargus.sourceforge.net, accessed: 2015-11-11.
- “BWAPI,” http://bwapi.github.io, accessed: 2015-11-11.
- “RoboCup,” http://www.robocup.org, accessed: 2015-11-11.
- S. J. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 2nd ed. Pearson Education, 2003. ISBN 0137903952
- 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
- 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
- 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
- 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
- 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