Ricerca gerarchica

La ricerca gerarchica è un metodo di ricerca delle soluzioni di un problema ( problem solving ) all'interno di una rete gerarchica. Le reti gerarchiche HTM sono alla base degli algoritmi di ricerca gerarchica. Nella ricerca gerarchica le azioni di alto livello sono codificate in sequenze di azioni primitive. Ogni sequenza di azioni primitive consente di compiere delle azioni elementari o risolvere problemi pratici ( es. come avviare il motore dell'automobile, come aprire il frigorifero, ecc. ). Tutte le sequenze sono registrate in una libreria. Per trovare la soluzione a un problema o per rispondere a un'istanza, l'algoritmo di ricerca gerarchica consulta la libreria per verificare quale concatenazione di sequenze consente di collegare la situazione iniziale alla situazione finale ( obiettivo ). La ricerca delle soluzioni primitive permette di costruire una sequenza di azioni di primo livello per risolvere il problema.

La libreria delle sequenze di azioni può essere alimentata da un altro algoritmo sulla base dell'osservazione dei dati e dell'esperienza pratica ( apprendimento ). La ricerca gerarchica può essere effettuata sia a livello atomico ( ricerca di soluzioni primitive ) che a livello astratto ( ricerca di soluzioni astratte ). La ricerca gerarchica a livello atomico è meno efficiente, poiché le combinazioni dello spazio di ricerca da analizzare sono molteplici. È quindi preferibile adottare un ricerca gerarchica con un elevato livello di astrazione. In questo modo lo spazio di ricerca delle combinazioni è molto più contenuto. Nella ricerca gerarchica di soluzioni astratte l'algoritmo analizza soltanto le precondizioni e l'effetto di ogni azione di alto livello ( HLA ).

Una volta individuto il percorso ( path ) delle azioni di alto livello ( HLA ), l'algoritmo può trasformarle in azioni operative di livello inferiore. L'algoritmo scompone il problema astratto in una sequenza di sottoproblemi. L'operazione di derivazione ( regressione ) delle azioni primitive a partire dalle azioni di alto livello ( HLA ) è detta raffinamento discendente.

---

• Azioni con effetti multipli. Le azioni di alto livello potrebbero avere effetti multipli. In questi casi ogni singola azione HLA ha molteplici implementazioni e ogni sequenza di azioni HLA può raggiungere diversi risultati ( stati finali ). Per capire se una sequenza di azioni HLA consente di risolvere un problema, è necessario analizzare l'insieme degli stati che può raggiungere ( insieme degli stati raggiungibili ). Se l'insieme degli stati raggiungibili interseca con l'insieme degli stati obiettivo, allora la sequenza conduce alla soluzione del problema. Viceversa, se l'insieme degli stati raggiungibili non interseca l'insieme degli stati obiettivo, allora la sequenza non conduce alla soluzione del problema. Ad esempio, a partire da uno stato iniziale (s₀) l'azione HLA a₁ conduce agli stati s₁ e s₂. L'azione a₂, a partire da s₁ o da s₂, conduce a un insieme di stati finali { s₃, s₄, s₅, s₆ } detto insieme degli stati raggiungibili. In questo caso l'insieme degli stati raggiungibili interseca l'insieme degli stati obiettivo, pertanto la sequenza delle azioni HLA ( azioni astratte ) comprende al suo interno almeno un cammino di azioni primitive in grado di risolvere il problema.
  
  Nel seguente esempio è, invece, rappresentato il caso di una sequenza di azioni di alto livello che non risolve il problema. In questo caso l'insieme degli stati raggiungibili non interseca l'insieme degli stati obiettivo. La sequenza di azioni di alto livello non conduce nemmeno a una soluzione al problema e, quindi, può essere scaratata.
  
• Teoria dei giochi. La ricerca gerarchica è efficace quando le scelte sono compiute soltanto dall'agente. Se esiste un'intersezione tra l'insieme degli stati raggiungibili e quello degli stati obiettivi, è razionale che l'agente esegua esattamente la sequenza di azioni operative che consente di raggiungere l'obiettivo. Quando le decisioni sono prese da due agenti, invece, non è detto che vi sia altrettanta certezza. Nel seguente esempio è rappresentato un gioco sequenziale con due agenti ( blu e rosso ). Nel primo turno del gioco l'agente G1 ( blu ) può scegliere tra due azioni, andare a sinistra o a destra. Nel secondo turno anche l'agente G2 ( rosso ) può scegliere di andare a sinistra o a destra. Ipotizzando che l'agente G2 non sia influenzato dalle scelte di G1, l'agente G1 raggiunge il risultato soltanto scegliendo di andare a sinistra, se anche l'agente G2 sceglie di andare a sinistra. Sicuramente l'agente G1 non raggiunge l'obiettivo andando a destra.
  
  Al posto del giocatore G2 si potrebbe considerare una variabile aleatoria. Ad esempio, il giocatore blu può scegliere di alzarsi presto o dormire. Se si alza presto può vedere l'alba ma soltanto se il cielo non è nuvoloso. Quando l'agente sceglie di dormire si può affermare con certezza che non potrà vedere l'alba, indipendentemente dalle condizioni meteorologiche, e il piano astratto fallisce. Viceversa, quando l'agente sceglie di alzarsi presto ha una probabilità su due di vedere l'alba.