Il corso mira a fornire un'introduzione alle principali problematiche, metodologie, tecniche e applicazioni dell'intelligenza artificiale.
Introduzione e concetti preliminari. Risoluzione di problemi attraverso ricerca. Rappresentazione della conoscenza, ragionamento automatico e logica. Introduzione alla programmazione logica. Problemi di soddisfacimento di vincoli. Ragionamento e conoscenza in presenza di incertezza. Pianificazione automatica. Introduzione all'apprendimento automatico
Introduzione e concetti preliminari
Cenni storici dell'IA, definizioni e obiettivi dell'IA. Cenni storici dell'IA, definizioni e obiettivi dell'IA. Concetti generali, agente razionale ideale, struttura di un agente intelligente, concetti preliminari di programmi agente, agenti con riflessi, agenti con stato del mondo, agenti basati su pianificazione e utilità, tipologie di ambiente per un agente.
Risoluzione di problemi attraverso ricerca
Concetti preliminari, conoscenza dell'agente e tipologie di problemi, problemi ben definiti e soluzioni, scelta degli stati e delle azioni (operatori). Diagramma degli stati, albero di ricerca, strategie di ricerca non informate e informate. Esempi di euristiche, criteri principali per valutare una strategia di ricerca. Ricerca in profondità, ricerca in ampiezza, ricerca con approfondimento iterativo. Analisi delle proprietà computazionali. Generalizzazione a grafi di ricerca. Backtracking e CSP, backtracking cronologico e backjumping. Ricerca in ampiezza informata, ricerca bestfirst, hillclimbing e discesa del gradiente, ricerca con memoria e senza memoria, tecniche di ricerca locale e problematiche connesse (minimi locali, pianure, creste). Algoritmo Simulated Anealing, beam search, algoritmi genetici, ricerca on-line. Tecniche di ricerca locale per SAT: algoritmi GSAT e WSAT. Tecniche di ricerca complete A*, IDA*, funzioni euristiche ammissibili, teorema completezza e ottimalità di A* e IDA*, A* per grafi. Algoritmi per giochi.
Rappresentazione della conoscenza, ragionamento automatico e logica
Introduzione alla logica come linguaggio di rappresentazione della conoscenza, concetti e definizioni di base: base di conoscenza, funzioni TELL e ASK, implicazione logica, dimostrazione, sintassi e semantica di un linguaggio, regole di inferenza e procedure di inferenza, soddisfacibilità, validità e tautologie. Logica proposizionale: sintassi, semantica e regole di inferenza. Esempi di dimostrazioni. Introduzione alla logica del I ordine: sintassi, semantica (intepretazione, modelli), regole di conversione deni quantificatori, definizione di teoria assiomatica del I ordine, decidibilità, semidecidibilità. Inferenza nella logica del I ordine, regole di inferenza per i quantificatori. Modus ponens generalizzato, sostituzioni di variabili, unificazione, unificatore più generale, forma normale di Horn, algoritmo di unificazione, teorema di unificazione. Procedure di inferenza "forward chaining" e "backward chaining". Risoluzione generalizzata per la logica del I ordine, dimostrazioni per refutazione, teorema di validità e completezza della risoluzione, grafi di refutazione. Conversione di formule del I ordine in forma normale congiuntiva, clausolare ed implicativa. Sussunzione tra formule, strategie di risoluzione. Il dimostratore di teoremi Otter.
Introduzione alla programmazione logica
Notazioni e concetti di base, risoluzione SLD, regola di calcolo, alberi di derivazione, nondeterminismo (scelta della regola), strategie di ricerca per la risoluzione SLD; introduzione al Prolog, negazione come fallimento, "unique name assumption". Dimostratori di teoremi: principali differenze con la programmazione logica.
Problemi di soddisfacimento di vincoli
Definizione di un Constraint Satisfaction Problem (CSP). Tecniche per CSP con domini discreti: Algoritmo di backtracking, metodi di ac-consistency, path-consistency, forward-checking, metodi basati su ricerca locale. Esempi e cenni ad applicazioni. Definizione di CSP binari con variabili continue. Ragionamento temporale qualitativo: algebra dei punti e algebra degli intervalli. Ragionamento temporale quantitativo: linguaggi TCSP, STP e DTP. Principali problemi di ragionamento temporale: complessità computazionale, algoritmi ed esempi di applicazione. Metodi basati su grafi per l'algebra dei punti. Ragionamento spaziale e spazio-temporale qualitativo. Il Region Connection Calculus (RCC5 e RCC8): complessità, algoritmi, esempi e problemi aperti.
Ragionamento e conoscenza in presenza di incertezza
Introduzione all'incertezza attraverso metodi probabilistici. Inferenza probabilistica e reti Bayesiane. Esempi di applicazioni. Sintassi, semantica, e costruzione di una rete Bayesiana. Struttura della rete e complessità del ragionamento. Metodi e algoritmi per l'inferenza esatta e approssimata in una rete Bayesiana. Modelli per rappresentare conoscenza incerta attraverso reti Bayesiane ("or rumoroso", "and rumoroso") esempi. Processi decisionali di Markov in ambienti totalmente osservabili e parzialmente osservabili (definizioni, algoritmi, esempi e cenni ad applicazioni). Cenni a tool esistenti per la creazione e l'uso di reti Bayesiane (Netica). Esempi di applicazioni delle reti Bayesiane.
Pianificazione automatica
Concetti preliminari sulla rappresentazione e gestione di azioni: Pianificazione domain-dependent, domain-independent, configurabile, interattiva. Esempi di applicazioni.
I linguaggi di pianificazione ad operatori STRIPS, ADL e PDDL (Planning Domain Definition Language). Sintassi e semantica. Esempi e esercizi di formalizzazione in PDDL per la codifica di semplici domini applicativi. Introduzione al Calcolo delle Situazioni. Esempi di derivazione automatica di un piano come risposta nella dimostrazione di un teorema.
Pianificazione nello spazio degli stati: approcci basati su ricerca euristica. Metodi progressivi e regressivi. Esempi di euristiche. Pianificazione nello spazio dei piani parziali: algoritmo POP base e generalizzazione a schemi di operatori con variabili. Il sistema di pianificazione UCPOP (cenni) e derivati. Algoritmi basati su "planning graph": il sistema Graphplan. Metodi basati su ricerca euristica locale: sistemi FF e LPG. Metodi basati su compilazione e verifica dei modelli in logica proposizionale: sistemi SATPLAN e BlackBox.
Pianificazione con informazioni temporali e numeriche. Integrazione di pianificazione e scheduling (esempi con il sistema LPG-td). Pianificazione interattiva e "mixed-initiative".
Elementi di apprendimento automatico
Reti Neurali e algoritmo back propagatio per l'apprendimento dei parametri della rete.
Uno dei segenti testi:
(a) Russel and Norvig, Artificial Intelligence - a Modern Approach, Third edition, Pearson, 2010.
(b) Russel Norvig, Intelligenza Artificiale - un Approccio Moderno, seconda edizione, Pearson Prentice Hall, 2005.
Materiale didattico distribuito dal docente
Lezioni frontali, esercitazioni (anche in laboratorio).
Prova scritta, prova orale e/o elaborato