Engineering in Computer Science and Artificial Intelligence

FABIO PATRIZI

General objectives.
The course aims to introduce the fundamentals of Artificial Intelligence, with a particular emphasis on automated reasoning and sequential decision making.
Students will become familiar with the main formalisms and approaches for knowledge representation and reasoning, in both static and dynamic contexts.
They will also learn the basics of decision making approaches for deterministic, non-deterministic, adversarial, and stochastic domains.

Specific objectives.

Knowledge and understanding:
Students will be introduced to the basics of Knowledge Representation for static and dynamic systems through formal approaches: propositional and first-order logic, situation calculus, MDPs. The fundamental logical tasks (evaluation, satisfiability, validity, logical implication) will be studied and basic solution techniques (DPLL, tableau method) will be learnt.
The goal is to understand the importance of the formal model and of domain-independent approaches as fundamental tools to automatically solve problems.
Students will learn how to model a Planning domain through the PDDL language and how to solve planning problems in deterministic, non-deterministic, adversarial, and stochastic scenarios. Essential forward state-space search techniques will be introduced: uninformed search, heuristic search, best-first search, A* search, AND-OR search.
For stochastic scenarios, Policy Evaluation and Policy Iteration will be learnt.

Applying knowledge and understanding:
Students will learn how to abstract and model real-world scenarios as static or dynamic domains in a rigorous way, as well as to identify and formalize real-world problems. They will also be able to apply the techniques acquired during the course to solve the modelled problems.
By understanding how to formally model and solve problems, students will become able to design and implement simple reasoning systems for a variety of real-world scenarios and related problems.

Making judgements:
Students will be able to evaluate the appropriateness and quality of a representation formalism with respect to various classes of problems and to select the most suitable solution technique.

Communication:
The course will provide students with the basic notions and vocabulary to effectively interact with their pairs and experts in the area. Oral communication skills are stimulated through the interaction during class, while writing skills are developed through the analysis of exercises and answers to the open questions included in the final test.

Lifelong learning skills:
The course will provide students with the essential tools needed to access the specialised literature. In this way, they can autonomously strengthen and broaden their competencies. In addition to such learning capabilities, students will also acquire advanced modelling and general problem solving skills.

The course aims to introduce the fundamentals of Artificial Intelligence, with a particular emphasis on automated reasoning techniques. Students will become familiar with the main formalisms for knowledge representation and with logical inference methodologies, in both static and dynamic contexts—deterministic, non-deterministic, and stochastic.

By the end of the course, students will be able to:
- Formalize simple logical reasoning problems using classical knowledge representation formalisms, particularly propositional logic and first-order logic.
- Identify and solve fundamental logical problems such as satisfiability, validity, logical implication, and query evaluation.
- Apply basic automated reasoning techniques, including: DPLL algorithm, Tableaux method, Logical deduction.
- Model dynamic domains, whether deterministic, non-deterministic, or stochastic, using formalisms such as Situation Calculus, PDDL, and Markov Decision Processes (MDPs).
- Apply basic reasoning and planning techniques in deterministic, non-deterministic, and stochastic domains, including: Regression, A* Search, AND-OR Search, Policy Evaluation, Policy Iteration

Knowledge of analysis, modeling, and object-oriented design. Databases. Basic notions of probability and statistics, covered in introductory academic-level courses.

Introduction.
Knowledge Representation: modeling the domain of interest; enabling autonomy; the role of logic.
Propositional Logic: syntax and semantics; evaluation, satisfiability, validity, logical implication; propositional tableaux; DPLL.
First-Order Logic: syntax, semantics; evaluation, satisfiability, validity, logical implication; FO tableaux.
Classical Planning: deterministic domains; STRIPS, ADL, PDDL, transition systems, forward search, Heuristics, Best-First, A* Search.
Contingent Planning (FOND): nondeterministic domains, PDDL with oneof operator, nondeterministic planning by AND-OR Search.
Reasoning about Actions: modeling (discrete) dynamic domains, action preconditions, effects, the frame problem.
Situation Calculus: precondition and successor-state axioms; situation tree; regression; executability and projection.
Modeling and planning for stochastic dynamic domains: MDPs, Policy Evaluation, Policy Iteration.

Artificial Intelligence: A Modern Approach, Global Edition, 4th Edition by Stuart Russell, Peter Norvig, Pearson 2020 (selected chapters).

The course is taught in person. Lectures are recorded and made available asynchronously.
Videos about labs and additional/focus lectures are made available.

Attendance is not mandatory but strongly encouraged.

The exam consists in a written test including questions about:
- Dynamic domain modeling.
- Reasoning about the modelled domain, e.g., regression, progression, or planning.
- Reasoning about propositional and/or first-order knowledge (e.g., satisfiability, validity, logical implication of formulas/knowledge bases).
- Techniques for Modeling and Planning in stochastic domains.

Suppose we have solar-powered cars that can move to specific locations in the city to deliver orders. Fluents:
• AtLoc(x, y) denotes that car x is in the location y.
• Delivered(y) denotes that the order has been delivered in location y. • Empty(x) denotes that the battery level of car x is empty.
Actions:
• move(x, y), which allows car x to move in location y. The action can be done if the battery of x is not empty and if no order
has been delivered in y. The effect is that x is in location y and not anymore in the previous one.
• recharge(x), which allows car x to recharge its battery using the solar energy. The action can be done if the battery of x is
empty, and the effect is that the battery of x will be full again.
• deliver(x,y), which allows car x to deliver an order in location y. The action can be done if x is located in y, and the effect
is that the order is delivered in y and the battery of x becomes empty.
Initial situation:
We have three cars c1, c2 and c3 with a full battery, and four locations l1, l2, l3 and l4. Initially, the cars are in l2, and no order has been delivered in any location.
Exercise 1. Formalize the above scenario as a Basic Action Theory in Situation Calculus. Consider the sequence of actions ρ = move(c1,l3);deliver(c1,l3);recharge(c1):
1. Check by regression if ρ is executable in S0;
2. Check by regression whether ρ results in a situation where c1 is in l2.
3. Check by regression whether ρ results in a situation where the order has been delivered in l3.
Exercise 2. Consider the following goal AtLoc(c1, l3) ∧ ¬AtLoc(c1, l1) ∧ ¬AtLoc(c1, l2) ∧ ¬AtLoc(c1, l4). First formalize the above scenario as a PDDL domain file and a PDDL problem file. Then:
1. Draw the corresponding transition system;
2. Solve planning for achieving the above goal by using forward depth-first search (uninformed), reporting the various steps of the forward search computation, and returning the resulting plan.
Exercise 3.
1. Formalize the following knowledge in FOL, by introducing suitable predicates, functions and constants, as needed:
• (φ1) Every animal is carnivore or herbivore • (φ2) Carnivores are not herbivores
• (φ3) Only carnivores chase other animals
• (φ4) No animal can chase itself
Using the tableaux method, check whether the knowledge base KB = {φ1,φ2,φ3} logically implies φ4. If not, show a counterexample.
2. Consider following propositional knowledge base KB:
• ¬a∨b∨c • ¬b∨a
• ¬c∨a
• ¬b∨¬c
• ¬a∨c
Using the DPLL procedure, check whether KB |= c ⊃ a.

• Introduction. Search Problems and Algorithms.(week 1-2)
  • Books: [AIMA] Artificial Intelligence: A Modern Approach, Global Edition, 4th Edition by Stuart Russell, Peter Norvig, Pearson 2020. Ch. 1, 2.


• Propositional logic and satisfiability algorithms. (week 3-4)
  • Books: AIMA: 7.4.1 - 7.4.3, 7.6.1


• First-order logic.(week 5-6)
  • Books: AIMA: 8.1-8.3


• Automated Planning(week 7-8)
  • Books: AIMA: 3 - 3.4.4, 4.3 - 4.3.2, 11 - 11.3.1


• Knowledge Representation and reasoning under uncertainty.(week 9-10)
  • Books: AIMA: 12, 17


• Situation calculus.(week 11-12)
  • Books: Slides and lecture notes.