algorithm - マルコフ決定プロセス: 値の反復、どのように機能するか?

Question

最近、マルコフ決定プロセス (値の反復を使用)についてよく読んでいますが、それらについて理解することはできません。インターネットや書籍で多くのリソースを見つけましたが、それらはすべて、私の能力には複雑すぎる数式を使用しています。

これは大学での最初の年であるため、Web で提供されている説明や数式は、私には複雑すぎる概念や用語を使用しており、読者が私が聞いたことのない特定のことを知っていると想定していることがわかりました。 .

2Dグリッドで使用したい（壁（達成不可能）、コイン（望ましい）、動く敵（これは絶対に避けなければならない）でいっぱい）。全体的な目標は、敵に触れずにすべてのコインを集めることです。マルコフ決定プロセス ( MDP )を使用して、メイン プレイヤー用の AI を作成したいと考えています。これは部分的にどのように見えるかです (ゲーム関連の側面はここではそれほど重要ではないことに注意してください. MDPの一般的な理解を本当に望んでいます):

私が理解していることから、MDP の無礼な単純化は、MDPが、進む必要がある方向を保持するグリッドを作成できることです (グリッド上の特定の位置から開始して、進む必要がある場所を指す「矢印」のグリッドのようなものです)。 ) 特定の目標を達成し、特定の障害物を回避します。私の状況に特有のことですが、それは、プレイヤーがコインを集めて敵を避けるためにどの方向に行くべきかを知ることができることを意味します.

ここで、MDP用語を使用すると、特定の状態 (グリッド上の位置) に対して特定のポリシー (実行するアクション -> 上、下、右、左) を保持する状態のコレクション (グリッド) を作成することを意味します。 ）。ポリシーは、各状態の「効用」値によって決定されます。この値自体は、そこに到達することが短期的および長期的にどれだけ有益であるかを評価することによって計算されます。

これは正しいです？それとも、私は完全に間違った方向に進んでいますか?

少なくとも、次の式の変数が私の状況で何を表しているか知りたいです。

(Russell & Norvig の本「Artificial Intelligence - A Modern Approach」から引用)

sグリッドからのすべての正方形のリストであり、特定のアクション (上/下/右/左) になることはわかっていaますが、残りはどうですか?

報酬関数と効用関数はどのように実装されますか?

ここからどこから始めればよいかさえわからないので、私の状況に似た基本的なバージョンを非常に遅い方法で実装するための疑似コードを示す簡単なリンクを誰かが知っていれば、本当に素晴らしいことです。

貴重な時間をありがとうございました。

（注：タグを追加/削除するか、何かまたはそのようなものについて詳細を提供する必要がある場合は、コメントで教えてください。）

Answer 1

はい、数学表記は、実際よりもはるかに複雑に見える可能性があります。本当に、それは非常に単純な考えです。より良いアイデアを得るために使用できる値反復デモ アプレットを実装しました。

基本的に、ロボットを含む 2D グリッドがあるとします。ロボットは北、南、東、西に移動しようとすることができます (これらはアクション a) ですが、左の車輪が滑りやすいため、北に移動しようとすると、正方形にたどり着く確率は 0.9 しかありません。 .1 の確率でその北に移動しますが、それがその西の正方形に到達する確率は .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 になる確率が .9 あり、西に行くと 5.5 になる確率が .1 になるからです。

(5,4)、(4,5)、(6,5) についても同様です。

他のすべての状態は、値の反復の最初の反復の後、U = 0 のままです。

Answer 2

完全な答えではありませんが、明確な発言です。

状態は単一のセルではありません。状態には、関連するすべてのセルの各セルにある情報が一度に含まれています。これは、1 つの状態要素に、どのセルがソリッドでどのセルが空であるかという情報が含まれていることを意味します。モンスターが含まれているもの。コインはどこにありますか。プレーヤーはどこですか。

おそらく、各セルからそのコンテンツへのマップを状態として使用できます。これはおそらく非常に重要なモンスターとプレイヤーの動きを無視します。

詳細は、問題をどのようにモデル化するかによって異なります (何が状態に属し、どの形式であるかを決定します)。

次に、ポリシーが各状態を左、右、ジャンプなどのアクションにマップします。

値の反復などのアルゴリズムがどのように機能するかを考える前に、まず MDP によって表現される問題を理解する必要があります。

Answer 3

実装には Q ラーニングを使用することをお勧めします。

ひょっとしたら、私が書いたこの記事をインスピレーションとして使っていただけるかもしれません。これは、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.

Answer 4

これはかなり古い投稿であることは知っていますが、MDP 関連の質問を探しているときに見つけました。(ここに来る人のために)「s」と「a」が何であるかを述べたときのコメントをいくつか書き留めておきたいと思います。 .

あなたが絶対に正しいと思うのは、[上、下、左、右]のリストです。

ただし、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% の確実性で前進することを意味します)、1 つのアクションを実行するのは非常に簡単です。あなたをそこに連れて行くことができる他の行動。これは、ホセが上で述べた滑りやすい車輪の文脈です。

他の人が言ったことを否定するつもりはありませんが、追加情報を提供したいだけです。