1

Laurea Magistrale in “Cinema e Media”

Corso di “Rappresentazione e Algoritmi” 2014-15 Modulo I - 6 CFU

mutuato da

Laurea Magistrale in “Scienze del Corpo e della Mente” 6 CFU

Laurea Magistrale in “Scienze della Mente” Corso di “Intelligenza artificiale” 2013-14

Modulo I - 4 CFU

Vincenzo Lombardo

Note per il corso

Queste note per i corsi di “Rappresentazione e algoritmi” sono parte del programma d’esame 2014/15. L’idea di scrivere le note scaturisce dalla considerazione che, essendo frequentato il corso anche da studenti provenienti da altre sedi in Italia o all’estero, spesso la preparazione di base dell’informatica non è sufficiente per affrontare lo studio dei testi adottati (come da guida degli studi). Dopo una ricerca sul web di testi e dispense possibili, mi sono convinto che sono tutti pensati per scopi diversi da un corso nell’ambito dei media o della psicologia. Gli esempi riportati, la presentazione degli argomenti, l’obiettivo a cui è destinato lo studio non sono familiari agli studenti di “Cinema e media” e di “Scienze del Corpo e della Mente”.

Capitolo 2 La ricerca nello spazio degli stati

Commenti benvenuti!

Aggiornamento: 24 ottobre 2017

2

Capitolo 2

La ricerca nello spazio degli stati

In questo capitolo, introduciamo il paradigma di soluzione dei problemi mediante ricerca nello spazio degli stati, il nucleo fondamentale della disciplina denominata Intelligenza Artificiale. In particolare, il metodo estrapola la conoscenza contenuta nella soluzione algoritmica, rappresentandola in forma dichiarativa e rendendola disponibile a un algoritmo generico che calcola la soluzione. Questo aspetto è di interesse per coloro che non avranno molto a che fare con gli algoritmi in senso stretto, ma verranno chiamati soprattutto a modellare dati e conoscenza, come avviene sempre più spesso in ambito produzione di media o formalizzazione basata sulla metafora computazionale. Il capitolo, quindi, una volta introdotto il metodo a partire dalle impostazioni tradizionali del capitolo 1, introdurrà la formulazione dei problemi, con i loro stati e azioni, e la soluzione algoritmica mediante ricerca nello spazio degli stati del problema, con lo scopo di raggiungere gli stati obiettivo e ricostruire la soluzione possibile. Questi temi sono di solito trattati nei corsi di Intelligenza Artificiale per informatici; la nostra intenzione qui è di preparare alla formalizzazione e codifica dei contenuti partendo dai motori che utilizzano la rappresentazione per prendere le decisioni.

Indice

1. La conoscenza dichiarativa 2. La formulazione di problemi 3. L’albero di ricerca nello spazio degli stati 4. Le strategie di ricerca

3

1. La conoscenza dichiarativa In questo capitolo, spostiamo la nostra attenzione dalla soluzione di problemi algoritmici specifici alla concezione di agenti e programmi che operano in ambienti. Un programma di oggi (una app direbbero in tanti, visto che il contatto con i programmi avviene nella maggior parte dei casi mediante uno smartphone) non risolve solo un problema specifico, ma si propone come un agente che rimane attivo a trattare le richieste (non sempre esplicite) dell’utente nel suo dominio di competenza. Ad esempio, la scrittura di un documento in un word processor risulta essere un’interazione con un programma gigantesco, che fornisce capacità di organizzazione della scrittura, schemi predefiniti per vari tipi di documento, archiviazione intelligente dei documenti prodotti, correttori ortografici, contenitore di fonti multiple di natura multimediale (immagini, schemi, grafici, ma anche filmati e suoni, che sembrano in antitesi con il prodotto da realizzare, un testo). Questa evoluzione si affianca alla visione prodotta a partire dagli anni ’50 dalla disciplina dell’Intelligenza Artificiale verso software che avesse capacità di pensiero e comportamento simili a quelle dell’uomo, cercando di risolvere (riuscendoci in molti casi) problemi che si pensava fossero oltre la competenza del software. Oggi le soluzioni trovate nell’ambito dell’IA sono presenti in moltissimi contesti a noi vicini: dai correttori ortografici citati prima, a cui si sono anche affiancati anche correttori sintattici, al rilevamento di elementi in un’immagine, ai riconoscitori della lingua parlata, al comportamento dei personaggi artificiali in un videogioco, … . Quando si risolve un problema mediante un algoritmo, di solito si implementa una funzione del tipo

f: I → O

Da input in una certa forma (data dalla rappresentazione del problema) si ottengono output che vengono prodotti dalla manipolazione della rappresentazione in input, secondo il tipo di funzione. Questa descrizione vale sia nel caso di problemi codificati one-shot, come l’ordinamento di una sequenza o la ricerca di un

anagramma, che portano da un problema a una soluzione, sia nel caso di servizi continuativi, come ad esempio un agente che opera in un ambiente. Consideriamo un esempio. Nel semplice mondo dell’aspirapolvere (da Russell & Norvig) illustrato in figura

Figura 1. Mondo dell’aspirapolvere. si ha un agente (aspirapolvere) in un appartamento con due stanze (A e B); l’agente può spostarsi tra A e B, percepire dove si trova e l’eventuale presenza di sporco; le azioni possibili sono lo spostamento verso sinistra (da B a A), lo spostamento verso

4

destra (da A a B), l’aspirazione dello sporco nella stanza in cui si trova. Formalmente, si può rappresentare in questo modo: l’agente realizza di istante in istante la funzione

f: P → A dove P sono i percetti e A le azioni possibili. La rappresentazione dei dati potrebbe essere la seguente:

• P = {<Stanza, Sporcizia>}, dove i possibili valori per la componente Stanza sono A e B (le stanze) e i valori per la componente Sporcizia sono Pulito e Sporco;

• A = {Left, Right, Aspira}, dove Right è un’azione che cambia la Stanza in B, rispettivamente Left cambia la Stanza in A, Aspira cambia la componente Sporcizia da Sporco a Pulito;

e l’algoritmo che descrive il suo comportamento il seguente:

action agente_aspirapolvere (Percetto p) if <A, Pulito> then return Right else if <A, Sporco> then return Aspira else if <B, Pulito> then return Left else if <B, Sporco> then return Aspira

La funzione agente_aspirapolvere è la mente del nostro agente, e viene chiamata in causa quando l’agente deve decidere cosa fare (appena dopo aver terminato l’esecuzione di un’azione); ogni chiamata della funzione elabora un nuovo percetto ricevuto dai sensori. Il programma consiste di una cascata di if-then-else (in realtà, si noti che la presenza del return a ogni riga elimina la necessità di avere gli else). Data la configurazione in Figura 1, la sequenza di azioni (simulare l’algoritmo) sarà:

Aspira, Right, Aspira, Left, Right, Left, Right, …

Quindi, il nostro agente continua a spostarsi all’infinito tra le stanze A e B, fino a che una stanza diventa di nuovo sporca e sarà costretto ad aspirare. [Esercizio: complicare il problema introducendo una quarta azione, standby, da attivare quando l’aspirapolvere trova entrambe le stanze pulite. Suggerimento: rappresentare il percetto con due componenti, il percetto precedente e quello attuale. Si tratta di un caso particolare (sequenza lunga 2) della memoria delle percezioni: la tabella, o insieme di regole, è più estesa, e deve tener conto di tutte le possibili sequenze di condizioni; la difficoltà di compilare una tabella del genere dipende anche dallo sforzo di mantenere la mutua esclusione tra le righe della tabella, altrimenti si generano conflitti nel comportamento dell’agente.] L’algoritmo contiene la conoscenza relativa al comportamento dell’aspirapolvere e la mette in pratica, determinando il suo comportamento, mediante la cascata di if-then-else; in altre parole, la conoscenza posseduta dall’agente è in qualche modo incastonata nell’algoritmo che determina il suo comportamento. Una rappresentazione alternativa dell’algoritmo, che deriva dagli approcci di Intelligenza Artificiale,

5

consiste nella separazione della conoscenza potere dalla sua applicazione nell’algoritmo. In questo modo l’algoritmo diventa una sorta di motore generico, universale, che applica un modulo di conoscenza descritto in qualche forma di rappresentazione. Variando il contenuto della rappresentazione della conoscenza, lo stesso motore può risolvere problemi differenti. Questo forma di conoscenza si dice dichiarativa, in quanto esplicita, descrivibile, non incastonata nella procedura che la

utilizza (di contro, la conoscenza espressa direttamente dall’algoritmo è detta procedurale). E’ una forma di astrazione. L’astrazione più immediata utilizza una forma di rappresentazione della conoscenza che è vicina all’algoritmo. Si tratta delle regole condizione-azione: ogni regola ha la forma if-then, cioè se vale una certa condizione, si può eseguire la corrispondente azione. Le regole si possono rappresentare quindi mediante una tabella, come la seguente, in cui a ogni riga corrisponde una coppia condizione-azione.

Stanza Sporcizia Azione

A Pulito Right

A Sporco Aspira

B Pulito Left

B Sporco Aspira

Figura 2. Tabella regole mondo dell’aspirapolvere.

Le condizioni sono suddivise in due componenti. La prima riga della tabella si potrebbe esprimere in italiano con la parafrasi: “Se 1) ci si trova nella stanza A e 2) si percepisce Pulito, allora vai a destra.” Dettagliando lo schema dell’agente sopra, si ha che i percetti (che arrivano dai sensori) danno all’Agente un’idea del mondo; a partire dai percetti l’agente scopre quale regola utilizzare, da cui estrae l’azione da eseguire (che viene passata agli attuatori). E il motore a regole assume la seguente forma:

read-only Regole (insieme di regole) soluzione motore_a_regole (input p) S ← interpreta_input (p) R_index ← regola_corrispondente (S, Regole) a ← regola_azione(Regole[R_index]) return a;

Le aree di memoria di tipo read-only hanno la caratteristica che la loro area di memoria non si può sovrascrivere e rimane attiva con il suo contenuto immutato da un’esecuzione all’altra di un programma (mentre le altre aree di memoria vengono liberate); quindi, l’area conterrà sempre le Regole condizione-azione, come quelle viste prima. Le Regole si possono vedere come un array di regole di due componenti a

6

loro volta, condizione e azione rispettivamente. Il motore a regole interpreta il percetto p tramite la subroutine interpreta_input, che costruisce un cosiddetto stato del mondo (variabile S), trova l’indice nella regola (variabile R_index) la cui condizione corrisponde allo stato del mondo tramite la subroutine regola_corrispondente, e infine estrae l’azione dalla regola che si trova all’indice R_index (Regole[R_index]) tramite la subroutine regola_azione. Il programma/agente sopra, estrapolando o meno la conoscenza in forma dichiarativa, produce un comportamento di tipo reattivo, cioè seleziona un’azione in seguito a un input, ma non prende in considerazione altri aspetti fondamentali della conoscenza, che concorrono alla soluzione di un problema. Certamente, l’ambiente in cui il programma (o l’agente) opera contiene elementi che non sono percepibili (cioè non fanno parte dell’input), ma contribuiscono alla definizione stessa del problema e alla formulazione della soluzione; quindi, un agente più efficace dovrebbe incorporare un modello del mondo che permetta di aggiornare lo stato non solo rispetto ai nuovi input (percetti), ma anche rispetto a ciò che non può osservare e che è intrinseco del mondo o che è una conseguenza delle azioni dell’agente stesso. Ad esempio, nel caso dell’aspirapolvere, un modello potrebbe contenere la conoscenza per cui, se qualcuno entra nell’appartamento (rilevazione mediante percezione), allora il pavimento si sporca di sicuro. Inoltre, il programma (o l’agente) possono essere non soltanto reattivi, ma avere propri desideri e obiettivi che lo rendono proattivo: l’agente, cioè, non decide della prossima azione solo sulla base delle regole, le cui condizioni siano verificate nello stato attuale, ma anche sulla base dei suoi obiettivi (o goal). Introduciamo quindi un programma più sofisticato, secondo lo schema seguente:

Il nuovo programma/agente non solo reagisce agli stimoli (modellando sui percetti le condizioni delle regole), ma elabora uno stato del mondo, che viene aggiornato ogni volta che occorre decidere che azione eseguire. Allo stato del mondo contribuiscono 1) il modello del mondo (che descrive come il mondo evolve indipendentemente dall’agente o in seguito all’esecuzione di un’azione) e 2) il modello delle azioni dell’agente stesso (da usare nella selezione della prossima azione). Inoltre, nella conoscenza dichiarativa sono contenuti anche 3) gli obiettivi, di lungo e breve termine, che l’agente prende in considerazione per decidere della prossima azione.

7

L’agente calcola gli stati successivi ipotetici, che si ottengono applicando allo stato attuale del mondo sia il modello del mondo sia il modello delle azioni; tra gli stati successivi ipotetici, si seleziona quello stato successivo, e quindi l’azione corrispondente, che contribuisce al raggiungimento dell’obiettivo; questa azione viene passata agli attuatori per l’esecuzione. Il motore che realizza questo schema può essere il seguente:

read-only modello (conoscenza sul mondo e sulle azioni) sequenza_azioni agente_basato_su_modelli_e_obiettivi (input p) static stato (stato corrente del mondo secondo l’agente) goal (obiettivo, inizialmente NULLO) problema (formulazione di problema) loop stato ← aggiorna_stato(stato, modello, p) goal ← formula_obiettivo(stato, modello) problema ← formula_problema(stato, modello, goal) sequenza_azioni ← ricerca_azione(problema) return sequenza_azioni (eventualmente NULLA) execute sequenza_azioni

La conoscenza dichiarativa, sul mondo e sulle azioni, è memorizzata in un’area globale di sola lettura. Le variabili di tipo static hanno la caratteristica che la loro area di memoria rimane accessibile con il suo contenuto da un’esecuzione all’altra di un programma (mentre le altre aree di memoria vengono liberate); quindi, le variabili di stato, obiettivo e problema rimangono disponibili alla successiva esecuzione. Il programma/agente prende in input un percetto e restituisce una soluzione. Le aree persistenti della memoria (variabili static), che vengono mantenute tra un’esecuzione e l’altra del programma, sono: 1) lo stato del mondo, secondo la conoscenza del programma/agente, aggiornato dalla subroutine aggiorna_stato; 2) l’obiettivo che si intende perseguire; 3) una formulazione del problema da risolvere (vedi paragrafo successivo). La subroutine aggiorna_stato tiene conto dello stato precedente, dell’input attuale e del modello; una volta aggiornato lo stato, il programma/agente formula un obiettivo (goal), tenendo conto anche del modello. Il problema del programma/agente diventa raggiungere l’obiettivo a partire dallo stato attuale e di ciò che si può fare nel mondo; la formulazione del problema produce quindi una formalizzazione del problema (problema). Sulla formalizzazione del problema, la subroutine ricerca_azione ricerca la sequenza di azioni raggiunge l’obiettivo a partire dallo stato attuale. Non sempre la ricerca ha successo: in questo caso, la sequenza di azioni sarà nulla. Nei prossimi paragrafi ci occuperemo della formulazione dei problemi e della ricerca della soluzione (la sequenza di azioni); nei prossimi capitoli, ci occuperemo del modello e dell’aggiornamento dello stato. 2. La formulazione di un problema La subroutine che ricerca la sequenza di azioni che raggiunge l’obiettivo opera calcolando gli stati successori di uno stato (a partire da uno stato iniziale e poi da quelli successivi, trovati applicando le azioni). E’ una ricerca nello spazio degli stati

8

possibili, collegati tra loro mediante le azioni; la soluzione si costruisce mettendo in sequenza le azioni che si ritrovano sul cammino dallo stato iniziale all’obiettivo. Prima di capire come funziona la subroutine, introduciamo la nozione di problema. Un problema viene definito formalmente mediante una quadrupla

<S0, G, A, C>

• S0 è lo stato iniziale in cui si viene a trovare l’agente (a partire dal quale viene ricercata la soluzione);

• G è il test obiettivo (goal test), cioè una funzione che verifica se uno stato corrisponde un obiettivo oppure no;

• A è l’insieme delle azioni possibili, che generano uno stato a partire da uno stato in input; quindi, A realizza quello che viene definito lo spazio degli stati, a partire dallo stato iniziale S e applicando tutte le possibili azioni di volta in volta;

• C è una funzione di costo che associa un costo a ogni azione, insieme con un’operazione che combina tutti i costi delle azioni singole per ottenere il costo totale.

Facciamo un esempio classico dell’Intelligenza Artificiale: il problema dei missionari e dei cannibali.

Sulla riva di un fiume ci sono tre missionari e tre cannibali; vogliono tutti attraversare il fiume, avendo a disposizione una barca che può trasportare fino a due persone; non può mai capitare di avere un sovrannumero di cannibali rispetto ai missionari su una riva (sulla barca questo non può capitare, dal momento che le configurazioni possibili sono due cannibali – 2C, un missionario e un cannibale – 1M1C, due missionari – 2M). Occorre individuare una sequenza di azioni che permetta di trasportare tutte le persone da una riva all’altra in modo sicuro.

Per comprendere come possiamo applicare la quadrupla <S, G, A, C> al problema dei missionari e dei cannibali, occorre provare a formalizzare. Formalizziamo innanzitutto lo stato generico di un problema, per specificare poi la formalizzazione nel caso dello stato iniziale, del goal test, delle azioni possibili, del costo delle azioni. Utilizziamo un vettore di più componenti, come abbiamo visto per altri casi nel capitolo introduttivo. La rappresentazione

S = <M, M, M, C, C, C, B> inserisce i tre missionari nelle prime tre posizioni, i tre cannibali nelle posizioni 4, 5, 6, e la barca nella posizione 7. Il valore delle componenti potrebbe essere L o R , a seconda se il missionario, il cannibale o la barca si trovino sulla riva sinistra o destra rispettivamente. Quindi, lo stato iniziale S0 sarà

S0 = <L, L, L, L, L, L, L>

e il goal test sarà una funzione che verifica se lo stato raggiunto è uguale allo stato

9

S1 = <R, R, R, R, R, R, R> Le azioni possibili permettono di spostare una o due persone da L a R e viceversa, e possono essere specificate come

AM1LR = <L, _, _, _, _, _, L> à <R, _, _, _, _, _, R> AM2LR = <_, L, _, _, _, _, L> à <_, R, _, _, _, _, R>

… AM1RL = <R, _, _, _, _, _, R> à <L, _, _, _, _, _, L>

… AM1C1LR = < L, _, _, L, _, _, L> à <R, _, _, R, _, _, _, R>

… AM1C2RL = < R, _, _, _, R, _, R> à <L, _, _, _, _, L, _, L>

… Come si vede, le azioni sono espresse come corrispondenze

“stato di input à stato di output”; il simbolo ‘_’ ci permette di soprassedere sul contenuto della componente corrispondente, cioè in quella componente ci potrebbe essere qualsiasi contenuto (L o R) – l’azione è applicabile comunque; sono riportate solo alcune azioni, le altre sono intuibili. La prima di queste azioni, AM1LR, trasporta il primo missionario (in posizione 1) da sinistra a destra (si noti come pure la barca cambia posizione), lasciando invariato tutto il resto; la seconda azione, AM2LR, trasporta il secondo missionario sempre da sinistra a destra; analogamente, il lettore può scrivere le altre quattro azioni che trasportano una persona da sinistra a destra. Dopo, per esercizio, a partire dalla prima già inserita (AM1RL), si possono scrivere le sei azioni che trasportano dalla riva destra alla riva sinistra; quindi, si passa a scrivere le azioni che riguardano tutte le combinazioni di due persone, da AM1C1LR, che rappresenta il trasporto del primo missionario e del primo cannibale da sinistra a destra, e continuando con le azioni di trasporto da destra a sinistra, come AM1C2RL, che rappresenta il trasporto del primo missionario e del secondo cannibale da destra a sinistra. Il costo di ogni azione, cioè di un trasporto tra le due rive, si assume uguale a 1; si potrebbero anche usare misure dipendenti dal numero di persone trasportate per volta, se si volesse tener conto dello sforzo energetico o pesare i missionari differentemente dai cannibali. A partire da S0, noi possiamo generare con tale formalizzazione tutti gli stati dello spazio degli stati. S0 = <L, L, L, L, L, L, L> AM1LR, <R, L, L, L, L, L, R> AM1RL, <L, L, L, L, L, L, L> … AM2LR, <L, R, L, L, L, L, R> … AM1C1LR, < R, L, L, R, L, L, R> …

10

In ogni riga è indicata, tramite indentazione, l’applicazione di una certa azione e il risultato dell’azione a partire dallo stato precedente. Si noti che, se proseguissimo dopo la terza riga con l’azione AM1LR, si avrebbe un ciclo infinito (il primo missionario che va avanti e indietro tra le due rive, certamente non un avanzamento verso la soluzione). E’ importante notare che una formalizzazione non è unica (anzi!). Ad esempio, in modo abbastanza immediato, rileggendo la definizione del problema, si può osservare che non si considerano le individualità dei missionari e dei cannibali. Per cui, riprendendo la rappresentazione precedente, possiamo operare una semplificazione della formalizzazione, riducendo i missionari e i cannibali a un numero, che rappresenta le presenze sulla riva sinistra. La differenza con il totale ci dà le presenze sulla riva destra. Infine, per rendere uniforme la rappresentazione, rappresentiamo con 1 la riva sinistra e 0 la riva destra. La nuova formalizzazione del problema dei missionari e dei cannibali è una tripla

<#M, #C, B>, dove #M è il numero di missionari sulla riva sinistra, #C è il numero di cannibali sulla riva sinistra, B la posizione della barca (1 o 0). Quindi, lo stato iniziale S0 è

S0 = <3, 3, 1> Lo stato finale è

S1 = <0, 0, 0> Si noti che in questo problema semplice non si ha bisogno di un goal test; è sufficiente indicare l’unico stato obiettivo che occorre raggiungere. In casi più complicati (ad esempio, i casi di scacco matto negli scacchi), in cui gli stati-obiettivo possono essere moltissimi, occorre definire i possibili stati-obiettivo in termini funzionali (ad esempio, lo scacco matto è una configurazione in cui il re è minacciato e non può mettersi in salvo). Le azioni, modificate con la nuova rappresentazione, le corrediamo delle condizioni di applicazione. In particolare, suddividiamo le condizioni in tre parti: il numero di elementi da spostare deve essere adeguato, sulla riva sinistra e sulla riva destra devono essere rispettate le condizioni di sopravvivenza dei missionari (essere in numero maggiore o uguale ai cannibali o essere assenti). Quindi, ad esempio, se si spostano due missionari da sinistra a destra, occorre che siano soddisfatte le seguenti condizioni:

I. ci siano in partenza almeno due missionari sulla riva sinistra, II. il numero di missionari che rimane sulla riva sinistra deve essere sempre

maggiore o uguale ai cannibali, o essere 0, III. il numero di missionari che si ritrovano sulla riva destra all’arrivo sia

maggiore o uguale ai cannibali, o essere 0 (quest’ultimo caso è impossibile, ma lo lasciamo per semplicità di verifica della correttezza).

11

Ecco l’elenco completo delle azioni:

• A1M10: <#M, #C, 1> à <#M–1, #C, 0> (sottrazione di <1, 0, 1>) I. #M ≥ 1,

II. #M–1 ≥ #C oppure #M–1 = 0, III. 3 – #M + 1 ≥ 3 – #C oppure 3 – #M + 1 = 0;

• A1M01: <#M, #C, 0> à <#M+1, #C, 1> (addizione di <1, 0, 1>) I. #M ≤ 2,

II. #M+1 ≥ #C, III. 3 – #M – 1 ≥ 3 - #C oppure 3 – #M – 1 = 0;

• A1C10: <#M, #C, 1> à <#M, #C-1, 0> (sottrazione di <0, 1, 1>) I. #C ≥ 1,

II. #M ≥ #C – 1, III. 3 – #M ≥ 3 – #C + 1 oppure 3 – #M = 0;

• A1C01: <#M, #C, 0> à <#M, #C+1, 1> (addizione di <0, 1, 1>) I. #C ≤ 2,

II. #M ≥ #C+1 oppure #M = 0, III. 3 – #M ≥ 3 – #C – 1 oppure 3 - #M = 0;

• A2M10: <#M, #C, 1> à <#M–2, #C, 0> (sottrazione di <2, 0, 1>) I. #M ≥ 2,

II. #M–2 ≥ #C oppure #M=0, III. 3 – #M + 2 ≥ 3 – #C oppure 3 – #M + 2 = 0;

• A2M01: <#M, #C, 0> à <#M+2, #C, 1> (addizione di <2, 0, 1>) I. #M ≤ 1,

II. #M+2 ≥ #C, III. 3 – #M – 2 ≥ 3 - #C oppure 3 – #M – 2 = 0;

• A2C10: <#M, #C, 1> à <#M, #C–2, 0> (sottrazione di <0, 2, 1>) I. C ≥ 2,

II. #M ≥ #C–2 oppure #M=0, III. 3 – #M ≥ 3 – #C + 2 oppure 3 – #M = 0;

• A2C01: <#M, #C, 0> à <#M, #C+2, 1> (addizione di <0, 2, 1>) I. #C ≤ 1,

II. #M ≥ #C + 2, III. 3 – #M ≥ 3 – #C – 2 oppure 3 – #M = 0;

• A1M1C10: <#M, #C, 1> à <#M–1, #C–1, 0> (sottrazione di <1, 1, 1>) I. #M ≥ 1, #C ≥ 1,

II. #M – 1 ≥ #C – 1 oppure #M – 1 = 0, III. 3 – #M + 1 ≥ 3 – #C + 1 oppure 3 – #M + 1 = 0;

• A1M1C01: <#M, #C, 0> à <#M+1, #C+1, 0> (addizione di <1, 1, 1>) I. 3 – #M ≥ 1, 3 – #C ≥ 1;

II. #M + 1 ≥ #C + 1 oppure #M + 1 = 0. III. 3 – #M – 1 ≥ 3 – #C – 1 oppure 3 – #M – 1 = 0;

Il costo rimane unitario per azione. Si ribadisce che alcune condizioni sono impossibili (ad esempio, #M + 1 = 0), ma sono state lasciate per facilità di scrittura e verifica. [Esercizio. Il lettore è invitato a operare le semplificazioni ovvie sulle condizioni e a verificare il corretto funzionamento.]

12

Una volta formulato il problema, il motore descritto in precedenza ricerca la soluzione applicando le azioni agli stati, partendo dallo stato iniziale e cercando di raggiungere l’obiettivo. Si forma quello che si chiama albero di ricerca nello spazio degli stati.

13

3. L’albero di ricerca nello spazio degli stati Cominciamo con un esempio di albero di ricerca nello spazio degli stati. In Figura 3 (sinistra) è illustrato l’albero di ricerca del problema dei missionari e dei cannibali. La radice dell’albero contiene lo stato iniziale (<3,3,1>); i figli di un nodo contengono stati successori, cioè ottenuti applicando un’azione possibile allo stato contenuto nel nodo padre. Una volta ottenuto un albero di ricerca, è sufficiente partire dai nodi contenenti gli stati goal e ripercorrere indietro il cammino sull’albero di ricerca (Figura 4, destra; si noti che in un albero ogni nodo ha un solo genitore).

Figura 3. Albero di ricerca nello spazio degli stati dei missionari e cannibali. I nodi con stato in rosso contengono uno stato già apparso più in alto nell’albero e di cui già si conoscono i discendenti. Questi duplicati non vengono ulteriormente espansi (come se esistesse nell’algoritmo un rilevamento dei duplicati – vedi sotto le strategie di ricerca). I nodi in verde contengono lo stato obiettivo. Sulla destra, la ricostruzione del cammino che porta dalla radice a uno dei due nodi contenenti lo stato obiettivo.

[Esercizio. Il lettore etichetti ogni arco dell’albero con l’azione che connette i due stati (nodo padre e nodo figlio).] Scriviamo quindi la subroutine che ricerca la sequenza di azioni, costruendo l’albero di ricerca. Si chiama ricerca_albero, e implementa la ricerca_azione, invocata in precedenza nell’algoritmo dell’agente_basato_su_modelli_e_obiettivi.

14

sequenza_azioni ricerca_albero (problema, strategia) inizializza albero di ricerca con lo stato iniziale del problema loop if NON ci sono nodi candidati per l’espansione then return NULL selezionare nodo foglia per l’espansione (secondo strategia) if nodo contiene uno stato goal then return la soluzione corrispondente else espandere il nodo aggiungere i nodi figli all’albero di ricerca

Raffiniamo la scrittura algoritmica con le strutture dati e le istruzioni corrette. In particolare introduciamo i nodi dell’albero, che contengono a loro volta gli stati (Figura 4)

Figura 4. Struttura dati che rappresenta i nodi dell’albero di ricerca nello spazio degli stati, con riferimento al problema dei missionari e cannibali.

Un nodo dell’albero di ricerca nello spazio degli stati contiene uno stato del problema e gli attributi, come l’azione che ha portato allo stato contenuto e il costo dello stato contenuto nel nodo; infine, è indicato il nodo padre del nodo attuale. Gli attributi sono tutti identificati mediante la notazione a punto (nome_nodo.attributo, ad esempio n_f.padre o n_p.costo). E’ importante notare la differenza tra stato del problema e nodo dell’albero di ricerca nello spazio degli stati. Lo stato riguarda il problema; lo stato è uno degli attributi di un nodo, il suo contenuto, che per il resto mantiene informazioni riguardanti il suo posizionamento nella struttura albero. In particolare, si può notare, ad esempio, che più nodi in un albero possono contenere lo stesso stato, ma essendo a distante diverse dalla radice, il costo di raggiungere lo stato contenuto sarà diverso. Considerando tali strutture dati possiamo raffinare l’algoritmo descritto in precedenza. I commenti (che non hanno effetto sull’esecuzione dell’algoritmo) sono preceduti da doppia barra (//)

15

sequenza_azioni ricerca_albero (problema, strategia) frontiera ← insert(make_node (problema[StatoIniziale]), strategia) loop if frontiera VUOTA then return NULLA nodo ← remove_first (frontiera) if problema[GoalTest](nodo.stato) then return solution(nodo) else nodi_successori ← expand(nodo, problema) for ogni n in nodi_successori do frontiera ← insert(n, strategia) insieme_nodi expand (n_p, problema) // n_p = nodo_padre successori ← insieme vuoto for ogni azione A in Azioni[problema] do n_f ← make_node (risultato(A(state[n_p])) // n_f = nodo_figlio n_f.padre ← n_p n_f.azione ← A n_f.stato ← risultato(A(n_p.stato) n_f.costo ← n_p.costo+ costo_azione(A, n_p.stato) aggiungere nodo n_f a insieme successori return successori

Si capisce quindi che la ricostruzione del cammino di soluzione utilizza le connessioni .padre, da un nodo obiettivo (cioè contenente uno stato obiettivo) fino alla radice (cioè contenente lo stato iniziale del problema). 4. Strategie di ricerca Prima di proseguire, introduciamo un nuovo esempio di problema, che presenta un costo differenziato delle operazioni in modo da comprendere la differenza esistente tra più soluzioni, cioè l’idea di ottimalità. Il problema (dal testo [Russell, Norvig]) tratta di una situazione di viaggio. Trovandosi in Romania in vacanza, il nostro agente è attualmente ad Arad (stato iniziale) e deve essere a Bucarest per domani (stato goal); non possiede una connessione e non può accedere a GoogleMaps, viaMichelin e simili, e si basa per la sua pianificazione del viaggio su una carta (riportata in Figura 5), dove sui collegamenti diretti tra le città è riportato il chilometraggio. Qual è la soluzione?

16

Figura 5. Carta con i collegamenti principali della Romania. Considerata la situazione, il nostro agente formula il goal

Bucarest e conseguentemente formula il seguente problema <S0, G, A, C>:

• S0 = Arad; • G = Bucarest; • A = {

o Arad à Sibiu, o Sibiu à Faragas, o …};

• C = { o C(Arad à Sibiu) = C(Sibiu à Arad) = 140, o C(Arad à Zerind) = C(Zerind à Arad) = 75, o … }.

Gli stati possibili sono le città sulla mappa e le azioni i collegamenti diretti. La funzione costo è data dalla distanza chilometrica tra le città. La soluzione sarà la sequenza di azioni che portano da Arad a Bucarest (ad esempio, Arad à Sibiu, Sibiu à Faragas, Fagaras à Bucarest). Il costo di una soluzione è la somma dei costi accumulati da ogni singola azione eseguita. Se esploriamo, secondo l’algoritmo descritto (e raffinato) in precedenza, otteniamo i primi livelli dell’albero di ricerca

17

Abbiamo ispessito i nodi già espansi. Si noti che da una certa città si può sempre tornare indietro alla città precedente (Arad nel terzo livello dell’albero). L’espansione prosegue fino a generare un nodo contenente lo stato Bucarest. A quel punto troviamo la soluzione tornando indietro sull’albero verso il nodo Genitore e memorizzando l’Azione corrispondente; l’intera sequenza di azioni viene quindi invertita per iniziare l’esecuzione. Espandendo (in modo selettivo) l’albero, si nota invece che di soluzioni ce ne sono più di una.

Infatti, come si nota in figura, un cammino di soluzione passa per Sibiu – Fagaras e un altro per Sibiu – Rimnicu Vilcea – Pitesti. Introduciamo il costo della soluzione per comprendere qual è il cammino ottimale, cioè la soluzione che costa meno.

18

In questa figura, abbiamo inserito, a valle di ogni nodo, il costo del cammino fino a quel nodo. Si noti innanzitutto la differenza fondamentale, ora conteggiata, tra lo stato e il nodo: infatti, i vari nodi che contengono lo stato Arad, ad esempio, avranno costi diversi a seconda di come siamo arrivati allo stato; se vado avanti e indietro o faccio giri lunghi, il costo aumenta di conseguenza. Il costo del cammino fino a un nodo è dato dalla somma tra il costo del nodo genitore e il costo dell’azione specifica che genera il nodo stesso (il viaggio diretto tra le due città). Scopriamo così che la soluzione ottimale (con costo 418) si trova a una profondità maggiore (livello 5) della soluzione trovata in precedenza (450 a livello 4). Entrambe, comunque, sono soluzioni del problema. Finora abbiamo trascurato la strategia di ricerca che determina quale nodo viene espanso a un certo passo di computazione e che, a livello di raffinamento dell’algoritmo, ordina la frontiera in modo da avere sempre al primo posto il nodo da espandere. Una strategia di ricerca definisce l’ordine di espansione dei nodi dell’albero di ricerca. In particolare, permette di ordinare i nodi presenti nella frontiera. Le strategie possono nascondere insidie, in quanto potrebbero non sempre trovare la soluzione (anche se questa esiste) oppure non sempre trovare la soluzione ottimale, oppure ancora essere più o meno convenienti dal punto di vista dei costi di computazione. Si assumono quattro fattori per la valutazione:

• completezza: trova sempre la soluzione (se ne esiste una)? • ottimalità: trova sempre la soluzione di costo minimo? • complessità temporale: numero di nodi generati • complessità spaziale: numero massimo di nodi da mantenere in memoria

Per parlare in generale della strategia di ricerca e dell’albero, conviene introdurre delle misure: chiamiamo b il fattore medio di ramificazione (branching factor) dell’albero di ricerca, cioè il numero di figli che un nodo ha in media, e d la profondità a cui si trova la soluzione ottima. Strategie di ricerca cieca (non informata) Le strategie di ricerca cieca (o non informata) usa solo l’informazione disponibile nella definizione del problema (la quadrupla <S0, G, A, C>). In particolare, usano le azioni, per come sono state formalizzate, e il costo, per comprendere quali sono gli

19

stati successivi a un certo stato e qual è il costo per arrivarci, rispettivamente. Gli algoritmi che risultano non hanno una scrittura diversa da quella che abbiamo visto in precedenza: occorre solo sostituire la strategia con la quale i nodi generati vengono ordinati nella frontiera con quella corretta. In particolare, occorre adottare una struttura dati adeguata per la frontiera. Nel caso della ricerca in ampiezza (breadth-first), si espande seguendo l’ordine di generazione dei nodi. Vengono sempre espansi i nodi che si trovano più vicino alla radice. La frontiera in questo caso è organizzata come una coda (anche detta struttura FIFO, First In – First Out, cioè il primo nodo entrato in coda è il primo a essere espanso e eliminato dalla coda). Nella figura sottostante, abbiamo inserito dei numerini accanto ai nodi, che indicano l’ordine di espansione.

In corrispondenza dei passi di espansione, la frontiera assume di volta in volta la seguente configurazione:

1. [n1-Arad] 2. [n2-Sibiu, n3-Timisoara, n4-Zerind] 3. [n3-Timisoara, n4-Zerind, n5-Faragas, n6-Oradea, n7-Rimnicu Vilcea, n8-

Arad] 4. [n4-Zerind, n5-Faragas, n6-Oradea, n7-Rimnicu Vilcea, n8-Arad, n9-Lugoj,

n10-Arad] 5. [n5-Faragas, n6-Oradea, n7-Rimnicu Vilcea, n8-Arad, n9-Lugoj, n10-Arad,

n11-Oradea, n12-Arad] 6. …

Come si nota, la frontiera venga consumata nello stesso ordine con cui si riempie; infatti, l’indice del nodo corrisponde all’ordine di espansione. L’algoritmo è completo (cioè trova la soluzione, se esiste) e trova la soluzione ottima se il costo è sempre uguale a 1; il numero di nodi considerati, quindi il tempo di computazione, è proporzionale a bd+1 (b è il numero medio di nodi figli e d è la profondità a cui si trova la soluzione – si comincia a contare da 0, la profondità della radice – quindi, ad esempio, se b = 2 e d = 3, allora si espanderanno 16 nodi per trovare la soluzione); l’occupazione di memoria, cioè i nodi da memorizzare per una futura espansione, è anch’essa proporzionale a bd+1, dal momento che quando si arriva a livello d (dove si trova la soluzione) si hanno in memoria tutti i nodi rimasti indietro dei livelli precedenti (che sono tutti, cioè bd+1, tranne uno, quello che ho espanso su ogni livello).

20

Il problema della memoria occupata non esiste per la strategia di ricerca in profondità (depth first). La ricerca in profondità espande il nodo a livello più profondo, secondo l’espansione che si vede in questa figura.

In corrispondenza dei passi di espansione, la frontiera assume di volta in volta la seguente configurazione:

1. [n1-Arad] 2. [n2-Sibiu, n3-Timisoara, n4-Zerind] 3. [n5-Faragas, n6-Oradea, n7-Rimnicu Vilcea, n8-Arad, n3-Timisoara, n4-

Zerind] 4. [n9-Bucarest, n10-Sibiu, n6-Oradea, n7-Rimnicu Vilcea, n8-Arad, n3-

Timisoara, n4-Zerind] 5. …

La struttura dati che implementa correttamente la frontiera in questo caso è la pila (o stack o LIFO – Last In, First Out): l’ultimo nodo che viene inserito è il primo a essere espanso. L’algoritmo non è completo (cioè, non è sicuro che trovi la soluzione, se esiste) e quindi non trova neanche la soluzione ottima; l’incompletezza è data dal problema dei loop in cui potrebbe infilarsi l’algoritmo, quando incontra un nodo che si ripete lungo un cammino (ad esempio, Arad, nel nostro); questa anomalia si risolve inserendo un controllo per la presenza di uno stato che si ripete lungo un cammino (come abbiamo fatto in precedenza, informalmente, per il problema dei missionari e dei cannibali). Anche la strategia di profondità genererà un numero proporzionale a bd+1, nel caso peggiore, ma l’occupazione di memoria, cioè i nodi da memorizzare per una futura espansione, è invece proporzionale solo a b×d, cioè quei nodi che sono lasciati per futura espansione lungo la spina di profondità dei nodi espansi (vedi figura). Concludiamo questa breve rassegna degli algoritmi di ricerca cieca, con un cenno alla strategia denominata Approfondimento Iterativo (Iterative deepening). Questa strategia combina gli aspetti positivi dei due algoritmi di ampiezza e profondità, rispettivamente. La strategia sfrutta la proprietà per cui l’ultimo livello di un albero supera in generale i nodi contenuti nella somma di tutti i livelli precedenti: si fissa a ogni iterazione un livello massimo di profondità da esplorare (cominciando da 0, che include solo la radice); tutti i livelli, dal livello 0 della radice fino al massimo livello attuale, vengono esplorati secondo l’algoritmo di ricerca in profondità, passando a un

21

nodo fratello sullo stesso livello fino a che non si completano e si torna necessariamente al livello precedente; una volta completato tutto il sotto-albero entro il livello m, si aumenta m di 1 e si riparte dalla radice, ripetendo fino al livello m-1 il lavoro già fatto.

La figura rispecchia esattamente l’ordine di espansione: la presenza di più numeri vicini a un nodo simboleggia tutti i passaggi in cui quel nodo è stato espanso; le linee rosse tratteggiate rappresentano i limiti di volta in volta dell’algoritmo. Strategie di ricerca informata Le strategie di ricerca informata (o euristiche) sfruttano della conoscenza in più sul dominio del problema, che permette di valutare il nodo da espandere. Operativamente, si usa una funzione di valutazione f(n), che determina la bontà del nodo n; una strategia di ricerca informata espande il nodo migliore, quello che presenta il valore minimo della funzione. La funzione di valutazione include una componente euristica, la funzione h(n), che ha il compito di stimare il costo del cammino ottimale dal nodo a un goal (nodo goal); la funzione h(n) vale 0 nel caso di un nodo con stato obiettivo. Ad esempio, una funzione euristica che stimi il costo del cammino ottimale verso Bucarest è la distanza in linea d’aria dalla città di partenza. Si noti che tale considerazione è al di fuori della definizione del problema e viene dalla nostra esperienza per cui la distanza in linea d’aria è correlata alla distanza chilometrica sul terreno. I seguenti valori sono le distanze in linea d’aria delle città nella mappa della Romania vista sopra:

Arad 366, Bucarest 0, Craiova 160, Drobeta 242, Eforie 161, Fagaras 176, Giurgiu 77, Hirsova 151, Iasi 226, Lugoj 244, Mehadia 241, Neamt 234, Oradea 380, Pitesti 100, Rimnicu Vilcea 193, Sibiu 253, Timisoara 329, Urziceni 80, Vaslui 199, Zerind 374

Vediamo due algoritmi di ricerca informata che usano la funzione euristica h(n). La strategia best-first espande il nodo che ha la migliore h(n); cioè, nel caso di best-first, f(n) = h(n), cioè tutta la valutazione è data dalla funzione euristica. Si tratta di una strategia denominata greedy (cioè ingorda), perché espande, senza memorizzare nulla, il nodo che ha la h(n) migliore. Una simulazione, nel nostro caso, è data dalla seguente figura.

22

Se va bene, si tratta di una marcia trionfale verso l’obiettivo, ma purtroppo non esistono euristiche così affidabili. E’ un algoritmo incompleto: potremmo bloccarci in un loop infinito, se un nodo figlio e un nodo genitore hanno i valori di h(n) minimi e vengono quindi scelti di continuo; non è neanche ottimale, in quanto la soluzione ottimale potrebbe essere raggiungibile da un cammino all’apparenza parziale non ottimale. Sebbene l’euristica possa contribuire a risparmiare tempo e spazio, nel caso peggiore abbiamo un costo esponenziale, cioè un numero proporzionale a bd. I problemi di incompletezza della strategia best-first si risolvono con l’algoritmo A*, che costruisce una funzione f(n) = g(n) + h(n); cioè, la valutazione di un nodo tiene conto sia del costo del cammino dalla radice al nodo stesso (costo sicuro), sia della stima euristica dal nodo al nodo obiettivo; quindi, la funzione f(n) valuta il costo del cammino dalla radice all’obiettivo, che passa per il nodo n. La figura seguente simula l’applicazione di A* nel nostro esempio.

Si noti come l’algoritmo la soluzione ottimale, che l’algoritmo best first aveva trascurato. L’algoritmo A* risulta essere completo se la funzione euristica è ammissibile, cioè la funzione stima sempre per difetto il costo reale della soluzione; cioè

per ogni nodo, h(n) ≤ h*(n)

23

dove h* è il costo reale della soluzione ottimale da n all’obiettivo. Si tratta cioè di una strategia ottimistica, in quanto non sovrastima mai costo reale. Anche se poniamo il vincolo di essere ammissibili, non esiste una sola euristica per informare l’algoritmo di ricerca nello spazio degli stati. Consideriamo questa il gioco delle tessere (che si ritrova negli esercizi a fine capitolo). Nella figura sottostante, si parte dalla configurazione di sinistra (stato iniziale) per arrivare alla configurazione di destra (stato obiettivo), muovendo le tessere verso l’alto, il basso, destra e sinistra, nel posto della casella vuota.

Vediamo ora due funzioni euristiche. La prima è

h1 = numero di tessere fuori posto (corrisponde al numero di passi necessario per risolvere il problema nel caso in cui potessimo strappare le tessere dal loro posto attuale e inserirle al posto giusto).

Nel nostro esempio sono fuori posto tutte e nove;

quindi,

h1(n1) = 1+1+1+1+1+1+1+1+1=9. La seconda euristica è

h2 = numero minimo di passi per mettere a posto ogni tessera (come se potessero scivolare una sull’altra, cosa che nella realtà non è possibile).

Questo tipo di distanza dalla posizione corretta si chiama Manhattan. Nel nostro esempio, si ha la situazione seguente, in cui le frecce indicano il percorso minimo che deve fare una tessera per andare a posto.

24

Si ha che

h2(n1) = 2+3+1+1+1+1+1+1+1 = 12. Come si può immaginare, la risoluzione di h2 è superiore a h1, dal momento che cerca di approssimare più da vicino il comportamento del gioco, producendo una stima del costo più vicina al costo reale. Per comprendere meglio come funziona la stima euristica, consideriamo una nuova configurazione.

In questo caso, di nuovo si ha h1(n2) = 9, dal momento che tutte le tessere sono fuori posto.

Un occhio attento, tuttavia, può notare che nel caso di n2 le tessere sono meno fuori posto di prima (n1). Infatti, usando la funzione euristica h2 si ha la seguente situazione

Questa volta, h2(n2) = 1+1+1+1+1+1+1+1+2 = 10, differenziandosi dal caso precedente, come era plausibile attendersi. La funzione euristica h2 è ammissibile come h1 (entrambe stimano per difetto il costo della soluzione), ma h2 differenzia di più la valutazione della bontà dei nodi. Si può dimostrare sperimentalmente che il numero di nodi che verrà espanso per raggiungere la soluzione è inferiore.

25

Esercizi [Esercizio facile. Formalizzare il gioco delle tessere come quadrupla <S0, G, A, C>, definendo anche le strutture dati per la rappresentazione degli stati e le azioni. Calcolare l’albero di ricerca dello spazio degli stati nel caso della figura sottostante. Definire le strutture per la rappresentazione degli stati e delle azioni in modo formale e calcolare lo spazio degli stati raggiunto a partire dallo stato iniziale mediante l’algoritmo ricerca_albero, dichiarando anche la strategia e numerando coerentemente i nodi. Suggerimento: si può raggiungere lo stato goal.]

[Esercizio medio. Formalizzare il problema dei mariti gelosi (una variante del più famoso problema dei missionari e dei cannibali): ci sono tre coppie sposate che devono attraversare un fiume con il vincolo che nessuna donna può essere in presenza di un uomo a meno che non sia presente anche suo marito. In questo caso, le strutture dati sono simili al problema dei missionari e dei cannibali; tracciare lo spazio degli stati raggiunto a partire dallo stato iniziale. Suggerimento: attenzione che in questo caso la rappresentazione degli individui singoli è importante per gli accoppiamenti.] [Esercizio difficile. Prendere in considerazione un film o un videogioco narrativo e segmentare la storia individuando 4/5 punti di svolta, con un fattore di ramificazione tra 2 e 4 (inventarlo nel caso del film o considerazione esplicitamente “Sliding doors”). Formalizzare la storia mediante un problema che contiene uno stato iniziale (che descrive l’inizio della storia), un test per il goal (dati i goal individuati dopo la segmentazione e la ramificazione), un insieme di azioni (che codificano i punti di svolta della storia), una funzione costo (che dovrà essere costruita in modo da favorire la storia effettivamente raccontata dal film). Esplorare quindi lo spazio degli stati per dimostrare che la formalizzazione rappresenta correttamente la trama del film e le possibili trame alternative create. E’ una versione basilare della tecnica utilizzata per evitare la dispersione data dall’interattività nei videogiochi.] Bibliografia utile per questa sezione Stuart Russell, Peter Norvig, Intelligenza artificiale 3/Ed. - Vol. 1, Un approccio moderno, Pearson Education, 2010, pp. 704. I primi tre capitoli. Voci di Wikipedia per: Missionari e Cannibali, Taxicab geometry (Distanza Manhattan).

1 2

4 5 3

7 8 6

1 2 3

4 5 6

7 8Stato iniziale Stato goal