Ricerca locale online

La ricerca locale online è una tecnica informatica di ricerca che unisce le caratteristiche della ricerca locale con quelle della ricerca online. Nella ricerca locale online l'agente razionale si trova in un ambiente operativo parzialmente osservabile e ancora da scoprire. Conosce lo stato della propria posizione ma non ha alcuna informazione sugli altri stati dell'ambiente ( problema di esplorazione ). Per ottenere le informazioni deve necessariamente esplorare l'ambiente intorno a sé, agendo in modo simile a una ricerca online. L'esplorazione può essere causale oppure basata su una funzione euristica. L'esplorazione può avvenire in due modi:

• Esplorazione casuale. L'agente esplora l'ambiente intorno a sé scegliendo in modo casuale. L'esplorazione casuale è efficace, alla fine l'obiettivo viene comunque trovato, e non richiede un consumo eccessivo di memoria. Tuttavia, si tratta di un metodo di ricerca inefficente poiché è esposto al rischio di esplorare più volte gli stessi stati.
• Esplorazione con memoria. L'agente esplora l'ambiente intorno a sé in modo casuale ma evitando di esplorare le celle già visitate. Per evitare di bloccarsi in una situazione irreversibile è possibile utilizzare tecniche di backtracking, mantenendo in memoria la mappa conosciuta dell'ambiente e le celle ancora da visitare, prediligendo l'esplorazione nelle celle ancora da visitare più vicine alla posizione corrente.
• Esplorazione euristica. L'agente esplora l'ambiente intorno a sé scegliendo la prossima mossa in base a una funzione euristica. Man mano che l'agente esplora l'ambiente, aggiorna la coda degli stati già visitati, la mappa dell'ambiente operativo e la funzione euristica. Questo tipo di ricerca è più efficace rispetto all'esplorazione con memoria poiché la funzione euristica consente di pianificare meglio gli spostamenti e prediligere i percorsi più promettenti per raggiungere un obiettivo.

A differenza della ricerca online classica, basata su una ricerca in profondità, nel caso della ricerca locale online ci si basa sulle tecniche di ricerca locale quali la ricerca hill climbing e la ricerca A*.

• Ricerca hill climbing online. È un adattamento della ricerca hill climbing alla ricerca online. A differenza dell'algoritmo hill climbing semplice, in questo caso l'algoritmo non conosce l'ambiente intorno a sé. Per ottenere queste informazioni deve prima esplorare l'ambiente in modo reale ( ricerca online ) unendo l'azione e la computazione in un'unica fase.
• Ricerca LRTA*. È un adattamento della ricerca A* alla ricerca online. La sigla LRTA significa Learning Real Time A*. Anche in questo caso la computazione e l'azione sono unite in un'unica fase, l'agente esplora l'ambiente ( learning ) sulla base di una funzione euristica ed esegue le decisioni in tempo reale. Nell'algoritmo LRTA* assume una grande importanza la funzione di apprendimento che consente all'algoritmo di migliorare l'euristica nel corso dell'esplorazione.