Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

Spazio degli stati

Possiamo rappresentare un generico stato del problema del lupo,

capra e cavoli in questo modo:

Φ, Φ]

[robot,

des = capra,

Φ,

[Φ,

sin = lupo, cavolo]

1 2 3

4 5 6 7

8 9 10 11

12 13 14 15

Terzo caso: verrà trattato nel Planning.

G. Paronitti - Risoluzione automatica dei problemi 13

Stato iniziale e stato finale

Possiamo rappresentare lo stato iniziale e finale del problema del

lupo, capra e cavoli in questo modo:

[robot,

des = lupo, capra, cavolo]

in Φ, Φ, Φ]

[Φ,

sin =

in Φ, Φ, Φ]

[Φ,

des =

fin [robot,

sin = lupo, capra, cavolo]

fin 0 2 1 3 0 1 2 3

4 5 10 7 4 5 6 7

Il gioco del 15: 15 9 6 13 8 9 10 11

12 11 14 8 12 13 14 15

G. Paronitti - Risoluzione automatica dei problemi 14

Operatori elementari azioni

Chiamiamo le singole che un agente artificiale

è capace di compiere. Combinando le azioni elementari in

un’opportuna sequenza, un agente è in grado di risolvere problemi

operatori.

più complessi. Le azioni si dicono anche

Caso del lupo, capra, cavolo e robot

traghetta(oggetto) Φ

oggetto = lupo, capra, cavolo,

Il gioco del 15

sposta(tessera, direzione)

tessera = 1≤n≤15;

direzione = destra, sinistra, sopra, sotto;

G. Paronitti - Risoluzione automatica dei problemi 15

Successori

Non tutti gli operatori sono eseguibili in tutti gli stati.

successore

è un di uno stato se è ottenuto da mediante

s’ s, s’ s

uno degli operatori applicabili ad s

Esercizi: individuare due operatori applicabili e due non applicabili ai

casi seguenti.

Caso del lupo, capra, cavolo e robot

Φ, Φ]

[robot,

des = capra,

Φ,

[Φ,

sin = lupo, cavolo]

1 15 5 11

12 2 4 10

Il gioco del 15: 14 3 0 6

13 9 8 7

G. Paronitti - Risoluzione automatica dei problemi 16

Definizioni

Lo spazio degli stati è l’insieme di tutti gli stati raggiungibili nel

corso del processo di soluzione. Uno stato è raggiungibile se può

essere ottenuto, a partire dallo stato iniziale, mediante l’applicazione

degli operatori a disposizione dell’agente.

Nello spazio degli stati, gli stati stessi sono rappresentati assieme

alla relazione tra essi: la relazione che lega due stati è l’azione che

determina il passaggio dall’uno all’altro.

Non è necessario uno stato finale unico. Ex. Scacchi

G. Paronitti - Risoluzione automatica dei problemi 17

Grafi nodes)

A graph is a set of objects called vertices (or connected by links

arcs)

called edges (or which can be directed (assigned a direction).

A graph is designed as a set of dots (the vertices) connected by lines (the

edges).

A graph structure can be extended by assigning a weight to each edge.

Another way to extend basic graphs is by making the edges to the graph

directed graph or digraph.

directional, technically called a network. A network can be

A digraph with weighted edges is called a

used to represent the state space of a specific problem.

(tratto da wikipedia)

G. Paronitti - Risoluzione automatica dei problemi 18

Grafi Orientati Terminologia

Un nodo X si dice di un

- successore

nodo Y se c’è un arco entrante in X e

proveniente da Y. Y è il predecessore

b di X

B

A Un tra due nodi X e Y di un

- cammino

grafo è una sequenza di nodi che

a inizia con X, termina con Y e in cui i

e nodi siano uno il successore

c dell’altro. Un cammino in cui X e Y

d

C D coincidano si chiama ciclo.

Tra due nodi di un grafo possono

- esserci nessuno, uno o più cammini.

f La di un cammino è data

- lunghezza

E dal numero di archi in esso contenuti

Un ciclo di lunghezza 1 si dice

- cappio

Un grafo diretto senza cicli si chiama

- grafo diretto aciclico (DAG)

G. Paronitti - Risoluzione automatica dei problemi 19

Grafo dell’esercizio

Costruire lo spazio degli stati per il problema del lupo, capra e cavolo.

Rappresentarlo in forma di grafo. E’ un DAG?

Abbiamo 10 stati:

s = [rb,lu,ca,cv,Φ,Φ,Φ,Φ]

1

s = [Φ,lu,Φ,cv,rb,Φ,ca,Φ]

2

s = [rb,lu,Φ,cv,Φ,Φ,ca,Φ]

3

s = [Φ,Φ,Φ,cv,rb,lu,ca,Φ]

4

s = [Φ,lu,Φ,Φ,rb,Φ,ca,cv]

5

s = [rb,Φ,ca,Φ,Φ,lu,Φ,cv]

6

s = [rb,lu,ca,Φ,Φ,Φ,Φ,cv]

7

s = [Φ,Φ,ca,Φ,rb,lu,Φ,cv]

8

s = [rb,Φ,ca,Φ,Φ,lu,Φ,cv]

9

s = [Φ,Φ,Φ,Φ,rb,lu,ca,cv]

10

G. Paronitti - Risoluzione automatica dei problemi 20

Grafo dell’esercizio s

1

Abbiamo 10 stati: t(ca)

s

2

s = [rb,lu,ca,cv,Φ,Φ,Φ,Φ]

1 t(Φ)

s = [Φ,lu,Φ,cv,rb,Φ,ca,Φ]

2 s

s s

s = [rb,lu,Φ,cv,Φ,Φ,ca,Φ] 3

4 5

t(cv)

t(lu)

3

s = [Φ,Φ,Φ,cv,rb,lu,ca,Φ] t(ca) t(ca)

4

s = [Φ,lu,Φ,Φ,rb,Φ,ca,cv] s S

5 6 7

s

8

s = [rb,Φ,ca,Φ,Φ,lu,Φ,cv] t(lu) t(cv)

6 t(Φ)

s = [rb,lu,ca,Φ,Φ,Φ,Φ,cv]

7 s

s = [Φ,Φ,ca,Φ,rb,lu,Φ,cv] 9

8

s = [rb,Φ,ca,Φ,Φ,lu,Φ,cv] t(ca)

9 s

s = [Φ,Φ,Φ,Φ,rb,lu,ca,cv] 10

10 Grafo dell’esercizio

G. Paronitti - Risoluzione automatica dei problemi 21

Cosa è una soluzione? s

Un problema è risolto quando abbiamo 1

raggiunto lo stato finale. t(ca)

s

2

Dunque la soluzione di un problema è un

particolare cammino nel grafo che t(Φ)

descrive il percorso dallo stato iniziale s

s s

3

allo stato finale. 4 5

t(cv)

t(lu)

t(ca) t(ca)

Vorremmo che l’agente artificiale s S

ottima

adottasse una soluzione cioè un 6 7

s

8

t(lu) t(cv)

certo cammino verso la soluzione t(Φ)

stabilito in base ad alcuni criteri. Ex. La

lunghezza, le risorse necessarie s

9

all’applicazione di un operatore, ecc. t(ca)

Es. evidenziare i cammini risolutivi e dire s

10

se rappresentano una soluzione ottima.

G. Paronitti - Risoluzione automatica dei problemi 22

Esercizio di ricapitolazione

Due recipienti sono rispettivamente di 4 e 3 litri, abbiamo a disposizione un

lavandino dove poterli riempire o vuotare. Come si possono ottenere esattamente

2 litri?

Descrivere: spazio degli stati, stato iniziale, stato finale, elenco degli operatori, la

parte dell’albero degli stati che contiene la soluzione.

op = (X<4) ‹4,Y› Riempi X

1 →

op = (Y<3) ‹X,3› Riempi Y

2 →

op = (X>0) ‹0,Y› Vuota X

3 →

op = (Y>0) ‹X,0› Vuota Y

4 →

op = (X+Y≥4)∧(Y>0) ‹4,Y-(4-X)› Travasa Y in X fino a riempire X

5 →

op = (X+Y≥3)∧(X>0) ‹X-(3-Y),3› Travasa X in Y fino a riempire Y

6 →

op = (X+Y≤4)∧(Y>0) ‹X+Y,0› Travasa Y in X fino a vuotare Y

7 →

op = (X+Y≤3)∧(X>0) ‹0,X+Y› Travasa X in Y fino a vuotare X

8 G. Paronitti - Risoluzione automatica dei problemi 23

Esercizio di ricapitolazione

Due recipienti sono rispettivamente di 4 e 3 litri, abbiamo a disposizione un

lavandino dove poterli riempire o vuotare. Come si possono ottenere esattamente

2 litri?

Descrivere: spazio degli stati, stato iniziale, stato finale, elenco degli operatori, la

parte dell’albero degli stati che contiene la soluzione.

0 , 0

0 , 3 4 , 0

3 , 0 4 , 3

3 , 3

4 , 2

0 , 2 2 , 0

G. Paronitti - Risoluzione automatica dei problemi 24

Titolo della slide

Anche altro modo (un passo più

lungo): 0 , 0

4 , 0

1 , 3 2 , 0

1 , 0

0 , 1

4 , 1 2 , 3

G. Paronitti - Risoluzione automatica dei problemi 25

Ricerca

Una ricerca è un attraversamento di un grafo: essa deve trovare un cammino che

va dal nodo iniziale a quello finale.

In linea di principio si potrebbe generare (per ogni problema che sia

rappresentabile tramite un grafo) il grafo di tutto lo spazio degli stati sfruttando in

ogni modo possibile gli operatori che definiscono le azioni a partire da un nodo

iniziale. Ma in genere, per economia computazionale, si fa diversamente, visto che

lo spazio degli stati è rappresentato implicitamente dalle regole di costruzione.

IN OGNI FASE DEL PROCESSO DI RICERCA DI UNA SOLUZIONE

VENGONO GENERATI ESPLICITAMENTE ED ESAMINATI SOLO ALCUNI

NODI.

TALE PROCEDURA E’ CHIAMATA GENERA-E-VERIFICA.

Così sono mantenuti i memoria solo quelle parti dello spazio degli stati che sono

ritenute interessanti per la soluzione.

In genere per implementare degli algoritmi di ricerca si utilizzano i cosidetti alberi

di ricerca G. Paronitti - Risoluzione automatica dei problemi 26

Alberi di ricerca

Un albero è un digrafo aciclico (DAG) in

cui un solo nodo non ha predecessori e

tutti gli altri ne hanno uno solo. A

B C D

E F I L

G H M N

Da ricordare: radice, figli, fratelli, foglie,

P

O rami, fattore di ramificazione.

Un albero è finito quando i suoi nodi

sono finiti. Altrimenti, un albero è

infinito (a) quando ha un ramo infinito,

(b) quando un suo nodo ha infiniti figli.

G. Paronitti - Risoluzione automatica dei problemi 27

Algoritmi di visita

Un algoritmo di visita di un albero è un algoritmo che attraversi tutti i suoi nodi una e una

sola volta.

Visita in ampiezza o a ventaglio (Breadth dalla radice tutti i figli e poi tutti i

First):

figli dei figli e cosi via fino all’esaurimento dell’albero.

La sequenza sarà: ABCDEFGHILMNOP.

Visita in profondità o a scandaglio (Depth dalla radice lungo tutto un ramo

First):

fino alla foglia. Si parte quindi dalla radice e se ne visita il primo figlio e poi il primo del

primo ecc. Poi si riparte dal fratello di livello più basso non visitato, e così via.

La sequenza sarà: ABEFOPGCHIDLMN A

B C D

E F I L

G H M N

P

O G. Paronitti - Risoluzione automatica dei problemi 28

Grafi e Alberi

Un nodo di un albero di ricerca contiene almeno le seguenti informazioni:

1. La rappresentazione dello stato associato ad esso;

2. Un arco che lo collega al padre;

3. L’operatore applicato per raggiungerlo;

4. Un arco che lo collega ai suoi figli che sono già stati generati;

5. L’elenco degli operatori che sono ancora applicabili allo stato a esso associato;

6. Un valore che indica il costo del cammino che porta dalla radice a quel nodo.

Il nodo di un albero rispetto a quello di un grafo contiene molta più informazione.

Uno stato compare nel grafo che rappresenta lo spazio degli stati una sola volta,

uno stesso stato può invece comparire molte volte nei vari nodi di un albero di

ricerca. G. Paronitti - Risoluzione automatica dei problemi 29


PAGINE

38

PESO

720.44 KB

AUTORE

Atreyu

PUBBLICATO

+1 anno fa


DESCRIZIONE DISPENSA

Questa dispensa si riferisce alle lezioni di Filosofia della scienza, tenute dal Prof. Roberto Cordeschi nell'anno accademico 2010 e tratta i seguenti argomenti:
[list]
Risoluzione automatica dei problemi;
Robot e Softbot;
Astrazione;
Stato iniziale e stato finale;
Operatori;
Grafi.
[/list]


DETTAGLI
Corso di laurea: Corso di laurea in filosofia
SSD:
A.A.: 2010-2011

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Atreyu di informazioni apprese con la frequenza delle lezioni di Filosofia della scienza e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università La Sapienza - Uniroma1 o del prof Cordeschi Roberto.

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 Filosofia della scienza

Macchine di Turing
Dispensa
Logica
Dispensa
Logica e rappresentazione della conoscenza
Dispensa
Modelli ad agenti
Dispensa