基于Python实现的机器人自动走迷宫.zip

<center><strong><font size="8">机器人自动走迷宫 ### 一 题目背景 #### 1.1 实验题目 在本实验中，要求分别使用基础搜索算法和 ***Deep QLearning*** 算法，完成机器人自动走迷宫。  <strong>图1 地图（size10）</strong> 如上图所示，左上角的红色椭圆既是起点也是机器人的初始位置，右下角的绿色方块是出口。 游戏规则为：从起点开始，通过错综复杂的迷宫，到达目标点(出口)。 + 在任一位置可执行动作包括：向上走 `'u'`、向右走 `'r'`、向下走 `'d'`、向左走 `'l'`。 + 执行不同的动作后，根据不同的情况会获得不同的奖励，具体而言，有以下几种情况。 - 撞墙 - 走到出口 - 其余情况 + 需要您分别实现**基于基础搜索算法**和 **Deep QLearning 算法**的机器人，使机器人自动走到迷宫的出口。 #### 1.2 实验要求 + 使用 ***Python*** 语言。 + 使用基础搜索算法完成机器人走迷宫。 + 使用 ***Deep QLearning*** 算法完成机器人走迷宫。 + 算法部分需要自己实现，不能使用现成的包、工具或者接口。 #### 1.3 实验使用重要python包 ```python import os import random import numpy as np import torch ``` ### 二 迷宫介绍 ###### 通过迷宫类 ***Maze*** 可以随机创建一个迷宫。 1. 使用 ***Maze(maze_size=size)*** 来随机生成一个 size * size 大小的迷宫。 2. 使用 ***print()*** 函数可以输出迷宫的 ***size*** 以及画出迷宫图 3. 红色的圆是机器人初始位置 4. 绿色的方块是迷宫的出口位置  <strong>图2 gif地图（size10）</strong> ###### Maze 类中重要的成员方法如下： 1. sense_robot() ：获取机器人在迷宫中目前的位置。 > return：机器人在迷宫中目前的位置。 2. move_robot(direction) ：根据输入方向移动默认机器人，若方向不合法则返回错误信息。 > direction：移动方向, 如:"u", 合法值为： ['u', 'r', 'd', 'l'] > return：执行动作的奖励值 3. can_move_actions(position)：获取当前机器人可以移动的方向 > position：迷宫中任一处的坐标点 > return：该点可执行的动作，如：['u','r','d'] 4. is_hit_wall(self, location, direction)：判断该移动方向是否撞墙 > location, direction：当前位置和要移动的方向，如(0,0) , "u" > return：True(撞墙) / False(不撞墙) 5. draw_maze()：画出当前的迷宫 ### 三 算法介绍 #### 3.1 深度优先算法 ###### 算法具体步骤： - 选取图中某一顶点$V_i$为出发点，访问并标记该顶点； - 以Vi为当前顶点，依次搜索$V_i$的每个邻接点$V_j$，若$V_j$未被访问过，则访问和标记邻接点$V_j$，若$V_j$已被访问过，则搜索$V_i$的下一个邻接点； - 以$V_j$为当前顶点，重复上一步骤），直到图中和$V_i$有路径相通的顶点都被访问为止； - 若图中尚有顶点未被访问过（非连通的情况下），则可任取图中的一个未被访问的顶点作为出发点，重复上述过程，直至图中所有顶点都被访问。 ###### 时间复杂度： 查找每个顶点的邻接点所需时间为$O(n^2)$，n为顶点数，算法的时间复杂度为$O(n^2)$ #### 3.2 强化学习QLearning算法 ***Q-Learning*** 是一个值迭代（Value Iteration）算法。与策略迭代（Policy Iteration）算法不同，值迭代算法会计算每个”状态“或是”状态-动作“的值（Value）或是效用（Utility），然后在执行动作的时候，会设法最大化这个值。 因此，对每个状态值的准确估计，是值迭代算法的核心。通常会考虑**最大化动作的长期奖励**，即不仅考虑当前动作带来的奖励，还会考虑动作长远的奖励。 ##### 3.2.1 Q值计算与迭代 ***Q-learning*** 算法将状态（state）和动作（action）构建成一张 Q_table 表来存储 Q 值，Q 表的行代表状态（state），列代表动作（action）：  在 ***Q-Learning*** 算法中，将这个长期奖励记为 Q 值，其中会考虑每个 ”状态-动作“ 的 Q 值，具体而言，它的计算公式为： $$ Q(s_{t},a) = R_{t+1} + \gamma \times\max_a Q(a,s_{t+1}) $$ 也就是对于当前的“状态-动作” $(s_{t},a)$，考虑执行动作 $a$ 后环境奖励 $R_{t+1}$，以及执行动作 $a$ 到达 $s_{t+1}$后，执行任意动作能够获得的最大的Q值 $\max_a Q(a,s_{t+1})$，$\gamma$ 为折扣因子。 计算得到新的 Q 值之后，一般会使用更为保守地更新 Q 表的方法，即引入松弛变量 $alpha$ ，按如下的公式进行更新，使得 Q 表的迭代变化更为平缓。 $$ Q(s_{t},a) = (1-\alpha) \times Q(s_{t},a) + \alpha \times(R_{t+1} + \gamma \times\max_a Q(a,s_{t+1})) $$ ##### 3.2.2 机器人动作的选择 在强化学习中，**探索-利用** 问题是非常重要的问题。 具体来说，根据上面的定义，会尽可能地让机器人在每次选择最优的决策，来最大化长期奖励。但是这样做有如下的弊端： 1. 在初步的学习中，Q 值是不准确的，如果在这个时候都按照 Q 值来选择，那么会造成错误。 2. 学习一段时间后，机器人的路线会相对固定，则机器人无法对环境进行有效的探索。 因此需要一种办法，来解决如上的问题，增加机器人的探索。通常会使用 **epsilon-greedy** 算法： 1. 在机器人选择动作的时候，以一部分的概率随机选择动作，以一部分的概率按照最优的 Q 值选择动作。 2. 同时，这个选择随机动作的概率应当随着训练的过程逐步减小。   ##### 3.2.3 Q-Learning 算法的学习过程  ##### 3.2.4 Robot 类 在本作业中提供了 ***QRobot*** 类，其中实现了 Q 表迭代和机器人动作的选择策略，可通过 `from QRobot import QRobot` 导入使用。 **QRobot 类的核心成员方法** 1. sense_state()：获取当前机器人所处位置 > return：机器人所处的位置坐标，如： (0, 0) 2. current_state_valid_actions()：获取当前机器人可以合法移动的动作 > return：由当前合法动作组成的列表，如： ['u','r'] 3. train_update()：以**训练状态**，根据 QLearning 算法策略执行动作 > return：当前选择的动作，以及执行当前动作获得的回报, 如： 'u', -1 4. test_update()：以**测试状态**，根据 QLearning 算法策略执行动作 > return：当前选择的动作，以及执行当前动作获得的回报, 如：'u', -1 5. reset() > return：重置机器人在迷宫中的位置 ##### 3.2.5 Runner 类 ***QRobot*** 类实现了 ***QLearning*** 算法的 Q 值迭代和动作选择策略。在机器人自动走迷宫的训练过程中，需要不断的使用 ***QLearning*** 算法来迭代更新 Q 值表，以达到一个“最优”的状态，因此封装好了一个类 ***Runner*** 用于机器人的训练和可视化。可通过 `from Runner import Runner` 导入使用。 **Runner 类的核心成员方法：** 1. run_training(training_epoch, training_per_epoch=150): 训练机器人，不断更新 Q 表，并讲训练结果保存在成员变量 train_robot_record 中 > training_epoch, training_per_epoch: 总共的训练次数、每次训练机器人最多移动的步数 2. run_testing()：�