马尔可夫决策过程:价值迭代,它是如何运作的？

我最近一直在阅读很多关于Markov Decision Processes(使用价值迭代)的内容,但我根本无法理解它们.我在互联网/书籍上找到了很多资源,但他们都使用的数学公式对我的能力来说过于复杂.

由于这是我上大学的第一年,我发现网上提供的解释和公式使用的概念/术语对我来说太复杂了,他们认为读者知道我从未听说过的某些事情. .

我想在2D网格上使用它(填充墙壁(无法实现),硬币(可取)和移动的敌人(必须不惜一切代价避免)).整个目标是收集所有硬币而不触及敌人,我想使用马尔可夫决策过程(MDP)为主要玩家创建AI .以下是它的部分外观(请注意,与游戏相关的方面在这里并不是很重要.我只是想了解一般的MDP):

根据我的理解,MDP的粗略简化是它们可以创建一个网格,它保持我们需要去的方向(指向我们需要去的地方的"箭头"网格的类型,从网格上的某个位置开始)达到某些目标并避免某些障碍.具体到我的情况,这意味着它允许玩家知道去哪个方向收集硬币并避开敌人.

现在,使用MDP术语,这意味着它创建了一个状态集合(网格),它保存某个特定状态的某些策略(要采取的操作 - >上,下,右,左)(网格上的一个位置) ).这些政策由每个州的"效用"值决定,这些价值本身是通过评估在短期和长期内获得多少益处来计算的.

它是否正确？还是我完全走错了路？

我至少想知道以下等式中的变量在我的情况中代表什么:

(取自Russell&Norvig的"人工智能 - 现代方法"一书)

我知道这s将是网格中所有方块的列表,a将是一个特定的动作(上/下/右/左),但其余的呢？

如何实施奖励和效用函数？

如果有人知道一个简单的链接,显示伪代码以非常慢的方式实现与我的情况相似的基本版本,那将是非常好的,因为我甚至不知道从哪里开始.

谢谢你宝贵的时间.

(注意:随意添加/删除标签或在评论中告诉我是否应该提供有关某些内容或类似内容的更多详细信息.)

是的,数学符号可以使它看起来比它复杂得多.真的,这是一个非常简单的想法.我已经实现了一个值迭代演示applet,您可以使用它来获得更好的想法.

基本上,假设您有一个带有机器人的2D网格.机器人可以尝试移动北,南,东,西(这些是动作a),但是,因为它的左轮是滑的,当它试图向北移动时,只有.9概率它最终会在广场上在它的北边,虽然它有一个概率,它最终会在它的西边(相似的其他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个实用程序从目标分配回一步,因此所有可以一步到达目标状态的状态(紧邻它的所有4个方格)将获得一些效用.也就是说,他们将得到一个效用等于从该状态我们可以达到所述目标的概率.然后我们继续迭代,在每个步骤中,我们将实用程序从目标移开1步.

在上面的例子中,假设你从所有其他状态的R(5,5)= 100和R(.)= 0开始.所以目标是达到5,5.

在我们设置的第一次迭代中

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

因为在5,6,如果你去北方有一个.9的概率最终在5,5,而如果你去西方有一个.1概率最终在5,5.

类似地,对于(5,4),(4,5),(6,5).

在值迭代的第一次迭代之后,所有其他状态保持U = 0.

我建议您使用Q-learning来实现.

也许你可以使用我写的这篇文章作为灵感.这是一个带有Java源代码的Q学习演示.这个演示是一个包含6个字段的地图,AI了解每个州应该从哪里获得奖励.

Q-learning是一种让AI通过给予奖励或惩罚来自学的技巧.

此示例显示用于路径查找的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.