Research Project: On Hierarchical Planning in Games

People

Supervisor

Description

This project aims at providing an overview about scientific papers that report where and how hierarchical planning techniques were and are applied -- either in practice or just on a conceptual basis.

Apart from an extensive literature survey, part of the project is to develop a concept on how to report on the found approaches, i.e., how to structure report: How should the papers be clustered? According to the formalism applied? According to whether it was used commercially or maybe even not at all (but it was just described in theory)? According to the purpose it was applied for (agent AI vs. something else, like level devel design)?

Note that "games" in the project title refers to both computer games as well as board or card games (i.e., not just "typical video games").

Please note: Personally I'm most interested in the survey character of this project -- i.e., if I had anything to say, then even *the entire project* could be an entire survey (which I would like to publish later on as survey article). Sadly, this is not allowed in any ANU project that I am aware of. That is, in each ANU project, surveys are not allowed, this might just be a small part (at most 30% or so, probably *much* less!) of the project, as part of the related work. Instead, projects must contain a significant practical -- i.e., *creative* -- part.

Thus, the project must also -- due to ANU rules -- contain some practical part that fits into this context. As this is not my main motivation about this work we still had to brainstorm what that could be. I'm thinking about identifying one such application/game and creating a model in HDDL, i.e., the standard domain description language for hierarchical planning problems and then conduct an empirical evaluation using state-of-the-art HTN planners. To make sure that this task does not become too hard, a scientific paper should be identified that makes such a model already available, so that the task would be to just transfer it to the language HDDL.

Important: Since this project should contain both an extensive literature research as well as an empirical part, the project shold be at least 12 points, 24 might be even better.

Goals

  • Conduct a complete literature survey of pretty much every single project and/or scientific paper that used Hierarchical Planning in any form of (computer) games.
  • Apart from having such a comprehensive (complete) list, it should of course be presented in an adequate way. In particular, the survey should have a clear message: Why was hierarchical planning chosen? Was it worth it? Would other formalisms have been better? (Were they even considered or even used?) Are we going to expect more applications of it? Where did it work particulalrly well? Did authors talk about lessons learned themselves?
  • Model one of the identified games from the literature in HDDL, i.e., transform one of the models from the originally used modeling language into this standard one so that it can be solved by current state-of-the-art planners.

Requirements

  • It expect that you have a good understanding (proven by good grades) in any related formal discipline, such as AI, AI planning, computational complexity, graph theory, etc.
  • You should not be bored with reading papers as conducting a survey will be a significant part of the work.
  • Relatedly, the main outcome is a report, so I expect that you can write very good English.

Please send me:

  • The course code.
  • The URL of your course.
  • The number of points your course has (i.e., 12, 24, or 24 honours final project).
  • When you would like to do your project.

Background Literature

  • My Hierarchical Planning Survey from IJCAI 2019 (You have to understand hierarchical planning!)
  • Xenija Neufeld (2018): Building a Planner: A Survey of Planning Systems Used in Commercial Video Games (IEEE Artikel)

Gain

  • Obtain knowledge on how AI planning is applied in computer games.
  • Being able to read through lots of literature to grasp and reproduce (in terms of a short summary) its core messages.
  • Being able to model hierarchical planning problems using HDDL, the standard description language for HTN planning problems.

Keywords

  • HTN Planning / Hierarchical Planning
  • Computer Game AI
  • Literature Survey

Updated:  10 August 2021/Responsible Officer:  Head of School/Page Contact:  CECS Webmaster