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

机器人自动走迷宫一题目背景 1.1 实验题目
在本实验中，要求分别使用基础搜索算法和 Deep算法，完成机器人自动走迷宫。
图1 地图（）
如上图所示，左上角的红色椭圆既是起点也是机器人的初始位置，右下角的绿色方块是出口。
游戏规则为：从起点开始，通过错综复杂的迷宫，到达目标点(出口) 。
需要您分别实现基于基础搜索算法和 Deep算法的机器人，使机器人自动走到迷宫的出口。
1.2 实验要求1.3 实验使用重要包
import osimport randomimport numpy as npimport 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 机器人动作的选择
在强化学习中，探索-利用问题是非常重要的问题。具体来说，根据上面的定义，会尽可能地让机器人在每次选择最优的决策，来最大化长期奖励。但是这样做有如下的弊端：