PyGame реализация алгоритма итерации значений
Добро пожаловать в этот блог, где мы реализуем алгоритм обучения с подкреплением для прохождения лабиринта! Я проведу вас через этапы создания среды лабиринта, определения класса лабиринта и использования алгоритма итерации значений для поиска оптимальной политики навигации по лабиринту. Чтобы визуализировать процесс, мы смоделируем решение лабиринта с помощью PyGame, что сделает процесс обучения более увлекательным и приятным.
Вы можете найти полный код и ресурсы в следующем репозитории GitHub:
Репозиторий GitHub: https://github.com/akshayballal95/reinforcement_learning_maze.git
Настройка проекта:
Прежде чем мы начнем, давайте настроим проект, создав виртуальную среду и установив необходимые зависимости.
# 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 является ядром алгоритма обучения с подкреплением, используемого для поиска оптимальной политики навигации по лабиринту. Он использует метод итерации значений, который представляет собой итеративный алгоритм, который постепенно обновляет оценочные значения каждого состояния, пока они не сойдутся к своим оптимальным значениям.
- Инициализация:
gamma: коэффициент скидки для будущих вознаграждений (значение по умолчанию: 0,99). Этот фактор определяет важность немедленного вознаграждения по сравнению с будущим вознаграждением. Более высокое значение гаммы заставляет агента больше ценить долгосрочные вознаграждения, в то время как более низкое значение заставляет его сосредоточиться на немедленных вознаграждениях.theta: порог сходимости (значение по умолчанию: 1e-6). Этот параметр определяет минимальное изменение значений состояния, которое будет рассматриваться как сходимость. Как только изменение значений состояния падает ниже этого порога, алгоритм прекращает итерацию.delta: переменная, инициализированная до бесконечности, которая будет использоваться для измерения изменения значений состояния во время итерации.
2. Итеративное обновление значений:
- Метод использует цикл while, который продолжается до тех пор, пока изменение значений состояния (
delta) не станет меньше указанного порога сходимости (theta). - Внутри цикла переменная
deltaсбрасывается в 0 перед каждой итерацией, чтобы отслеживать максимальное изменение значений состояния во всех состояниях.
3. Итерация значения:
- Для каждой ячейки лабиринта (исключая стены) алгоритм вычисляет значение Q (q_max) для всех возможных действий (вверх, вниз, влево, вправо).
- Q-значение представляет собой ожидаемое совокупное вознаграждение, которое агент может получить, предприняв определенное действие в данном состоянии и следуя оптимальной политике после этого.
- Значение Q определяется на основе немедленного вознаграждения, полученного с помощью метода
simulate_step, и дисконтированного значения значения следующего состояния (гамма * self.state_values[next_state]). - Действие с максимальным значением Q (q_max) выбирается как наилучшее действие в текущем состоянии.
- Чтобы обновить политику, соответствующие вероятности политики (action_probs) обновляются, чтобы отразить, что это действие имеет наибольшую вероятность быть выбранным. Вероятности всех остальных действий равны 0.
4. Обновление значений состояний и вероятностей политик:
- После вычисления значений Q для всех действий в заданном состоянии значение состояния (self.state_values[строка, столбец]) для этого состояния обновляется до максимального значения Q (q_max) среди всех действий.
- Вероятности политики (self.policy_probs[row, col]) для этого состояния обновляются, чтобы иметь высокую вероятность (1,0) для действия, которое привело к максимальному значению Q, и 0 вероятности для всех других действий.
- Этот процесс продолжается для всех состояний в лабиринте, итеративно обновляя значения состояний и вероятности политики, пока не будет достигнут порог сходимости.
5. Проверка сходимости:
- После обновления значений состояний и вероятностей политик для всех состояний в лабиринте метод проверяет, меньше ли максимальное изменение значений состояний (
delta) во время этой итерации порога сходимости (theta). - Если условие выполнено, цикл завершается, и процесс решения лабиринта считается сходящимся. На данный момент массив
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
Объяснение кода:
- Импорт библиотек и создание констант:
— Код импортирует необходимые библиотеки, включая Pygame, NumPy и пользовательский классMaze.
— Для настройки лабиринта определено несколько констант. окружение, размеры экрана и размеры плитки. - Создайте среду лабиринта:
— Схема лабиринта определяется с помощью списка строк с именемlevel.
— Создается экземпляр классаMaze, передаваяlevelи позицию цели. в качестве параметров.
— Затем объектenvиспользуется для сброса лабиринта и поиска оптимальной политики с помощью методаsolve. - Инициализировать PyGame
- Основной цикл игры:
— Программа входит в цикл, который выполняется до тех пор, пока переменнаяrunningне станет равной False.
— Функцияreset_goalвызывается в отдельном потоке, чтобы проверить, игрок достиг цели и при необходимости сбрасывает цель. - Рисование лабиринта:
— лабиринт рисуется на экране путем итерации по спискуlevellist и рисования плиток на основе символов стены («X»).
— позиция игрока рисуется в виде прямоугольника, залитого определенным цветом (красным) и центрируемого в ячейке лабиринта.
— Целевая позиция рисуется в виде зеленого прямоугольника с закругленными углами. - Обновление состояния игры и движения игрока:
— действие игрока определяется на основе текущей политики (env.policy_probs) на позиции игрока. Действие с наибольшей вероятностью выбирается с помощьюnp.argmax.
— На основе выбранного действия обновляется позиция игрока, если это допустимый ход (без удара по стенам).
— Позиция игрока вenvобъекте так же обновляется. - Выход из игры:
— Игровой цикл завершается, когда переменнаяrunningстановится равной False, что обычно происходит, когда пользователь закрывает окно игры.
— Pygame закрывается с помощьюpygame.quit().
Теперь вы можете просто запустить main.py и увидеть код в действии.
Заключение:
Поздравляем! Вы успешно внедрили алгоритм итерации значений для решения лабиринта с помощью обучения с подкреплением. Вы также визуализировали процесс прохождения лабиринта с помощью PyGame, сделав его более интерактивным и увлекательным. Не стесняйтесь экспериментировать с различными конфигурациями лабиринта, скоростью обучения и коэффициентами дисконтирования, чтобы наблюдать, как они влияют на процесс обучения. Удачного решения лабиринта!
Помните, путь обучения никогда не заканчивается. Продолжайте исследовать и экспериментировать с новыми алгоритмами и приложениями обучения с подкреплением!
Want to Connect? My website LinkedIn Twitter
