Sistemi di Pianificazione Automatica e Grafi

Sistemi di Pianificazione Automatica

• I sistemi di pianificazione automatica possono essere classificati in due tipi: goal based e utility based.
• I sistemi goal based mirano a raggiungere un obiettivo predefinito.
• I sistemi utility based mirano a raggiungere l'obiettivo con il piano che massimizza la performance o minimizza i costi.
• I sistemi utility based agiscono sulla base di una funzione di utilità.

Modellazione di un Problema di Pianificazione come un Problema di Ricerca su Grafo

• Un problema di pianificazione può essere modellato come un problema di ricerca su grafo.
• Ogni stato dell'ambiente è rappresentato come un nodo del grafo.
• Il nodo di partenza rappresenta lo stato iniziale e il nodo finale rappresenta lo stato obiettivo.
• Le transizioni di stato sono rappresentate come archi che collegano i nodi.
• La soluzione è trovata cercando la sequenza di azioni che conduce dal nodo iniziale al nodo finale attraverso il percorso con il minor costo.
• Ogni azione ha un esito deterministico.

Algoritmi di Ricerca su Grafo

• Esistono due tipi di algoritmi di ricerca su grafo: Uninformed Search e Informed Search.
• Uninformed Search esplora lo spazio delle possibili soluzioni senza alcuna conoscenza riguardo al percorso migliore.
• Esempi di Uninformed Search includono BFS e DFS.
• Informed Search utilizza la conoscenza impressa dallo sviluppatore per ricercare la soluzione in modo più efficiente.
• Esempi di Informed Search includono Greedy Algorithm e A*.

Proprietà dell’algoritmo A*

• L'algoritmo A* è completo, ottimale ed efficiente quando la funzione euristica h utilizzata è una sottostima.
• Completo: trova una soluzione quando ne esiste una.
• Ottimale: trova la soluzione ottimale, se questa esiste.
• Efficiente: non ci sono altri algoritmi con la stessa funzione euristica che ottengono performance migliori.

Funzioni Euristiche del Puzzle a 8 Tasselli

• Nel puzzle a 8 tasselli, due principali funzioni euristiche sono utilizzate dall'algoritmo A*:
  • h1(s): conta il numero di tasselli fuori posto.
  • h2(s) (Manhattan Distance): stima il numero di mosse necessarie per posizionare ogni tassello nella posizione corretta.
• h2(s) fornisce una stima migliore rispetto a h1(s) e guida la ricerca in modo più efficace.

Concetto di Mondo Chiuso

• In un approccio dichiarativo, il mondo è descritto attraverso predicati (logica del primo ordine).
• Le azioni sono eseguibili solo se soddisfano delle precondizioni.
• Il concetto di mondo chiuso afferma che qualsiasi condizione non dichiarata nella descrizione dello stato è considerata falsa.

Funzione Euristica basata sul modello STRIPS

• Nel modello STRIPS, il dominio è rappresentato utilizzando la logica del primo ordine, attraverso i letterali.
• Una funzione euristica può essere una stima del numero di letterali nell'obiettivo che mancano nello stato attuale.

Stato Successore per un Agente che Manipola Blocchi

• L'azione Move(C, Table, A) è applicabile se le precondizioni On(C, Table), Clear(A) e Clear(C) sono soddisfatte.
• Lo stato successore è rappresentato da:
  • On(B,Table)
  • On(A,Table)
  • On(C,A)
  • ¬Clear(A)
  • ¬On(C,Table)
  • Clear(B)
  • Clear(C)

Matrice di Ricompensa o Tabella delle Decisioni

• La tabella delle decisioni rappresenta l'interazione tra gli stati e le conseguenze di ogni azione.
• Ogni azione ha una conseguenza che varia a seconda dello stato della natura.

Decisioni sotto Incertezza

• In condizioni di incertezza stretta, l'agente conosce i possibili stati della natura, ma non può quantificarne la probabilità.
• In condizioni di rischio, l'agente può caratterizzare gli stati della natura con una distribuzione probabilistica.

Criterio di Bayes

• Il criterio di Bayes seleziona l'azione che fornisce il massimo reward in condizioni di rischio.

Approcci alla Decisione in condizioni di Incertezza Stretta

• Approccio conservativo (Wald): sceglie l'azione con la minima ricompensa peggiore.
• Approccio ottimistico (Max reward): sceglie l'azione con la massima ricompensa migliore.
• Approccio ponderato (Hurwicz): combina il minimo e il massimo reward con un indice di ponderazione.
• Criterio di regret / rammarico (Savage): sceglie l'azione che minimizza il massimo rammarico.

Informazione Perfetta

• L'informazione perfetta si ha quando lo stato della natura che si verificherà è noto con certezza.
• Expected Reward under Perfect Information (ERPI) è la somma dei massimi reward per ogni azione moltiplicate per la distribuzione di probabilità.
• Expected Value of Perfect Information (EVPI) è la differenza tra ERPI e la ricompensa attesa senza informazione perfetta.

Valore della Sample Information

• Expected Value of Sample Information (EVSI) è il valore che un'azienda attribuisce a informazioni supplementari che possono migliorare la decisione.
• Efficienza dell'informazione campione (ESI) misura l'accuratezza di un sondaggio rispetto all'informazione perfetta.

Decisore Incline al Rischio

• Un decision-maker incline al rischio sceglie l'azione con la più alta expected reward, anche se ha una varianza alta.
• Un decision-maker non incline al rischio sceglie l'azione con la varianza più bassa, anche se ha una expected reward più bassa.

Soluzione Ammissibile

• Una soluzione a un problema di ottimizzazione è ammissibile se soddisfa tutti i vincoli del problema.