Classical AI Planning serves the goal of finding a sequence of actions that transforms a given state into a desired goal state. Given an adequate model of the world this technology can be used in a wide range of possible application scenarios. It has been deployed successfully in many real-world applications such as automated factories and robotics.
In this research project you have to model a set of puzzle games as a classical planning problem in the well known description language PDDL (consisting of two files: the PDDL problem instance defining the initial state and the goal, and the PDDL domain file defining the set of available actions). On top of that, a problem-dependent text format has to be developed that allows an easy and intuitive specification of the problem instance. That input should again be parsed and transformed into a PDDL problem file. Finally, an existing planning system should be deployed to solve the respective problem for differing initial states.
These planner and their solutions are to be analyzed. I.e, how long are optimal solutions? How large is the respective explored search space? How are these values if a non-admissible heuristic is used so that solutions are non-optimal?
- Planning and Optimization
- Knowledge in classical planning is helpful, but not required
- Lecture slides introducing classical planning from scratch, focusing on heuristic search, one 3-hour lecture: download
- Example puzzle games:
- Binary: https://www.puzzlemad.co.uk/2015/04/when-bi-nary-i...
- Waiter's tray / Six Bottle Puzzle: https://www.youtube.com/watch?v=vBf_NHDH_C0
- Towers of Hanoi: https://en.wikipedia.org/wiki/Tower_of_Hanoi
- You will be able to use AI planning and current existing planning systems to model and solve planning problems.
- Artificial Intelligence
- Automated Planning
- Puzzle Games