Ricerca hill climbing online

La ricerca hill climbing online è una versione della ricerca hill climbing utilizzata quando l'agente razionale non conosce gli stati dell'ambiente intorno a sé. In tale caso l'agente non può "scalare" i valori degli stati confinanti poiché non li conosce ancora. Per ottenere queste informazioni l'agente deve esplorare realmente l'ambiente ( problema di esplorazione ) tramite una ricerca online. Nella ricerca hill climbing online l'agente esplora l'ambiente intorno a sé per ottenere le informazioni.

• Hill climbing online casuale. L'agente esplora l'ambiente intorno a sé in modo casuale. È una tecnica semplice ed efficace. Tuttavia, essendo elevato il rischio di esplorare più volte gli stessi stati è anche una tecnica molto lunga e inefficiente.
• Hill climbing online con memoria. L'agente esplora l'ambiente intorno a sé in modo casuale mantenendo in memoria la mappa dell'ambiente e la coda degli stati ancora da visitare. La memoria consente di ridurre notevolmente la ridondanza delle mosse e i tempi dell'esplorazione casuale.
• Hill climbing online euristica. È una versione perfezionata della ricerca hill climbing online con memoria. In questo caso, a partire dalla posizione corrente, l'agente calcola una stima euristica del costo di spostamento verso gli stati ancora da visitare. Nel corso dell'esplorazione l'agente migliora la funzione euristica aggiornandola con le nuove informazioni ottenute. Questa tecnica consente di ridurre ulteriormente l'inefficienza delle scelte casuali.

Ambiente infinito. Quando l'ambiente operativo è infinito l'agente rischia di incappare in una esplorazione perenne. Si rischia, pertanto, sia un problema di complessità spaziale e sia di complessità temporale dell'algoritmo di ricerca.

Massimo locale. Come nella ricerca hill climbing semplice anche nella versione online è elevato il rischi che la ricerca si blocchi su un punto di massimo locale o di minimo locale ossia su una soluzione sub-ottimale.

Riavvio casuale. La ricerca hill climbing online non può avvalersi del riavvio casuale poiché l'agente di ricerca esplora realmente l'ambiente Per spostarsi da una posizione all'altra della mappa deve obbligatoriamente muoversi. Non può, pertanto, saltare da una posizione all'altra.