Q-learningで迷路を解く

上記のような迷路をQ-learningで解いていきます。

やり始めたきっかけ

もともとゲーム木探索アルゴリズムで最弱オセロを作っていましたが、機械学習で作りたいと思い、DQNを使う必要がありました。そこで手始めに、簡単なQ-learningを作ってみることにしました。

迷路のルール

□マークは通過できない
何もないマスは通過できて、0.5点の失点
×マークのマスは、通過できて、1点の失点

これらのルールをもとに、S(スタート）からG（ゴール）まで、最も失点が少ないルートを探索します。

迷路の環境を実装

以下、迷路の環境のコードです。後ほど解説していきます。

#Maze.py

class Direction():
UP = -12
DOWN = + 12
LEFT = -1
RIGHT = +1


class Maze:
    def __init__(self):
        self.maze = [
            "□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□",
            "□", "S", " ", " ", " ", " ", " ", " ", " ", " ", " ", "□",
            "□", "□", " ", "×", " ", "□", "□", "□", "□", "□", "□", "□",
            "□", "□", " ", "×", " ", "□", " ", " ", " ", "×", " ", "□",
            "□", "□", " ", "×", "□", "□", " ", "×", " ", " ", " ", "□",
            "□", "□", " ", "×", "□", "□", " ", "□", "□", "□", " ", "□",
            "□", "□", " ", " ", "□", "□", " ", "□", "□", "□", " ", "□",
            "□", " ", "×", " ", " ", "×", " ", " ", " ", "□", " ", "□",
            "□", " ", " ", " ", " ", " ", " ", " ", " ", "□", "G", "□",
            "□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□"
        ]
        self.position = 13

    def initialize(self):
        self.position = 13

    def print_map(self):
        for y in range(len(self.maze)):
            if (y + 1) % 12 != 0:
                if y == self.position:
                    print("P", end='')
                else:
                    print(self.maze[y], end='')                    
            else:
                if y == self.position:
                    print("P")
                else:
                    print(self.maze[y])


    def step(self, direction):
        if direction + self.position>= 0 and \
            direction + self.position <= 120 and \
            self.maze[direction + self.position] != "□":
            self.position = self.position + direction


    def is_goal(self):
        if self.maze[self.position] == "G":
            return True
        else:
            return False
    
    def reward(self):
        if self.maze[self.position] == "×":
            return -1
        elif self.maze[self.position] == " " or self.maze[self.position] == "S":
            return -0.5
        else:
            return 0
    
    def get_position(self):
        return self.position

迷路を定義

Mazeクラスに迷路を定義します

class Maze:
    def __init__(self):
        self.maze = [
            "□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□",
            "□", "S", " ", " ", " ", " ", " ", " ", " ", " ", " ", "□",
            "□", "□", " ", "×", " ", "□", "□", "□", "□", "□", "□", "□",
            "□", "□", " ", "×", " ", "□", " ", " ", " ", "×", " ", "□",
            "□", "□", " ", "×", "□", "□", " ", "×", " ", " ", " ", "□",
            "□", "□", " ", "×", "□", "□", " ", "□", "□", "□", " ", "□",
            "□", "□", " ", " ", "□", "□", " ", "□", "□", "□", " ", "□",
            "□", " ", "×", " ", " ", "×", " ", " ", " ", "□", " ", "□",
            "□", " ", " ", " ", " ", " ", " ", " ", " ", "□", "G", "□",
            "□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□", "□"
        ]
        self.position = 13

左上から、
0,1,2, ... , 10,11,
12,13, ...,
という順に、１次の配列に格納します。

self.position = 13

は、迷路の"S"地点に初期位置を設定しています。

    def initialize(self):
        self.position = 13

迷路を１回解き終わったら、初期位置に戻すために、関数を用意しておきます。

class Direction():
UP = -12
DOWN = + 12
LEFT = -1
RIGHT = +1

迷路は12×10のサイズです。下に移動するときは、現在位置に12を加えれば良いです。上下左右に移動するためのクラスDirectionを用意します。

    def print_map(self):
        for y in range(len(self.maze)):
            if (y + 1) % 12 != 0:
                if y == self.position:
                    print("P", end='')
                else:
                    print(self.maze[y], end='')                    
            else:
                if y == self.position:
                    print("P")
                else:
                    print(self.maze[y])

標準出力に、迷路を表示するための関数です。迷路の配列mazeをループさせてprintしますが、現在位置(position)のところだけpをprintします。

    def step(self, direction):
        if direction + self.position>= 0 and \
            direction + self.position <= 120 and \
            self.maze[direction + self.position] != "□":
            self.position = self.position + directio

引数のDirectionの値を受け取り、その方向にpositionを移動させるstep関数です。□マスの方向には移動できません。

    def is_goal(self):
        if self.maze[self.position] == "G":
            return True
        else:
            return False

positionが、迷路の"G"と重なったとき、ゴールしたという判定をします。

    def reward(self):
        if self.maze[self.position] == "×":
            return -1
        elif self.maze[self.position] == " " or self.maze[self.position] == "S":
            return -0.5
        else:
            return 0

報酬関数rewardです。positionが×の上にいたら-1、空白マスにいたら-0.5を返します。□マスの方向に移動しようとしても、移動することはできず、無駄に-1を食らいます。こうすることで、壁に向かって進もうとしなくなります。

    def get_position(self):
        return self.position

最後に、positionを返す関数です。

ここまでで、迷路の環境を作りました。まだ強化学習、Q-learningに関するコードは記載していません。次回は、迷路を実際に学習して、解くためのエージェントのコードを紹介します。