Марковский процесс принятия решений: итерация значения, как она работает?

Question

Я много читал о Марковских процессах принятия решений (с использованием итерации значений) в последнее время, но я просто не могу разобраться с ними.Я нашел много ресурсов в Интернете / книгах, но все они используют математические формулы, которые слишком сложны для моей компетенции.

Поскольку это мой первый год в колледже, я обнаружил, что объяснения и формулы, представленные в Интернете, используют слишком сложные для меня понятия / термины, и они предполагают, что читатель знает некоторые вещи, которые яЯ просто никогда не слышал об этом.

Я хочу использовать его на двумерной сетке (заполненной стенами (недостижимой), монетами (желательно) и движущимися врагами (которых следует избегать любой ценой)).Вся цель состоит в том, чтобы собрать все монеты, не касаясь врагов, и я хочу создать ИИ для основного игрока, используя процесс принятия решений Маркова ( MDP ).Вот как это выглядит частично (обратите внимание, что аспект, связанный с игрой, здесь не так важен. Я просто очень хочу понять MDP в целом):

Из того, что я понимаю, грубое упрощение MDP заключается в том, что они могут создавать сетку, которая указывает, в каком направлении нам нужно идти (вид сетки "стрелок", указывающих, где мынужно идти, начиная с определенной позиции в сетке), чтобы достичь определенных целей и избежать определенных препятствий.Конкретно для моей ситуации это будет означать, что он позволяет игроку знать, в каком направлении идти, чтобы собирать монеты и избегать врагов.

Теперь, используя термины MDP , он будетозначает, что он создает коллекцию состояний (сетка), которая содержит определенные политики (действие, которое нужно выполнить -> вверх, вниз, вправо, влево) для определенного состояния (позиция в сетке).Политики определяются значениями «полезности» каждого состояния, которые сами рассчитываются путем оценки того, сколько прибыли будет полезно в краткосрочной и долгосрочной перспективе.

Это правильно?Или я совершенно не на том пути?

Мне бы хотя бы хотелось узнать, что представляют собой переменные из следующего уравнения в моей ситуации:

(взято из книги «Искусственный интеллект - современный подход» Рассела и Норвиг)

Я знаю, что s будет списком всех квадратов из сетки, a будет конкретным действием(вверх / вниз / вправо / влево), но как насчет остальных?

Как будут реализованы функции вознаграждения и полезности?

Было бы действительно здорово, если бы кто-то знал простую ссылку, котораяпоказывает псевдокод для медленной реализации базовой версии с сходством с моей ситуацией, потому что я даже не знаю, с чего начать.

Спасибо за ваше драгоценное время.

(Примечание: не стесняйтесь добавлять / удалять теги или сообщать мне в комментариях, если я должен дать более подробную информацию о чем-либо или о чем-то подобном.)

Answer 1

Да, математическая запись может показаться намного более сложной, чем она есть.На самом деле, это очень простая идея.У меня есть реализованный демонстрационный апплет value итерации , с которым вы можете поиграть, чтобы получить лучшее представление.

По существу, предположим, что у вас есть двумерная сетка с роботом.Робот может попытаться переместиться на север, юг, восток, запад (это действия а), но, поскольку его левое колесо скользкое, когда он пытается двигаться на север, существует только 0,9 вероятность того, что он окажется на площади.К северу от него, в то время как есть вероятность .1, что он окажется в квадрате к западу от него (аналогично для 3 других действий).Эти вероятности фиксируются функцией T ().А именно, T (s, A, s ') будет выглядеть следующим образом:

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 

Затем вы устанавливаете вознаграждение равным 0 для всех состояний, но 100 для целевого состояния, то есть местоположения, которое вы хотитеРобот, к которому нужно добраться.

Итерация значения состоит в том, что она запускается, давая Утилите 100 для состояния цели и 0 для всех остальных состояний.Затем на первой итерации эти 100 утилит распределяются назад на 1 шаг от цели, поэтому все состояния, которые могут перейти к целевому состоянию за 1 шаг (все 4 квадрата рядом с ним), получат некоторую полезность.А именно, они получат Утилиту, равную вероятности того, что из этого состояния мы сможем добраться до указанной цели.Затем мы продолжаем итерацию, на каждом шаге мы перемещаем утилиту назад еще на 1 шаг от цели.

В приведенном выше примере, скажем, вы начинаете с R (5,5) = 100 и R (.) =0 для всех остальных штатов.Таким образом, цель состоит в том, чтобы получить 5,5.

На первой итерации мы устанавливаем

R (5,6) = гамма * (.9 * 100) + гамма * (.1* 100)

, потому что на 5,6, если вы идете на север, вероятность того, что вы окажетесь на 5,5, составит 0,9, тогда как на западе вероятность того, что вы окажетесь на 5,5, составит 0,1..

Аналогично для (5,4), (4,5), (6,5).

Все остальные состояния остаются с U = 0 после первой итерации итерации значения.

Answer 2

Я бы рекомендовал использовать Q-learning для вашей реализации.

Может быть, вы можете использовать этот пост, который я написал, как вдохновение. Это демонстрация Q-обучения с исходным кодом Java . Это демо-карта с 6 полями, и ИИ узнает, куда ему следует идти из каждого состояния, чтобы получить награду.

Q-learning - это метод, позволяющий ИИ учиться самостоятельно, давая ему награду или наказание.

В этом примере показано Q-обучение, используемое для поиска пути. Робот узнает, куда он должен идти из любого состояния.

Робот запускается в произвольном месте, он сохраняет память о счете, пока он исследует область, всякий раз, когда он достигает цели, мы повторяем с новым случайным началом. После достаточного количества повторений значения баллов будут стационарными (конвергенция).

В этом примере результат действия является детерминированным (вероятность перехода равна 1), а выбор действия является случайным. Значения баллов рассчитываются по алгоритму Q-обучения Q (s, a).
На изображении показаны состояния (A, B, C, D, E, F), возможные действия из состояний и данное вознаграждение.

Результат Q * (s, a)

Политика Π * (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]);
        }          
    }
}

Результат печати

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.

Answer 3

Не полный ответ, а уточняющее замечание.

Состояние равно , а не одной ячейке.Состояние содержит информацию о том, что находится в каждой ячейке для всех соответствующих ячеек одновременно.Это означает, что один элемент состояния содержит информацию о том, какие ячейки являются сплошными, а какие - пустыми;какие из них содержат монстров;где монеты;где игрок.

Может быть, вы могли бы использовать карту из каждой ячейки для ее содержимого в качестве состояния.Это игнорирует движение монстров и игроков, что, вероятно, также очень важно.

Детали зависят от того, как вы хотите смоделировать свою проблему (решить, что принадлежит состоянию и в какой форме).

Затем политика отображает каждое состояние в действие, например, влево, вправо, прыжок и т. Д.

Сначала вы должны понять проблему, выраженную MDP, прежде чем думать о том, как работают алгоритмы, такие как итерация значения.

Answer 4

Я знаю, что это довольно старый пост, но я наткнулся на него, когда искал вопросы, связанные с MDP, я хотел бы отметить (для людей, которые приходят сюда) еще несколько комментариев о том, когда вы указали, что "s" и " "были.

Я думаю, что вы абсолютно правы, это ваш список [вверх, вниз, влево, вправо].

Однако для s это действительно местоположение в сетке, а s '- это место, куда вы можете перейти. Это означает, что вы выбираете состояние, а затем выбираете определенное «s» и проходите через все действия, которые могут привести вас к этому спрайму, которые вы используете, чтобы выяснить эти значения. (выберите максимум из них). Наконец, вы переходите к следующим s и делаете то же самое, когда вы исчерпали все значения s, вы найдете максимум того, на чем вы только что закончили поиск.

Предположим, что вы выбрали ячейку сетки в углу, у вас было бы только 2 состояния, в которые вы могли бы перейти (при условии, что левый нижний угол), в зависимости от того, как вы решили «назвать» свои состояния, мы могли бы в этом случае предположить состояние - это координата x, y, поэтому текущее состояние s равно 1,1, а список s (или простое число s) равен x + 1, y и x, y + 1 (в этом примере диагональ отсутствует) (Суммирование часть, которая проходит через все s ')

Кроме того, вы не перечислили его в своем уравнении, но максимум равен a или действию, которое дает вам максимум, поэтому сначала вы выбираете s ', которое дает вам максимум, а затем в пределах этого вы выбираете действие (по крайней мере, это мое понимание алгоритма).

Так что, если у вас было

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

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

Вы выберете x, y + 1 в качестве s, но затем вам нужно будет выбрать максимизированное действие, которое в этом случае оставлено для x, y + 1. Я не уверен, есть ли небольшая разница между нахождением максимального числа и нахождением состояния, а затем максимального числа, хотя, возможно, кто-нибудь когда-нибудь сможет уточнить это для меня.

Если ваши движения являются детерминированными (то есть, если вы говорите, идите вперед, вы идете вперед со 100% уверенностью), то довольно легко у вас есть одно действие, однако, если они недетерминированы, у вас есть уверенность 80%, то вы следует рассмотреть другие действия, которые могут привести вас туда. Это контекст скользкого колеса, о котором упоминал Хосе.

Я не хочу умалять то, что говорили другие, а просто дать некоторую дополнительную информацию.