Ricerca di soluzioni a problemi
Prof. M.T. PAZIENZA
a.a. 2014-2015
Agenti reattivi
Gli agenti reattivi non possono operare bene in
ambienti ove la
corrispondenza tra stati ed azioni diventa troppo
grande per essere memorizzata e troppo
complessa da apprendere.
Agenti basati su obiettivi
Conoscere lo stato attuale dell’ambiente non
sempre è sufficiente per decidere cosa fare
Bisogna avere un obiettivo
Ricerca di una soluzione al problema
Pianificazione
Agenti risolutore di problemi
(agente basato su obiettivi)
L’agente risolutore di problemi è un tipo
particolare di agente basato su obiettivi;
decide cosa fare ricercando sequenze di azioni
che conducono a stati desiderabili: gli obiettivi
aiutano a selezionare le sequenze.
Quindi cerca di massimizzare la misura delle
prestazioni
Formulazione di un problema
Processo che porta a decidere, dato un
obiettivo, quali azioni e stati considerare.
Ricerca di una soluzione
La ricerca è l’enumerazione di un insieme di potenziali
soluzioni parziali di un problema che possono essere
testate per identificare quelle che sono soluzioni reali o
che potrebbero condurre a soluzioni reali del problema.
Per sviluppare una ricerca è necessario definire:
• una soluzione potenziale
• un metodo chiaro per la generazione di soluzioni
potenziali
• un metodo per verificare quale soluzione potenziale
costituisca una soluzione reale
Ricerca di una soluzione
Il meccanismo generale della ricerca si può
esprimere in termini di ricerca di cammini
in un grafo
Per risolvere un problema si deve esplicitare il
sottostante spazio di ricerca ed applicare a
tale spazio un algoritmo di ricerca
Ricerca di una soluzione
Gli umani usano spesso l’intuizione per risolvere
problemi di difficile soluzione; ciò porta a
ricercare soluzioni ad hoc e non generali.
Analogamente un agente potrebbe accedere a
conoscenza specifica per trovare una soluzione.
Tale conoscenza extra al di là dello spazio di
ricerca è la cosiddetta conoscenza euristica.
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
La ricerca è una parte necessaria per la risoluzione
di un problema
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 di tutti e soli gli stati del mondo
in cui è soddisfatto l’obiettivo stesso.
• Le azioni sono causa di transizioni tra stati del mondo.
• L’agente deve scegliere (tra tutte quelle possibili) una
sequenza di azioni che lo conduca ad uno stato obiettivo.
Agente risolutore di problemi
(basato su obiettivi)
1. Formulazione dell’obiettivo
(basata sulla situazione corrente e sulla misura di
prestazione dell’agente)
2. Formulazione del problema
(processo di decisione di quali azioni e stati della
risoluzione del problema considerare,
successivamente alla formulazione dell’obiettivo)
Agente risolutore di problemi
(basato su obiettivi)
Ove esistano 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
Quando non è noto a priori quale sia la migliore azione
immediata da compiere,
nell’ipotesi che esistano possibili sequenze di azioni per
raggiungere l’obiettivo,
l’agente può analizzare diverse sequenze per ricercare la
soluzione migliore (cosiddetto processo di ricerca).
Prima di cominciare a ricercare soluzioni, è necessario
formulare un obiettivo e poi usare tale obiettivo per
formulare un problema.
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 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 in base alla
collezione di informazioni dell’agente 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
Algoritmo generale di ricerca
Dato un problema, una strategia ed un insieme di candidati
Ripeti fino ad esaurimento dei candidati/nodi:
Se non esistono candidati/nodi da espandere,
Allora non c’è soluzione al problema
Altrimenti scegli un nodo 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
Algoritmo generale di ricerca
L’output di un algoritmo di ricerca è una
soluzione,
ovvero
un cammino dallo stato iniziale allo stato che
soddisfa il test obiettivo
Agente risolutore di problemi
Soluzione di problema offline-si considera che l’ambiente non cambi
durante la soluzione (una soluzione online richiede l’agire senza una
completa conoscenza del problema e della soluzione)
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; dato uno
stato x, funzione successore(x) produce un insieme di coppie
ordinate <azione,successore> dove successore è lo stato che può
essere raggiunto da x eseguendo azione
Un cammino nello spazio degli stati è una qualsiasi
sequenza di azioni che conduce da uno stato ad un altro
(funzione costo di cammino g)
Il test obiettivo è applicato dall’agente alla descrizione di un
singolo stato per determinare se è in uno stato obiettivo.
Agente risolutore di problemi
Elementi fondamentali nella definizione di un
problema sono gli stati e le azioni
La conoscenza che l’agente ha sulle sue azioni e
sugli stati del mondo dipende da come è
connesso al suo ambiente, tramite
“percezioni e azioni”.
Conoscenza e Tipi di problemi
Problemi a stato singolo (mondo accessibile, l’agente conosce
l’effetto delle azioni; può calcolare lo stato dopo la sequenza delle
azioni)
Problemi a stati multipli (mondo non accessibile (no sensori),
l’agente conosce l’effetto delle azioni, 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)
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 :
1.
2.
3.
4.
Stato iniziale x
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 :
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 il 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:
rappresentazione
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
Rappresentazione
Un nodo dell’albero di ricerca può essere rappresentato da
una struttura dati a cinque componenti:
1.
2.
3.
4.
5.
Stato nello spazio degli stati a cui corrisponde il nodo
Nodo genitore di quello corrente
Operatore applicato per generare il nodo
Numero nodi del cammino dalla radice (profondità)
Costo del cammino dallo stato iniziale
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)
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
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 semplificato
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
Il problema determina il grafo di rappresentazione degli stati
e l’obiettivo (ovvero ciò che rappresentano i vicini di un
nodo) ma non definisce la modalità di selezione di un nodo
o come aggiungere un nodo alla frontiera dell’esplorazione.
Un unico algoritmo di ricerca può essere usato per risolvere
qualsiasi problema; specifiche varianti dell’algoritmo
realizzano strategie differenti.
Una strategia di ricerca specifica quali elementi devono
essere selezionati nella frontiera; strategie diverse di
ricerca si differenziano per le modalità di selezione e di
aggiunta di un nodo alla frontiera.
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; tutto quello che si può fare è generare
successori e distinguere gli stati obiettivo dagli altri
2. 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,…); si assume che ciascun
arco pesi 1.
Ricerca in ampiezza
Se esiste una sola soluzione, la ricerca in ampiezza
la trova (completezza)
Se esistono più soluzioni, viene trovato per prima lo
stato obiettivo più alto/superficiale - quindi a
costo minimo (ottimalità) (tutti gli archi hanno
uguale peso 1)
Valutazione: ricerca completa ed ottimale
Ricerca in ampiezza (complessità)
Se fattore di ramificazione = b
i
al livello i si avrà ramificazione = b
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 a costo uniforme
Quando si hanno archi di costo non unitario,
esiste l’interesse a trovare la soluzione che
minimizzi il costo totale del cammino.
Costi possono essere le distanze tra i punti
rappresentati dai nodi, oppure costi possono
essere le risorse richieste dall’agente per
realizzare il task associato ad un nodo; e si
vuole minimizzare i costi.
Ricerca a costo uniforme
Il più semplice algoritmo che garantisce di trovare
un cammino minimo è di tipo ricerca in ampiezza
con la selezione del cammino a costo minimo.
La ricerca a costo uniforme modifica la strategia in
ampiezza espandendo sempre il nodo sul confine
con il costo più basso (misurato con il costo del
cammino g(n) dal nodo origine a quello corrente –
non c’è conoscenza sul prosieguo del cammino),
invece del nodo di profondità minima
Ricerca a costo uniforme
La ricerca a costo uniforme si implementa gestendo i nodi
di frontiera con una coda a priorità ed ordinandola tramite
la funzione g(n);
Si trova sempre la soluzione più economica se si verifica
che il costo del cammino non decresce mai quando lo
percorriamo. Se ci fosse un operatore con costo negativo
dovremmo applicare una ricerca esaustiva per trovare la
soluzione ottimale.
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:
andare da S a G
Ricerca in profondità
La ricerca in profondità espande sempre il primo
dei nodi fino a raggiungere il livello più
profondo dell’albero.
La ricerca torna indietro (backtracking) 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 (l’elemento estratto è
sempre l’ultimo che era stato inserito)
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
m
Complessità temporale della ricerca in profondità : O(b )
La ricerca in profondità può rimanere bloccata in un
cammino sbagliato di lunghezza infinita.
Valutazione: né completa, né ottimale
Ricerca a profondità limitata
Si migliora la ricerca in profondità imponendo un
taglio/limite (scelto in base alla conoscenza del
problema) alla profondità massima di un
cammino, ovvero non si espandono ulteriormente
i nodi al limite di profondità imposto
Suggerimento:
Taglio = profondità obiettivo più superficiale
Ricerca bidirezionale
Le strategie di ricerca di soluzione di un problema sono
simmetriche nel senso che non c’è alcuna preferenza a
cominciare dallo stato iniziale per giungere allo stato
obiettivo, o cominciare dallo stato obiettivo e giungere a
quello iniziale (ove possibile)
Nei casi in cui l’obiettivo è esplicito, può essere più
efficiente cominciare da questo.
Principio generale: si ricerca in avanti o in indietro a
seconda del costo di ramificazione
Ricerca bidirezionale
Per ridurre i tempi della ricerca, 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
d /2
d /2
soluzione verrà trovata in O(2b )  O(b )
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.
Suggerimenti:
• Non ritornare allo stato da cui si proviene
• Non creare cammini che abbiano cicli
• Non generare alcuno stato già generato prima
Argomenti trattati in questa lezione
• Struttura e funzionalità degli agenti risolutori
di problemi
• Processo di ricerca
• Tipologie di problemi da risolvere
• Informazioni necessarie a definire un
problema
• Tipologie di strategie di ricerca e metodologie
per la loro valutazione