Intelligenza Artificiale: Markov Decision Process

In Intelligenza artificiale, in alcune situazioni, hai bisogno di una semplice sequenza di azioni per raggiungere in determinato obiettivo, partendo da uno stato noto; in tutti quegli ambienti dove invece le azioni non sono deterministiche (non deterministiche o stocastiche), questo non è più sufficiente: c’è bisogno di una policy, ovvero di una politica che ci dice qual’è l’azione giusta da fare in ogni stato.

Le Markov Decision Process sono una struttura matematica che ci aiuta a costruire queste policy in ambienti stocastici dove si conoscono le probabilità che si verifichino determinati risultati.

In questo post, io vi darò una brevissima introduzione e poi vi mostrerò le parti essenziali della mia implementazione, in python, dei più importanti algoritmi che vi possono aiutare per trovare le policy in ambienti stocastici. Potete trovare una più dettagliata descrizione delle Markov Decision Process nelle mie slide che ho preparato per un seminario nella mia università.

Per spiegarvi cosa siano, utilizziamo lo stesso esempio del libro “Artificial Intelligence: A Modern Approach (3rd ed.)“. Questo ambiente viene chiamato dagli autori: Grid World, una semplice griglia dove le possibili azioni sono NORTH, SOUTH, EAST, WEST. Questo ambiente non è deterministico, ma stocastico; assumiamo però delle probabilità ben definite. La probabilità di compiere l’azione che abbiamo deciso di intraprendere è dello 0.8, mentre la probabilità di andare nella cella di sinistra e nella cella di destra sono dello 0.1. Ad esempio se ci troviamo nella cella (2,1) e vogliamo fare l’azione NORTH, i possibili risultati potrebbero essere rappresentati in questo modo:

Queste probabilità potrebbero modellare ad esempio il movimento di un robot, che ogni tanto, a causa dell’attrito del terreno sul quale poggia, può andare leggermente a sinistra o leggermente a destra rispetto a dove volevamo andare.

Abbiamo bisogno anche di un goal, il grid world ha infatti un uscita con un reward positivo di +1. Inoltre, ci sono alcuni fossi che hanno un reward negativo di -1. Sia l’uscita che il fosso sono stati finali, cioè non possiamo fare nessuna azione partendo da quello stato. Non possiamo uscire fuori dalla griglia e possiamo avere altre limitazioni spaziali avendo delle celle che fungono da muro; in questo modo possiamo creare dei percorsi di lunghezza diversa per arrivare al nostro goal.

Per costruire la policy, abbiamo bisogno di una stima delle utility di ogni cella. Possiamo calcolare queste utility usando un metodo simile a minimax: questo metodo viene chiamato expectiminimax. Ma per la maggior parte delle applicazioni questo metodo è infattibile, per esempio perché non ci sono stati terminali o perché memorizzare tutto l’albero richiede moltissima memoria.

Le Markov Decision Process ci aiutano a calcolare queste utility con metodi più performanti.

Un commento su “Intelligenza Artificiale: Markov Decision Process

  1. Pingback: Angelo Stella. Matematica generale ed applicata

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

*