Appunti completi corso Intelligenza Artificiale

Concetti di base sugli agenti razionali

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.

Definizione di agente razionale

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.

Definizione di task e PEAS

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…

Tipologie di ambiente

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.

Classificazione degli 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.

Domande fondamentali per gli agenti

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.

Formulazione del problema

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ò, possono 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.

Goal test e path cost

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).

Riassunto degli ingredienti

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>)

Definizione di soluzione

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.

Esempio delle 8 regine

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 vuote
• 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.

Ricerca della 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 passato, abbiamo trovato una soluzione.