Appunti completi corso Intelligenza Artificiale

Saltiamo beatamente l’introduzione concettuale che a leggerla è una palla assurda e

passiamo subito al sodo. Chiamiamo AGENTE un dispositivo che può osservare

l’ambiente attraverso dei SENSORI e modificarlo con degli ATTUATORI. Senza per forza

tirar fuori robot spaziali che distruggono una città, anche un normale PC è un agente

perché con dei sensori prende degli input e con degli attuatori stampa degli output.

Diamo una definizione di AGENTE RAZIONALE: per ogni possibile sequenza di

percezioni, l’agente deve scegliere la prossima azione in modo da massimizzare la

misura della performance, data la conoscenza che l’agente ha in partenza e che ha

acquisito col tempo.

Per razionale non intendiamo perfetto o onnisciente, perché le scelte che fa un agente

qualsiasi (anche umano) si basano sulla conoscenza che esso ha del mondo, che è

parziale. Tipo se vediamo una strada vuota e decidiamo di attraversarla, è molto razionale.

Poi se mentre attraversiamo la strada a 10 km di altezza si stacca un pezzo di aereo e

quello ci cade in testa, non possiamo mica dire che siamo stati irrazionali nel decidere di

attraversare la strada. Semplicemente nella nostra percezione del mondo non c’era

quell’elemento. La razionalità si basa sulla conoscenza parziale che abbiamo ottenuto nel

tempo in un certo ambiente. Un aspetto importante è quindi il cosiddetto INFORMATION

GATHERING, cioè ottenere informazioni sull’ambiente per migliorare le decisioni future.

Un agente intelligente deve avere AUTONOMIA, cioè deve essere in grado, da sé, di

osservare l’ambiente. Se ad un agente gli fissi tu una conoscenza iniziale e l’agente si

comporta basandosi su quella, basta che nel mondo reale cambi qualcosa e l’agente non

se ne accorge.

Siccome gli agenti trovano soluzioni a problemi, bisogna definire cos’è un task. Gli

elementi chiave sono quelli che compongono il PEAS: performance measure,

environment, actuators, sensors. Se prendiamo un esempio più complesso, come un

taxi autonomo, possiamo capire che:

- Le performance measure sono numerose: arrivare a destinazione, minimizzare il tempo e

la benzina, massimizzare la sicurezza, non infrangere le regole della strada…

- L’environment contiene tutto l’ambiente stradale: altre auto, pedoni, strisce pedonali,

semafori, stradine, autostrade…

- Gli attuatori sono quelli di un’auto: acceleratore, freno, cambio, ma anche mezzi per

comunicare con i passeggeri

- I sensori possono essere videocamere, accelerometro, GPS, microfoni…

L’ambiente non è per forza qualcosa di “reale”. Anche il mondo digitale è un ambiente, e

non è per forza più semplice. Ci sono scenari reali abbastanza semplici (per esempio una

catena di montaggio) e scenari digitali molto complessi (per esempio l’analisi delle notizie

diffuse su internet e l’interesse dei singoli utenti verso di esse).

L’ambiente può essere COMPLETAMENTE OSSERVABILE o PARZIALMENTE

OSSERVABILE: dipende se i sensori riescono ad acquisire tutti gli aspetti o solo alcuni

dell’ambiente in cui operano. Nel caso di un ambiente parzialmente osservabile, l’agente

dovrà memorizzare al suo interno ciò che “scopre” durante l’esecuzione.

L’ambiente può essere SINGLE-AGENT o MULTI-AGENT. Naturalmente un risolutore di

Sudoku è single-agent, ma definire il multi-agent dipende dal contesto. Sicuramente

un’entità dell’ambiente è un agent se interferisce con la nostra performance: nel gioco

degli scacchi per esempio l’avversario vuole minimizzare il nostro punteggio. In un taxi

automatico invece le altre automobili fanno parte del nostro decidere dove andare, dove

parcheggiare e quindi influiscono sulla lunghezza del percorso, sulla sicurezza e in genere

sulle decisioni che facciamo per muovere l’auto.

Un ambiente può anche essere DETERMINISTICO o STOCASTICO. In un ambiente

deterministico, dato uno stato ed una azione, è sicuro prevedere il prossimo stato. In un

ambiente stocastico no. Anche qui, se prendiamo un gioco come il Sudoku lì è tutto

determinato (e anche per giochi competitivi come gli scacchi, anche se non conosciamo a

priori la mossa dell’avversario). Ma per un taxi automatico è praticamente tutto casuale,

perché non puoi prevedere dove si muoveranno le altre automobili e pedoni se non con

una certa probabilità. Inoltre possono accadere eventi inattesi come, per esempio, la

foratura di una gomma.

Un’altra distinzione è tra EPISODICO e SEQUENZIALE: un ambiente episodico è uno in

cui ogni azione è scorrelata dall’altra. L’azione che fai in un certo modo non dipende dalle

precedenti e non influenzerà le successive: per esempio se hai una catena di montaggio e

devi fare un controllo di qualità, ogni pezzo è a se stante. Invece in un ambiente

sequenziale c’è una storia. Gli scacchi e il taxi autonomo sono sequenziali. Naturalmente

questi ambienti sono più complessi da analizzare.

La distinzione tra ambiente STATICO e DINAMICO è anch’essa importante. Se mentre

l’agente è in funzione l’ambiente non cambia, esso è statico, per esempio nelle parole

crociate. Ma se mentre l’agente opera l’ambiente cambia, allora l’agente deve

continuamente osservare il mondo e decidere in breve tempo cosa fare. Anche il non fare

nulla mentre il tempo scorre è di fatto una decisione. Il taxi autonomo è ovviamente un

ambiente dinamico. Esiste una via di mezzo detta SEMIDINAMICA in cui in genere

l’ambiente è statico ma ci sono limiti di tempo.

Poi distinguiamo l’ambiente DISCRETO da quello CONTINUO: nel discreto possiamo

distinguere i singoli stati l’uno dall’altro e anche le azioni. Praticamente tutti i giochi con

una griglia sono discreti nella rappresentazione e nelle azioni possibili. In un taxi

autonomo invece abbiamo a che fare con il tempo, lo spazio, la velocità, l’angolo di

rotazione e sono tutti valori continui.

Infine un ambiente può essere CONOSCIUTO o SCONOSCIUTO: non ha a che fare con

l’osservabilità. Ha a che fare con le conseguenze delle azioni che compiamo. Se

sappiamo cosa accade se eseguiamo una certa azione (anche con una probabilità per gli

ambienti stocastici) allora l’ambiente è noto. Se non sappiamo cosa succede, dobbiamo

impararlo da soli e questo rende l’ambiente sconosciuto.

È intuitivo capire che il caso peggiore è l’ambiente parzialmente osservabile, multi-agent,

stocastico, sequenziale, dinamico, continuo e sconosciuto. Il taxi autonomo le tocca tutte,

ma almeno ha l’ambiente noto. Nel repository del libro di testo esiste un interessante

generatore di ambienti con tanto di simulatore di agenti.

Anche gli agenti possono essere classificati. Il primo tipo che vediamo sono i SIMPLE

REFLEX AGENTS. Sono i più semplici di tutti: osservano l’ambiente in uno stato specifico

ignorando la storia passata e agiscono secondo una lista di regole del tipo “se allora”. Il

problema di questi agenti è che, oltre ad essere molto limitati, richiedono un ambiente

pienamente osservabile. Anche un minimo di non osservabilità causa problemi e può

generare dei loop. Un modo per evitare i loop quando l’ambiente non è noto è definire la

prossima azione in modo causale, così facendo prima o poi l’agente si trova in una

situazione in cui ha gli elementi per definire la prossima azione e proseguire il suo lavoro.

Un miglioramento è dato dai MODEL BASED AGENTS, che mantengono internamente lo

stato dell’ambiente e lo aggiornano col tempo. Questo permette di agire anche in ambienti

parzialmente osservabili, perché cerchiamo di “ricordarci” com’erano fatti quei pezzi

dell’ambiente che ora non vediamo direttamente. Tramite la storia poi possiamo dedurre

alcuni comportamenti o azioni che stanno accadendo o accadranno: queste deduzioni

formano il modello usato dall’agente.

Il prossimo passo è dato dai GOAL BASED AGENTS. Sono agenti che agiscono con il

fine di raggiungere un obiettivo. Per esempio il taxi ha l’obiettivo principale di portare un

passeggero da un punto ad un altro e deve compiere diverse azioni per arrivare a quel

traguardo. In questo senso è quasi l’opposto dei simple reflex. Mentre questi ultimi

ragionano solo sul presente, i goal based ragionano sul futuro: come si evolverà la

situazione se compio una certa azione? Scelgono un’azione che possa semplificare il

raggiungimento dell’obiettivo.

Seguono gli UTILITY BASED AGENTS, che sono un po’ una generalizzazione dei goal

based. Cioè mentre i goal based possono dire “sono riuscito” e “non sono riuscito”, gli

utility based invece cercano di massimizzare un valore che può avere valori intermedi e lo

chiamiamo utilità. Questo valore sostanzialmente non è altro che la performance

measure, che però qui è un valore espressamente inserito e calcolato nell’algoritmo

dell’agente.

Ogni agente quindi in pratica dovrà saper rispondere a tre domande:

- Com’è fatto l’ambiente adesso

- Quale azione eseguo ora

- Che conseguenze avranno le mie azioni

I GOAL BASED AGENT o PROBLEM SOLVING AGENT sono agenti che decidono qual

è il prossimo passo da fare al fine di raggiungere un obiettivo e sono quelli che

analizzeremo a lungo in questo corso. Nella definizione di un agente goal based bisogna

seguire tre passi.

Il primo passo è la formulazione del problema.

Il secondo passo è cercare una soluzione.

Infine, il terzo passo è l’esecuzione della soluzione.

Il primo passo è eseguito dal designer, da una persona! Sono gli altri due passi quelli svolti

dalla macchina. La soluzione è una SEQUENZA di semplici azioni (per esempio giocare a

scacchi). Vedremo alla fine del corso che esistono anche soluzioni che non sono

sequenze di semplici azioni ma interi algoritmi, azz… In generale gli agenti trovano

soluzioni che sono algoritmi, sequenze complesse di azioni: costruiscono da sé algoritmi

che risolvono problemi. La macchina non si limita a eseguire, ma cerca la soluzione che

poi esegue.

Oggi analizziamo bene il primo passo: come formulare il problema in modo formale per

poterlo dare in pasto ad un agente che poi passerà al passo successivo. Per formulare un

problema dobbiamo fornire cinque elementi. Il primo elemento è lo STATO INIZIALE del

problema. Come esempio usiamo un gioco che manco conosco ma che ha in sostanza

una griglia 3*3 con delle lettere da spostare. Lo stato iniziale è quindi una matrice e dal

punto di vista computazionale useremo una struttura dati in cui inserire i valori (sarà

appunto una matrice dove ogni cella avrà un intero o una stringa con un certo valore). Il

secondo elemento è una FUNZIONE DI AZIONI che, dato uno stato, ritorna l’insieme di

azioni che si possono compiere: è quindi una funzione Stato → [Azione]. Per esempio nel

gioco 3+3 lo stato è la griglia e questa funzione ritornerà un sottoinsieme di {Sopra, Sotto,

Su, Giù}. Anche qui dal punto di vista di programmazione è molto semplice. Il terzo

elemento è la FUNZIONE RISULTATO: essa prende come parametri uno stato e

un’azione. Ritorna lo stato risultante dall’applicazione dell’azione. Ma è davvero figo

perché sono le cose che faccio io quando cerco di risolvere i problemi di Hackerrank! C’è

un’assunzione molto importante su questa funzione però: l’applicazione di un’azione deve

essere deterministica. Se ho uno stato e un’azione, lo stato risultante deve essere

definito. Ma anche per la funzione precedente dobbiamo conoscere tutto l’ambiente: se

non conoscessimo alcuni aspetti non potremmo definire stati e azioni (per dire se non

conosci mezza scacchiera non puoi definire il prossimo stato). Prima di proseguire

dobbiamo definire lo SPAZIO DEGLI STATI: è un grafo in cui i nodi sono gli stati e gli archi

sono le azioni. Questo grafo può essere finito o infinito, ma c’è persino la situazione

assurda in cui il grafo è composto da due componenti non connesse tra loro (e quindi da

una configurazione iniziale c’è mezzo mondo che non puoi esplorare…). Questo spazio

può essere enorme ma finito, per esempio negli scacchi il numero di stati è nell’ordine di

grandezza del numero di atomi nell’universo osservabile! Ne consegue che non puoi

rappresentare tutto lo spazio degli stati degli scacchi, perché pure se usi un atomo per

ogni singolo stato poi non hai più atomi per fare un computer che calcola...

Comunque un fatto interessante è che tu puoi costruire l’intero spazio degli stati usando i

tre elementi introdotti prima (lo stato iniziale, la funzione di azioni e la funzione risultato).

Diciamo che nel grafo c’è un percorso quando passiamo da uno stato ad un altro che

sono connessi da azioni intermedie. Anche in un grafo piccolo però, posso esistere infiniti

percorsi (basta che ci sia un ciclo). La presenza di un ciclo significa che le azioni sono

reversibili, cioè possiamo tornare allo stato precedente ad un’azione. Ora possiamo

finalmente proseguire la lista di ingredienti: il quarto elemento è il GOAL TEST. È un test

che, dato uno stato, ci dice se esso è uno stato finale o meno. Si tratta quindi di un

predicato Stato → Bool. Questo test può essere implementato in due modi in base al

contesto: uno è esplicitamente dire quali sono gli stati finali e confrontarli con lo stato

attuale, in altri problemi invece controlliamo delle proprietà dello stato. Per dire negli

scacchi non possiamo fare la lista degli stati finali, ma verifichiamo se certe proprietà ci

sono (cioè controlliamo se il re può muoversi o no). Il goal test quindi può indicare

proprietà dello stato finale. L’ultimo elemento è il PATH COST: una funzione che dato un

percorso ci dice qual è il suo costo. Si implementa assegnando ad ogni azione un costo e

dato un percorso sommiamo i costi delle azioni usate (questa è una possibile

implementazione, teoricamente la definiamo come vogliamo).

Riassumendo, gli ingredienti sono:

- Stato iniziale State initialState

- Funzione di azioni Set<Action> action(State)

- Funzione risultato State result(State, Action)

- Goal test bool goalTest(State)

- Path cost int pathCost(List<Action>)

A questo punto diciamo cos’è una SOLUZIONE per un problema. È un percorso dello

spazio degli stati che ci porta dallo stato iniziale ad uno stato che soddisfa il goal test.

Sottolineiamo che lo stato iniziale è unico, mentre lo stato finale non lo è per forza.

Possono esserci più soluzioni: l’importante è finire in uno stato che soddisfa il goal test.

Chiamiamo poi una soluzione OTTIMALE se è una soluzione con costo minimo. Vedremo

che ci sono algoritmi che trovano una soluzione qualsiasi e quelli che trovano la soluzione

ottimale. Trovare la soluzione quindi è trovare un percorso nel grafo. Beh… noi

conosciamo algoritmi efficienti per cercare percorsi in un grafo… Ma perché non li

applichiamo? Perché non conosciamo a priori lo spazio degli stati, e nemmeno lo stato

finale! Gli algoritmi sui grafi richiedono la conoscenza del grafo. Noi invece non

conosciamo nulla dello spazio degli stati! Quello che faremo sarà espanderci in una parte

del grafo che esploreremo un po’ alla volta: vedremo solo una porzione al fine di trovare

una soluzione. Questo obiettivo è quello su cui gira tutto il corso praticamente.

Per esempio abbiamo una scacchiera 8*8 e dobbiamo mettere 8 regine in modo che non

si possano mangiare l’un l’altra.

- Stato iniziale = una griglia 8*8 con le celle vuole

- Funzione di azioni = data la griglia, ritorna le celle che possono essere occupate

- Funzione risultato = data la griglia e una cella, inserisce la regina in quella cella

- Goal test = ci sono 8 regine e nessuna regina può attaccare nessun’altra

- Path cost = ?

Curiosità: quanto è grande lo spazio degli stati? 64*63*62*61*60*59*58*57

Ovviamente non puoi provare tutti gli stati perché sono 180 mila miliardi, ma non ce n’è

bisogno… Se metti una regina in una certa cella puoi già dire che non puoi mettere

un’altra regina nella stessa riga, colonna o diagonale: in questo modo sei più intelligente

nella scelta delle possibili azioni future e riduci di brutto il grafo (meno di 2 miliardi di

possibili stati). Per risolvere efficientemente i problemi dovremo mettere la maggior parte

della conoscenza nella funzione delle azioni e meno nel goal test: questo permette di

ridurre lo spazio degli stati e trovare più facilmente la soluzione.

La volta scorsa abbiamo presentato il primo step della risoluzione di un problema, cioè la

progettazione. Ora dobbiamo vedere come un agente può cercare una soluzione al

problema fornito. Il processo di trovare una soluzione si riconduce ad una ricerca su un

grafo che però non conosciamo a priori. Dobbiamo espandere solo delle porzioni del grafo

degli stati e cercare lì dentro un percorso che è una soluzione. Abbiamo visto che una

soluzione è un percorso che va dallo stato iniziale ad uno stato che soddisfa il goal test.

Per fare questa ricerca costruiremo una struttura dati che è l’ALBERO DI RICERCA. Con

questa struttura l’agente potrà trovare la soluzione. Come viene costruito? Inizializziamo

l’albero di ricerca con il nodo radice che corrisponde allo stato iniziale del problema. Poi

dovremo selezionare i prossimi stati da esaminare e saranno i figli della radice. Su questi

nodi eseguiamo il goal test: se esso viene passa