Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

Nota che quando un nodo non è ancora stato visitato, quel parametro vale infinito e quindi

garantisce che tutti i figli di un nodo siano esplorati almeno una volta.

La prima componente avvantaggia lo sfruttamento, perché è più alta per i nodi che hanno

un alto rapporto partite vinte su partite giocate. Il secondo parametro invece avvantaggia

l’esplorazione di nodi con poche giocate. Il parametro c contiene questo trade-off. Di solito

vale sqrt(2) ma viene poi scelto empiricamente. È una formula che impariamo a memoria

qui ma poi a machine learning la insegnano bene. Comunque ogni nodo contiene un

valore dato da questa formula e noi scegliamo, per l’espansione, quello che ha il valore

maggiore di quella formula. Nota che per l’espansione sono coinvolte TUTTE le foglie, non

solo i figli del nodo corrente. Inoltre il numero di volte che hai visitato un nodo è uguale alla

somma delle visite dei figli. In pratica più volte visiti un nodo, più piccolo diventa la

seconda componente. Cambiando il valore di c puoi diventare più “esplorativo”, cioè

l’albero diventa bilanciato aumentandolo. Se lo diminuisci invece dai subito la precedenza

ai nodi favorevoli.

Dopo il primo step, il resto è semplice. Infatti ora c’è l’espansione: espandiamo il nodo

scelto nel modo classico.

Poi si passa alla simulazione: partendo dal nodo scelto, facciamo partire la simulazione.

Questa cosa produce? Un outcome: vittoria, sconfitta, pareggio (chiamiamoli -1 0 1).

Prendiamo l valore ottenuto e attraverso la backpropagation lo aggiungiamo in tutti i nodi

da quello espanso fino alla radice.

Riassumendo il Montecarlo è un algoritmo efficiente che converge al minimax con tante

giocate e funziona bene per quei giochi in cui è difficile definire una funzione di

valutazione. Aumentando il parametro c diventa efficiente anche in presenza di alti

branching factor, visto che l’albero cresce in modo asimmetrico. Inoltre l’algoritmo si può

interrompere in qualsiasi momento e ti fornisce la miglior soluzione trovata finora. Adatta

una strategia ottimale dato che è stato dimostrato che con l’aumentare delle simulazioni

essa converge al minimax, ma non richiede la stesura di una euristica per i nodi foglia (che

richiede conoscenza del dominio di applicazione, che comunque si può usare per

migliorare l’efficienza). Nel mondo reale comunque minimax è più utilizzato in quei giochi

in cui è utile avere conoscenza del dominio (e quindi è possibile modellare una euristica),

mentre il Montecarlo funziona laddove non è possibile definire facilmente una euristica,

infatti il gioco degli scacchi funziona meglio con il minimax, mentre il Go funziona

unicamente con Montecarlo. Quest’ultimo tra l’altro non si accorge dei “trap states”, ovvero

quegli stati che sono vicini a farti perdere (e gli scacchi ne hanno parecchi).

Ok i quattro passi mi sono chiari, ma non mi è chiaro il suo funzionamento nel complesso.

Questo algoritmo parte dal nodo radice, che sarebbe LA SITUAZIONE IN CUI CI

TROVIAMO ADESSO. Da quello inizia a fare delle simulazioni finché non esaurisce una

certa risorsa (tempo, memoria, numero di iterazioni…). Alla fine ritorna la miglior azione da

svolgere dal nodo radice (ovvero l’azione che ti porta al figlio migliore o al figlio più visitato,

dipende dall’implementazione visto che a volte non coincidono). In pratica durante il

funzionamento costruisce un albero in cui le nuove partite simulate migliorano i dati

generati dalle simulazioni precedenti. Questi dati poi si propagano alla radice. Per questo

motivo ha senso dire che espandiamo un nodo tra tutte le foglie, se no non ha senso… Poi

espandere un nodo non significa trovare tutti i figli, ma significa trovare solo il successivo.

In pratica l’algoritmo è scrivibile così:

crea il nodo radice v dallo stato iniziale s

0 0

while c’è risorsa computazionale

v = Selection(v ) // seleziona il prossimo nodo

i 0

d = Simulation(v ) // esegui la simulazione e ottieni il risultato

i

BackPropagation(d) // aggiorna i nodi precedenti con il risultato

return miglior azione da v 0

La funzione di selezione fa questo:

while v non è terminale

if v non è completamente espanso

return Expansion(v)

else v = miglior figlio di v

return v

Oggi parliamo di un nuovo argomento. Finora abbiamo considerato problemi in cui lo stato

era atomico, un singolo valore, una etichetta. Naturalmente lo stato è qualcosa di più

complesso (per esempio la configurazione di una griglia), ma per gli algoritmi visti finora

ogni stato è semplicemente un id, un numero. Non devi sapere nulla su come è fatto

internamente uno stato: devi solo sapere se due stati sono uguali, ma non ti interessa

come sono fatti internamente, se sono parzialmente simili o completamente diversi. Le

strategie di ricerca usate finora non considerano la struttura degli stati, per questo diciamo

che gli stati sono atomici. Adesso gli stati invece saranno FACTORED, ovvero sono una

lista di coppie variabile/valore. Facendo così perdiamo generalità, nel senso che non

tutti i problemi saranno risolvibili con questa rappresentazione, ma quelli che si possono

rappresentare così avranno un grande miglioramento di efficienza nella risoluzione.

I problemi rappresentabili con coppie variabile/valore formano una classe chiamata

PROBLEMI DI SODDISFACIMENTO DI VINCOLI (CSP). Un problema di questo tipo è

definito da un insieme di VARIABILI del tipo x x x , ogni variabile può assumere valori di

1 2 3

un proprio DOMINIO denominato d d d , e da un insieme di VINCOLI che sono limitazioni

1 2 3

sulla combinazione dei valori che le variabili possono assumere. Per fare un esempio

intuitivo di vincolo possiamo scrivere x != x oppure x > x + x . Un vincolo formalmente è

1 2 2 1 3

una relazione sul prodotto cartesiano dei domini: questa relazione può indicare le

combinazioni accettate di valori o quelle non accettate. Nella pratica non useremo le

relazioni però la definizione è questa.

Qual è la soluzione di questi problemi? Un assegnamento alle variabili tale che tutti i

vincoli siano soddisfatti. Ad ogni variabile x assegniamo un valore del dominio d in modo

i i

che i vincoli siano tutti soddisfatti. La soluzione deve essere CONSISTENT (non viola

nessun vincolo) e COMPLETE (tutte le variabili hanno un valore, altrimenti hai un

assegnamento PARTIAL).

Facciamo un esempio con la mappa dell’Australia e le sue regioni. Dobbiamo colorare le

regioni: abbiamo tre colori (rosso, verde, blu) e ogni regione deve essere colorata in modo

che due regioni adiacenti non abbiano lo stesso colore. È il noto COLORING PROBLEM.

Le variabili sono quindi sette (una per ogni regione), mentre ogni variabile ha lo stesso

dominio dato dai tre colori. Per i vincoli non c’è una definizione unica per dire che due

regioni adiacenti non devono avere lo stesso colore: devi fare un vincolo per ogni coppia di

regioni adiacenti dicendo che le due variabili devono essere diverse, per esempio

Queensland != Victoria. Siccome sono una lista di diseguaglianze che coinvolgono solo

due variabili, abbiamo dei VINCOLI BINARI e in questa situazione possiamo costruire un

GRAFO DEI VINCOLI che vedremo meglio alla prossima lezione. Scopriremo che

aggiungendo variabili in più, anche i vincoli non binari li possiamo trasformare in binari e

questo darà interessanti vantaggi. Quando abbiamo vincoli binari, possiamo costruire un

grafo non orientato in cui i nodi corrispondono alle variabili, mentre un arco tra due variabili

indica che esse sono coinvolte in uno stesso vincolo. Facendo il grafo dell’Australia, già

intuitivamente capisci che il nodo più critico è quello con più archi (Southern Australia)

perché è coinvolto in più vincoli. Al contrario il nodo che non ha nessun arco può

assumere qualsiasi valore perché non è coinvolto in nessun vincolo (Tasmania). Qui il

problema è banale e ti accorgi di queste cose subito, ma nei problemi con 1000 variabili il

grafo ti aiuta a scoprire queste cose.

I domini possono essere continui o discreti. Il caso continuo è quello più semplice per gli

algoritmi. Con i domini discreti dobbiamo ulteriormente distinguere se il dominio è finito o

infinito.

Problemi di questo tipo nel mondo reale sono per esempio l’assegnamento di task a

degli agenti (le variabili sono i task, i domini sono gli agenti capaci di svolgere quel task, i

vincoli possono essere per esempio che un agente può svolgere un solo task), oppure

problemi di scheduling (questo molto importante e usato, anche dai satelliti). Le variabili

sono le attività da svolgere, il dominio rappresenta il momento in cui iniziare l’attività e i

vincoli sono sull’ordinamento temporale. E tanti altri… sono problemi molto legati alla

ricerca operativa.

Adesso formalizziamo il problema delle otto regine, quello visto nelle prime lezioni.

Partiamo dalla definizione più banale, in cui abbiamo 64 variabili x che rappresentano le

ij

singole celle. Ogni variabile ha un dominio binario {0, 1} che indica se la cella ha una

regina o meno. Ora arriva la parte complicata dei vincoli…

Due regine non possono stare sulla stessa riga:

x = 1 → x = 0 per ogni 1 ≤ k ≤ 8, k != j

ij ik

Due regine non possono stare sulla stessa colonna:

x = 1 → x = 0 per ogni 1 ≤ k ≤ 8, k != i

ij kj

Due regine non possono stare sulla stessa diagonale:

x = 1 → x = 0 per ogni 1 ≤ h, k ≤ 8, |i – h| = |j – k| != 0

ij hk

Non abbiamo detto che devono esserci otto regine… Se non lo dici la migliore soluzione è

non mettere nessuna regina :)

sum[i, j](x ) = 8

ij

Ora miglioriamo questa rappresentazione. Siccome sai già che devi mettere otto regine,

che hai otto colonne e che non puoi mettere due regine sulla stessa colonna, puoi usare

solo 8 variabili, una per ogni colonna. La variabile x rappresenta la posizione (la riga) in

i

cui inserire la regina nella colonna i. Il loro dominio è quindi l’insieme [1..8]

In pratica abbiamo iniettato un vincolo nella definizione del problema per restringerlo. A

questo punto abbiamo meno variabili, ma anche meno vincoli perché quello delle colonne

è implicito.

Due regine non possono stare nella stessa riga:

x = k → x != k per ogni 1 ≤ k ≤ 8, j != k

i j

Due regine non possono stare sulla stessa diagonale

x = k → |k – x | != |1 – d|, 1 ≤ d ≤ 8, d != i

i d

Non c’è bisogno di specificare che le regine devono essere otto, tanto meno il vincolo delle

colonne. Praticamente se usi una formalizzazione banale per il problema, hai tante

variabili e tanti vincoli. Invece con una modellazione furba, che contiene già dei vincoli, hai

meno variabili e meno vincoli. Vuol dire che la soluzione si trova in modo molto più

efficiente (pensa al Sudoku…). In pratica devi mettere nella definizione del problema la

maggior parte di conoscenza che hai del problema.

Compito per casa: formalizza il Sudoku, ne parlerà la prossima volta

Adesso passiamo alla parte algoritmica: come risolvere un CSP.

Per questi problemi usiamo gli algoritmi che conosciamo, cioè algoritmi di ricerca. Lo stato

iniziale è l’assegnamento vuoto. Poi, dato uno stato, la funzione di azione ritorna tutti i

possibili assegnamenti di una variabile non assegnata che sono consistenti con lo stato

(esempio in arrivo). Poi dati lo stato e l’azione, la funzione risultato ritorna un nuovo

assegnamento in cui lo stato è l’assegnamento dato finora e l’azione è un assegnamento

ad una variabile. Usiamo l’Australia come esempio.

Partiamo quindi dall’assegnamento vuoto. Quali sono le azioni possibili? AAAH ok, una

lista di assegnamenti per ogni variabile non assegnata e che siano consistenti con

l’assegnamento attuale. La funzione risultato quindi prende lo stato (l’assegnamento

corrente), un’azione (l’assegnamento ad una variabile) e ritorna un nuovo assegnamento.

Tornando alla definizione del problema: cos’è un goal test qui? Un assegnamento

completo. Basta che l’assegnamento sia completo affinché sia un goal state. La

consistenza è implicita nella funzione delle azioni che non ammette assegnamenti non

consistenti. Lo step cost è sempre uguale a 1.

Con questa definizione, vedi che lo stato è factored e non atomico. È una lista di variabili

con il loro assegnamento. Vedremo nella prossima lezione che questa struttura permette

di usare metodi risolutivi efficienti, ma talmente efficienti che potremmo addirittura non

dover costruire nessun albero! Pensa al Sudoku, lì non fai mica tutte le combinazioni, fai

dei ragionamenti per escludere a priori dei valori.

Nel problema dell’Australia, hai sette variabili e la soluzione la trovi al livello 7 dell’albero

perché devi assegnare tutte le variabili. Non puoi trovare una soluzione prima del livello 7,

ma neanche dopo perché non esiste niente dopo quel livello. Quindi la soluzione è al

livello 7 ed è garantito che non ci sono loop. Ora assumi che hai costruito l’intero albero

possibile. Al livello 7 puoi avere più di una soluzione. Hai qualche motivo per preferire una

soluzione ad un’altra? Assolutamente no, perché noi facciamo solo assegnamenti e tutte

le soluzioni hanno lo stesso costo. Non c’è il concetto di ottimalità. Dobbiamo solo

soddisfare vincoli ma non c’è niente da ottimizzare. Più avanti ci saranno anche problemi

di assegnamento in cui questi hanno un costo, ma qui non c’è nessun costo o valore da

ottimizzare. Dobbiamo solo trovare una combinazione di variabili che soddisfi i vincoli.

Dato quindi che:

- La soluzione è al livello n (con n il numero di variabili)

- Ogni soluzione è equivalente

quale strategia di ricerca dovremmo usare? DEPTH FIRST senza dubbio, per scendere il

prima possibile a trovare una soluzione, perché la prima soluzione che trovi va bene e

l’albero è limitato, non puoi cadere in un loop. Nel CSP useremo SEMPRE la ricerca in

profondità: naturalmente puoi usare anche le altre ma non ha senso. La usiamo nella

nostra versione di BACKTRACKING in cui torniamo indietro quando non possiamo

proseguire.

Ma c’è un’ulteriore ottimizzazione per velocizzare tutto… Nel momento in cui dobbiamo

espandere un nodo, perché provare tutti i possibili assegnamenti di tutte le variabili se

tanto l’ordine con cui li facciamo non conta? Verrebbe fuori un albero gigantesco: se ad

n

ogni livello facciamo d assegnamenti alle n variabili mancanti viene un albero con n!d

foglie... Possiamo allora fare in modo che ogni livello dell’albero è associato ad una

variabile in particolare, quindi quando siamo al livello 1 (cioè l’assegnamento vuoto)

cerchiamo SOLO gli assegnamenti possibili per la prima variabile. Poi nel secondo livello

cerchiamo gli assegnamenti solo della seconda variabile e così via… IN EFFETTI È

VERO, ANCHE IN UN SUDOKU FATTO COL BRUTEFORCE NON CERCHI TUTTI GLI

ASSEGNAMENTI DI TUTTE LE CELLE, MA SOLO DI QUELLA “CORRENTE” DICIAMO

n

COSÌ. Questa tecnica riduce mostruosamente la grandezza dell’albero (abbiamo d foglie)

e ci permette ancora di trovare la soluzione, per il fatto che non conta l’ordine con cui

assegni le variabili. Puoi scegliere tu l’ordine in cui assegnarle e ad ogni livello ti dedichi

solo a quella variabile. Questa ottimizzazione va a modificare la funzione delle azioni. Il

problema successivo quindi è scegliere l’ordine con cui assegnare le variabili, e anche

quale valore provare per primo una volta scelta la variabile. La scelta inficia sull’efficienza,

però MAI sulla possibilità di trovare la soluzione. Puoi scegliere un ordine casuale nella

scelta delle variabili e dei valori, ma la soluzione la trovi comunque. Il punto è che se sei

furbo nella scelta dell’ordine, potrai essere più veloce. Come pensavo, nel problema

dell’Australia la cosa più sensata è partire dal Southern Australia perché è la variabile più

critica. Se scegli un’altra regione, potresti poter assegnare cinque regioni senza problemi e

quando arrivi in SA non puoi assegnare niente e devi tornare indietro.

Formulazione del Sudoku. Iniziamo con una formulazione banale

Variabili

81 x dove ogni x rappresenta una cella

ij

Dominio

L’insieme [1..9]

Vincoli

Un numero non può comparire più di una volta nella stessa riga

x = y → x != y per ogni 1 ≤ k ≤ 9

ij ik k != j

Un numero non può comparire più di una volta nella stessa colonna

x = y → x != y per ogni 1 ≤ k ≤ 9

ij kj k != i

Un numero non può comparire più di una volta nello stesso blocco

x = y → x != y per ogni (i - i % 3 + 1) ≤ k ≤ (i - i % 3 + 3)

ij kl (j - j % 3 + 1) ≤ l ≤ (j - j % 3 + 3)

k != i

l = j

Un valore iniziale per ogni cella già assegnata

Abbiamo detto che usiamo un’esplorazione in profondità con backtracking e ogni livello

analizza una certa variabile. Dobbiamo decidere però da quale variabile iniziare, con quale

ordine selezionare le variabili e con quale ordine assegnare i valori possibili del dominio.

Abbiamo notato che se scegliamo bene l’ordine delle variabili, siamo più efficienti nel

trovare la soluzione, la quale comunque la troviamo in qualsiasi situazione.

Iniziamo con la scelta delle variabili. Esistono due tecniche basate su euristiche per fare

questa decisione, la prima si chiama MINIMUM REMAINING VALUE (MRV). Scegliamo

ad ogni livello la variabile con il minor numero di assegnamenti validi rimasti. Facendo

l’esempio dell’Australia, all’inizio tutte le sette variabili possono avere tre assegnamenti

validi, quindi le variabili sono equivalenti nell’euristica e la scegliamo casualmente. Il prof

ha scelto Western Australia e lo coloriamo di verde. Al secondo passo accade che le due

regioni SA e NT hanno solo due assegnamenti validi, quindi scegliamo una di queste due

variabili e non le altre che possono ancora assumere tre valori possibili. Mettiamo caso

che scegliamo il Northern Territory e lo coloriamo di rosso: a quel punto abbiamo che SA

ha un solo valore possibile (il blu) e lo scegliamo al terzo passo, mentre il Queensland ne

ha due, e prosegui in questo modo. Questa euristica è molto migliore rispetto alla scelta

random, perché se fai una scelta degli assegnamenti che non ti permette di arrivare alla

soluzione (cioè arrivi in un punto in cui non puoi assegnare nessun valore ad una variabile

e devi fare backtracking), con MRV lo scopri in fretta dopo pochi assegnamenti, mentre

con la scelta random potresti scoprirlo più tardi. Questo è ciò che rende MRV un algoritmo

efficiente: capiamo velocemente se stiamo seguendo un branch sbagliato. Il suo obiettivo

è proprio quello di cercare il prima possibile un assegnamento che ci fa capire che

abbiamo sbagliato strada e dobbiamo cambiare le scelte fatte in precedenza. Un problema

di questo algoritmo però è che all’inizio non ci dà nessuna informazione su quale variabile

assegnare per prima: nel problema dell’Australia infatti tutte le sette variabili hanno tre

possibili assegnamenti. Non c’è modo di fare una buona scelta alla partenza.

Per questo motivo esiste un’altra euristica chiamata DEGREE HEURISTIC. Quando

dobbiamo scegliere una variabile, scegliamo quella che è coinvolta nel maggior numero di

vincoli con variabili che non sono ancora state assegnate. Si chiama degree perché in

pratica guardi il degree della variabile nel grafo dei vincoli! Prendi la variabile che ha il

maggior numero di archi (tra quelli relativi a variabili non assegnate). In questo modo, nel

problema dell’Australia la prima variabile scelta è Southern Australia, perché confina con

cinque regioni. Scegliendo SA come prima variabile, più avanti avremo meno probabilità di

finire in un branch che non porta alla soluzione.

Nella realtà queste euristiche non sono usate da sole, ma sono usate insieme! Si usa

MRV come euristica principale, e si usa il degree heuristic quando c’è una situazione di

parità. Questo si può applicare naturalmente al problema dell’Australia. Hai visto che

all’inizio tutte le variabili hanno tre assegnamenti possibili, allora per decidere da chi

partire guardi il degree e per questo scegli il Southern Australia. Poi vai avanti con MVR e

in caso di parità usi il degree heuristic. Il bello di queste euristiche è che sono generali, le

puoi usare in tutti i contesti, ma le puoi comunque modificare perché ricordati che nei CSP

l’euristica modifica l’efficienza, ma non la possibilità di trovare una soluzione.

Ora c’è un altro problema: scegliere quale valore assegnare tra quelli possibili e

serviranno altre euristiche. Anche qui potremmo fare scelte random, oppure in un ordine

fissato (per esempio prima rosso, poi verde e blu), ma è più intelligente usare metodi

efficienti. Vediamo per esempio il LEAST CONSTRAINING VALUE. Quando dobbiamo

scegliere un valore, scegliamo quello che dà più libertà alle variabili che non sono ancora

state assegnate. Significa che dobbiamo vincolare il meno possibile le variabili che non

abbiamo ancora assegnato. Anche qua si capisce bene il significato nel problema

dell’Australia: se assegni il blu a WA, il verde a NT e poi scegli il Queensland, se lo colori

rosso il SA non ha più assegnamenti possibili, se invece lo colori di blu al SA rimane un

colore disponibile. Vedi che in pratica assegni un colore valido ad un nodo che però

obbliga altri nodi ad avere un solo colore o addirittura nessuno. Scegliere un altro colore

invece può permettere agli altri nodi di avere a disposizione più colori: lo scopo

dell’euristica in pratica è evitare che si arrivi ad un punto in cui non puoi più assegnare

valori alle variabili. La filosofia di questa euristica è l’esatto opposto di MRV! Quest’ultimo

cerca di tagliare subito un branch che non arriva alla soluzione: ci permette dal punto di

vista computazionale di evitare di costruire nuovi nodi. Ma una volta che li abbiamo

costruiti, cerchiamo di allungare quel branch il più possibile, e questo è ciò che fa LCV. La

combinazione di queste due euristiche è una bomba di efficienza.

Finora abbiamo visto che i CSP si possono risolvere attraverso la ricerca, come avevamo

fatto nei problemi con stati atomici ad inizio corso. Ma dato che qui gli stati sono composti,

potremmo trovare una soluzione non con la ricerca, ma usando il ragionamento,

l’inferenza: CONTRAINT PROPAGATION. L’idea è di controllare i vincoli non solo quando

generiamo i nodi figli con la funzione delle azioni, ma proprio durante la ricerca. Una

tecnica possibile e semplice è il FORWARD CHECKING: dice che quando assegniamo un

valore ad una variabile, dobbiamo aggiornare il dominio delle altre variabili, in modo da

eliminare i valori che non sono compatibili con l’assegnamento appena fatto, tipo il

Sudoku? Per esempio assegno il colore rosso al Western Australia, e a quel punto cerco

le variabili che hanno un vincolo con quella appena assegnata e rimuovo il rosso dai loro

valori possibili, perché non è consistente con i vincoli (sì, come con il Sudoku quando

assegni un numero e lo rimuovi dai candidati delle altre celle, qui togli il rosso da SA e

NT). Ora mettiamo caso che assegno il verde al Queensland: aggiorno i domini delle

variabili, togliendo il verde da SA, NT e NSW. Poi assegno il blu al Victoria: tolgo il blu da

SA e NSW. Ottengo che il NSW può essere solo rosso, mentre SA non ha nessun valore

ammissibile. A questo punto posso già fare backtrack e capire che il branch non porta ad

una soluzione, ma lo ho scoperto non dopo aver selezionato SA, ma già prima al momento

dell’assegnamento di un’altra variabile, cioè NSW. Appena assegno un valore, aggiorno i

domini delle altre variabili e memorizzo i domini in una struttura dati. È esattamente quello

che ho fatto nel risolutore del Sudoku. Questa tecnica ti aiuta a scoprire un branch cieco in

anticipo, ma solo se arrivi al caso in cui una variabile non ha più nessun assegnamento

possibile. Non scopre in anticipo tutti i casi possibili di inconsistenza: per esempio se

assegni il verde a WA e il rosso a Q, hai che SA e NT possono entrambe avere solo il blu,

ma ciò di fatto non è possibile e il forward checking non se ne accorge prima di aver

effettivamente assegnato il blu ad una delle due variabili.

Di questi casi se ne accorge invece la tecnica dell’ARC CONSISTENCY. Esso si basa su

una versione del grafo dei vincoli con archi orientati. Esso è costruito in questo modo: se

abbiamo due variabili X e Y connesse da un arco, quest’ultimo è diviso in due archi: uno

che va da X a Y e l’altro da Y a X. L’algoritmo di arc consistency guarda ogni arco tra due

variabili non assegnate e fa questo controllo: l’arco è considerato CONSISTENTE se per

ogni valore assegnato del dominio di X, c’è almeno un valore consistente nel dominio di Y.

Se un arco non è consistente, significa che c’è un valore nel dominio di X per cui non

esiste un valore consistente per Y, allora rendo l’arco consistente cancellando quel valore

dal dominio di X. Ogni volta che cancello un valore dal dominio, riesamino gli archi e

continuo finché non faccio più modifiche ai domini delle variabili. Una volta completato

questo loop, se esiste almeno una variabile con un dominio vuoto, allora l’assegnamento

fatto in quel momento non è consistente e sicuramente non mi porterà alla soluzione,

perciò mi posso fermare subito nella ricerca. È esattamente quello che faccio nel Sudoku.

Spettacolare. Vedendo più precisamente il funzionamento dell’algoritmo (chiamato AC-3):

abbiamo una coda con gli archi del grafo orientato. Finché la coda non è vuota, tiri fuori un

arco: controlli se è consistente. Se lo è passi al prossimo, se non lo è elimini delle variabili

dal dominio di X. Ciò accade se si verifica questa condizione: se sto controllando l’arco X

→ Y AND l’arco non è consistente AND per renderlo consistente modifico il dominio di X

THEN reinserisco nella coda tutti gli archi di tipo Z → X (cioè vicini di X) perché potrei

ulteriormente ridurre i domini dei vicini. Questo algoritmo è davvero figo perché se il

dominio delle variabili è finito, allora è garantito che esso converga in una situazione tra

queste: una variabile ha il dominio vuoto (di conseguenza l’assegnamento non è

consistente e interrompiamo subito l’esecuzione) oppure si è svuotata la coda. Per i

domini finiti è garantito che una di queste situazioni accada. In quest’ultimo caso possono

verificarsi a loro volta altri due casi: ogni variabile ha un solo valore nel dominio, e quindi

HO TROVATO LA SOLUZIONE, oppure almeno uno dei domini ha più di un valore e in

quel caso non posso dire nulla sulla presenza della soluzione, per cui proseguo nella

ricerca. La coda rappresenta gli archi per i quali devo ancora controllare la consistenza. In

alcuni casi è utile fare il controllo della consistenza non dopo aver fatto un assegnamento,

ma all’inizio del problema per semplificare la ricerca. Di fatto puoi combinare ricerca e

ragionamento nell’ordine che vuoi: prima ragioni e poi cerchi, oppure cerchi e poi ragioni…

Naturalmente ragionare costa computazionalmente, ma è molto più efficiente ragionare un

po’ per ridurre l’albero di ricerca piuttosto che fare una ricerca cieca con un bruteforce.

L’algoritmo visto qui è anche chiamato 2-CONSISTENCY, perché di fatto facciamo un

controllo tra coppie di variabili. L’algoritmo si può estendere per esempio al 3-

CONSISTENCY, controllando triplette di variabili (diciamo che una coppia di variabili x y è

3-consistent ad una terza variabile z se, per ogni assegnamento possibile di x e di y, esiste

un assegnamento valido per z), o al sempre più generico k-CONSISTENCY. Naturalmente

gli algoritmi diventano sempre più complessi sia da implementare che da calcolare.

Vedendo gli estremi: cos’è il 1-CONSISTENCY? Significa controllare il dominio di una

singola variabile (funziona con vincoli unari ed è anche chiamato NODE CONSISTENCY).

Cosa succede invece se abbiamo n variabili e applichiamo l’n-consistency? La difficoltà

dell’n-consistency è esattamente uguale a quella dell’intero problema da risolvere e ti trova

la soluzione. Questo suggerisce che c’è un trade-off tra la computazione del ragionamento

che puoi fare e il guadagno che puoi avere dal risultato di quel ragionamento. Per dire

nessuno usa l’n-consistency perché equivale a risolvere il problema stesso: la complessità

del ragionamento è la stessa della ricerca. Da molti esperimenti risulta che il 2-consistency

(quindi l’arc consistency) è in genere un buon trade-off, al massimo 3-consistency in alcuni

casi, ma già dal 4-consistency in poi diventano troppo complessi e non c’è un guadagno di

efficienza sensato.

I CSP quindi si risolvono mischiando la ricerca e il ragionamento. Scopriamo quindi che se

noi conosciamo la struttura degli stati, possiamo risolvere i problemi non solo con la

ricerca, ma componendo ricerca e ragionamento. Questo tipo di inferenza si può fare solo

perché conosciamo la struttura degli stati. Se essi fossero atomici, non potremmo fare

cose come queste. Questa idea si applica a molti domini e applicazioni. Ciò vuol dire che

gli schemi di ricerca visti all’inizio del corso nella pratica non sono quasi mai usati da soli:

nella pratica si usano ricerca + ragionamenti dipendenti dal contesto.

IL SUDOKU È UN OTTIMO ESEMPIO DI CSP E PUÒ ESSERE RISOLTO USANDO

SOLO IL RAGIONAMENTO E NESSUNA RICERCA, PRECISAMENTE LA 3-

CONSISTENCY

Esercitazione

Variabile x con dominio {1, 2, 3, 4}

Variabile y con dominio {A, B, G}

Variabile z con dominio {a, b}

Vincoli espressi come coppie accettabili di valori

(x, y) = (1, A) (2, G) (3, A) (4, G)

(x, z) = (1, a) (3, a) (4, b)

(y, z) = (A, b) (B, a) (G, b)

Ad ogni passo dobbiamo controllare coppie di variabili perché facciamo arc consistency

x = {1, 2, 3, 4} y = {A, B, G} z = {a, b}

x, y y, x x, z z, x y, z z, y

Fai arc consistency per ogni coppia e rimuovi dei valori dal dominio di ogni variabile

(x, y) è sempre consistente

(y, x) non è consistente se y = B quindi rimuovi B da y → {A, G}

Rimuovendo B da y, dai vincoli rimuoviamo anche (y, z) = (B, a)

Avendo fatto una modifica, nella lista degli archi da controllare riaggiungiamo tutti gli archi

che hanno y come destinazione, ovvero (z, y) che comunque non abbiamo ancora

controllato.

(x, z) non è consistente se x = 2 quindi rimuovi 2 da x → {1, 3, 4}

Aggiungi alla lista gli archi (y, x) e (z, x)

(z, x) è sempre consistente

(y, z) è sempre consistente

(z, y) non è consistente se z = a quindi rimuovi a da z → {b}

Aggiungi alla lista gli archi (x, z) e (y, z)

Abbiamo che z = b

Grazie a z abbiamo che x = 4

E che y = G

Da oggi si parla dei KNOWLEDGE-BASED AGENT attraverso al logica, uno dei più

importanti aspetti dell’IA. Noi per ora abbiamo discusso dell’esplorazione di un albero per

trovare gli stati che soddisfano il terminal state. Gli stati li abbiamo analizzati inizialmente

come atomici e poi come composti nei CSP. Ora gli stati saranno ancora più complessi:

saranno un insieme di formule logiche. Uno stato è una lista di formule logiche. Queste

formule rappresentano lo stato dell’ambiente in un certo momento, e tali stati sono

chiamati KNOWLEDGE BASED (KB). Rappresentare gli stati in questo modo ci permette

di riutilizzare alcune informazioni in altri stati,abbiamo una rappresentazione conoscitiva

dell’ambiente, ovvero possiamo fare inferenza e deduzione con la logica. Non c’è bisogno

di rappresentare tutto il mondo, ma solo ciò che è sufficiente per derivare altra conoscenza

dell’ambiente e agire di conseguenza. In pratica facciamo ragionare i nostri agenti.

La LOGICA è un linguaggio formale per rappresentare la conoscenza. Quando parliamo di

un linguaggio logico ci servono la SINTASSI e la SEMANTICA. La sintassi è come le

formule logiche sono scritte, mentre la semantica indica la verità di una formula. Le logiche

che vedremo sono quella PROPOSIZIONALE e quella DEL PRIM’ORDINE.

Con la logica proposizionale, ogni stato è una lista di formule di questo tipo. Le lettere

dichiarative sono associate ad un significato nel linguaggio naturale che può essere o vero

o falso. Per esempio in un satellite potremmo dire che la lettera A indica “la temperatura è

superiore ai 90 gradi” mentre B significa “il satellite sta guardando il sole”. Poi definiamo la

lettera C con “il satellite funziona correttamente”, ma questa non è una conoscenza che

misuriamo direttamente, possiamo vederla come conseguenza di altra conoscenza,

scrivendo A and B → C. Il punto è che il valore di verità delle lettere dichiarative è dato in

parte dall’osservazione diretta dell’ambiente (A e B li conosciamo con dei sensori), altre

informazioni invece sono delle derivazioni da questa conoscenza (C non è calcolato coi

sensori, ma è una derivazione da altre variabili). La conoscenza che misuriamo

direttamente compone i FATTI dell’ambiente, mentre la conoscenza che deriviamo forma

le REGOLE. La lettera C non è qualcosa che misuriamo, ma è una conoscenza implicita

nelle lettere A e B che scopriamo con la logica.

A and B → C

C → D

C and E → F

A

B

Questo modello è molto usato per studiare il funzionamento di macchinari di ogni tipo (un

satellite, un’automobile…) oppure per fare la WHAT IF ANALYSIS, in cui studi cosa

succede dati certi input. Il processo di derivare nuova conoscenza dalla KB è chiamato

INFERENZA. La scrittura KB |= α significa che dalla KB, attraverso un algoritmo di

i

inferenza i, posso derivare α. Una procedura di inferenza banale potrebbe essere quella di

elencare tutte le lettere che trovi, e hai così che dalla KB ottieni tutte le formule A, B, C, D,

E, F. Ma non ha senso! Funziona sintatticamente, ma semanticamente no, perché non c’è

nulla nella KB che ti fa logicamente derivare E ed F. L’inferenza ha senso con

l’ENTAILMENT, ovvero che KB |= α ha senso se, ogni volta che KB è vero, anche A è

i

vero, cioè c’è conseguenza semantica. Nella logica proposizionale ciò si può fare in

modo molto semplice. Se hai un assegnamento alla KB che rende KB vero, allora

quell’assegnamento è detto MODELLO per KB. Se in una procedura di inferenza si ha che

ogni modello di KB è anche modello di α, allora la procedura è detta SOUND (corretta). La

nostra procedura di inferenza che elenca tutte le variabili non è sound, perché le variabili

che otteniamo non sono un conseguenza logica della KB. Poi se una procedura di

inferenza trova tutte le conseguenze logiche della KB, essa è detta COMPLETE. Se

dovessi scegliere una sola di queste due proprietà, ovviamente la migliore sarebbe la

soundness. La procedura di inferenza è una cosa legata alla sintassi, alla manipolazione

delle formule, per cui è un algoritmo. L’entailment invece è legato alla semantica.

Ragioniamo ora in termini di logica del prim’ordine. È ovviamente più potente. La logica

proposizionale è basata su fatti che sono o veri o falsi. Puoi dire se la temperatura è

superiore o inferiore ad un certo valore, ma non puoi dire che la temperatura vale, che so,

50 gradi. Nella logica del prim’ordine invece abbiamo oggetti, funzioni su questi oggetti e

relazioni tra gli oggetti. Questa è una descrizione dell’ambiente molto più ricca. Per

quanto riguarda la sintassi, gli oggetti sono rappresentabili con costanti o variabili. Poi

simboli funzionali per rappresentare le funzioni e simboli relazionali per rappresentare le

relazioni. Tra gli operatori logici si aggiungono i quantificatori. La semantica è data

dall’assegnamento ai predicati e alle variabili.

Naturalmente anche qui vale il discorso della conseguenza semantica, sulla soundness e

completeness. Una cosa molto interessante è che nei domini finiti delle variabili possiamo

“proposizionalizzare” delle formule del prim’ordine. In pratica, se hai un “per ogni” devi

esplicitamente ricopiare la formula per ogni assegnamento possibile (cosa che puoi fare

perché il dominio è finito). La KB proposizionale che ottieni è detta INFERENZIALMENTE

EQUIVALENTE. Naturalmente lo puoi fare anche con il quantificatore esistenziale usando

un trucchetto, che è la Skolemizzazione: togli il quantificatore ma sostituisci la variabile

quantificata con una costante. Però questa trasformazione in logica proposizionale NON

FUNZIONA se la KB ha delle funzioni, perché puoi sostituire i parametri delle funzioni con

altre funzioni e così ricorsivamente all’infinito, anche se il dominio è finito! Questo per il

fatto che la logica del prim’ordine è semi-decidibile in tante cose, ovvero se voglio provare

che una formula è vera, il processo può finire oppure durare all’infinito. Se una formula

non è conseguenza logica, il processo non finisce mai dicendoti “no” e ciò dipende da

questo fatto. Se una formula è effettivamente conseguenza logica, prima o poi ti dirà “sì”.

È per questo motivo che trasformiamo il prim’ordine in proposizionale quando possiamo,

perché questa logica è decidibile ed è anche analizzabile in modo molto efficiente.

Ora vediamo come derivare nuova conoscenza partendo da un insieme di formule, la KB.

Lo scopo è capire se una formula α è conseguenza semantica della KB. La prima

procedura che vediamo è chiamata FORWARD CHAINING: la KB però deve contenere

solo DEFINITE CLAUSES, cioè delle frasi che sono o delle singole lettere enunciative,

oppure una serie di lettere unite in AND che implicano una sola lettera enunciativa. Del

tipo A, B, C and D → E… Se questa condizione è verificata, allora il forward chaining può

usare questa regola di inferenza chiamata MODUS PONENS, ovvero se ho A e A → B

allora genero B. Nota quindi che con il modus ponens puoi derivare solo altre lettere

enunciative, cioè derivi dei fatti.

Dal punto di vista implementativo, le formule sono memorizzate non come stringhe ma

come alberi. In una KB con sole definite clause, il forward chaining è sound e complete.

Vuol dire che tutte le lettere generate sono vere, e che trova tutte le lettere enunciative che

sono vere. Inoltre questo algoritmo termina sempre in una condizione finale in cui ha

scoperto tutta la conoscenza che c’è.

Ora passiamo ad una procedura più complicata: la RISOLUZIONE. La KB stavolta può

essere generica, con qualsiasi tipo di frase. Però affinché possiamo applicare la

risoluzione, dobbiamo trasformare la KB in una forma chiamata CNF (CONJUNCTIVE

NORMAL FORM), che sarebbe la seconda forma canonica. Ogni frase è composta da

sottofrasi collegate in AND e le sottofrasi hanno delle lettere enunciative collegate in OR.

Le sottofrasi sono chiamate CLAUSOLE, e le clausole sono formate da una congiunzione

di letterali (i letterali sono un simbolo dritto o un simbolo negato). Se hai due clausole in

cui compare lo stesso letterale, e in una è dritto e nell’altra negato, si dice che le due

clausole sono COMPLEMENTARI.

Come trasformare un insieme di frasi in forma CNF? Con quattro fasi:

- Eliminazione delle doppie implicazioni: una formula del tipo A ↔ B è equivalente a (A →

B) and (B → A)

- Eliminazione delle implicazioni: una formula del tipo A → B è equivalente a not A or B

- Spostamento interno delle negazioni: significa spostare il not in modo che si trovi

esclusivamente davanti ad una singola lettera enunciativa. Qui è utile usare De Morgan,

oltre alla doppia negazione. Quindi not (A and B) = not A or not B mentre not (A or B) =

not A and not B

- Distribuzione degli or sugli and: qui bisogna riordinare le cose in modo da avere una CNF

Una volta ottenuto un insieme di clausole, ecco la regola di risoluzione: date due

clausole, se esse sono complementari (cioè un letterale compare dritto in una e negato

nella seconda), puoi generare una nuova clausola in cui quel letterale non compare più.

Come consideriamo le clausole? Beh in una KB tutte le frasi sono vere, quindi possiamo

vedere la KB come un gigantesco insieme di clausole unite in and. Se arrivi a generare la

clausola vuota, succede che la tua KB è INSODDISFACIBILE: non esiste un

assegnamento alle lettere affinché tutte le regole siano vere. Questa situazione viene

rivelata dalla risoluzione se trova la clausola vuota. Ciò è causato dal fatto che ottieni due

regole contenenti una A e l’altra not A e ovviamente non possono essere entrambe vere.

Data questa caratteristica, se ci chiedono se una frase α è derivabile dalla KB, basta

seguire questi passi:

- Traduci la KB in CNF

- Aggiungi alla CNF la clausola not α

- Prova a derivare la clausola vuota con la risoluzione

Se ottieni la clausola vuota allora α è conseguenza della KB. Percα deve essere negata?

Beh la dimostrazione formale è complicata, però io ho scoperto una dimostrazione

“grafica” che è geniale.

Vabbè fa vedere il metodo sistematico e poi quello con l’albero che è più intelligente. Poi

durante lo svolgimento a mano si possono applicare vari trucchi per velocizzare il tutto: per

esempio se hai una clausola del tipo A or not A or C la puoi trasformare in C. Oppure una

clausola con A or A la trasformi in A (si chiama FATTORIZZAZIONE). Anche qui la

risoluzione è sound e complete, e l’algoritmo raggiunge sempre un punto fisso MA devi

usare la fattorizzazione, se no potrebbe inutilmente continuare all’infinito.

Un altro metodo di inferenza si chiama MODEL CHECKING. Si cerca di dimostrare che

KB |= α controllando se ogni modello di KB è anche modello per α. Ma richiede un tempo

esponenziale… I model checking però usa un modo efficiente per controllare proprio

questo. L’algoritmo che vediamo si chiama DPLL, che brutto nome. Comunque è semplice

ed ha un approccio diverso dalle regole di inferenza viste prima. Si prende α, la si mette

negata dentro la KB, si ottiene una enorme CNF e si verifica se questa è insoddisfacibile.

Ci vuole quindi un algoritmo per verificare se una formula in CNF è soddisfacibile o meno:

è lo stesso usato per risolvere il SAT. Ma guarda caso si tratta di un CSP… devi

assegnare dei valori (vero o falso) a delle variabili (le lettere enunciative). Si parte dal

modello vuoto e si segue il classico algoritmo di assegnamento per i CSP. Però ci sono

metodi appositi per ottimizzare questo algoritmo visto che siamo nel mondo esponenziale,

come metodi intelligenti per la scelta delle variabili da assegnare e metodi per fermarsi in

largo anticipo.

Per esempio ci fermiamo quando è chiaro che non c’è una soluzione nel branch in cui ci

troviamo. Come ce ne accorgiamo? Se una singola clausola è falsa nel modello costruito

finora, possiamo già dire che dobbiamo tornare indietro. Perché? Perché le clausole sono

collegate in and, quindi devono essere tutte vere per prima cosa. Un CSP normale si

ferma quando non ha più assegnamenti possibili, qui invece ci fermiamo quando una

clausola è falsa, visto che possiamo sempre assegnare quello che vogliamo. Allo stesso

modo, se in una clausola assegniamo il valore vero ad un letterale dritto, sappiamo già

che quella clausola è vera e non la consideriamo più. Si chiama EARLY TERMINATION

HEURISTIC.

Poi c’è anche il trucco per scegliere una variabile. Metti caso che hai una clausola del tipo

B or C e B è falso, devi per forza assegnare vero a C. Si chiama SINGLE UNIT

HEURISTIC: se hai una singola variabile per rendere vera una clausola, la scegli e ci dai

l’assegnamento che rende il letterale vero. Se in una clausola un letterale è falso, puoi

toglierlo e potresti finire nella situazione della single unit. E assegnando un valore ad una

variabile potresti generare altre single unit. Potresti anche arrivare ad una situazione in cui

le clausole sono vere indipendentemente dal valore di alcune variabili: in quella situazione

hai comunque trovato un modello e puoi dire con tranquillità che α deriva da KB, anche

con un modello parziale.

Diciamo che un simbolo è un PURE SYMBOL se compare sempre dritto o sempre negato

(cioè “con lo stesso segno”). Si può provare che se esiste un modello per KB e α,

sicuramente esiste un modello (anche lo stesso di partenza) in cui i simboli puri sono veri.

Questo perché se un pure symbol è vero lo è in tutte le clausole in cui compare. Quindi se

trovi un pure symbol per prima cosa rendi vero il letterale associato. Tra l’altro, usando il

solito trucco di escludere dalle clausole i letterali che si sa già essere falsi, potremmo

trovare dei pure symbol che prima non lo erano e quindi propagare questa interessante

proprietà. Insomma alla fine è un Sudoku pure qua :D

Comunque anche qua c’è un mondo interessantissimo di roba… Comunque il DPLL cerca

di trovare un assegnamento ad un insieme di formule logiche: se usi DPLL per fare la

risoluzione, ovviamente non devi essere in grado di trovare un assegnamento. L’algoritmo

viene eseguito in quest’ordine e gli input sono le clausole c, i simboli da assegnare sym e

l’assegnamento a (inizialmente vuoto)

Se tutte le clausole sono vere return true

Se esiste una clausola falsa return false

P, val = Cerca i pure symbol # P sono i simboli, val assegnamenti che li rendono veri

Se P è non vuoto

DPLL(c, sym \ P, a U {P = val})

P, val = Cerca le unit clause # P sono i simboli, val assegnamenti che li rendono veri

Se P è non vuoto

DPLL(c, sym \ P, a U {P = val})

x = sym[0], xs = sym[1:]

return DPLL(c, xs, a U {x = true}) or DPLL(c, xs, a U {x = false})

Vedi che quest’algoritmo è usato in modo ricorsivo e va bene per un computer…

Comunque ricorda di usare la fattorizzazione! E poi nell’algoritmo ufficiale non si vede,

ma quando lo fai a mano, una volta che una clausola è vera la togli perché ormai è

soddisfatta. Il bello dei pure symbol è proprio il fatto che rendi vere tutte le clausole in cui il

pure symbol compare e quindi le rimuovi dai calcoli successivi!

L’ultima parte del corso: uniamo tutte le cose viste finora nel PLANNING

Si tratta sempre della ricerca di una soluzione in un albero di ricerca, la sequenza di azioni

da eseguire qui si chiama PLAN e lo stato del problema è rappresentato come un insieme

di formule logiche. Dovremo però rappresentare le azioni per passare da uno stato

all’altro: una certa azione come modifica lo stato logico? Integriamo l’uso della logica con

la ricerca della soluzione.

Ricominciando dall’inizio, che cos’è uno STATO nel caso del planning? È un insieme di

formule logiche, precisamente una congiunzione di letterali positivi della logica del

prim’ordine, senza variabili (cioè GROUND) e senza funzioni. Per esempio siamo un

macchinario che deve prendere dei blocchi e spostarli con un braccio meccanico. A

sinistra abbiamo due blocchi A e C uno sopra l’altro, a destra un blocco B. Questo stato si

può descrivere così: Block(A), Block(B), Block(C),

On(A, Table), On(B, Table), On(C, A),

Clear(B), Clear(C),

HandEmpty

Il significato è intuitivo: A, B, C sono blocchi, A e B sono sul tavolo, C è sopra A, B e C non

hanno nessun blocco sopra e il braccio robotico è vuoto. Vedi che i letterali sono tutti

positivi, non ci sono funzioni, non ci sono variabili e immagina che tutte le regole siano

unite in AND, come succede con la KB. Nota che non si danno informazioni del tipo che B

si trova a destra, o che un blocco è alto 50 cm. Abbiamo detto solo se un blocco è sopra

l’altro o separato dagli altri. È da notare anche il fatto che questa conoscenza non è

completamente primitiva, ma parte di essa è derivabile da altre frasi: per esempio Clear(B)

si deduce dal fatto che non esiste una frase del tipo On(qualcosa, B). Prova come compito

ad aggiungere qualche regola per derivare la frase Clear(x). Comunque l’importante è che

Clear(B) e Clear(C) non sono primitivi, ma si ottengono da informazioni che conosciamo

già, come avevamo visto nelle lezioni precedenti: da un insieme di fatti e regole, derivi

nuovi fatti. Ma quando usiamo il planning, facciamo un’assunzione molto forte: il CLOSED

WORLD ASSUMPTION, ovvero assumiamo che ogni cosa che noi non diciamo

esplicitamente nella descrizione dello stato, è FALSO. Quindi ogni cosa che diciamo

esplicitamente nello stato è vera, tutto il resto è falso. Con questa assunzione non puoi

derivare niente: devi elencare tutto quello che ti serve.

Sappiamo quindi com’è fatto uno stato. Ora come rappresentiamo un GOAL? Come una

On(A, B) On(A,

congiunzione di letterali. Un goal può essere che è un solo letterale, oppure

B), On(B, C) not On(A, Table)

che ha due letterali, o anche quindi puoi mettere una

negazione. È importante sapere che stati e goal sono cose diverse: non è come all’inizio

del corso dove gli stati stessi possono essere goal. Infatti nell’esempio hai messo una

negazione, che negli stati non si può fare. I goal non sono stati nel senso che tanti stati

diversi possono essere goal: uno stato infatti soddisfa un goal se i letterali positivi del goal

sono contenuti nello stato e i letterali negativi del goal non sono contenuti nello stato.

Il PDDL (PLANNING DOMAIN DESCRIPTION LANGUAGE) è il linguaggio per descrivere

stati, goal e anche le azioni che vedremo nel planning. È un linguaggio strano, e ne

abbiamo abbastanza di linguaggi… si tratta di un linguaggio pensato per competizioni, e

ancora più strano è il fatto che ad ogni versione nuova a volte aggiunge cose, a volte le

toglie! Un sottoinsieme di PDDL è chiamato STRIPS, che NON ammette le negazioni nei

goal! Si può fare in PDDL ma non in STRIPS. Storicamente STRIPS è stato creato ai

primordi, quindi contiene le idee di base del planning e il primo robot è stato programmato

con questo linguaggio. Si chiama Shaking e aveva una fotocamera ANALOGICA! Non

aveva foto fatte di pixel, ma in segnali analogici e li doveva analizzare in tempo reale per

trovare gli ostacoli mentre si muoveva… pazzesco

Comunque, abbiamo una descrizione per gli stati e per i goal e sappiamo se uno stato

soddisfa un goal. Quello che manca è il passaggio da uno stato all’altro, cioè le AZIONI.

Come sono descritte? È la parte più interessante… Le azioni sono descritte anch’esse con

formule logiche. Partiamo da qualche esempio per descriverle.

OnStack(x, y)

P: HandEmpty, Block(x), Block(y), Clear(x), On(x, y)

E: not HandEmpty, not Clear(x), Holding(x), not On(x, y), Clear(y)

Un’azione è composta da due liste: la prima è chiamata lista di PRECONDIZIONI, la

seconda è la lista degli EFFETTI. Le precondizioni sono le cose che devono essere vere

prima dell’applicazione della regola, mentre gli effetti indicano la situazione dopo

l’applicazione dell’azione. Ma questa qui sopra non è un’azione, bensì una ACTION

SCHEMA. Le action schema definiscono implicitamente un grande numero di azioni, in

base a come le variabili x e y sono istanziate. Quella è la descrizione di un insieme di

OnStack(A, B) OnStack(C, A)

azioni. Una vera azione è per esempio oppure

Si capisce che istanziare un’azione significa passare dei parametri ad una action schema.

Le precondizioni dicono se un’azione è applicabile ad un certo stato. Dato uno stato s e

un’azione a, l’azione a è applicabile in s se tutte le precondizioni di a sono soddisfatte in s.

Per soddisfatte si intende la stessa cosa dei goal: i letterali positivi devono apparire nello

stato, mentre quelli negativi non devono apparire (ah ma non so se possono esistere

precondizioni negative, sopra non compaiono). Come si definisce poi lo stato a seguito

dell’applicazione dell’azione? Lo stato iniziale viene copiato così com’è, poi elimino le

formule che sono negate negli effetti dell’azione e infine aggiungo le formule che sono

positive negli effetti dell’azione. Tutto quanto non è che un semplice operare con gli

insiemi: controllare se degli elementi sono nell’insieme, togliere elementi, aggiungere

elementi. Usi la logica, ma nell’implementazione esegui operazioni con gli insiemi, che

sono molto semplici.

Come è intuitivo, con STRIPS le precondizioni delle azioni contengono solo letterali

positivi. Con PDDL le precondizioni possono essere negative, quindi un’azione è

applicabile se i letterali negativi non compaiono in uno stato. Negli effetti i letterali possono

essere sempre negativi, perché si tratta di eliminarli. La negazione degli effetti ha un

significato ben diverso da quella delle precondizioni.

È interessante il fatto che finora nel corso non abbiamo descritto molto le azioni: sono

sempre state o operazioni atomiche o effettive operazioni come la scelta di una variabile e

l’assegnamento. Qui invece anche le azioni hanno una descrizione fatta con la logica e

rappresentano come modifichiamo il mondo!

Ora mostriamo un esempio famoso: il FRAME PROBLEM

Quando hai un insieme di formule logiche, queste sono relative ad un istante temporale.

Sono vere in un certo istante. Poi osservi il mondo un secondo dopo e avrai un altro

insieme di formule logiche e vai avanti così ogni secondo. Se devi rappresentare le

transizioni da un fotogramma all’altro in formule logiche, è un casino: devi incorporare

nelle frasi il tempo in una qualche variabile. O meglio in ogni predicato devi aggiungere la

variabile temporale per dire che qualcosa è vero in un certo istante temporale, a parte nei

pochi casi in cui qualcosa è sempre vero. Se devi esprimere i fotogrammi con la logica


ACQUISTATO

1 volte

PAGINE

42

PESO

792.38 KB

AUTORE

fiorixf2

PUBBLICATO

8 mesi fa


DESCRIZIONE APPUNTO

Appunti completi del corso Artificial Intelligence tenuto dal prof Francesco Amigoni al Politecnico di Milano. Argomenti trattati:
- Agenti goal-based
- Formulazione di un problema di ricerca di una soluzione
- Strategie di ricerca uninformed e informed
- Ricerca avversaria (algoritmi Minimax e Montecarlo)
- Problemi di soddisfacimento di vincoli
- Inferenza con la logica
- Planning


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica (COMO - CREMONA - MILANO)
SSD:
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher fiorixf2 di informazioni apprese con la frequenza delle lezioni di Intelligenza artificiale e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Politecnico di Milano - Polimi o del prof Amigoni Francesco.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in ingegneria informatica (como - cremona - milano)

Robotica - Elementi introduttivi
Dispensa
Controllo di posizione e velocità
Dispensa
Formulario Elettrotecnica
Appunto
Dinamica dei robot
Dispensa