Решение лабиринта с помощью обучения с подкреплением

Решение лабиринта с помощью обучения с подкреплением

Реализация алгоритма итерации значений в PyGame

Добро пожаловать в этот блог, где мы будем реализовывать алгоритм обучения с подкреплением для решения лабиринта! Я проведу вас через шаги создания среды лабиринта, определения класса лабиринта и использования алгоритма Value Iteration для поиска оптимальной политики для навигации по лабиринту. Для визуализации процесса мы смоделируем решение лабиринта с помощью PyGame, что сделает процесс обучения более увлекательным и приятным.

Настройка проекта:

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

# Create a virtual environment
python -m venv venv

# Activate the virtual environment on Windows
venv\Scripts\activate.bat

# Activate the virtual environment on macOS
source venv/bin/activate

# Install dependencies
pip install -r requirements.txt

Создание класса “Лабиринт”:

Начнем с определения класса Maze, который будет представлять нашу среду лабиринта. Класс будет включать атрибуты и методы, связанные с созданием лабиринта и обучением с подкреплением.

import numpy as np
import random
from typing import Tuple

class Maze:
    def __init__(self, level, goal_pos: Tuple[int, int], MAZE_HEIGHT=600, MAZE_WIDTH=600, SIZE=25):
        # Attributes for maze configuration
        self.goal = goal_pos
        self.number_of_tiles = SIZE
        self.tile_size = MAZE_HEIGHT // self.number_of_tiles
        self.walls = self.create_walls(level)
        self.goal_pos = goal_pos
        self.state = self.get_init_state(level)
        self.maze = self.create_maze(level)

        # Attributes for reinforcement learning
        self.state_values = np.zeros((self.number_of_tiles, self.number_of_tiles))
        self.policy_probs = np.full((self.number_of_tiles, self.number_of_tiles, 4), 0.25)

Создание лабиринта:

Далее реализуем методы для создания лабиринта и определения начального состояния.

def create_maze(self, level):
    maze = []
    walls = []
    for row in range(len(level)):
        for col in range(len(level[row])):
            if level[row][col] == " ":
                maze.append((row, col))
            elif level[row][col] == "X":
                walls.append((row, col))
    return maze, walls

def get_init_state(self, level):
    for row in range(len(level)):
        for col in range(len(level[row])):
            if level[row][col] == "P":
                return (row, col)

Шаги и вычисление вознаграждения:

Теперь определим методы для вычисления вознаграждения, моделирования шагов и получения следующего состояния.

def compute_reward(self, state: Tuple[int, int], action: int):
    next_state = self._get_next_state(state, action)
    return -float(state != self.goal_pos)

def step(self, action):
    next_state = self._get_next_state(self.state, action)
    reward = self.compute_reward(self.state, action)
    done = next_state == self.goal
    return next_state, reward, done

def simulate_step(self, state, action):
    next_state = self._get_next_state(state, action)
    reward = self.compute_reward(state, action)
    done = next_state == self.goal
    return next_state, reward, done

def _get_next_state(self, state: Tuple[int, int], action: int):
    if action == 0:
        next_state = (state[0], state[1] - 1)
    elif action == 1:
        next_state = (state[0] - 1, state[1])
    elif action == 2:
        next_state = (state[0], state[1] + 1)
    elif action == 3:
        next_state = (state[0] + 1, state[1])
    else:
        raise ValueError("Action value not supported:", action)
    if (next_state[0], next_state[1]) not in self.walls:
        return next_state
    return state

Разгадка лабиринта:

Наконец, реализуем алгоритм Value Iteration для решения лабиринта и нахождения оптимальной политики.

def solve(self, gamma=0.99, theta=1e-6):
    delta = float("inf")
 
    while delta > theta:
        delta = 0
        for row in range(self.number_of_tiles):
            for col in range(self.number_of_tiles):
                if (row, col) not in self.walls:
                    old_value = self.state_values[row, col]
                    q_max = float("-inf")

                    for action in range(4):
                        next_state, reward, done = self.simulate_step((row, col), action)
                        value = reward + gamma * self.state_values[next_state]
                        if value > q_max:
                            q_max = value
                            action_probs = np.zeros(shape=(4))
                            action_probs[action] = 1

                    self.state_values[row, col] = q_max
                    self.policy_probs[row, col] = action_probs

                    delta = max(delta, abs(old_value - self.state_values[row, col]))

Метод solve является ядром алгоритма обучения с подкреплением, используемого для поиска оптимальной политики перемещения по лабиринту. В нем используется метод Value Iteration, представляющий собой итерационный алгоритм, который постепенно обновляет оценочные значения каждого состояния до тех пор, пока они не сходятся к оптимальным значениям.

1.Инициализация:

  • gamma: Коэффициент дисконтирования для будущих вознаграждений (значение по умолчанию: 0,99). Этот коэффициент определяет важность немедленного вознаграждения по сравнению с будущим. При большем значении гаммы агент больше ценит долгосрочные вознаграждения, а при меньшем – ориентируется на немедленные.
  • theta: Порог сходимости (значение по умолчанию: 1e-6). Этот параметр определяет минимальное изменение значений состояния, которое будет считаться сходимостью. Как только изменение значений состояний становится меньше этого порога, алгоритм прекращает итерацию.
  • delta: Инициализированная на бесконечность переменная, которая будет использоваться для измерения изменения значений состояния в ходе итерации.

2.Итеративное обновление значений:

  • Метод использует цикл while, который продолжается до тех пор, пока изменение значений состояний (дельта) не станет меньше заданного порога сходимости (тета).
  • В цикле переменная delta перед каждой итерацией сбрасывается в 0, чтобы отследить максимальное изменение значений состояния по всем состояниям.

3. Итерация значений:

  • Для каждой клетки лабиринта (за исключением стен) алгоритм вычисляет значение Q (q_max) для всех возможных действий (вверх, вниз, влево, вправо).
  • Q-value представляет собой ожидаемое кумулятивное вознаграждение, которое агент может получить, предприняв определенное действие в данном состоянии и следуя в дальнейшем оптимальной политике.
  • Q-значение определяется на основе немедленного вознаграждения, полученного методом simulate_step, и дисконтированного значения стоимости следующего состояния (gamma * self.state_values[next_state]).
  • Действие с максимальным значением Q-value (q_max) выбирается в качестве наилучшего действия в текущем состоянии.
  • Для обновления политики соответствующие вероятности политики (action_probs) обновляются, чтобы отразить, что это действие имеет наибольшую вероятность быть выбранным. Вероятности для всех остальных действий устанавливаются в 0.

4. Обновление значений состояний и вероятностей политики:

  • После вычисления Q-значений для всех действий в данном состоянии значение состояния (self.state_values[row, col]) для этого состояния обновляется до максимального Q-значения (q_max) среди всех действий.
  • Вероятности политики (self.policy_probs[row, col]) для этого состояния обновляются таким образом, чтобы вероятность действия, которое привело к максимальному значению Q, была высокой (1,0), а вероятность всех остальных действий была равна 0.
  • Этот процесс продолжается для всех состояний лабиринта, итеративно обновляя значения состояний и вероятности политики до тех пор, пока не будет достигнут порог сходимости.

5. Проверка конвергенции:

  • После обновления значений состояний и вероятностей политики для всех состояний лабиринта метод проверяет, меньше ли максимальное изменение значений состояний (дельта) на данной итерации порога сходимости (тета).
  • Если условие выполнено, то цикл завершается, и процесс решения лабиринта считается сходящимся. В этот момент массив self.state_values содержит оптимальные значения для каждого состояния, а массив self.policy_probs отражает оптимальную политику движения по лабиринту.

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

Моделирование робота с помощью PyGame

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

Для начала создайте новый Python-скрипт main.py и добавьте в него следующий код:

import pygame
import numpy as np
from maze import Maze
import threading

# Constants
GAME_HEIGHT = 600
GAME_WIDTH = 600
NUMBER_OF_TILES = 25
SCREEN_HEIGHT = 700
SCREEN_WIDTH = 700
TILE_SIZE = GAME_HEIGHT // NUMBER_OF_TILES

# Maze layout
level = [
    "XXXXXXXXXXXXXXXXXXXXXXXXX",
    "X XXXXXXXX          XXXXX",
    "X XXXXXXXX  XXXXXX  XXXXX",
    "X      XXX  XXXXXX  XXXXX",
    "X      XXX  XXX        PX",
    "XXXXXX  XX  XXX        XX",
    "XXXXXX  XX  XXXXXX  XXXXX",
    "XXXXXX  XX  XXXXXX  XXXXX",
    "X  XXX      XXXXXXXXXXXXX",
    "X  XXX  XXXXXXXXXXXXXXXXX",
    "X         XXXXXXXXXXXXXXX",
    "X             XXXXXXXXXXX",
    "XXXXXXXXXXX      XXXXX  X",
    "XXXXXXXXXXXXXXX  XXXXX  X",
    "XXX  XXXXXXXXXX         X",
    "XXX                     X",
    "XXX         XXXXXXXXXXXXX",
    "XXXXXXXXXX  XXXXXXXXXXXXX",
    "XXXXXXXXXX              X",
    "XX   XXXXX              X",
    "XX   XXXXXXXXXXXXX  XXXXX",
    "XX    XXXXXXXXXXXX  XXXXX",
    "XX        XXXX          X",
    "XXXX                    X",
    "XXXXXXXXXXXXXXXXXXXXXXXXX",
]

# Create the maze environment
env = Maze(
    level,
    goal_pos=(23, 20),
    MAZE_HEIGHT=GAME_HEIGHT,
    MAZE_WIDTH=GAME_WIDTH,
    SIZE=NUMBER_OF_TILES,
)
env.reset()
env.solve()

# Initialize Pygame
pygame.init()

# Create the game window
screen = pygame.display.set_mode((SCREEN_HEIGHT, SCREEN_WIDTH))
pygame.display.set_caption("Maze Solver")

# Create a surface to draw the maze
surface = pygame.Surface((GAME_HEIGHT, GAME_WIDTH))

# Set the frame rate
clock = pygame.time.Clock()

# Running flag for the game loop
running = True

# Get the initial player and goal positions
treasure_pos = env.goal_pos
player_pos = env.state


def reset_goal():
    # Check if the player reached the goal, then reset the goal
    if env.state == env.goal_pos:
        env.reset()
        env.solve()


# Game loop
while running:
    # Start a new thread to check and reset the goal
    x = threading.Thread(target=reset_goal)
    x.daemon = True
    x.start()

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

    # Clear the surface
    surface.fill((27, 64, 121))

    # Draw the walls in the maze
    for row in range(len(level)):
        for col in range(len(level[row])):
            if level[row][col] == "X":
                pygame.draw.rect(
                    surface,
                    (241, 162, 8),
                    (col * TILE_SIZE, row * TILE_SIZE, TILE_SIZE, TILE_SIZE),
                )

    # Draw the player's position
    pygame.draw.rect(
        surface,
        (255, 51, 102),
        pygame.Rect(
            player_pos[1] * TILE_SIZE,
            player_pos[0] * TILE_SIZE,
            TILE_SIZE,
            TILE_SIZE,
        ).inflate(-TILE_SIZE / 3, -TILE_SIZE / 3),
        border_radius=3,
    )

    # Draw the goal position
    pygame.draw.rect(
        surface,
        "green",
        pygame.Rect(
            env.goal_pos[1] * TILE_SIZE,
            env.goal_pos[0] * TILE_SIZE,
            TILE_SIZE,
            TILE_SIZE,
        ).inflate(-TILE_SIZE / 3, -TILE_SIZE / 3),
        border_radius=TILE_SIZE,
    )

    # Update the screen
    screen.blit(
        surface, ((SCREEN_HEIGHT - GAME_HEIGHT) / 2

Пояснение к коду:

  1. Импорт библиотек и создание констант:
  • В коде импортируются необходимые библиотеки, включая Pygame, NumPy и пользовательский класс Maze.
  • Определяется несколько констант для настройки окружения лабиринта, размеров экрана и размеров плиток.

2. Создайте окружение лабиринта:

  • Схема лабиринта задается с помощью списка строк, называемого level.
  • Создается экземпляр класса Maze, которому в качестве параметров передаются уровень и положение цели.
  • Объект envobject используется для перезагрузки лабиринта и поиска оптимальной политики с помощью метода solve.

3. Инициализация PyGame

4. Основной цикл игры:

  • Программа входит в цикл, который выполняется до тех пор, пока переменная running не станет равной False.
  • Функция reset_goal вызывается в отдельном потоке, чтобы проверить, достиг ли игрок цели, и при необходимости сбросить цель.

5. Рисование лабиринта:

  • Лабиринт рисуется на экране путем итераций по левеллисту и рисования плиток на основе символов стены (“X”).
  • Позиция игрока рисуется в виде прямоугольника, залитого определенным цветом (красным) и центрированного в ячейке лабиринта.
  • Позиция цели рисуется в виде зеленого прямоугольника со скругленными углами.

6. Обновление состояния игры и движения игрока:

  • Действия игрока определяются на основе текущей политики (env.policy_probs) в позиции игрока. Действие с наибольшей вероятностью выбирается с помощью np.argmax.
  • На основе выбранного действия обновляется позиция игрока, если это правильный ход (не задевает стены).
  • Также обновляется позиция игрока в объекте envobject.

7. Выход из игры:

  • Цикл игры завершается, когда переменная running становится равной False, что обычно вызывается закрытием пользователем окна игры.
  • Pygame закрывается с помощью pygame.quit().

Теперь можно просто запустить файл main.py и увидеть код в действии.

Заключение:

Поздравляем! Вы успешно реализовали алгоритм Value Iteration для решения лабиринта с помощью обучения с подкреплением. Кроме того, вы визуализировали процесс решения лабиринта с помощью PyGame, что сделало его более интерактивным и приятным. Не стесняйтесь экспериментировать с различными конфигурациями лабиринта, скоростью обучения и коэффициентами дисконтирования, чтобы увидеть, как они влияют на процесс обучения. Удачного решения лабиринта!

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

+1
0
+1
0
+1
0
+1
0
+1
0
Просмотры: 616

Похожие записи

Ответить

Ваш адрес email не будет опубликован. Обязательные поля помечены *