AUTOMATED REASONING

Academic Year 2019-2020

Teachers:
Agostino Dovier

Total Course Credits: 6

Teaching Period: First Period

Teaching Language: Inglese

Prerequisites. Bachelor degree in Computer Science or similar curricula.

Teaching Methods. Material will be presented mostly using slides. Practical lessons with problem encoding in various paradigms will be organized (possibly, in lab).

Verification of Learning. Development of a project where the student can apply the techniques subject of the course; in particular using constraint programming and answer set programming for problem modeling and experimental comparison of the approaches. There is a mandatory oral exams where the knowledge of the foundational part of all the course program is verified.

More Information. All the material is available on web.

OBJECTIVES

The student will study the main languages and techniques for knowledge representation and automated reasoning. Emphasis will be given on declarative Languages based on the notion of “constraint” and on their practical application will be analyzed: Constraint programming, answer set programming, and on action description languages.

HARD SKILLS

1.1 Knowledge and understanding: the student will improve her/his capability of analyzing and solving problem. She/He will see an overview of the Artificial Intelligence languages for modeling problems and techniques for solving them. In particular the course is mainly focused on logical-declarative modeling and on constraint based solution search

1.2 Applying knowledge and understanding: the student will be able to exploit the knowledge of the techniques and of the languages learnt for solving real-life problems, such as combinatorial problems, scheduling problem, automated reasoning problem etc. that are ubiquitous in industry.

SOFT SKILLS

2.1 Making judgements: given the formal specifics of a problem, the student will have the capability of understanding if it is one that can be naturally solved with the techniques seen in the course. In particular, if the problem is NP complete, these techniques allow compact encodings and allow to exploit the “AI’’ embedded into the solvers for solutions search. Similarly, if the problem is a KR problem where several agents have to reason individually or together for reaching a specified goal, the student will know how to model and solve it.

2.2 Communication: the student will learn the precise terminology, the possibilities, and the intrinsic limits of the “exact’’ part of artificial intelligence and is able to use them properly when presenting his work even to non specialists.

2.3 Lifelong learning skills: the student will learn some of the “magic’’ that is inside artificial intelligence and can use this knowledge as a starting point for the study of development of the area and of its application in several fields in the remaining part of its life. Of course, being the course held in English, she/he will improve her/his language skills.

IS/Fundamental Issues: – Overview of AI problems, examples of successful recent AI applications IS/Basic Knowledge Representation and Reasoning: – Review of propositional and predicate logic – Resolution and theorem proving IS/Advanced Representation and Reasoning: – Knowledge representation issues – Non-monotonic reasoning – Reasoning about action and change – Planning – Argumentation IS/Basic Search Strategies – Problem spaces (states, goals and operators), problem solving by search – Factored representation (factoring state into variables) – Uninformed search (breadth-first, depth-first, depth-first with iterative deepening) – Heuristics and informed search (hill-climbing, generic best-first, A*) – Space and time efficiency of search – Constraint satisfaction (backtracking and local search methods) IS/Agents – Definitions of agents – Multi-agent systems (Collaborative agents) IS/Advanced Search – Global constraints – Large Neighborhood Search – SAT and ASP solving with Learning – Parallelism Students should encode and solve problems using Answer Set Programming and Minizinc (and will meet PDDL and Picat)

TEXTS

Handbook of Constraint Programming. By Francesca Rossi, Peter van Beek and Toby Walsh. Elsevier.

M. Gelfond and Y. Kahl. Knowledge Representation, Reasoning, and the Design of Intelligent Agents. The Answer-Set Programming Approach. Cambridge University Press.

Lecture Notes available on-line