Ricerca locale
M. Simi, 2008-2009
Assunzioni sui problemi



Gli algoritmi visti esplorano gli spazi di ricerca e
restituiscono un cammino soluzione
Ma a volte lo stato goal è la soluzione del problema.
Gli algoritmi di ricerca locale sono adatti per
problemi in cui:


La sequenza di azioni non è importante: quello che conta è
lo stato goal
Tutti gli elementi della soluzione sono nello stato ma alcuni
vincoli sono violati. Es. le regine nella versione a stato
completo
Algoritmi di ricerca locale



Tengono traccia solo dello stato corrente e si
spostano su stati adiacenti (non necessario un
puntatore al padre)
Efficienti in occupazione di memoria
Utili per risolvere problemi di ottimizzazione


Funzione obiettivo da massimizzare
Funzione costo da minimizzare
Panorama dello spazio degli stati


Uno stato ha una posizione e una altezza che corrisponde al
valore della f. di valutazione
Un algoritmo provoca movimento sulla superficie
Ricerca in salita (Hill climbing)


Anche detto ricerca locale greedy
Vengono generati i successori e valutati; viene scelto
un nodo, che migliora la valutazione dello stato
attuale:




il migliore (salita rapida)
uno a caso (stocastico)
il primo (con successori generati a caso)
Se non ce ne sono l’algoritmo termina (non si tiene
traccia degli altri)
Problemi con Hill-climbing
Se la f. è da ottimizzare i picchi sono massimi locali o
soluzioni ottimali
collina

Massimi locali

Pianori

Crinali (o creste)
montagna
?
Miglioramenti
Miglioramenti della strategia di base:
1. Espandere l’albero di ricerca 2 o 3 livelli e
ripetere la valutazione
2. Ripartire da un punto scelto a caso: HillClimbing con riavvio casuale (random restart)

Se la probabilità di successo è p saranno
necessarie in media 1/p ripartenze per trovare
la soluzione (es. 8 regine, p=0.14, 7 iterazioni)
Osservazione


Hill-climbing è un metodo locale; funziona bene
quando la funzione di valutazione non ha essa
stessa un carattere locale.
Le funzioni “più globali” costano di più.
Il mondo dei blocchi
Stato
iniziale
A
D
D
C
C
B
B
A
Stato
finale
Operatori:
• Sposta un blocco da un blocco ad un altro
• Sposta un blocco da un blocco al tavolo
• Sposta un blocco dal tavolo ad un altro blocco
Euristica “locale” per il mondo dei blocchi
Euristica dei blocchi fuori posto:
+1 per ogni blocco a posto, -1 fuori posto
A
D
D
C
C
B
2-2=0
A
B
3-1=2
L’algoritmo si blocca
C
A
B
2-2=0
D
Euristica “non locale” per il mondo dei blocchi
Euristica dei blocchi con supporto corretto:
(#blocchi supporto OK - #blocchi supporto non OK)
A
D
D
D
C
C
B
-3-2-1
A
-2-1
B
C
C
B
A
-1
B
D
A
…
3+2+1
Tempra simulata (simulated annealing)
[Kirkpatrick, Gelatt, Vecchi 1983]

Ad ogni passo si sceglie un successore a caso:




se migliora lo stato corrente viene espanso
se no (caso in cui E=f(n’)-f(n) 0) quel nodo viene scelto
con probabilità p=eE/T [0  p  1]
Si genera un numero casuale tra 0 e 1: se questo è 
p il successore viene scelto, altrimenti non si fa niente.
T descresce col progredire dell’algoritmo secondo uno
schedule definito (lo schedule definisce valore iniziale
e decremento).
Simulated annealing: analisi


La probabilità di una mossa in discesa diminuisce col
tempo e l’algoritmo si comporta sempre di più come
Hill Climbing. Se T viene decrementato abbastanza
lentamente siamo sicuri di raggiungere la soluzione
ottimale.
Analogia col processo di tempra dei metalli



T corrisponde alla temperatura
E alla variazione di energia
Valori per T determinati sperimentalmente: il valore
iniziale di T è tale che per valori medi di E, eE/T sia
all’incirca 0.5
Ricerca local beam


Si tiene traccia di k stati anziché uno solo
Ad ogni passo si generano i successori di tutti i
k stati



Se si trova un goal ci si ferma
Altrimenti si prosegue con i k migliori
Nella variante local beam stocastica, si
scelgono k successori a caso con probabilità
maggiore per i migliori (selezione naturale).
Algoritmi genetici


Popolazione: k stati generati casualmente
Ogni individuo rappresentato come stringa


Gli individui sono valutati da una funzione di fitness


Esempio: 24748552 stato delle 8 regine
Esempio: n. di coppie di regine che non si attaccano
Si scelgono gli individui per gli “accoppiamenti” con
una probabilità proporzionale alla fitness
Esempio


Per ogni coppia viene scelto un punto di cross-over e i
due genitori producono due figli scambiandosi pezzi
Viene infine effettuata una mutazione casuale che da
luogo alla prossima generazione.
Algoritmi online
Maria Simi, a.a. 2008/09
Problemi di esplorazione

Gli agenti risolutori di problemi assumono:



ambienti osservabili e deterministici
il piano generato può essere generato offline e eseguito
senza imprevisti
Assunzioni per un problema di esplorazione:



Solo lo stato corrente è osservabile, l’ambiente è
sconosciuto
Non si conosce l’effetto delle azioni e il loro costo
Gli stati futuri e le azioni che saranno possibili non sono
conosciute a priori
Algoritmi online



Si devono compiere azioni esplorative
Si alternano pianificazione e azione
Cosa conosce un agente online …




Le azioni legali nello stato attuale
Il costo della mossa c(s1, a, s2) ma dopo averla
eseguita
Goal-test(s)
La stima della distanza: dal goal: h(s)
Esempio: Teseo con mappa e senza

Con mappa


applicabili tutti gli
algoritmi di
pianificazione visti
Senza mappa


l'agente non può
pianificare può solo
esplorare nel modo più
razionale possibile
Ricerca online
h=4
h=3
h=2
h=1
T
h=2
h=1
h=0
h=4
h=3
h=2
h=1
h=5
h=4
h=3
h=2
h=3
Assunzione ulteriore

Ambienti esplorabili in
maniera sicura


Non esistono azioni
irreversibili
Diversamente non si può
garantire una soluzione
Ricerca in profondità online


Gli agenti online ad ogni passo decidono l'azione da
fare (non il piano) e la eseguono.
Ricerca in profondità online

Esplorazione sistematica delle alternative


È necessario ricordarsi ciò che si è scoperto


notexp[s] mosse ancora da esplorare
risultato[a, s] = s’
Il backtracking significa tornare sui propri passi

notback[s] stati a cui si può tornare
Esempio
1




Sceglie il primo tra (1,1)
e (2,2)
In (1, 1) non ha azioni;
può solo tornare indietro
…
Nella peggiore delle
ipotesi esplora ogni
casella due volte
1
T
2
T
2
3
4
T
T
3
T
T
4
T
T
T
Algoritmo DF online
function Agente-Online-DFS(s) returns an action
static: risultato, notexp, notback,
s- (stato precedente), a- (ultima azione)
if Goal-Test(s) then return stop
if s nuovo stato then notexpl[s]  AzioniLegali(s)
if s- non è null then risultato[a-, s-]  s; notback[s]  s-;
if notexpl[s] vuoto then
if notbackl[s] vuoto then return stop
else a  azione per tornare in POP(notback[s])
else a  POP(notexpl[s])
s-  s; return a
Ricerca euristica online





Nella ricerca online si conosce il valore della
funzione euristica una volta esplorato lo stato.
Un algoritmo di tipo Best First non
funzionerebbe.
Serve un metodo locale
Hill-climbing con random-restart non praticabile
Come sfuggire a minimi locali?
Due soluzioni
1.
Random-walk

2.
si fanno mosse casuali in discesa
Apprendimento Real-Time:

esplorando si aggiustano i valori dell'euristica per
renderli più realistici.
H: migliore stima fin qui
Si valutano i successori:

Costo-LRTA*(s, a, s', H) = h(s) se s' indefinito
H(s') + costo(s,a,s') altrimenti
Ci si sposta sul successore di Costo-LRTA* minore


Esempio di Real Time Learning A* (LRTA*)
1
1
2
3
4
T
T
T
(h=3)
T
(h=2)
(h=3)
(h=1)
(H=0)
T
T
T
(h=3)
(h=2)
(H=4)
(H=1)
T
T
(H=3)
(H=2)
T
(h=4)
2
3
4
LRTA*
function Agente-LRTA*(s) returns an action
static: risultato, H, s-, aif Goal-Test(s) then return stop
if s nuovo (non in H) then H[s]  h[s]
1. if s-  null // si aggiusta il costo H del predecessore
risultato[a-, s-]  s
H[s-]  min Costo-LRTA*(s-, b, risultato[b, s-], H)
2. a  un'azione b tale che minimizza
Costo-LRTA*(s, b, risultato[b, s], H)
s-  s; return a
b  AzioniLegali(s)
Considerazioni su LRTA*




LRTA* cerca di simulare A* con un metodo locale:
tiene conto del costo delle mosse come può
aggiornando al volo la H
Completo in spazi esplorabili in maniera sicura
Nel caso pessimo visita tutti gli stati due volte ma è
mediamente più efficiente della profondità online
Non ottimale, a meno di usare una euristica perfetta
(non basta una f=g+h con h ammissibile)