2. 实现Q-Learning算法

任务目标

在5×5的Gridworld环境中，从零实现Q-Learning算法。智能体通过表格记录每个状态-动作对的Q值，使用ε-greedy策略探索环境，并通过贝尔曼方程迭代更新Q值，最终学习到从起点到终点的最优路径。

环境定义

Gridworld为5×5网格，状态编号0~24（行优先）。动作空间为4个方向：0=上，1=下，2=左，3=右。智能体从状态0出发，到达状态24获得奖励+10并终止；进入障碍物状态（编号6、7、12、17、18）获得奖励-5并终止；其余移动奖励为-1（鼓励最短路径）。越界移动不改变状态，奖励为-1。

Q-Learning实现

import numpy as np

# Gridworld参数
GRID_SIZE = 5
N_STATES = GRID_SIZE * GRID_SIZE
N_ACTIONS = 4
START_STATE = 0
GOAL_STATE = 24
OBSTACLES = {6, 7, 12, 17, 18}

# 动作定义: 0=上, 1=下, 2=左, 3=右
ACTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def step(state, action):
    """执行动作，返回(下一状态, 奖励, 是否终止)"""
    row, col = divmod(state, GRID_SIZE)
    dr, dc = ACTIONS[action]
    new_row, new_col = row + dr, col + dc
    
    # 越界检查
    if new_row < 0 or new_row >= GRID_SIZE or new_col < 0 or new_col >= GRID_SIZE:
        return state, -1, False
    
    next_state = new_row * GRID_SIZE + new_col
    
    # 障碍物检查
    if next_state in OBSTACLES:
        return next_state, -5, True
    
    # 目标检查
    if next_state == GOAL_STATE:
        return next_state, 10, True
    
    return next_state, -1, False

def q_learning(episodes=500, alpha=0.1, gamma=0.9, epsilon=0.1):
    """Q-Learning主训练函数"""
    # 初始化Q表为0
    Q = np.zeros((N_STATES, N_ACTIONS))
    
    for _ in range(episodes):
        state = START_STATE
        done = False
        
        while not done:
            # ε-greedy策略选择动作
            if np.random.random() < epsilon:
                action = np.random.randint(N_ACTIONS)
            else:
                action = np.argmax(Q[state])
            
            next_state, reward, done = step(state, action)
            
            # Q值更新（Q-Learning核心公式）
            best_next = np.max(Q[next_state]) if not done else 0
            Q[state, action] += alpha * (reward + gamma * best_next - Q[state, action])
            
            state = next_state
    
    return Q

def extract_policy(Q):
    """从Q表中提取确定性策略"""
    policy = {}
    for s in range(N_STATES):
        if s == GOAL_STATE or s in OBSTACLES:
            continue
        policy[s] = int(np.argmax(Q[s]))
    return policy

def simulate_optimal_path(Q):
    """模拟最优路径，返回路径状态序列"""
    path = [START_STATE]
    state = START_STATE
    visited = set()
    
    while state != GOAL_STATE and state not in visited:
        visited.add(state)
        action = np.argmax(Q[state])
        next_state, _, done = step(state, action)
        path.append(next_state)
        state = next_state
        if done and state != GOAL_STATE:
            return None  # 落入障碍物或无法到达
    
    return path if state == GOAL_STATE else None

# 训练并输出结果
if __name__ == "__main__":
    np.random.seed(42)  # 固定随机种子保证可复现
    Q = q_learning()
    path = simulate_optimal_path(Q)
    
    if path:
        print("找到最优路径:", " -> ".join(map(str, path)))
        print("路径长度:", len(path) - 1, "步")
    else:
        print("未找到有效路径，请调整超参数或增加训练轮数")

运行与验证

直接运行脚本即可完成训练并输出结果。验证通过条件：

  • 程序输出一条从状态0到状态24的路径，且路径中不包含障碍物状态（6、7、12、17、18）
  • 路径长度不超过15步（5×5网格中绕过4个障碍物的最短路径为13步）
  • 多次运行（修改随机种子）仍能稳定找到路径，说明Q-Learning已收敛

预期输出（固定随机种子42时）：

找到最优路径: 0 -> 1 -> 2 -> 3 -> 4 -> 9 -> 14 -> 19 -> 24
路径长度: 8 步

该路径绕过了所有障碍物，长度为8步，是当前障碍物布局下的最短路径之一。若需观察训练过程，可在q_learning函数中每50个episode打印一次当前策略的模拟路径长度，应看到路径长度随训练递减并最终稳定。

← 上一章 📖 返回目录 下一章 →