Sistemi basati su conoscenza
Ricerca di soluzioni a problemi
Prof. M.T. PAZIENZA
a.a. 2001-2002
Agente risolutore di problemi
(basato su obiettivi)
PROBLEMA
Obiettivo + Mezzi per raggiungere l’obiettivo
RICERCA
Processo di esplorazione
Cosa possono fare i mezzi a disposizione
Agente risolutore di problemi
(basato su obiettivi)
Gli obiettivi aiutano l’agente ad organizzare il
comportamento limitando gli scopi che l’agente
sta cercando di raggiungere.
Un obiettivo è l’ insieme degli stati del mondo in
cui è soddisfatto l’obiettivo stesso.
Le azioni sono causa di transizioni tra stati del mondo.
L’agente deve scegliere una sequenza di azioni (tra tutte
quelle possibili) che lo conduce ad uno stato obiettivo.
Agente risolutore di problemi
(basato su obiettivi)
Formulazione dell’obiettivo
(basata sulla situazione attuale)
Formulazione del problema
(processo di decisione di quali azioni e stati della
risoluzione del problema considerare,
susseguentemente alla formulazione dell’obiettivo)
Agente risolutore di problemi
(basato su obiettivi)
Ove esistono più alternative (sequenze di azioni
che raggiungono l’obiettivo), l’agente
Se non conosce lo stato risultante dopo aver
compiuto ciascuna azione, né altre informazioni
addizionali, potrà solo scegliere a caso
Se possiede informazioni sugli stati nei quali
potrebbe portarsi e sulle azioni che potrebbe
compiere, userà queste informazioni per
scegliere la sequenza di azioni da intraprendere.
Ricerca
Ricerca è il processo per l’individuazione / scelta della
migliore sequenza di azioni che conducono a stati di
esito conosciuto effettuata da parte di un agente che
abbia diverse opzioni immediate di esito sconosciuto
La soluzione di un problema proposta da un algoritmo di
ricerca è quella sequenza di azioni individuata a fronte
di un particolare input
L’esecuzione coincide con la realizzazione delle azioni
suggerite dalla soluzione
Agente risolutore di problemi
(basato su obiettivi)
Formulato un obiettivo ed un problema da
risolvere, l’agente attiva una procedura di
ricerca per risolverlo, quindi usa la
soluzione per guidare le proprie azioni
Eseguita la soluzione, l’agente individuerà un
nuovo obiettivo
Agente di ricerca
• Formulazione dell’obiettivo (basata sulla situazione
attuale). Obiettivo = Insieme degli stati del mondo
che soddisfano l’obiettivo
• Formulazione del problema (processo di scelta di
azioni e stati da considerare)
• Ricerca (esaminare differenti sequenze di possibili
azioni e poi scegliere la migliore
• Esecuzione della sequenza di azioni
Algoritmo di risoluzione / ricerca
1. INPUT = problema
2. OUTPUT = soluzione nella forma di sequenze
di azioni
3. ESECUZIONE =
realizzazione/implementazione delle sequenze di
azioni
Agente risolutore di problemi
Soluzione di problema offline; una soluzione di
problema online richiede l’agire senza una completa
conoscenza del problema e della soluzione
Processo di formulazione di
problemi
Conoscenza che l’agente ha sulle sue azioni e
sugli stati
Ciò dipende da come l’agente è connesso al suo
ambiente, attraverso le percezioni e le azioni.
Quindi elementi fondamentali nella definizione
di un problema sono gli stati e le azioni
Formulazione di problemi
Spazio degli stati del problema ( insieme di tutti gli
stati raggiungibili dallo stato iniziale attraverso
qualsiasi sequenza di azioni) (operatore / funzione
successore S)
Un cammino nello spazio degli stati è una qualsiasi
sequenza di azioni che conduce da uno stato ad un
altro (costo di cammino g)
Il test obiettivo è applicato dall’agente alla
descrizione di un singolo stato per determinare se
è in uno stato obiettivo.
Formulazione di problemi
L’output di un algoritmo di ricerca è una
soluzione, ovvero un cammino dallo stato
iniziale allo stato che soddisfa il test
obiettivo
Algoritmo generale di Ricerca
Dato un problema, una strategia ed un insieme di candidati
Ripeti fino ad esaurimento dei candidati:
Se non esistono candidati da espandere,
Allora non c’è soluzione al problema
Altrimenti scegli un nodo foglia da espandere
secondo strategia
Se il nodo contiene stato obiettivo soluzione trovata
Altrimenti espandi nodo secondo strategia
Aggiungi all’albero di ricerca i nodi risultanti
Struttura dati di un Nodo
datatype NODO
components: STATO, NODO-GENITORE, OPER.,
PROFONDITA’, COSTO-CAMMINO
Evitare ripetizioni di stati:
Non ritornare allo stato da cui si proviene
(NO successore=padre)
Non creare cammini che abbiano cicli
(NO successore=antenato)
Non generare nessuno stato già generato prima
(NO successore=any prima)
Conoscenza e Tipi di problemi
• Problemi a stato singolo (deterministico,
accessibile)
• Problemi a stati multipli (deterministico,
inaccessibile)
• Problemi di contingenza (nondeterministico,
inaccessibile)
• Problemi di esplorazione (spazio degli stati
sconosciuto)
Conoscenza e Tipi di problemi
• Problemi a stato singolo (mondo accessibile, conoscenza
effetto delle azioni, quindi agente può calcolare lo stato
dopo la sequenza delle azioni)
• Problemi a stati multipli (mondo non accessibile,
conoscenza effetto delle azioni, agente ragiona su insiemi di
stati raggiungibili dopo la sequenza di azioni)
• Problemi di contingenza (ignoranza dell’agente sulla
sequenza di azioni, quindi definizione alberi di azioni =
pianificazione)
• Problemi di esplorazione (nessuna conoscenza sugli effetti
delle proprie azioni, attraverso la sperimentazione scoprire
gradualmente effetti delle azioni e stati esistenti)
Problemi a stato singolo
Caso più semplice
Agente riceve dai sensori informazioni sufficienti
sullo stato in cui si trova (mondo accessibile) e
Conosce esattamente le conseguenze di ciascuna
azione
Quindi l’agente può calcolare esattamente in quale
stato sarà dopo qualsiasi sequenza di azioni
Formulazione di problemi
a stato singolo
Un tale problema è definito da 4 caratteristiche:
1.
2.
3.
4.
Stato iniziale
Operatore / funzione successore S(x)
Test obiettivo
Funzione costo cammino
Una soluzione è una sequenza di operatori che
conducono dallo stato iniziale ad uno stato obiettivo
Problemi a stati multipli
L’agente conosce tutti gli effetti delle sue azioni, ma
Ha un accesso limitato allo stato del mondo (per
esempio può non avere sensori – sa solo che il suo
stato iniziale appartiene all’insieme degli stati)
L’agente deve ragionare su insiemi di stati in cui
potrebbe giungere invece che su stati singoli, in
quanto il mondo non è completamente accessibile
Formulazione di problemi
a stati multipli
Un tale problema è definito da 4 caratteristiche:
1. Insieme di stati iniziali
2. Insieme di operatori / funzione successore S(x) (per
ciascuna azione viene specificato l’insieme di stati
raggiunti da qualsiasi stato considerato. Un cammino
collega insiemi di stati)
3. Test obiettivo
4. Funzione costo cammino
Una soluzione è un cammino che conduce ad un insieme
di stati che sono tutti stati obiettivo.
Spazio dell’insieme di stati
Problemi di contingenza
pianificazione
Talvolta l’ignoranza impedisce all’agente di trovare
una sequenza di azioni che garantisca di arrivare
alla soluzione
Capacità di rilevamento durante la fase di esecuzione
L’agente deve calcolare un intero albero di azioni
piuttosto che una singola sequenza di azioni (un
ramo dell’albero tratta una situazione contingente
possibile che si potrebbe verificare)
Nel mondo reale si incontrano molti problemi di
contingenza poiché la predizione esatta è
impossibile
Problemi di contingenza
pianificazione
Necessari algoritmi complessi
L’agente può agire prima di aver trovato un
piano garantito (comincia effettivamente
l’esecuzione e vede quali soluzioni
contingenti si verificano veramente)
Date le informazioni supplementari l’agente
può poi continuare a risolvere il problema
Problemi di esplorazione
L’agente non ha alcuna informazioni sugli effetti
delle proprie azioni
L’agente deve sperimentare scoprendo gradualmente
cosa produrranno le sue azioni e quali tipi di stati
esistono.
La ricerca si svolge nel mondo reale e non in un
modello: agire può comportare danni significativi
per un agente privo di conoscenza
Se sopravvive, acquisisce conoscenza che può
riusare per problemi successivi
Efficacia della ricerca
Misura dell’efficacia
1. Si trova almeno una soluzione?
2. E’ una buona soluzione (con un costo di
cammino basso)?
3. Qual è il costo della ricerca associato al tempo ed
alla memoria richiesti per trovare una soluzione?
Costo totale = costo di cammino + costo di
ricerca
Costo della ricerca
L’agente deve decidere quali risorse dedicare alla
ricerca e quali all’esecuzione.
Per spazi degli stati piccoli, si considera il costo di
cammino più basso
Per problemi complessi trovare punto di equilibrio
(l’agente può cercare per un tempo molto lungo di
ottenere una soluzione ottimale, oppure può
cercare per un tempo più breve ed ottenere una
soluzione con costo di cammino lievemente
maggiore)
Risoluzione di problemi
Decidere cosa inserire nella descrizione degli stati e degli
operatori e cosa tralasciare (rappresentazione)
Il processo di eliminare dettagli da una rappresentazione
viene chiamato astrazione (astrazione nella descrizione
dello stato e delle azioni)
Una buona astrazione comporta l’eliminazione di più
dettagli possibili mantenendo la validità ed assicurando
che le azioni astratte siano facili da realizzare
Classi di problemi
Problemi giocattolo
(Rompicapo dell’8 – Mondo dell’aspirapolvere)
Problemi del mondo reale
(Ricerca di itinerario)
Rompicapo dell’8
Operatore: la tessera vuota cambia posto con
la tessera alla sua sinistra
Rompicapo dell’8
Formulazione del problema
Stati: specifica della posizione di ciascuna
delle 8 tessere + tessera vuota
Operatori: muovere la tessera vuota a sinistra,
destra, sopra, sotto (nessun salto ammesso)
Test obiettivo: verifica della configurazione
finale
Costo di cammino: ciascun passo costa 1
(costo del cammino = lunghezza del
cammino)
Mondo dell’aspirapolvere
Spazio degli stati
Archi/azioni: L=spostati a sn, R=spostati a dx,
S=aspira
Mondo dell’aspirapolvere
semplificato
Agente conosce la propria posizione e le posizioni
di tutte le parti con sporcizia; aspira bene.
Stati: uno degli stati di figura
Operatori: spostati a sn, spostati a dx, aspira
Test obiettivo: non lasciare sporcizia nei quadrati
Costo di cammino: ciascuna azione costa 1
Soluzione: da un qualsiasi stato di partenza seguire
le frecce fino ad uno stato obiettivo
Mondo dell’aspirapolvere senza sensori
In qualsiasi istante l’agente si trova in un insieme di
stati ma non sa in quale stato di quell’insieme sia
Mondo dell’aspirapolvere senza sensori
L’aspirapolvere non ha alcun sensore e deve
raccogliere tutta la sporcizia
Insiemi di stati: sottoinsiemi di stati della figura
Operatori: spostati a sn, spostati a dx, aspira
Test obiettivo: ogni stato dell’insieme degli stati
non contiene sporcizia
Costo di cammino: ciascuna azione costa 1
Soluzione: dall’insieme iniziale degli stati (tutti)
seguire le frecce fino a raggiungere un insieme
di stati senza sporcizia
Strategia di ricerca
Criteri di valutazione della strategia :
• Completezza (se esiste una soluzione viene
trovata sempre)
• Complessità temporale
• Complessità spaziale
• Ottimalità
Strategie di ricerca
1. Ricerca non informata ( o cieca)
Non si ha alcuna informazione sul numero di
passi o sul costo di cammino dallo stato
attuale all’obiettivo
1. Ricerca informata ( euristica)
Si hanno informazioni di preferenze tra gli stati
Ricerca informata più efficace di quella non
informata
Ricerca in ampiezza
• Tutti i nodi di profondità d nell’albero si
espandono prima dei nodi di profondità d+1
• Strategia sistematica (esaminati prima i
cammini di lunghezza i, poi i+1,poi i+2,…)
Ricerca in ampiezza
Se esiste una sola soluzione, la ricerca in
ampiezza la trova
Se esistono più soluzioni, viene trovato per
prima lo stato obiettivo più alto (quindi a
costo minimo)
Valutazione: ricerca completa ed ottimale
Ricerca in ampiezza
Se esiste una sola soluzione, la ricerca in
ampiezza la trova
Se esistono più soluzioni, viene trovato per
prima lo stato obiettivo più alto (quindi a
costo minimo)
Valutazione: ricerca completa ed ottimale
Ricerca in ampiezza
Se fattore di ramificazione = b
al livello i si avrà ramificazione = b i
Se la soluzione si trova dopo un cammino di
lunghezza d, il numero massimo (soluzione
peggiore) di nodi espansi è
1  b  b  b  ...  (b  1)  O(b )
2
3
d
d
(l’obiettivo non viene espanso)
Ricerca in ampiezza
Complessità spaziale coincide con complessità
temporale perché tutti i nodi foglia dell’albero
di ricerca devono essere mantenuti in memoria
contemporaneamente
Ricerca a costo uniforme
La ricerca a costo uniforme trova gli obiettivi più
superficiali.
Modifica la strategia in ampiezza espandendo
sempre il nodo sul confine con il costo più basso
(misurato con il costo del cammino g(n)),
invece del nodo di profondità minima
La prima soluzione trovata è quella più
conveniente
Ricerca a costo uniforme
• Si trova sempre la soluzione più economica
se si verifica che il costo del cammino non
decresce mai quando lo percorriamo.
g ( Successore (n))  g (n)
• Il costo del cammino di un nodo è somma
dei costi degli operatori che determinano il
cammino
Ricerca a costo uniforme
Ricerca in profondità
• La ricerca in profondità espande sempre il
primo dei nodi al livello più profondo
dell’albero.
• La ricerca torna indietro ed espande nodi a
livelli più superficiali solo quando arriva ad
un nodo foglia non obiettivo.
• La funzione di ricerca userà un meccanismo
di inserimento in un pila
Ricerca in profondità
Ricerca in profondità
• Occupazione di memoria modesta (memorizza un
solo cammino dalla radice al nodo foglia, oltre ai
nodi fratelli di ciascun nodo del cammino che
rimangono non espansi)
• Con uno spazio degli stati con fattore di
ramificazione b e profondità massima m, la ricerca
in profondità memorizza bm nodi
• Complessità temporale della ricerca in profondità
è O(b m )
• La ricerca in profondità può rimanere bloccata in
un cammino sbagliato di lunghezza infinita.
• Valutazione: né completa, né ottimale
Ricerca a profondità limitata
Si impone un taglio/limite alla profondità
massima di un cammino (se si conosce bene
il problema)
Suggerimento:
Taglio=profondità obiettivo più superficiale
Ricerca bidirezionale
La ricerca bidirezionale ricerca contemporaneamente
sia in avanti, dallo stato iniziale, sia all’indietro,
dall’obiettivo, fermandosi quando le due ricerche
si incontrano.
Con fattore di ramificazione pari a b in entrambe le
direzioni e soluzione a profondità d, allora la
soluzione verrà trovata in O(2b d / 2 )  O(b d / 2 )
Ricerca bidirezionale
Ricerca bidirezionale
• Problemi:
• Definire predecessori di un nodo n (quei
nodi che abbiano n come successore)
• Gli operatori in genere non sono reversibili,
per cui il calcolo dei predecessori in genere
risulta complesso.
• Cosa succede quando si hanno più stati
obiettivo?
Ripetizioni di stati
• Si possono semplificare alberi di ricerca
infiniti dovuti a ripetizioni di stati,
generando solo la porzione di albero che
ricopre il grafo dello spazio degli stati.
• Evitare riduzioni di stati può generare una
riduzione esponenziale del costo di ricerca.
Ripetizioni di stati
Suggerimenti:
• Non ritornare allo stato da cui si proviene
• Non creare cammini che abbiano cicli
• Non generare alcuno stato già generato
prima