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. It is thus a general problem solving technique that's applied when ever we need to find a sequence of actions (of unknown lenght) to transform an initial world state into a state that fulfills some desired properties.
Other AI techniques, mostly Constraint Satisfaction Problem (CSP) solvers, Integer Linear Programming (ILP) solvers, or Satisfiability (SAT) solvers, are used to solve problems that require to find a certain "configuration", or an "assignment" of values to a pre-defined number of variables.
Both technologies are thus well-suited to solve a range of puzzle games or board games.
In this project, we will first decide on approximately two interesting puzzles or games (feel free to propose something!). Then you will have to:
- model these games/puzzles in an appropriate description language (classical planning, CSP, ILP, etc.) of the respective technology
- translate this formal model into a text-file representation using standard languages like PDDL for classical planning.
- conduct an empirical evaluation thus comparing different solvers and also different versions of the model
- present the result in your project report
Please note that I will accept almost no if any students for S1 2020 due to an extreme work-load teaching-wise. You might apply, but chances for acceptance are slim (unless you have expectional good grades in the clear HD spectrum).
- Planning and Optimization
- Knowledge in classical planning is helpful, but not required
- Knowledge in constraint reasoning (CSP, SAT, etc.) are helpful, but not required
Please send me:
- The course code.
- The URL of your course.
- The number of points your course has (i.e., 6, 12, 24, or 24 honours final project).
- When you would like to do your project.
- 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 -- OR, depending on the technology you end up using -- you will be able to use constraint reasoning and current existing constraint reasoning systems to model and solve constraint reasoning problems.
- Artificial Intelligence
- Automated Planning
- Constraint Reasoning
- Puzzle Games