Ricerca LRTA*
La ricerca LRTA* ( Learning Real Time A* ) è un algoritmo di apprendimento in tempo reale che utilizza la funzioni euristiche di una ricerca A* in una ricerca locale online. L'agente razionale si trova in un ambiente ignoto o parzialmente osservabile, deve quindi esplorare l'ambiente in tempo reale ( ricerca online ). La sua visibilità è limitata ai soli stati del mondo confinanti ( ricerca locale online ). Per raggiungere un obiettivo l'algoritmo LRTA* si avvale di una funzione euristica che aggiorna progressivamente con i dati ottenuti dall'esplorazione. Nel corso dell'esplorazione dell'ambiente operativo l'algoritmo di ricerca LRTA* seleziona il miglior valore euristico tra le mosse possibili. Se le euristiche sono ammissibili, l'algoritmo di ricerca LRTA* è in grado di convergere verso soluzioni ottimali dopo ripetute prove. Ad esempio, nella seguente matrice l'agente razionale deve raggiungere un obiettivo ma non conosce l'ambiente che lo circonda e può vedere soltanto le celle confinanti. Le zone grigie rappresentano l'ambiente sconosciuto. Nella mappa è presente anche un ostacolo per rendere ulteriormente più difficoltosa la ricerca.
In questo caso l'algoritmo di ricerca LRTA* si avvale di una semplice funzione euristica che gli consente di avere una stima della distanza aerea tra la posizione di partenza e quella dell'obiettivo. Questi valori euristici h(x) sono indicati in blu in ogni cella della matrice. I valori di colore rosso indicano, invece, il costo g(x) dello spostamento nelle caselle a partire dalla posizione corrente dell'agente. Il costo stimato f(x) per raggiungere l'obiettivo è, infine, determinato dalla somma del valore euristico h(x) e del costo dello spostamento locale g(x).
f(x) = h(x) + g(x)
La ricerca LRTA* consente all'agente razionale di esplorare in modo informato ( ricerca informata ) l'ambiente parzialmente osservabile, di appianare eventuali situazioni di minimo locale, di aggirare l'ostacolo e infine trovare la soluzione ( obiettivo ) in poche mosse. La migliore mossa viene determinata dal minore costo stimato ( verde ) tra le celle confinanti alla posizione corrente dell'agente. In caso di pari costo stimato viene scelta la cella inesplorata. A parità di ulteriori condizioni viene effettuata una scelta casuale tra le migliori destinazioni possibili. Nel corso dell'esplorazione l'algoritmo di ricerca LRTA* migliora la sua conoscenza dell'ambiente tramite l'apprendimento, aggiornando la stima euristica delle celle. Questo aspetto è particolarmente importante in quanto riduce il rischio di ritornare nelle stesse celle durante l'esporazione e consente all'agente razionale di appianare le eventuali posizioni di minimo locale e di aggirare gli ostacoli lungo il suo cammino.
Ammissibilità euristiche. Il buon funzionamento dell'algoritmo di ricerca LRTA* è fortemente legato alle euristiche. In caso di euristiche ammissibili l'algoritmo LRTA* consente di giungere alla soluzione ottimale nei problemi di ricerca online. Viceversa, quando le euristiche non sono ammissibili offre un livello di performance inferiore rispetto ad altri algoritmi simili.
