Ricerca e Ragionamento
Fondamenti classici dell'AI: agenti intelligenti, algoritmi di ricerca uninformed e informed (A*), ricerca locale, CSP con backtracking e arc-consistency, giochi zero-sum con minimax e alpha-beta, e rappresentazione della conoscenza in logica proposizionale e del primo ordine.
Ricerca e Ragionamento
Appunti del modulo dedicato ai fondamenti classici dell'intelligenza artificiale.
Le note coprono l'intera filiera: dalla definizione formale di agente intelligente con il framework PEAS e la classificazione degli ambienti, agli algoritmi di ricerca sistematica (BFS, DFS, IDS, UCS, A* con euristiche ammissibili e consistenti), alla ricerca locale per spazi grandi (hill climbing, simulated annealing, algoritmi evolutivi).
Si trattano poi gli ambienti complessi parzialmente osservabili tramite belief state e alberi AND-OR, i Constraint Satisfaction Problems con backtracking search, propagazione dei vincoli e algoritmo AC-3, e i giochi zero-sum a due giocatori con minimax, alpha-beta pruning e Monte Carlo Tree Search.
Il modulo si conclude con la rappresentazione della conoscenza e il ragionamento (KRR): logica proposizionale, model checking, theorem proving by resolution, clausole di Horn, e logica del primo ordine con quantificatori e inferenza.
Contents
- Agenti Intelligenti Definizione formale di agente intelligente, razionalità e framework PEAS; classificazione degli ambienti (osservabilità, determinismo, episodicità) e tipologie di agenti (riflessivi, basati su modello, orientati a obiettivi, basati sull'utilità, apprendenti).
- Algoritmi di Ricerca Formulazione formale dei problemi di ricerca e panoramica degli algoritmi uninformed (BFS, DFS, IDS, UCS) e informed (greedy best-first, A*) con analisi di completezza, ottimalità e complessità.
- Ricerca Locale e Algoritmi Evolutivi Algoritmi di ricerca locale (hill climbing, simulated annealing, local beam search) e algoritmi evolutivi per la massimizzazione di funzioni obiettivo in spazi grandi o continui senza memoria del percorso.
- Ricerca in Ambienti Complessi Ricerca in ambienti parzialmente osservabili e non deterministici tramite belief state, alberi AND-OR e piani condizionali; trattamento di problemi sensorless e con osservazioni parziali.
- Constraint Satisfaction Problems (CSP) Definizione formale dei CSP con variabili, domini e vincoli; algoritmi di risoluzione tramite backtracking search, propagazione dei vincoli (AC-3), coerenza locale e ricerca locale su assegnamenti completi.
- Sistemi Multi-Agente e Giochi Ricerca in ambienti multi-agente competitivi e cooperativi; algoritmo minimax per giochi zero-sum a due giocatori, alpha-beta pruning per ridurre lo spazio di ricerca, e Monte Carlo Tree Search (MCTS).
- Rappresentazione della Conoscenza e Ragionamento Knowledge representation and reasoning (KRR): agenti basati sulla conoscenza, logica proposizionale, inferenza tramite model checking e resolution, clausole di Horn, e logica del primo ordine con predicati e quantificatori.