Reasoning and Planning

Master in Artificial Intelligence

Slides

• Unit 1. Introduction. Videos: 
• RP01 [quiz], knowledge representation (KR), reasoning about actions
  
• RP02 [quiz], example-based methodology, declarative problem solving
  
• RP03 [quiz], KR goals, elaboration tolerance, STRIPS language
  
• RP04 [quiz], frame problem and inertia, non-monotonic reasoning, KR topics
  
  
• Missionaries & cannibals automaton (by Ovidio Manteiga)
  
  
• Unit 2. Propositional Reasoning. Videos: 
• RP05 [quiz], propositional logic, syntax and semantics, set of models
  
• RP06 [quiz], entailment, inconsistence, tautology, deduction theorem, weaker/stronger formulas
  
• RP07 [quiz], deduction/abduction/induction, from language to formulas, the SAT problem
  
• RP08 [quiz], computational complexity, NP-completeness
• RP09 [quiz], SAT solvers, Conjunctive Normal Form (CNF)
  
  
• 3 examples for propositional reasoning [slides]
  
  
• Unit 3. Rule-based Reasoning. Videos:
  
  • RP10 [quiz], Closed World Assumption (CWA), positive programs, least model, T_P immediate consequences
    
  • RP11 [quiz], default negation, program reduct, stable models
  • RP12 [quiz], examples getting stable models, stratified programs
  • RP13 [quiz], choice rules, constraints, splitting
  • RP14a [quiz], Here-and-There (HT)
    
  • RP14b [quiz], Equilibrium models, strong equivalence
    
  
  
• Unit 4. Relational Reasoning. Videos:
• RP15 [quiz], grounding, deductive databases, Datalog, domain independence, safety
  
• RP16 [quiz], Hamiltonian cycles, Answer Set Programming (ASP), GDT methodology
  
• RP17 [quiz], Pooling, terms, reification, aggregates
• RP18a [quiz], Optimisation
• RP18b [quiz], ASP applications and solvers
  
  
• Exercises (using clingraph): sudoku.zip, einstein.zip
• Exercise with optimisation and preferences
  
  
• Unit 5. Temporal Reasoning and Planning. Videos:
• RP19 [quiz], telingo, switches example, simulation, postdiction, planning
• RP20 [quiz], missionaries and cannibals, the blocks world
  
• RP21 [quiz], abduction, explanation, diagnosis
  
• RP22 [quiz], temporal equilibrium logic
• RP23 [quiz], classical AI Planning, STRIPS and PDDL, Forward Planning
• RP24 [quiz], Backward Planning, Bounded Horizon, Other Planning Techniques
• RP25 [quiz], Planning and Learning, Beyond Classical Planning
  


• Unit 6. Terminological Reasoning. Videos:
• RP26 [quiz], Description Logics
  
• Link to Description Logic Complexity Navigator
  
  
  
• Unit 7. Reasoning under Uncertainty (Vicente Moret)
  

• A pair of talks on the World Logic Day, January 14 2020:
• Georg Gottlob
• Moshe Y. Vardi
  

Assignments

• Assignment 1: Thermometers. Deadline: Monday, November 9th, 2025.
  

Old assignments

• 2023-24. assignment 1: The light-up puzzle.
  
• 2023-24, assignment 2: The vacuum cleaner.
  
• 2022-23, assignment 1: Binairo problem.
  
• 2022-23, assignment 2: Wire routing problem.

Lab materials

• Files for drawing the N Queens problem (using pygame): queens.zip
  
• Files for drawing a Sudoku (using pygame): sudoku.zip
  
• Files for drawing the Einstein's puzzle (using pygame): einstein.zip
  

Previous exams

• January 2023: statement, solutions
• June 2023: statement, solutions
• January 2024: statement, solutions
• June 2024: statement, solutions
  

Documentation and bibliography

• clingo, gringo/clasp guide
• G. Brewka, T. Eiter and M. Truszczynski: Answer Set Programming at a Glance. Communications of the ACM 54(12): 92-103 (2011)
  
• E. Erdem, M. Gelfond and N. Leone: Applications of Answer Set Programming. AI Magazine 37(3): 53-68 (2016)
  

Maintained by Pedro Cabalar