algorithm - Proceso de decisión de Markov: iteración de valores, ¿cómo funciona?

language-agnostic artificial-intelligence

Question

He estado leyendo mucho sobre los procesos de decisión de Markov (usando la iteración de valor) últimamente, pero simplemente no puedo entenderlos. He encontrado muchos recursos en Internet / libros, pero todos usan fórmulas matemáticas que son demasiado complejas para mis competencias.

Como este es mi primer año en la universidad, descubrí que las explicaciones y fórmulas proporcionadas en la web usan nociones / términos que son demasiado complicados para mí y suponen que el lector sabe ciertas cosas de las que simplemente nunca he oído hablar .

Quiero usarlo en una grilla 2D (llena de paredes (inalcanzables), monedas (deseables) y enemigos que se mueven (lo cual debe evitarse a toda costa). Todo el objetivo es recoger todas las monedas sin tocar a los enemigos, y quiero crear una IA para el jugador principal usando un Proceso de Decisión de Markov ( MDP ). Así es como se ve parcialmente (tenga en cuenta que el aspecto relacionado con el juego no es tan importante aquí. Realmente quiero entender los MDP en general):

Por lo que entiendo, una simplificación descortés de los MDP es que pueden crear una cuadrícula que mantenga en qué dirección debemos avanzar (una especie de cuadrícula de "flechas" apuntando hacia donde tenemos que ir, comenzando en una posición determinada en la grilla) ) para alcanzar ciertos objetivos y evitar ciertos obstáculos. Específico para mi situación, eso significaría que le permite al jugador saber en qué dirección ir a recoger las monedas y evitar a los enemigos.

Ahora, usando los términos MDP , significaría que crea una colección de estados (la grilla) que mantiene ciertas políticas (la acción a tomar -> arriba, abajo, derecha, izquierda) para un cierto estado (una posición en la grilla) ) Las políticas están determinadas por los valores de "utilidad" de cada estado, que a su vez se calculan al evaluar cuánto sería beneficioso obtenerla a corto y largo plazo.

¿Es esto correcto? ¿O estoy completamente en el camino equivocado?

Al menos me gustaría saber qué representan las variables de la siguiente ecuación en mi situación:

(tomado del libro "Inteligencia Artificial - Un Enfoque Moderno" de Russell y Norvig)

Sé que sería una lista de todos los cuadrados de la grilla, a sería una acción específica (arriba / abajo / derecha / izquierda), pero ¿y el resto?

¿Cómo se implementarían las funciones de recompensa y utilidad?

Sería realmente genial si alguien supiera un simple enlace que muestra pseudo-código para implementar una versión básica con similitudes a mi situación de una manera muy lenta, porque ni siquiera sé por dónde empezar aquí.

Gracias por tu precioso tiempo.

(Nota: siéntase libre de agregar / eliminar etiquetas o dígame en los comentarios si debería dar más detalles sobre algo o algo así).

Answer 1

No es una respuesta completa, sino una observación aclaratoria.

El estado no es una sola célula. El estado contiene la información de cada celda para todas las celdas involucradas a la vez. Esto significa que un elemento de estado contiene la información de qué celdas son sólidas y cuáles están vacías; cuales contienen monstruos; donde estan las monedas; donde esta el jugador

Tal vez podrías usar un mapa de cada celda para su contenido como estado. Esto ignora el movimiento de monstruos y jugadores, que probablemente también sean muy importantes.

Los detalles dependen de cómo quiera modelar su problema (decidir qué pertenece al estado y en qué forma).

Luego, una política asigna cada estado a una acción como izquierda, derecha, salto, etc.

Primero debe comprender el problema que expresa un MDP antes de pensar en cómo funcionan los algoritmos como la iteración de valores.

Answer 2

Sé que esta es una publicación bastante antigua, pero me encontré con ella cuando busqué preguntas relacionadas con MDP, quería señalar (para la gente que viene aquí) algunos comentarios más sobre cuándo dijiste qué eran "s" y "a" .

Creo que es absolutamente correcto que sea su lista de [arriba, abajo, izquierda, derecha].

Sin embargo, para s es realmente la ubicación en la grilla y s ''es la ubicación a la que puede ir. Lo que eso significa es que eliges un estado, y luego escoges un ''s'' en particular y realizas todas las acciones que te pueden llevar a ese sprime, que usas para descubrir esos valores. (elige un máximo de ésos). Finalmente, vaya a la siguiente s ''y haga lo mismo, cuando haya agotado todos los valores s'', entonces encontrará el máximo de lo que acaba de terminar de buscar.

Supongamos que eligió una celda de la cuadrícula en la esquina, solo tendría 2 estados a los que podría mudarse (asumiendo la esquina inferior izquierda), dependiendo de cómo elija "nombrar" sus estados, podríamos suponer en este caso que el estado es una coordenada x, y, por lo que su estado actual es 1,1 y su lista s ''(o s prime) es x + 1, y y x, y + 1 (no diagonal en este ejemplo) (La parte de suma que va sobre todo s '')

Además, no lo tienes en la ecuación, pero el máximo es de a o la acción que te da el máximo, así que primero escoges la s ''que te da el máximo y luego dentro de eso eliges la acción (al menos esta es mi comprensión del algoritmo).

Entonces si tuviste

x,y+1 left = 10
x,y+1 right = 5
x+1,y left = 3
x+1,y right 2

Elegirás x, y + 1 como tu s '', pero luego necesitarás elegir una acción que esté maximizada, que en este caso queda para x, y + 1. No estoy seguro de si hay una diferencia sutil entre simplemente encontrar el número máximo y encontrar el estado, luego el número máximo, así que tal vez alguien algún día pueda aclarar eso para mí.

Si tus movimientos son deterministas (es decir, si dices avanzar, avanzas con certeza al 100%), entonces es bastante fácil que tengas una acción. Sin embargo, si no son deterministas, puedes decir 80% de certeza, entonces debes considerar la otras acciones que podrían llevarte allí. Este es el contexto de la rueda resbaladiza que José mencionó anteriormente.

No quiero restarle importancia a lo que otros han dicho, sino solo dar algo de información adicional.

Answer 3

Sí, la notación matemática puede hacer que parezca mucho más complicado de lo que es. Realmente, es una idea muy simple. He implementado un applet de demostración de iteración de valor con el que puedes jugar para obtener una mejor idea.

Básicamente, digamos que tienes una grilla 2D con un robot. El robot puede intentar moverse hacia el norte, sur, este, oeste (esas son las acciones a) pero, como su rueda izquierda es resbaladiza, cuando intenta moverse hacia el norte, solo hay una probabilidad de .9 de que termine en la casilla Al norte de ella, mientras que hay una probabilidad de .1 que terminará en el cuadrado Oeste de la misma (de manera similar para las otras 3 acciones). Estas probabilidades son capturadas por la función T (). A saber, T (s, A, s '') se verá así:

s A s'' T //x=0,y=0 is at the top-left of the screen
x,y North x,y+1 .9 //we do move north
x,y North x-1,y .1 //wheels slipped, so we move West
x,y East x+1,y .9
x,y East x,y-1 .1
x,y South x,y+1 .9
x,y South x-1,y .1
x,y West x-1,y .9
x,y West x,y+1 .1

A continuación, establece la recompensa en 0 para todos los estados, pero 100 para el estado objetivo, es decir, la ubicación a la que desea que llegue el robot.

Lo que hace la iteración de valor es que comienza dando una Utilidad de 100 al estado objetivo y 0 a todos los demás estados. Luego, en la primera iteración, estas 100 utilidades se distribuyen en 1 paso desde la meta, por lo que todos los estados que puedan llegar al estado de la meta en 1 paso (las 4 casillas contiguas) obtendrán cierta utilidad. A saber, obtendrán una utilidad igual a la probabilidad de que desde ese estado podamos alcanzar la meta establecida. Luego continuamos iterando, en cada paso movemos la utilidad hacia atrás 1 paso más lejos de la meta.

En el ejemplo anterior, supongamos que comienza con R (5,5) = 100 y R (.) = 0 para todos los demás estados. Entonces el objetivo es llegar a 5,5.

En la primera iteración establecemos

R (5,6) = gamma * (.9 * 100) + gamma * (.1 * 100)

porque en 5,6 si vas al norte hay una probabilidad de .9 de terminar en 5,5, mientras que si vas al oeste hay una probabilidad de .1 de terminar en 5,5.

Del mismo modo para (5,4), (4,5), (6,5).

Todos los demás estados permanecen con U = 0 después de la primera iteración de la iteración del valor.

Answer 4

Yo recomendaría utilizar Q-learning para su implementación.

Tal vez puedas usar esta publicación que escribí como inspiración. Esta es una demostración de Q-learning con código fuente de Java . Esta demostración es un mapa con 6 campos y la IA aprende dónde debe ir desde cada estado para llegar a la recompensa.

Q-learning es una técnica para dejar que la IA aprenda por sí misma al darle recompensa o castigo.

Este ejemplo muestra el Q-learning utilizado para encontrar ruta. Un robot aprende dónde debe ir desde cualquier estado.

El robot comienza en un lugar aleatorio, mantiene la memoria del puntaje mientras explora el área, cada vez que alcanza la meta, repetimos con un nuevo inicio aleatorio. Después de suficientes repeticiones, los valores de puntaje serán estacionarios (convergencia).

En este ejemplo, el resultado de la acción es determinista (la probabilidad de transición es 1) y la selección de acción es aleatoria. Los valores de puntuación se calculan mediante el algoritmo Q-learning Q (s, a).
La imagen muestra los estados (A, B, C, D, E, F), las posibles acciones de los estados y la recompensa otorgada.

Resultado Q * (s, a)

Política Π * (s)

Qlearning.java

import java.text.DecimalFormat;
import java.util.Random;
/**
* @author Kunuk Nykjaer
*/
public class Qlearning {
final DecimalFormat df = new DecimalFormat("#.##");
// path finding
final double alpha = 0.1;
final double gamma = 0.9;
// states A,B,C,D,E,F
// e.g. from A we can go to B or D
// from C we can only go to C
// C is goal state, reward 100 when B->C or F->C
//
// _______
// |A|B|C|
// |_____|
// |D|E|F|
// |_____|
//
final int stateA = 0;
final int stateB = 1;
final int stateC = 2;
final int stateD = 3;
final int stateE = 4;
final int stateF = 5;
final int statesCount = 6;
final int[] states = new int[]{stateA,stateB,stateC,stateD,stateE,stateF};
// http://en.wikipedia.org/wiki/Q-learning
// http://people.revoledu.com/kardi/tutorial/ReinforcementLearning/Q-Learning.htm
// Q(s,a)= Q(s,a) + alpha * (R(s,a) + gamma * Max(next state, all actions) - Q(s,a))
int[][] R = new int[statesCount][statesCount]; // reward lookup
double[][] Q = new double[statesCount][statesCount]; // Q learning
int[] actionsFromA = new int[] { stateB, stateD };
int[] actionsFromB = new int[] { stateA, stateC, stateE };
int[] actionsFromC = new int[] { stateC };
int[] actionsFromD = new int[] { stateA, stateE };
int[] actionsFromE = new int[] { stateB, stateD, stateF };
int[] actionsFromF = new int[] { stateC, stateE };
int[][] actions = new int[][] { actionsFromA, actionsFromB, actionsFromC,
actionsFromD, actionsFromE, actionsFromF };
String[] stateNames = new String[] { "A", "B", "C", "D", "E", "F" };
public Qlearning() {
init();
}
public void init() {
R[stateB][stateC] = 100; // from b to c
R[stateF][stateC] = 100; // from f to c
}
public static void main(String[] args) {
long BEGIN = System.currentTimeMillis();
Qlearning obj = new Qlearning();
obj.run();
obj.printResult();
obj.showPolicy();
long END = System.currentTimeMillis();
System.out.println("Time: " + (END - BEGIN) / 1000.0 + " sec.");
}
void run() {
/*
1. Set parameter , and environment reward matrix R
2. Initialize matrix Q as zero matrix
3. For each episode: Select random initial state
Do while not reach goal state o
Select one among all possible actions for the current state o
Using this possible action, consider to go to the next state o
Get maximum Q value of this next state based on all possible actions o
Compute o Set the next state as the current state
*/
// For each episode
Random rand = new Random();
for (int i = 0; i < 1000; i++) { // train episodes
// Select random initial state
int state = rand.nextInt(statesCount);
while (state != stateC) // goal state
{
// Select one among all possible actions for the current state
int[] actionsFromState = actions[state];
// Selection strategy is random in this example
int index = rand.nextInt(actionsFromState.length);
int action = actionsFromState[index];
// Action outcome is set to deterministic in this example
// Transition probability is 1
int nextState = action; // data structure
// Using this possible action, consider to go to the next state
double q = Q(state, action);
double maxQ = maxQ(nextState);
int r = R(state, action);
double value = q + alpha * (r + gamma * maxQ - q);
setQ(state, action, value);
// Set the next state as the current state
state = nextState;
}
}
}
double maxQ(int s) {
int[] actionsFromState = actions[s];
double maxValue = Double.MIN_VALUE;
for (int i = 0; i < actionsFromState.length; i++) {
int nextState = actionsFromState[i];
double value = Q[s][nextState];
if (value > maxValue)
maxValue = value;
}
return maxValue;
}
// get policy from state
int policy(int state) {
int[] actionsFromState = actions[state];
double maxValue = Double.MIN_VALUE;
int policyGotoState = state; // default goto self if not found
for (int i = 0; i < actionsFromState.length; i++) {
int nextState = actionsFromState[i];
double value = Q[state][nextState];
if (value > maxValue) {
maxValue = value;
policyGotoState = nextState;
}
}
return policyGotoState;
}
double Q(int s, int a) {
return Q[s][a];
}
void setQ(int s, int a, double value) {
Q[s][a] = value;
}
int R(int s, int a) {
return R[s][a];
}
void printResult() {
System.out.println("Print result");
for (int i = 0; i < Q.length; i++) {
System.out.print("out from " + stateNames[i] + ": ");
for (int j = 0; j < Q[i].length; j++) {
System.out.print(df.format(Q[i][j]) + " ");
}
System.out.println();
}
}
// policy is maxQ(states)
void showPolicy() {
System.out.println("/nshowPolicy");
for (int i = 0; i < states.length; i++) {
int from = states[i];
int to = policy(from);
System.out.println("from "+stateNames[from]+" goto "+stateNames[to]);
}
}
}

Imprimir resultado

out from A: 0 90 0 72,9 0 0
out from B: 81 0 100 0 81 0
out from C: 0 0 0 0 0 0
out from D: 81 0 0 0 81 0
out from E: 0 90 0 72,9 0 90
out from F: 0 0 100 0 81 0
showPolicy
from a goto B
from b goto C
from c goto C
from d goto A
from e goto B
from f goto C
Time: 0.025 sec.