基于Python实现机器人自动走迷宫【100011016】

机器人自动走迷宫 一 题目背景 1.1 实验题目

在本实验中，要求分别使用基础搜索算法和 Deep 算法，完成机器人自动走迷宫。

图1 地图（）

如上图所示，左上角的红色椭圆既是起点也是机器人的初始位置，右下角的绿色方块是出口。

游戏规则为：从起点开始，通过错综复杂的迷宫，到达目标点(出口)。

需要您分别实现基于基础搜索算法和 Deep 算法的机器人，使机器人自动走到迷宫的出口。

1.2 实验要求 1.3 实验使用重要包

import os
import random
import numpy as np
import torch

二 迷宫介绍 通过迷宫类 Maze 可以随机创建一个迷宫。 使用 Maze(=size) 来随机生成一个 size * size 大小的迷宫。使用 print() 函数可以输出迷宫的 size 以及画出迷宫图红色的圆是机器人初始位置绿色的方块是迷宫的出口位置

图2 gif地图（）

Maze 类中重要的成员方法如下： () ：获取机器人在迷宫中目前的位置。

：机器人在迷宫中目前的位置。

() ：根据输入方向移动默认机器人，若方向不合法则返回错误信息。

：移动方向, 如:“u”, 合法值为： [‘u’, ‘r’, ‘d’, ‘l’]

：执行动作的奖励值

()：获取当前机器人可以移动的方向

：迷宫中任一处的坐标点

：该点可执行的动作，如：[‘u’,‘r’,‘d’]

(self, , )：判断该移动方向是否撞墙

, ：当前位置和要移动的方向，如(0,0) , “u”

：True(撞墙) / False(不撞墙)

()：画出当前的迷宫 三 算法介绍 3.1 深度优先算法 算法具体步骤： 时间复杂度：

查找每个顶点的邻接点所需时间为 O ( n 2 ) O(n^2) O(n2)，n为顶点数，算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)

3.2 强化学习算法

Q- 是一个值迭代（Value ）算法。与策略迭代（ ）算法不同，值迭代算法会计算每个”状态“或是”状态-动作“的值（Value）或是效用（），然后在执行动作的时候，会设法最大化这个值。 因此，对每个状态值的准确估计，是值迭代算法的核心。通常会考虑最大化动作的长期奖励，即不仅考虑当前动作带来的奖励，还会考虑动作长远的奖励。

3.2.1 Q值计算与迭代

Q- 算法将状态（state）和动作（）构建成一张 表来存储 Q 值，Q 表的行代表状态（state），列代表动作（）：

在 Q- 算法中，将这个长期奖励记为 Q 值，其中会考虑每个 ”状态-动作“ 的 Q 值，具体而言，它的计算公式为：

Q ( s t , a ) = R t + 1 + γ × max ⁡ a Q ( a , s t + 1 ) Q(s_{t},a) = R_{t+1} + \gamma \times\max_a Q(a,s_{t+1}) Q(st​,a)=Rt+1​+γ×amax​Q(a,st+1​)

也就是对于当前的“状态-动作” ( s t , a ) (s_{t},a) (st​,a)，考虑执行动作 a a a 后环境奖励 R t + 1 R_{t+1} Rt+1​，以及执行动作 a a a 到达 s t + 1 s_{t+1} st+1​后，执行任意动作能够获得的最大的Q值 max ⁡ a Q ( a , s t + 1 ) \max_a Q(a,s_{t+1}) maxa​Q(a,st+1​)， γ \gamma γ 为折扣因子。

计算得到新的 Q 值之后，一般会使用更为保守地更新 Q 表的方法，即引入松弛变量 a l p h a alpha alpha ，按如下的公式进行更新，使得 Q 表的迭代变化更为平缓。

Q ( s t , a ) = ( 1 − α ) × Q ( s t , a ) + α × ( R t + 1 + γ × max ⁡ a Q ( a , s t + 1 ) ) 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})) Q(st​,a)=(1−α)×Q(st​,a)+α×(Rt+1​+γ×amax​Q(a,st+1​))

3.2.2 机器人动作的选择

在强化学习中，探索-利用 问题是非常重要的问题。 具体来说，根据上面的定义，会尽可能地让机器人在每次选择最优的决策，来最大化长期奖励。但是这样做有如下的弊端：

在初步的学习中，Q 值是不准确的，如果在这个时候都按照 Q 值来选择，那么会造成错误。学习一段时间后，机器人的路线会相对固定，则机器人无法对环境进行有效的探索。

因此需要一种办法，来解决如上的问题，增加机器人的探索。通常会使用 - 算法：

在机器人选择动作的时候，以一部分的概率随机选择动作，以一部分的概率按照最优的 Q 值选择动作。同时，这个选择随机动作的概率应当随着训练的过程逐步减小。

3.2.3 Q- 算法的学习过程

3.2.4 Robot 类

在本作业中提供了 类，其中实现了 Q 表迭代和机器人动作的选择策略，可通过 from 导入使用。

类的核心成员方法

()：获取当前机器人所处位置

：机器人所处的位置坐标，如： (0, 0)

()：获取当前机器人可以合法移动的动作

：由当前合法动作组成的列表，如： [‘u’,‘r’]

()：以训练状态，根据 算法策略执行动作

：当前选择的动作，以及执行当前动作获得的回报, 如： ‘u’, -1

()：以测试状态，根据 算法策略执行动作

：当前选择的动作，以及执行当前动作获得的回报, 如：‘u’, -1

reset()

：重置机器人在迷宫中的位置

3.2.5 类

类实现了 算法的 Q 值迭代和动作选择策略。在机器人自动走迷宫的训练过程中，需要不断的使用 算法来迭代更新 Q 值表，以达到一个“最优”的状态，因此封装好了一个类 用于机器人的训练和可视化。可通过 from 导入使用。

类的核心成员方法：

(, =150): 训练机器人，不断更新 Q 表，并讲训练结果保存在成员变量 中

, : 总共的训练次数、每次训练机器人最多移动的步数

()：测试机器人能否走出迷宫

()：将训练结果输出到指定的 gif 图片中

：合法的文件路径,文件名需以 .gif 为后缀

()：以图表展示训练过程中的指标： Times、 、 Times per Epoch 3.3 DQN

DQN 算法使用神经网络来近似值函数，算法框图如下。

在本次实验中，使用提供的神经网络来预计四个动作的评估分数，同时输出评估分数。

类的核心成员方法

state: 当前机器人位置

: 选择执行动作的索引

： 执行动作获得的回报

：执行动作后机器人的位置

：机器人是否到达了终止节点（到达终点或者撞墙）

: 整数，不允许超过数据集中数据的个数

maze: 以 Maze 类实例化的对象

四 求解结果 4.1 深度优先

编写深度优先搜索算法，并进行测试，通过使用堆栈的方式，来进行一层一层的迭代，最终搜索出路径。主要过程为，入口节点作为根节点，之后查看此节点是否被探索过且是否存在子节点，若满足条件则拓展该节点，将该节点的子节点按照先后顺序入栈。若探索到一个节点时，此节点不是终点且没有可以拓展的子节点，则将此点出栈操作，循环操作直到找到终点。

测试结果如下：

搜索出的路径： ['r', 'd', 'r', 'd', 'd', 'r', 'r', 'd']
恭喜你，到达了目标点
Maze of size (5, 5)

图3 基础搜索地图（size5）

搜索出的路径： ['r', 'r', 'r', 'r', 'r', 'r', 'r', 'd', 'r', 'd', 'd', 'd', 'r', 'd', 'd', 'd', 'l', 'd', 'd', 'r']
恭喜你，到达了目标点
Maze of size (10, 10)

图4 基础搜索地图（）

搜索出的路径： ['d', 'r', 'u', 'r', 'r', 'r', 'r', 'd', 'r', 'd', 'r', 'r', 'r', 'r', 'd', 'd', 'r', 'd', 'd', 'd', 'd', 'r', 'r', 'r', 'r', 'r', 'd', 'r', 'r', 'd', 'r', 'd', 'd', 'l', 'l', 'd', 'd', 'd', 'd', 'd', 'r', 'd', 'd', 'r']
恭喜你，到达了目标点
Maze of size (20, 20)

图5 基础搜索地图（）

部分代码如下：

def myDFS(maze):"""对迷宫进行深度优先搜索:param maze: 待搜索的maze对象"""start = maze.sense_robot()root = SearchTree(loc=start)queue = [root]  # 节点堆栈，用于层次遍历h, w, _ = maze.maze_data.shapeis_visit_m = np.zeros((h, w), dtype=np.int)  # 标记迷宫的各个位置是否被访问过path = []  # 记录路径peek = 0while True:current_node = queue[peek]  # 栈顶元素作为当前节点#is_visit_m[current_node.loc] = 1  # 标记当前节点位置已访问if current_node.loc == maze.destination:  # 到达目标点path = back_propagation(current_node)breakif current_node.is_leaf() and is_visit_m[current_node.loc] == 0:  # 如果该点存在叶子节点且未拓展is_visit_m[current_node.loc] = 1  # 标记该点已拓展child_number = expand(maze, is_visit_m, current_node)peek+=child_number  # 开展一些列入栈操作for child in current_node.children:queue.append(child)  # 叶子节点入栈else:queue.pop(peek)  # 如果无路可走则出栈peek-=1return path

4.2

在算法训练过程中，首先读取机器人当前位置，之后将当前状态加入Q值表中，如果表中已经存在当前状态则不需重复添加。之后，生成机器人的需要执行动作，并返回地图奖励值、查找机器人现阶段位置。接着再次检查并更新Q值表，衰减随机选取动作的可能性。

算法实现过程中，主要是对Q值表的计算更新进行了修改和调整，调整后的Q值表在运行时性能优秀，计算速度快且准确性、稳定性高。之后调节了随机选择动作可能性的衰减率。因为在测试过程中发现，如果衰减太慢的话会导致随机性太强，间接的减弱了奖励的作用，故最终通过调整，发现衰减率取0.5是一个较为优秀的且稳定的值。

部分代码如下：

    def train_update(self):"""以训练状态选择动作，并更新相关参数:return :action, reward 如："u", -1"""self.state = self.maze.sense_robot()  # 获取机器人当初所处迷宫位置# 检索Q表，如果当前状态不存在则添加进入Q表if self.state not in self.q_table:self.q_table[self.state] = {a: 0.0 for a in self.valid_action}action = random.choice(self.valid_action) if random.random() < self.epsilon else max(self.q_table[self.state], key=self.q_table[self.state].get)  # action为机器人选择的动作reward = self.maze.move_robot(action)  # 以给定的方向移动机器人,reward为迷宫返回的奖励值next_state = self.maze.sense_robot()  # 获取机器人执行指令后所处的位置# 检索Q表，如果当前的next_state不存在则添加进入Q表if next_state not in self.q_table:self.q_table[next_state] = {a: 0.0 for a in self.valid_action}# 更新 Q 值表current_r = self.q_table[self.state][action]update_r = reward + self.gamma * float(max(self.q_table[next_state].values()))self.q_table[self.state][action] = self.alpha * self.q_table[self.state][action] +(1 - self.alpha) * (update_r - current_r)self.epsilon *= 0.5  # 衰减随机选择动作的可能性return action, reward

测试结果如下：

图6 强化学习搜索gif地图（size3）

图7 训练结果

图8 强化学习搜索gif地图（size5）

图9 训练结果

图10 强化学习搜索gif地图（）

图11 训练结果

图12 强化学习搜索gif地图（）

图13 训练结果

经过测试，强化学习搜索算法可以快速给出走出迷宫的路径并且随着训练轮次增加，成功率也逐渐上升。当训练轮次足够时，最终后期准确率可以达到100%。

4.3 DQN

在Q- 的基础上，使用神经网络来估计评估分数，用于决策之后的动作。只需在Q-相应部分替换为神经网络的输出即可。

测试结果如下： 4.4 提交结果测试 4.4.1 基础搜索算法测试

图17 基础搜索算法路径

用时0秒

4.4.2 强化学习算法（初级）

图18 强化学习算法（初级）

用时0秒

4.4.3 强化学习算法（中级）

图19 强化学习算法（中级）

用时0秒

4.4.4 强化学习算法（高级）

图20 强化学习算法（高级）

用时0秒

4.4.5 DQN算法（初级）

图21 DQN算法（初级）

用时2秒

4.4.6 DQN算法（中级）

图22 DQN算法（中级）

用时3秒

4.4.7 DQN算法（高级）

图23 DQN算法（高级）

用时105秒

五 比较分析

比较基础搜索算法、强化学习搜索算法和DQN算法可以发现，在训练轮次提升到较大数字的时候，三算法速度均很快且有较高的准确率。DQN算法耗费时间长，但是性能稳定。

算法用时状态

深度优先+

0

到达终点

强化学习+size3

0

到达终点

强化学习+size5

0

到达终点

强化学习+

0

到达终点

DQN+size3

2

到达终点

DQN+size5

3

到达终点

DQN+

105

到达终点

六 心得与感想

通过本次实验，学习到了多种基础搜索算法的具体工作方式，并且在实践中实现了这些基础搜索算法；同时学习了强化学习搜索算法的工作原理和应用方式，让我对这些方法有了更加深刻的认识，也对各个环节有了更加深层次的理解，受益匪浅。

♻️ 资源

大小： 5.28MB

➡️ 资源下载：

注：如当前文章或代码侵犯了您的权益，请私信作者删除！