Planning and reasoning

Lecturer: Paolo Liberatore
Year: 2022/2023

Change

Starting from year 2023/2024, the course will be held by Professor Andrea Marrella. Changes of the course program and exam format will be announced by him.

Students enrolled in the year 2021/2022 and before who attended the course in year 2022/2023 and before can still take the exam with the previous professor, with the old exam format.

Program

• planning:
  • the planning problem
  • planning languages
  • heuristics search
  • domain-independent heuristics
  • non-deterministic planning
  • planning by translation
  • preference-based planning
  • planning portfolio
  suggested book: Automated Planning: Theory & Practice by Malik Ghallab, Dana Nau, Paolo Traverso

• automated reasoning:
  • incomplete methods: GSAT and unit propagation
  • DPLL
  • propositional tableau
  • First-order logic, examples
  • First-order logic tableaux: ground and with unification
  • modal logics and tableau for modal logics
  • LTL, model checking and symbolic model checking
  • propositional natural deduction and first-order natural deduction
  • Hilbert systems
• constraint satisfaction
• belief revision

Final project and exam

Students need to complete a project on one of the two parts of the program (automated planning or automated reasoning) and pass a test on the other. Currently, the test is by an homework assigment.

The project may be:

• an essay on some research topic; examples: deontic logic; preference-based planning; students may propose a topic of their choice, if related to either automated reasoning or planning
• a program that is related to automated reasoning or automated planning; example: write a program that searches for propositional formulae that are as short as possible but still difficult for GSAT; another example: write a system for planning the download and installation of Linux packages;
• a mix of the two, with a scientific literature search followed by the development of a program that improves or uses it

In all cases a report is expected.

Student may propose their own projects, and are actually encouraged to do so especially regarding solution of realistic problems. Otherwise, students may develop a project as in the list of example project Either way, the project subject to a previous approval from the professor.