02. Heuristic search

Introduzione

A differenza della blind search l'heuristic search (o ricerca informata) oltre a dipendere (non sempre!) dalla posizione del nodo nello spazio di ricerca, dipende anche da una qualche funzione (detta euristica) che valuta la distanza dal nodo corrente al goal. Questa distanza, lo vedremo, deve essere una sottostima della distanza reale ed in particolare deve avvicinarsi alla distanza reale dal goal da valori più piccoli per essere migliore (cioè se la distanza reale è 6, un'euristica che stima 5 è migliore di una che stima 4).
L'euristica non garatisce sempre l'ottenimento della soluzione in tempo polinomiale, a volte sarà necessario fare backtracking sullo spazio di ricerca per trovare il goal. Tuttavia l'euristica diventa più accurata con l'avvicinarsi al goal (effetto orizzonte).

Quando scegliere una ricerca euristica rispetto alla blind search?

Si può usare la ricerca euristica quando:

  • la stima della funzione euristica è più o meno accurata (altrimenti prendiamo direzioni nello spazio di ricerca del tutto sbagliate)
  • Il costo del calcolo della funzione euristica non deve essere computazionalmente oneroso altrimenti più che espandere pochi nodi calcolando poche volte la funzione euristica è meglio espanderne molti con la blind search.

In generale il costo dell'euristica nel caso peggiore è sempre esponenziale (la funzione euristica si arrende e si va di backtracking), ma se nella maggioranza dei casi (casi medi) si comporta bene, allora vale la pena usarla.

Tecniche euristiche

Ci sono 2 tecniche euristiche base: hill climbing e best first. Il flavor (sapore) di queste è rispettivamente: depth first e breadth first.

Hill climbing

Usando alg1 pag11r

1. se L=vuoto fail
2. else n=cima(L)
2.1 se n=goal return n,path(n)
2.2 else L-{n}
2.2.1 sort(figli(n), funzioneEuristica) //ordina i figli di (n) secondo la funzione euristica
2.2.2 insertInCima(figli(n),L) //ecco il flavour depth first, poichè poi il prossimo nodo da visitare è un figlio di n
2.2.3 goto 1.

Il difetto dell'algoritmo è che se abbiamo un buon nodo non in cima ad L, lo perdiamo (o meglio, lo visiteremo molto in ritardo). Inoltre si hanno gli svantaggi del depth first su alberi sbilanciati o rami infiniti.

Best first

Differenza con l'hill climbing, i nodi figli del nodo corrente non si mettono in cima ad L, ma vengono inseriti in L mantenendo l'ordine di L, cioè L è ordinata (e resta ordinata dopo l'inserimento) secondo la funzione euristica. Così si evita di "perdere di vista" un buon nodo da esplorare. Questo algoritmo può degenerare nel breadth first con costi spaziali e temporali esponenziali.

Problemi delle tecniche viste finora

Ogni volta si analizzano i vicini di un nodo, se la funione euristica ha un minimo locale allora continua per la strada corrente senza vederne altre. Insomma non si percorrono strade temporaneamente peggiori che magari possono rivelarsi migliori alla lunga. In certi casi vedere anche strade peggiori può risultare conveniente, come quando ci sono altipiani o crinali.

d3.jpg

(in realtà l'altipiano è una funzione che per un tratto è costante e poi cala verso il valore migliore. Tuttavia cercando il minimo non ha senso spostarsi nell'altipiano perchè i punti dell'altipiano sono tutti minimi locali).

Dunque queste tecniche sono greedy. COme faccio a superare i crinali posso fare un lookahead, cioè guardo in avanti che valore avranno i figli dei figli del nodo corrente per stabilire che valore hanno i figli, ma così aumento il tempo di calcolo sul metalivello. Oppure posso usare la lemmatizzazione cioè si riconoscono composizioni di mosse che han dato vantaggi, e se esistono composizioni simili nei rami figli di un nodo (sempre lookahead) assegno a questo un valore migliore.
Quando ho altipiani o ancor peggio pianure (molti nodi con valore simile) posso usare un algoritmo di scelta casuale. Un tipo di algoritmo simile è simulated annealing.

Simulated annealing

Usa un'analogia con un processo fisico. Usando l'hill climbing, questo sceglierebbe un certo nodo. Noi faremo questa scelta con una certa probabilità $(1-p(t))$, quindi:

  • con prob $(1-p(t))$ -> hill climbing move
  • con prob $p(t)$ -> random move (selezione di un nodo a caso dalla lista dei nodi da espandere)

t è il tempo, o numero di mosse, o quel che si vuole che permetta di modellare il seguente concetto: all'inizio la probabilità p(t) è alta (quindi di sceglie casualmente) e poi alla lunga usiamo l'algoritmo euristico hill climbing che si dovrebbe muovere bene grazie all'effetto orizzonte. Questo algoritmo in molti casi funziona bene. Si dimostra che, con un numero opportuno di tentativi (molto alto) quest algoritmo trova sempre la soluzione ottima poichè all'inizio sceglie casualmente, dunque con abbastanza tentativi sceglierà anche il ramo con la soluzione ottima.

Modifica al best first/hill climbing per vedere potenziali "buoni nodi". A star (A*)

Esponiamo le modifiche con un esempio, dato il seguente spazio di ricerca:

d4.jpg

I numeri tra parentesi indicano la sequenza dei nodi visitati secondo sia l'hill climbing, sia il best first. Come si vede si arriva al goal (g) ma noi vorremmo trovare il goal più vicino alla radice che è dopo un crinale "impassabile" per entrambi gli algoritmi nella loro versione base poichè si basano sui minimi locali (localmente ai nodi in lista da espandere). La modifica che si effettua forza l'euristica a tener conto anche della posizione del nodo nell'albero1, in particolare della profondità di questo, così si cerca di non perdere goal molto vicini alla radice.
Sia $g(n)$ la profondità del nodo n ed $h(n)$ il valore dell'euristica sullo stesso nodo, la funzione euristica totale sarà: $f(n) = h(n) +g(n)$.
Nota: $h(n)>0$ per ogni nodo non goal (stima la distanza da questo) ed in generale qualsiasi funzione euristica vale zero per i nodi goal.

Vediamo come si comporta con l'esempio di prima, usando il best first:

d5.jpg

Quindi il best first che tiene conto della profondità del nodo è A*.

Con A* si trova sempre la soluzione ottima? No, basta che il goal a sinistra sia al posto del nodo con valore 1+5 che non si troverebbe la soluzione ottima. Infatti dopo 1+4 (il 5° nodo visitato) avrei 0 (il goal) e non sceglierei più il nodo con valore 4+1 (il 6° nodo visitato).

Dubbio: ma la soluzione ottima non è sempre il goal più vicino alla radice? Sembra di si ma devo verificare.
Osservazione: (grazie Pasquale C.) sul libro di IA vol1 pag. 99 dice "il nodo meno profondo non è necessariamente quello ottimo; tecnicamente la ricerca in ampiezza è ottima solamente se il costo del cammino è una funzione monotona crescente della profondità del nodo (nel caso della blind search)".

Questo ci fa capire che un nodo a profondità 3 con costo per raggiungerlo pari a 5 è migliore di un nodo a profondità 2 con costo pari a 7. Questo vale nella blind search dove non si tiene conto di funzioni euristiche varie. Nella ricerca euristica, tuttavia, sembra che sia tanto meglio tanto più si raggiunge il nodo ottimo meno profondo (vedere A*) quindi il dubbio permane.

Funzioni euristiche usabili

Abbiamo sempre detto che le funzioni euristiche migliori, ed ora aggiungiamo utilizzabili, sottostimano la distanza del nodo corrente dal goal. Il valore 4 assegnato al secondo nodo a destra non è una sottostima, quindi la funzione euristica dell'esempio, se vogliamo esser rigorosi, non è utilizzabile!

Su A*

Problemi di A*

A* è l'algoritmo di ricerca euristica più usato, specie su spazi di ricerca non difficili (non troppo grandi ne difficili da valutare in termini di funzione euristica), il problema è che può degenerare in un breadth first (prima scende sul ramo e poi ne visita un altro a causa della funzione che valuta la profondità del nodo). Dunque può avere costo spaziale esponenziale.

Combinare A* con l'iterative deepening

Producendo IDA* ( iterative deepening A star )

1. set c=1 //cutoff limit
2. L = {nodi iniziali} ; 
   c' = +inf //cutoff stimato alla prossima iterazione dell'iterative deepening
3. if L == empty and c' == +inf
     fail
4. if L == empty and c' != +inf
     c = c' //NOTA: qui aggiorno c con c'
     goto 2
     //se abbiamo svuotato L c ma c' è cambiato, allora riproviamo da capo (come da iterative deepening, iniziamo dalla root). 
5. n = firstNode(L)
6. if (goal(n))
     return n,path(n)
     stop //abbiamo trovato il goal
7. else
     L = L-{n} //togliamo n dai nodi da valutare
8. for all n' in children(n)

8.1  if f(n')<=c' //se la funzione euristica è minore del cutoff della prossima iterazione
       addFirst(n',L) //vedremo n' prima degli altri nodi
8.2  //pezzo in dubbio, vedi il fix sotto con l'8.1 fixed che sostituisce 8.1 ed 8.2.
     else
       c'=min{c', f(n')} //aggiorniamo il cutoff poichè si ha che f(n')>c' quindi
                         //vediamo di limitare il valore per salvarci i check. Ma la cosa strana
                         //è che il minimo sarà sempre c' da come abbiam scritto l'if.
                         //anzi, visto che c' è infinito all'inizio, quando mai lo aggiorneremo?  
       goto 4

8.1 fixed (usando on the fly http://en.wikipedia.org/wiki/IDA*)
     if f(n')<=c' //se la funzione euristica è minore del cutoff della prossima iterazione
       addFirst(n',L) //vedremo n' prima degli altri nodi
       c'=min{c', f(n')} //aggiorniamo il cutoff della prossima iterazione
     end if
   end for    
   goto 4

In sostanza si dice che se il figlio del nodo corrente ha una valutazione euristica inferiore al cutoff della prossima iterazione (dell'iterative deepening))lo valuteremo altrimenti lo scartiamo (e lo scarteremo anche nella prossima valutazione). Nell'esecuzione di IDA* c' diventa la distanza dal primo goal interessante. Ovviamente essendo fuso con l'ID ora IDA* ha un flavour depth first.

Dubbio: Da testare l'algoritmo per capirlo bene e non solo ad occhio, inoltre chiedere il fix dell'algoritmo per quanto riguarda c'.

Questioni su A*

Se ad A* assegniamo una funzione euristica perfetta, cioè ${h}'(n) = h(n)$ come si comporta rispetto ad A* con una funzione euristica ottimistica?
Se, con IDA*, invece di inserire i figli del nodo corrente in cima ad L, li inseriamo ordinatamente in lista secondo $f(n)$, cosa cambia?

Teorema: A* trova sempre la soluzione ottima se la funzione euristica è ottimistica

Funzione euristica ottimistica: si sottostima la distanza reale dal goal nello spazio di ricerca.

Enunciato teorema:

Sia ${h}'(n)$ la funzione euristica, se $\forall \ \mbox{nodo} \ n \ \left ( {h}'(n) \leq h(n) \right )$ è vera l'asserzione appena fatta (cioè che ${h}'(n)$ è una funzione euristica ottimistica), con h(n) la reale distanza tra n ed il goal e g(n) lineare rispetto alla profondità, allora A* trova sempre la soluzione ottima nello spazio di ricerca.

Dimostrazione (pier)

Distinguiamo due casi:

  1. il caso in cui la stima della funzione euristica ${h}'(n)$ sia proporzionale alla distanza dal goal, quindi ${h}'(n) \propto h(n)$, ovvero man mano che ci si avvicina ad un goal, la funzione assegna valori decrescenti ai nodi;
  2. il caso peggiore (la dimostrazione che sia il caso peggiore la lascio all'intuito) ovvero quando la funzione euristica non è sempre proporzionale alla distanza dal goal, in particolare per tutti i nodi dei rami che non portano alla soluzione ottima (il goal più vicino alla radice), ma portano comunque ad un goal, la distanza assegnata sarà $0<{h}'(n)<1$ (quindi tutti i nodi citati sembreranno essere vicinissimi ad un goal), mentre per i nodi sul ramo che porta alla soluzione ottima si avrà ${h}'(n)=h(n)$ (cioè si ha la vera distanza del nodo dal goal, senza sottostime).

Analizziamo il primo caso. Consideriamo due nodi nell'albero di ricerca: uno, detto nopt, che non appartiene al ramo che porta alla soluzione ottima ed uno, detto opt che ci appartiene. Se nopt è ad una profondità inferiore di opt, ovvero è più vicino alla radice, si avrà che ${h}'(nopt)+g(nopt) < {h}'(opt)+g(opt)$, ovvero la funzione euristica complessiva riporta un valore più basso su nopt, solo quando la distanza stimata dal goal (sullo stesso ramo del nodo corrente), assegnata da ${h}'$, su nopt è abbastanza piccola da rispettare la seguente condizione: ${h}'(nopt) < {h}'(opt) + g(opt) - g(nopt)$; considerando che si ha per certo $g(nopt) < g(opt)$ .
Se ciò è vero si prosegue con l'espansione del sottoalbero sotto nopt. Poichè ${h}'$ assegna distanze, anche se sottostimate, proporzionali a quelle reali rispetto al goal, allora quando le profondità tra nopt e opt uguali (in qualche caso anche quando sono vicine ma non uguali ma semplifichiamo il discorso) si avrà che ${h}'(opt)< {h}'(nopt)$, in quanto nopt è più distante dal goal rispetto ad opt (mentre $g(nopt) = g(opt)$ ). Dunque a parità di livello espando sempre prima il sottoalbero sotto opt, e quindi la prima soluzione che troverò sarà quella più vicina a partire da opt, che è proprio quella ottima.

Analizziamo il secondo caso: stavolta prima di espandere opt, che rimane inespanso al livello subito dopo la radice, devo spingermi in profondità con i nodi nopt fino a quando ${h}'(nopt)+g(nopt) > {h}'(opt)+g(opt)$, cioè quando la funzione euristica assegna a nopt un valore maggiore rispetto ad opt.
Quando si ha questo? Si ha quando si arriva ad un nopt che si trova al livello della soluzione ottima sul ramo a cui appartiene opt. Infatti si avrà che il ramo che porta alla soluzione ottima non è stato mai esplorato quindi si è in attesa, con opt, su uno dei figli della radice, quindi $g(opt)=1$ con ${h}'(opt)$ pari alla distanza goal-radice meno uno, perchè siamo su un nodo figlio della radice; inoltre, proprio perchè nopt si trova al livello della soluzione ottima, si ha che la sua profondità è pari alla distanza del goal ottimo dalla radice, ovvero $g(nopt) = {h}'(opt) + 1$ che è pari a $g(nopt) = {h}'(opt) + g(opt)$ per quanto scritto. Ma non è finita qui perchè non abbiamo considerato ancora ${h}'(nopt)$.
Grazie alla condizione $0<{h}'(n)<1$, sui nodi non appartenenti al ramo della soluzione ottima, avremo espanso prima tutti i rimanenti nopt fino alla profondità precedente alla soluzione ottima2. Siccome ${h}'(nopt)=\varepsilon>0$ allora, sfruttando ciò che abbiam detto prima, si ha che ${h}'(nopt)+g(nopt) = \varepsilon + g(nopt) = \varepsilon + {h}'(opt) + g(opt) > {h}'(opt)+g(opt)$ , ovvero un nodo nopt allo stesso livello del goal ottimo ha un valore euristico maggiore rispetto al nodo sul ramo del goal ottimo in attesa al livello uno. Questo perchè basta già $g(nopt)$ ad eguagliare i due valori euristici, come prima visto, e l'aggiunta di un $\varepsilon$ rende $f(nopt)$ maggiore.
Dunque espando opt. Ma il nodo figlio di opt sul ramo che porta al goal ottimo, detto opt'(tutti i nodi nopt nel sottoalbero con radice opt seguono il ragionamento di prima), avrà sempre valore ${h}'(opt)+g(opt)$ in quanto ${h}'({opt}')={h}'(opt)-1 \wedge g({opt}')=g(opt)+1$, dunque i nodi nopt nella frontiera arrivano sempre al massimo fino ad un livello di profondità precedente rispetto al goal ottimo (e tutti gli altri goal si trovano almeno ad una profondità di uno superiore rispetto al goal ottimo) per poi veder espandere sempre il ramo ottimo che porterà al primo goal scoperto in tutta la ricerca, che è proprio il goal ottimo.

Esempio:

e: epsilon
valore: g(n)+h'(n), quindi profondità + euristica della distanza dal goal più vicino su quel ramo

        root
      /     \
  1+e         1+3
  2+e         2+2
  3+e         3+1
  4+e         g
  g

Nota sulle funzioni euristiche ottimistiche

Una funzione euristica è considerabile ottimistica se lo spazio di ricerca è limitato, se è molto grande o infinito è difficile vedere se è ottimistica o meno.

Sapere se una funzione euristica è ottimistica

Quando il dominio è troppo grande come facciamo a sapere se la funzione euristica è ottimistica o meno? Si procede come in ricerca operativa. Si sà come è descritta una soluzione e si procede togliendo vincoli che descrivono la soluzione. Quindi la funzione viene calcolata con vincoli meno stringenti e dunque ritornerà un valore ottimistico. Un esempio è la distanza di manatthan nel gioco del mosaico.

Richiamo su generazione dell'albero di ricerca

Come si è scritto, e come si evince dagli algoritmi in pseudocodice, lo spazio di ricerca è generato di volta in volta, non è già bello pronto (si disegna totalmente per fini di compattezza, altrimenti dovremmo disegnare un albero per ogni passo dell'algoritmo).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License