使用 Q - learning 算法解决迷宫路径规划问题

整体功能概述

这段 Python 代码实现了一个使用 Q - learning 算法解决迷宫路径规划问题的程序。智能体在给定的迷宫环境中学习如何找到从起点到终点的最优路径，以获得最大奖励。

模块导入

python

import numpy as np
import random

• numpy：用于处理数组和矩阵操作，在代码中主要用于创建和操作 Q 表。
• random：用于生成随机数，在智能体的探索阶段选择随机动作。

迷宫环境类 Maze

python

class Maze:def __init__(self, maze_layout, start, goal):self.maze = np.array(maze_layout)self.start = startself.goal = goalself.current_position = startself.rows, self.cols = self.maze.shape

• 功能：表示迷宫环境。
• 参数：
  • maze_layout：二维列表，表示迷宫的布局，其中 0 表示通路，1 表示墙壁。
  • start：元组，表示智能体的起始位置。
  • goal：元组，表示迷宫的终点位置。
• 属性：
  • maze：numpy 数组，存储迷宫布局。
  • start：起始位置。
  • goal：终点位置。
  • current_position：智能体当前所在位置。
  • rows 和 cols：迷宫的行数和列数。

python

    def reset(self):self.current_position = self.startreturn self.current_position

• 功能：将智能体的位置重置为起始位置。
• 返回值：重置后的智能体位置。

python

    def step(self, action):x, y = self.current_positionif action == 0:  # 上new_x, new_y = x - 1, yelif action == 1:  # 下new_x, new_y = x + 1, yelif action == 2:  # 左new_x, new_y = x, y - 1elif action == 3:  # 右new_x, new_y = x, y + 1if 0 <= new_x < self.rows and 0 <= new_y < self.cols and self.maze[new_x, new_y] != 1:self.current_position = (new_x, new_y)if self.current_position == self.goal:reward = 100done = Trueelse:reward = -1done = Falsereturn self.current_position, reward, done

• 功能：根据智能体的动作更新其位置，并返回新位置、奖励和是否到达终点的标志。
• 参数：
  • action：整数，表示智能体的动作，0 表示上，1 表示下，2 表示左，3 表示右。
• 返回值：
  • self.current_position：智能体的新位置。
  • reward：奖励值，到达终点为 100，否则为 -1。
  • done：布尔值，表示是否到达终点。

Q - learning 智能体类 QLearningAgent

python

class QLearningAgent:def __init__(self, state_size, action_size, learning_rate=0.1, discount_factor=0.9, exploration_rate=1.0, exploration_decay=0.995):self.state_size = state_sizeself.action_size = action_sizeself.learning_rate = learning_rateself.discount_factor = discount_factorself.exploration_rate = exploration_rateself.exploration_decay = exploration_decayself.q_table = np.zeros((state_size[0], state_size[1], action_size))

• 功能：实现 Q - learning 算法的智能体。
• 参数：
  • state_size：元组，表示状态空间的大小，即迷宫的行数和列数。
  • action_size：整数，表示动作空间的大小，这里为 4（上、下、左、右）。
  • learning_rate：学习率，控制 Q 表更新的步长，默认为 0.1。
  • discount_factor：折扣因子，用于计算未来奖励的折现值，默认为 0.9。
  • exploration_rate：探索率，控制智能体随机探索的概率，默认为 1.0。
  • exploration_decay：探索率衰减率，每次更新后探索率会乘以该值，默认为 0.995。
• 属性：
  • state_size：状态空间大小。
  • action_size：动作空间大小。
  • learning_rate：学习率。
  • discount_factor：折扣因子。
  • exploration_rate：探索率。
  • exploration_decay：探索率衰减率。
  • q_table：numpy 数组，存储 Q 值，形状为 (行数, 列数, 动作数)。

python

    def act(self, state):if np.random.rand() <= self.exploration_rate:return random.randrange(self.action_size)else:x, y = statereturn np.argmax(self.q_table[x, y, :])

• 功能：根据当前状态选择动作。
• 参数：
  • state：元组，表示当前状态，即智能体的位置。
• 返回值：
  • 整数，表示选择的动作。

python

    def update(self, state, action, reward, next_state):x, y = statenext_x, next_y = next_statetarget = reward + self.discount_factor * np.max(self.q_table[next_x, next_y, :])self.q_table[x, y, action] = (1 - self.learning_rate) * self.q_table[x, y, action] + self.learning_rate * targetself.exploration_rate *= self.exploration_decay

• 功能：根据当前状态、动作、奖励和下一个状态更新 Q 表，并更新探索率。
• 参数：
  • state：元组，表示当前状态。
  • action：整数，表示选择的动作。
  • reward：奖励值。
  • next_state：元组，表示下一个状态。

训练智能体函数 train_agent

python

def train_agent(maze, agent, episodes=1000):for episode in range(episodes):state = maze.reset()done = Falsewhile not done:action = agent.act(state)next_state, reward, done = maze.step(action)agent.update(state, action, reward, next_state)state = next_state

• 功能：训练智能体，让其在迷宫环境中学习最优策略。
• 参数：
  • maze：Maze 类的实例，表示迷宫环境。
  • agent：QLearningAgent 类的实例，表示智能体。
  • episodes：整数，表示训练的回合数，默认为 1000。

找到最优路径函数 find_optimal_path

python

def find_optimal_path(maze, agent):state = maze.reset()path = [state]done = Falsewhile not done:action = np.argmax(agent.q_table[state[0], state[1], :])next_state, _, done = maze.step(action)path.append(next_state)state = next_statereturn path

• 功能：根据训练好的 Q 表找到从起点到终点的最优路径。
• 参数：
  • maze：Maze 类的实例，表示迷宫环境。
  • agent：QLearningAgent 类的实例，表示智能体。
• 返回值：
  • 列表，包含从起点到终点的路径。

主程序

python

# 示例迷宫
maze_layout = [[0, 0, 0, 0],[0, 1, 1, 0],[0, 1, 0, 0],[0, 0, 0, 0]
]
start = (0, 0)
goal = (3, 3)maze = Maze(maze_layout, start, goal)
state_size = maze.maze.shape
action_size = 4
agent = QLearningAgent(state_size, action_size)train_agent(maze, agent)
optimal_path = find_optimal_path(maze, agent)
print("最优路径:", optimal_path)

• 功能：定义一个示例迷宫，创建迷宫环境和智能体，训练智能体并找到最优路径，最后打印最优路径。

通过以上步骤，智能体可以在迷宫环境中学习并找到从起点到终点的最优路径。

完整代码

import numpy as np
import random# 迷宫环境
class Maze:def __init__(self, maze_layout, start, goal):self.maze = np.array(maze_layout)self.start = startself.goal = goalself.current_position = startself.rows, self.cols = self.maze.shapedef reset(self):self.current_position = self.startreturn self.current_positiondef step(self, action):x, y = self.current_positionif action == 0:  # 上new_x, new_y = x - 1, yelif action == 1:  # 下new_x, new_y = x + 1, yelif action == 2:  # 左new_x, new_y = x, y - 1elif action == 3:  # 右new_x, new_y = x, y + 1if 0 <= new_x < self.rows and 0 <= new_y < self.cols and self.maze[new_x, new_y] != 1:self.current_position = (new_x, new_y)if self.current_position == self.goal:reward = 100done = Trueelse:reward = -1done = Falsereturn self.current_position, reward, done# Q - learning 智能体
class QLearningAgent:def __init__(self, state_size, action_size, learning_rate=0.1, discount_factor=0.9, exploration_rate=1.0, exploration_decay=0.995):self.state_size = state_sizeself.action_size = action_sizeself.learning_rate = learning_rateself.discount_factor = discount_factorself.exploration_rate = exploration_rateself.exploration_decay = exploration_decayself.q_table = np.zeros((state_size[0], state_size[1], action_size))def act(self, state):if np.random.rand() <= self.exploration_rate:return random.randrange(self.action_size)else:x, y = statereturn np.argmax(self.q_table[x, y, :])def update(self, state, action, reward, next_state):x, y = statenext_x, next_y = next_statetarget = reward + self.discount_factor * np.max(self.q_table[next_x, next_y, :])self.q_table[x, y, action] = (1 - self.learning_rate) * self.q_table[x, y, action] + self.learning_rate * targetself.exploration_rate *= self.exploration_decay# 训练智能体
def train_agent(maze, agent, episodes=1000):for episode in range(episodes):state = maze.reset()done = Falsewhile not done:action = agent.act(state)next_state, reward, done = maze.step(action)agent.update(state, action, reward, next_state)state = next_state# 找到最优路径
def find_optimal_path(maze, agent):state = maze.reset()path = [state]done = Falsewhile not done:action = np.argmax(agent.q_table[state[0], state[1], :])next_state, _, done = maze.step(action)path.append(next_state)state = next_statereturn path# 示例迷宫
maze_layout = [[0, 0, 0, 0],[0, 1, 1, 0],[0, 1, 0, 0],[0, 0, 0, 0]
]
start = (0, 0)
goal = (3, 3)maze = Maze(maze_layout, start, goal)
state_size = maze.maze.shape
action_size = 4
agent = QLearningAgent(state_size, action_size)train_agent(maze, agent)
optimal_path = find_optimal_path(maze, agent)
print("最优路径:", optimal_path)

完整代码（增加可视化部分）

import numpy as np
import random
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap# 迷宫环境
class Maze:def __init__(self, maze_layout, start, goal):self.maze = np.array(maze_layout)self.start = startself.goal = goalself.current_position = startself.rows, self.cols = self.maze.shapedef reset(self):self.current_position = self.startreturn self.current_positiondef step(self, action):x, y = self.current_positionif action == 0:  # 上new_x, new_y = x - 1, yelif action == 1:  # 下new_x, new_y = x + 1, yelif action == 2:  # 左new_x, new_y = x, y - 1elif action == 3:  # 右new_x, new_y = x, y + 1if 0 <= new_x < self.rows and 0 <= new_y < self.cols and self.maze[new_x, new_y] != 1:self.current_position = (new_x, new_y)if self.current_position == self.goal:reward = 100done = Trueelse:reward = -1done = Falsereturn self.current_position, reward, done# Q - learning 智能体
class QLearningAgent:def __init__(self, state_size, action_size, learning_rate=0.1, discount_factor=0.9, exploration_rate=1.0,exploration_decay=0.995):self.state_size = state_sizeself.action_size = action_sizeself.learning_rate = learning_rateself.discount_factor = discount_factorself.exploration_rate = exploration_rateself.exploration_decay = exploration_decayself.q_table = np.zeros((state_size[0], state_size[1], action_size))def act(self, state):if np.random.rand() <= self.exploration_rate:return random.randrange(self.action_size)else:x, y = statereturn np.argmax(self.q_table[x, y, :])def update(self, state, action, reward, next_state):x, y = statenext_x, next_y = next_statetarget = reward + self.discount_factor * np.max(self.q_table[next_x, next_y, :])self.q_table[x, y, action] = (1 - self.learning_rate) * self.q_table[x, y, action] + self.learning_rate * targetself.exploration_rate *= self.exploration_decay# 训练智能体
def train_agent(maze, agent, episodes=1000):for episode in range(episodes):state = maze.reset()done = Falsewhile not done:action = agent.act(state)next_state, reward, done = maze.step(action)agent.update(state, action, reward, next_state)state = next_state# 找到最优路径
def find_optimal_path(maze, agent):state = maze.reset()path = [state]done = Falsewhile not done:action = np.argmax(agent.q_table[state[0], state[1], :])next_state, _, done = maze.step(action)path.append(next_state)state = next_statereturn path# 可视化迷宫和路径
def visualize_maze(maze, path):maze_array = maze.maze.copy()for pos in path:maze_array[pos] = 2maze_array[maze.start] = 3maze_array[maze.goal] = 4cmap = ListedColormap(['white', 'black', 'green', 'blue', 'red'])plt.figure(figsize=(8, 8))plt.imshow(maze_array, cmap=cmap)# Set the font to SimSun (宋体)plt.rcParams['font.sans-serif'] = ['SimSun']plt.rcParams['axes.unicode_minus'] = False  # Ensure that minus signs are displayed correctlyplt.title('迷宫路径可视化', fontproperties='SimSun')plt.xticks([])plt.yticks([])plt.show()# 示例迷宫
maze_layout = [[0, 0, 0, 0],[0, 1, 1, 0],[0, 1, 0, 0],[0, 0, 0, 0]
]
start = (0, 0)
goal = (3, 3)maze = Maze(maze_layout, start, goal)
state_size = maze.maze.shape
action_size = 4
agent = QLearningAgent(state_size, action_size)train_agent(maze, agent)
optimal_path = find_optimal_path(maze, agent)
print("最优路径:", optimal_path)# 可视化结果
visualize_maze(maze, optimal_path)