概述

在这个项目中，你会需要实现一个 Q-learning算法来解决一个增强学习问题 -- 走迷宫。

Github Repo

• 更新你的 qlearning_robot 目录

git clone https://github.com/nd009/qlearning_robot.git

• Qlearner.py 提供了实现 QLearner 类的模版。
• maze.py 提供了实现Maze 类的模版。
• mazeqlearning.py 利用 QLearner 类和 Maze类解决走迷宫问题
• testworlds 目录下提供了一些迷宫可以用来测试。

定义迷宫问题

地图

我们用一个二位数组定义了整个迷宫。迷宫的纬度是 10 * 10， 每一个迷宫都存储在csv文件中，用 integer 表示每个位置的属性，具体含义如下

• 0: 空地.
• 1: 障碍物.
• 2: 机器人的起始点.
• 3: 目标终点.
• 5: 陷阱.

一个迷宫 (world01.csv) 如下图所示

3,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,1,1,1,1,1,0,0,0
0,5,1,0,0,0,1,0,0,0
0,5,1,0,0,0,1,0,0,0
0,0,1,0,0,0,1,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,2,0,0,0,0,0

在这个例子中，机器人从最后一行的中间位置开始，目标为第0行第0列，中间连续的障碍物组成一面墙阻挡路线，同时左边有很多陷阱。

机器人行走

有四个可能的行为： 向上走, 向右走, 向下走, 向左走。如果机器人尝试走入陷阱，则会真的走入陷阱。如果机器人尝试走入障碍物或走出地图，则会停留在原地，但依旧算作一步。

随机行为

机器人有 0.2 的概率不执行指令，而是在四种行为中随机选择。 例如，如果机器人收到指令 “向上走”，会有一定的概率不往上走，而走其他方向。因此，一个 “聪明的” 机器人应该尽可能得远离陷阱。

目标

我们的目标是让机器人在不走入陷阱的情况下，用最少的步数从起点到达终点。

定义迷宫问题为 Markov 决策过程 (MDP)

在使用 QLearning 解决走迷宫问题之前，我们首先要重新定义走迷宫问题为一个 Markov 决策过程， 因为 QLearning 是用来解决 Markov 决策过程的。

Markov 决策过程包含四个元素，状态，行为，模型和奖励。

状态

S: 10*10 地图上的每个位置，都对应一个状态，共 100 个状态。我们可以用 0 ~ 99 来代表所有状态。

行为

A: 向上走，向下走，向左走，向右走，共 4 个行为。我们可以用 0 ~ 3 来代表所有行为。

模型

T(s, a, s') = P(s|s, a): 在状态 s, 执行行为 a, 进入状态 s' 的概率。模型可以被地图完全定义。例如从一个格子向上走，如果四周都没有障碍物，那么进入上下左右四个格子的概率分别为 0.85, 0.05, 0.05, 0.05, 进入其他各自的概率为0 。

奖励

R(s): 进入状态 s 的奖励。根据我们的目标:

让机器人在不走入陷阱的情况下，用最少的步数从起点到达终点。

我们可以选择了最直接的奖励／惩罚。

• reward = -1 如果机器人走进了一个空地。
• reward = -1 如果机器人尝试走进障碍物，或走出地图。
• reward = -100 如果机器人走进了陷阱。
• reward = 1 如果机器人走到了终点。

如果你觉得选择其他的奖励函数更好得达到目标（更快收敛，更好收敛），也可以使用其他奖励函数。

定义迷宫问题为增强学习问题

在强化学习的问题中，我们并不知道完整的模型 T(s, a, s') 和奖励 R(s)。我们只知道四元组 <s, a, s', r>, 既在状态s下， 执行行为 a, 会进入s', 获得奖励 r。

我们的 Qlearner 会不断和世界互动，在状态 s 下， 执行行为 a，观察新的状态 s' 和获得的奖励 r。不断收集四元组，来学习这个世界的规则，找到最优策略。这也就是增强学习的学习过程。

实现 QLearner

你不可以导入任何额外的库，你需要按照下面定义的 API，在 QLearner.py 中实现 QLearner 类。 注意你的 QLearner 不应该知道任何有关走迷宫的信息。

QLearner()

QLearner 的构造函数，应该预留空间存放 所有状态和行为的 Q-table Q[s, a], 并将整个矩阵初始化为 0. 构造函数的每一个参数如下定义：

• num_states integer, 所有状态个数。
• num_actions integer, 所有行为个数。
• alpha float, 更新Q-table时的学习率，范围 0.0 ~ 1.0, 常用值 0.2。
• gamma float, 更新Q-table时的衰减率，范围 0.0 ~ 1.0, 常用值 0.9。
• rar float, 随机行为比例, 每一步随机选择行为的概率。范围 0.0（从不随机） ~ 1.0（永远随机）, 常用值 0.5。
• radr float, 随机行为比例衰减率, 每一步都更新 rar = rar * radr. 0.0（直接衰减到0） ~ 1.0（从不衰减）, 常用值 0.99。
• verbose boolean, 如果为真，你的类可以打印调试语句，否则，禁止所有打印语句。

query(s_prime, r)

QLearner 的核心方法。他应该记录最后的状态 s 和最后的行为 a，然后使用新的信息 s_prime 和 r 来更新 Q-Table。 学习实例是四元组 <s, a, s_prime, r>. query() 应该返回一个 integer, 代表下一个行为。注意这里应该以 rar 的概率随机选择一个行为，并根据 radr 来更新 rar的值。

参数定义：

• s_prime integer, 新的状态
• r float, 即时奖励／惩罚，可以为正，可以为负。

querysetstate(s)

query() 方法的特殊版本。设置状态为 s，并且返回下一个行为 a （和 query() 方法规则一致，例如包括以一定概率随机选择行为）。但是这个方法不更新 Q-table，不更新 rar。我们主要会在两个地方用到它： 1）设置初始状态 2) 使用学习后的策略，但不更新它

这里是一个使用 API 的例子

import QLearner as ql

learner = ql.QLearner(num_states = 100, \ 
    num_actions = 4, \
    alpha = 0.2, \
    gamma = 0.9, \
    rar = 0.98, \
    radr = 0.999, \
    verbose = False)

s = 99 # 初始状态

a = learner.querysetstate(s) # 状态s下的执行行为 a

s_prime = 5 # 在状态 s，执行行为 a 之后，进入新状态 s_prime

r = 0 # 在状态 s，执行行为 a 之后，获得即使奖励／惩罚 r

next_action = learner.query(s_prime, r)

重声一次，QLearner 不应该知道任何有关迷宫的信息。

实现 Maze

Maze 类定义了迷宫的世界，起点，终点，障碍物和陷阱。

Maze()

Maze 的构造函数，定义了地图，随机行走概率，以及每一步的奖励／惩罚。你也可以在构造函数中定义自己的成员变量。例如起始地点，目标地点等。

get_start_pos()

返回机器人的起始地点。即地图中，数值为2的位置。

get_goal_pos()

返回机器人的目标地点。即地图中，数值为3的位置。

move()

根据地图信息，现在位置和行为指令来移动机器人。机器人有 0.2 的概率不执行指令，而是在4个行为中随机选择。如果机器人尝试走入障碍物或走出地图，则会停留在原地。

返回新的位置和得到的奖励。

print_map()

工具函数，打印地图，无需修改。

print_trail()

工具函数，打印地图和路径，无需修改。参数 trail 是一个坐标的数组。例如 [(0,0), (0,1), (0,2), (1,2)]

实现 mazeqlearning

to_state()

将位置用 0～99 的数字来表达，每个数字代表一个状态。

返回位置所对应的状态

train()

在给定的地图中进行多次行走，每次行走都会让机器人从起点走到终点，或者超时（超过100,000步）。

返回所有行走的奖励。

每一次尝试的伪代码:

total_reward = 0
robopos = startpos
action = learner.querysetstate(to_state(robopos))
while not at goal and not timeout:
	newpos, reward = maze.move(robopos, action)
	robopos = newpos
	action = learner.query(to_state(robopos), reward)
	totol_reward += reward		

maze_qlearning()

定义 QLearner 和 Maze，你可以使用默认参数，或使用自己的参数。调用 train() 进行训练，

返回所有行走的奖励的中位数。