Ingegneria della conoscenza e sistemi esperti Dario Bianchi, 1999 Risoluzione di problemi e ricerca.

Ingegneria della conoscenza e sistemi esperti Dario Bianchi , 1999

Risoluzione di problemi

e

ricerca



Un semplice agente risolutore di problemi



Un esempio: vacanza in Romania.

Attualmente in Arad. L’aereo parte domani da Bucarest.

Formulare un goal:

esssere in Bucarest

Formulare un problema:

stati: varie città

operatori: guidare da una città all’altra

Trovare una soluzione:

sequenza di città, es: Arad, Sibiu, Faragas, Bucarest



Il mondo dell’aspirapolvere

Tipi di problemi:

Stato Singolo : {5}

Stato Multiplo: {1,2,3,4,5,7,8}

destra produce {2,4,6,8}

Contingenza: {5}

Aspirare dove non c’è polvere può produrre dello sporco

È necessario un sensoreAzioni: destra, sinistra, aspira



Formulazione di un problema a singolo stato:

stato iniziale: essere “in Arad”

operatori: Arad -> Zerind, Arad -> Sibiu etc.

La funzione successore S fa passare dallo stato x agli stati S(x).

L’insieme degli stgati raggiungibili definisce lo spazio degli stati.

test obiettivo:

esplicito: “in Bucarest”

implicito: “NonSporco(x)”

costo del cammino: es. Somma delle distanze, numero di operatori applicati, etc.

soluzione: una sequenza di operatori che porta da uno stato iniziale

a uno stato obiettivo.



Una tipica istanza del rompicapo dell’8

Stati: uno stato specifica la posizione di ciascuna delle 8 tessere.Operatori: lo spazio vuoto si muove a destra, a sinistra, sopra, sotto.Test obiettivo: lo stato rispecchia la configurazione obiettivo (Goal).Costo del cammino: ciascun passo costa 1. Il costo del camminocoincide con la sua lunghezza.



Stati: qualsiasi configurazione da 0 a 8 regine sulla scacchiera.

Operatori: aggiungi una regina in qualsiasi quadrato

Test obiettivo: 8 regine sulla scacchiera, nessuna minacciata.

Costo cammino: 0.

Il problema delle 8 regine



Mondo dell’aspirapolvere (singolo stato).

Stati: uno degli 8 stati della figura.

Operatori: spostati a destra, spostati a sinistra, aspira.

Test obiettivo: non lasciare alcuna sporcizia nei quadrati.

Costo del cammino: ciascuna azione costa 1.

Risolvere il problema da uno stato di partenza comporta seguire le frecce nel diagramma degli stati fino a uno statoi obiettivo.



Mondo dell’aspirapolvere (stato multiplo).

In ogni istante l’apirapolvere si

trovain uno stato di un insieme ma

non sa quale stato dell’insieme è.

Stati: sottoinsiemi degli stati 1-8 della figura.

Operatori: spostati a destra, spostati a sinistra, aspira.

Test obiettivo: tutti gli stati dell’insieme degli stati non contengono sporcizia.

Costo del cammino: ciascuna azione costa 1.

Una soluzione del problema è una qualsiasi sequenza che porti dall’insieme iniziale degli stati ad un insieme di stati senza sporcizia.


Risoluzione di problemiCercare soluzioni

Generare sequenze di azioni.

Espansione: si parte da uno stato e apllicando gli operatori (o la funzione

successore) si generano nuovi stati.

Strategia di ricerca: ad ogni passo scegliere qiale stato espandere.

Albero di ricerca: rappresenta l’espansione degli stati a partire dallo stato

iniziale (la radice dell’albero). Le fogle dell’albero rappresentano gli stati da

espandere.


Risoluzione di problemiCercare soluzioni

Strutture dati per l’ albero di ricerca (struttura di un nodo).

•Lo stato nello spazio degli stati a cui il nodo corrisponde.

•Il nodo genitore.

•L’operatore che è stato applicato per ottenere il nodo.

•La profondità del nodo.

•Il costo del cammino dallo stato iniziale al nodo



Albero di ricerca parziale per trovare un itinerario da Arad a Bucarest.



L’algoritmo generale di ricerca



L’algoritmo generale di ricerca

Tramite l’argomento Queuing-Fn viene passata una funzione per accodare i nodi ottenuti dall’espansione



Strategie di ricercaUna strategia di ricerca è un ordine di espansione dei nodi.

Completezza: la strategia garantisce di trovare una soluzione quando ne esiste una?

Complessità temporale: quanto tempo ci vuole per trovare una soluzione?

Complessità spaziale: quanta memoria occorre per effettuare una ricerca?

Ottimalità: la strategia trova una soluzione ottima (a costo minimo) quando ci sono varie soluzioni differenti?

La complessità temporale e spaziale è misurata in termini di:

b - massimo fattore di diramazione dell’albero di ricerca

d - profondità della soluzione a costo minimo

m - massima profondità dello spazio degli stati (può essere infinita)



Ricerca in ampiezza

QueueingFn = metti i successori alla fine della coda



Ricerca in ampiezza

Lo svantaggio principale è l’eccessiva occupazione di memoria. Nell’esempio si suppone che il fattore di ramificazione sia b=10. Si espandono 1000 nodi/secondo. Ogni nodo occupa 100 byte di memoria.



Ricerca a costo uniformeciascun nodo è etichettato con il costo g(n)

QueueingFn = inserisci i successori in ordine di costo di cammino crescente



Ricerca in profonditàsi assume che i nodi di profondità 3 non abbiano successori

QueueingFn = inserisci i successori all’inizio della coda.



Ricerca con limite di profondità

Si scende lungo un ramo finchè non si trova la soluzione o si raggiunge il limite di profondità.

Si evita di scendere lungo rami infiniti.



Ricerca con approfondimento iterativo



Ricerca bidirezionale



Confronto fra le strategie di ricerca

b = fattore di ramificazione; d = profondià della soluzione; m=profondità massima dell’albero di ricerca; l=limite di profondità.



Evitare ripetizioni di stati

Uno spazio degli stati che genera un albero di ricerca esponenziale . Il lato sinistro mostra lo spazio degli stati, nel quale ci sono due azioni possibili che conducono da A a B, due da B a C e così via. Il lato destro mostra l`albero di ricerca corrispondente.



Metodi di ricerca informati

usano conoscenza specifica relativa al problema

Ricerca Best First

Usa una funzione di valutazione che calcola un numero che rappresenta la desiderabilità relativa all’espansione di nodo.

Best-first significa scegliere come nodo da espandere quello che sembra più desiderabile.

QueuingFn = inserisce I successori in ordine decrescente di desiderabilità.

Casi particolari:

•ricerca greedy (golosa)

•ricerca A*



Una realizzazione della ricerca best-first che usa l’algoritmo

di ricerca generale e la funzione di valutazione EvalFn



Mappa della Romania con distanze stradali e distanze in linea d’aria da Bucarest



Ricerca greedy (golosa)

Funzione di valutazione h(n) (heuristic)

= stima del costo dal nodo n al goal.

Es. h(n) = distanza in linea d’aria fra n e Bucarest.

La ricerca golosa espande quel nodo che sembra essere il più vicino all’obiettivo (goal).



Stadi di una ricerca golosa per Bucarest usando come funzione di valutazione la distanza in linea d’aria. I nodi sono etichettati con i valori di h



Ricerca A*

Evita di espandere quei cammini che sono già costosi.

Funzione di valutazione f(n) = g(n) + h(n)

g(n) = costo effettivo dalla radice al nodo n

h(n) = costo stimato dal nodo n al nodo obiettivo (goal)

f(n) = costo totale stimato di un cammino che arriva al goal passando per n

La ricerca A* usa una euristica ammissibile cioè:

h(n) <= h*(n) dove h*(n) è il vero costo da n al goal.

(Nel nostro esempio la distanza in linea d’aria non svrastima mai l’effettiva distanza stradale)

Teorema: la ricerca A* è ottimale (e completa)



Stadi di una ricerca A* per Bucarest usando come funzione di valutazione

f = g + h ( h è la distanza in linea d’aria per Bucarest).



Ottimalità di A*

Mappa della Romania che mostra le frontiere f=380, f=400, f=420, con Arad come stato iniziale. I nodi dentro una frontiera hanno valori più bassi del valore della frontiera.



Funzioni euristiche

E’possibile definire differenti funzioni euristiche. Ad esempio:

h1= numero di tessere che sono fuori posto (h1= 7)

h2= la somma delle distanze dalle posizioni che le tessere devono assumere nella configurazione obiettivo. La distanza è una somma delle distanze orizzontali e verticali (distanza di Manhattan). Le tessere da 1 a 8 nello stato iniziale danno una distanza h2= 2+3+3+2+4+2+0+2 = 18



Confronto fra la ricerca ad approfondimento iterativo

e l’algoritmo A* con h1 e h2

Ingegneria della conoscenza e sistemi esperti Dario Bianchi, 1999 Risoluzione di problemi e ricerca.

Documents

Transcript of Ingegneria della conoscenza e sistemi esperti Dario Bianchi, 1999 Risoluzione di problemi e ricerca.