迷宫求解

一、必做任务一

使用强化学习算法，对于给定的迷宫，训练老鼠在迷宫中寻找蛋糕。

迷宫与图中类似，黑色格子为墙，不能走，老鼠试图走向墙时，会停在原地。白色格子为空地，可以走。黄色圆圈标志老鼠走过的格子，五角星为老鼠所在位置。起始位置为左上角，结束位置为右下角。

二、必做任务二

自行生成不同迷宫（尺寸、地图），完成前述操作。

我对这个任务的理解是：程序中事先定义好了一些不同大小和样式的迷宫，供用户挑选，此外，用户也可以自己定义迷宫。

三、必做任务三

若迷宫中存在老鼠夹子，且位置固定，完成前述操作。

如图，红色方格代表陷阱，即老鼠夹子。与黑色方格的墙不同，老鼠可以走向陷阱，而一旦走入陷阱，游戏失败。

四、选做任务一

考虑时变因素，如迷宫的某些格子会周期性产生火焰。

如图，红色三角为火焰，和陷阱相同，老鼠可以走向火焰，但一旦走入就会导致游戏失败。

设老鼠每走一步的时间为一个时间单位，火焰在一个周期时间（偶数个时间单位）内的后半段出现，前半段不出现。比如火焰周期为 4，老鼠走两步，火焰出现，再走两步，火焰消失。火焰周期可在用户自定义界面由用户定义。

五、问题建模

5.1 迷宫

迷宫用一个二维数组建模，数组中的每个数代表一个方格，数字值代表方格类型（如 0 表示墙, 2 表示陷阱, 3 表示火）。

迷宫是强化学习中的“环境”，老鼠在迷宫中每走一步（采取一个动作），迷宫会返回一个 reward，游戏状态（输或赢），以及老鼠下一个位置。

reward 基本都是负值，除了到达终点的动作。

动作	Reward
移动	-0.05
撞墙	-0.85
重复走过的格子	-0.3
死亡（陷阱或火焰）	-2
到达终点	1

之所以将移动的 reward 设为负值，是为了减少老鼠的路线长度，尽快到达终点。

为防止游戏无止境地进行下去，当 reward 积累到足够小时，游戏也会结束。

5.2 表模型

使用 Q-learning 算法进行训练，就是要得到 Q 表：行动价值函数，对每一个状态的每个动作都有一个行动价值与其对应，做决策时选择当前状态下行动价值最高的动作。

动作：向上下左右四个方向前进。

状态：老鼠所在的格子（引入时间因素后还有考虑时间）。

下图是可视化的 Q 表，从每个状态的四个动作中选出 Q 值最大的一个，用箭头画出来，颜色表示 Q 值大小，从红到绿 Q 值越来越大。

5.3 监督学习模型

除 Q 表模型外，我们也尝试了使用监督学习模型进行预测，将 1 中提到的代表迷宫的二维数组变成一维向量，输入到全连接网络中，网络输出 1 × 4 大小的向量，分别表示四个动作的 Q 值。

使用监督学习模型进行训练时，需要使用批量式价值近似方法。把训练数据存到一个库里，训练时从库里拿一批数据出来训练，即经验回放。注意库的大小有限，库满时删除旧数据，加入新数据。

5.4 -learning 学习过程

Q-learning 是一种离线策略学习的方法，行为策略采用-贪心策略，有利于进行探索，目标策略采用贪心策略，有利于充分利用学到的经验。

具体学习过程如下，在老鼠处于状态 state 时，首先基于当前 Q 表采用-贪心策略进行预测，选择一个动作，采取该动作，从”环境”中得到反馈：下一状态 +1, 回馈 +1, 游戏状态（输赢）game_status。再采用贪心策略对下一状态 +1 进行预测，得到 Q(+1, +1)，使用时序差分方法对 Q 表进行更新：

, ) Q(, ) + [+1 + Q(+1, +1) Q(, )]

在每一局游戏的每一步移动都重复上面的步骤，直到游戏结束，一轮游戏叫做一个 epoch。训练会在足够多 epoch 后，或 Q 表足够完善时停止。

5.5 加入时间因子

选做任务中要求火焰周期性变化，因此我们需要在状态中加入时间维度，Q 表也会发生响应的变化。

迷宫问题符合马尔可夫过程的定义，即当前状态下的决策与之前的步骤无关。加入时间因子后也是如此，当前状态下，即考虑时间和老鼠的位置，进行的决策与过去的步骤无关。因此时间因子不是无限大的，但又因为“环境”的反馈与时间有关，所以需要考虑一个周期内的时间因子即可。比如火焰出现周期为 4，则时间变量的取值范围为 0，1，2，3，变化规律为：0 → 1 → 2 → 3 → 0 → 1 → 2 …

在不加入时间因子时，状态由一个二元组表示(x,y)，即老鼠的坐标；加入时间因子后，状态由三元组表示(x,y,t)。Q 表也会扩大规模，比如火焰周期为 4 时，Q 表规模会变为原来的 4 倍。

下图是周期为 2 时 Q 表的可视化结果，每个坐标点有两个 Q 值，分别对应时间 0 和时间 1，时间 t 为 1 时火焰出现。