强化学习-DQN-走迷宫实战_强化学习 迷宫

强化学习

RL：面对一个不断变化的的状态空间，解决决策问题，找到在当前环境状态下最佳决策是什么。

即：最大折扣化奖励的平均值，预期效益。

输入一个动作状态，尝试输出关于s、a的动作状态值函数值。s——状态，a——动作。

其中最重要的特征：动作与状态、状态转移、奖励、策略、环境。

选择某策略来优化最大化折扣奖励平均值

强化学习的特点：

• 没有监督数据、只有奖励信号。
• 奖励信号不一定是实时的，而很可能是延后的，有时甚至延后很多。
• 时间（序列）是一个重要因素。
• 当前的行为影响后续接收到的数据。

应用：下棋、机器人、自动驾驶。

R1即现在走到的这个状态的奖励值。即折扣因子，即找到使奖励最大化的状态a‘

QLearning，DQN-基于深度学习的Q-Learning算法

该算法核心原理是Q-Table，其行和列表示State和Action的值，Q-Table的值Q(s,a)是衡量当前States采取行动a的重要依据

由于机器会失误，所以我们在更新新的奖励状态时取之前的一部分与新的一部分。

具体步骤如下：

1. 初始化Q表，学习率、折扣因子、贪婪策略取值、
2. 执行以下循环：
   1. 初始化一个Q表格，Q表格的行表示状态，列表示动作，Q值表示某个状态下采取某个动作的价值估计。初始时，Q值可以设置为0或随机值。
   2. 针对每个时刻，根据当前状态s，选择一个动作a。可以根据当前状态的Q值和某种策略（如贪心策略）来选择动作。
   3. 执行选择的动作a，得到下一个状态s'和相应的奖励r$
   4. 基于下一个状态s'，更新Q值。Q值的更新方式为：
      1. 初始化一个状态s。
      2. 根据当前状态s和Q表中的Q值，选择一个动作a。可以通过epsilon-greedy策略来进行选择，即有一定的概率随机选择动作，以便于探索新的状态，否则就选择Q值最大的动作。
      3. 执行选择的动作a，得到下一个状态s'和奖励r。
      4. 根据s'和Q表中的Q值，计算出最大Q值maxQ。
      5. 根据Q-learning的更新公式，更新Q值：Q(s, a) = Q(s, a) + alpha * (r + gamma * maxQ - Q(s, a))，其中alpha是学习率，gamma是折扣因子。
      6. 将当前状态更新为下一个状态：s = s'。
      7. 如果当前状态为终止状态，则转到步骤1；否则转到步骤2。
      8. 重复执行步骤1-7直到收敛，即Q值不再发生变化或者达到预定的最大迭代次数。最终得到的Q表中的Q值就是最优的策略。
   5. 重复执行2-4步骤，直到到达终止状态，或者达到预设的最大步数。
   6. 不断执行1-5步骤，直到Q值收敛。
   7. 在Q表格中根据最大Q值，选择一个最优的策略。

import numpy as np
import random
#生成迷宫图像
from matplotlib import pyplot as plt
 
#实现QL
class QLearningAgent:
    # 首先初始化动作空间，设置学习率，discount——factor折扣因子，epsilon-贪婪略取值，num_actions动作数
    def __init__(self,actions,size):
        self.actions=actions
        self.learning_rate=0.04
        self.discount_factor=0.9
        self.epsilon=0.1
        self.num_actions=len(actions)
        #初始化，q_table=动作状态.Q-Table的值Q(s,a)是衡量当前States采取行动a的重要依据
        self.q_table=np.zeros((size,size,self.num_actions))
        # 核心，给定当前动作，状态、奖励、下一状态去更新下一个Q表。
    def learn(self,state,action,reward,next_state):
        current_q=self.q_table[state][action]
        new_q=reward+self.discount_factor*max(self.q_table[next_state])
        self.q_table[state][action]+=self.learning_rate*(new_q-current_q)
        #新的q值要根据公式计算，更新时要与学习率相结合采取原q值的0.9+新q值的0.1
    #得到下一个动作
    def get_action(self,state):
        if np.random.rand()<self.epsilon:
            action=np.random.choice(self.actions)
        else:
            state_action=self.q_table[state]
            action=self.argmax(state_action)
        return action
     #从所有状态中选择最大奖励的那个。对于奖励相同的我们随机选择一个。
    # #获取最大值对应的动作，遍历q表中的所有动作，找到最大值对应的，最后从这些动作中随机选择一个为最终
    @staticmethod
    def argmax(state_action):
        max_index_list=[]
        max_value=state_action[0]
        for index,value in enumerate(state_action):
            if value>max_value:
                max_index_list.clear()
                max_value=value
                max_index_list.append(index)
            elif value==max_value:
                max_index_list.append(index)
        return random.choice(max_index_list)
 
 
#定义迷宫环境
class MazeEnv:
    def __init__(self,size):
        self.size=size
        self.actions=[0,1,2,3]
        self.maze,self.start,self.end=self.generate(size)
        #重置 状态
    def reset(self):
        self.state=self.start
        self.goal=self.end
        self.path=[self.start]
        self.solve=np.zeros_like(self.maze)
        self.solve[self.start]=1
        self.solve[self.end]=1
        return self.state
    def step(self,action):
        #执行动作
        next_state=None
        if action==0 and self.state[0]>0:
            next_state=(self.state[0]-1,self.state[1])
        elif action==1 and self.state[0]<self.size-1:
            next_state=(self.state[0]+1,self.state[1])
        elif action==2 and self.state[1]>0:
            next_state=(self.state[0],self.state[1]-1)
        elif action==3 and self.state[1]<self.size-1:
            next_state=(self.state[0],self.state[1]+1)
        else:
            next_state=self.state
        #坐标随方向变后，更改奖励
        if next_state==self.goal:
            reward=100
        elif self.maze[next_state] == -1:
            reward=-100
        else:
            reward=-1
        self.state=next_state
        self.path.append(self.state)
        self.solve[self.state]=1
        done=(self.state==self.goal)
        #判断是否结束
        return next_state,reward,done
    @staticmethod
    #生成迷宫图像
    def generate(size):
        maze=np.zeros((size,size))
        start=(random.randint(0,size-1),0)
        end=(random.randint(0,size-1),size-1)
        maze[start]=1
        maze[end]=1
        for i in range(size*size):
            x,y=random.randint(0,size-1),random.randint(0,size-1)
            if (x,y)==start or (x,y)==end:
                continue
            if random.random()<0.2:
                maze[x,y]=-1
            if np.sum(np.abs(maze))==size*size-2:
                break
 
        return maze,start,end
    #bfs求出路径
    @staticmethod
    def solve_maze(maze,start,end):
        size=maze.shape[0]
        visited=np.zeros((size,size))
        solve=np.zeros((size,size))
        queue=[start]
        visited[start[0],start[1]]=1
        while queue:
            x,y=queue.pop(0)
            if(x,y)==end:
                break
            for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
                nx,ny= x+ dx,y+dy
                if nx<0 or nx>=size or ny<0 or ny>=size or visited[nx,ny] or maze[nx,ny]==-1:
                    continue
                queue.append((nx,ny))
                visited[nx,ny]=visited[x,y]+1
        if visited[end[0],end[1]]==0:
            return solve,[]
        path=[end]
        x,y=end
        while(x,y)!=start:
            for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
                nx,ny=x+dx,y+dy
                if nx<0 or nx>=size or ny<0 or ny>=size or visited[nx,ny]!=visited[x,y]-1:
                    continue
                path.append((nx,ny))
                x,y=nx,ny
                break
        #倒序
        points=path[::-1]
        for point in points:
            solve[point[0]][point[1]]=1
        return solve,points
 
#执行
maze_size=32
#创建环境
env=MazeEnv(maze_size)
#初始化QLerning智能体
agent=QLearningAgent(actions=env.actions,size=maze_size)
#进行30000次游戏
for epoisode in range(30000):
    state =env.reset()
    while True:
        action=agent.get_action(state)
        next_state,reward,done=env.step(action)
        agent.learn(state,action,reward,next_state)
        state=next_state
        if done:
            break
print(agent.q_table)
 
 
#显示迷宫的路线
from PIL import Image
def maze_to_image(maze,path):
    size=maze.shape[0]
    img=Image.new('RGB',(size,size),(255,255,255))
    pixels=img.load()
    for i in range(size):
        for j in range(size):
            if maze[i,j]==-1:
                pixels[j,i]=(0,0,0)
            elif maze[i,j]==1:
                pixels[j,i]=(0,255,0)
    for x,y, in path:
        pixels[y,x]=(255,0,0)
    return np.array(img)
 
#接着显示三个迷宫的图像：原图像、bfs求解图像，QLearning图像
plt.figure(figsize=(16,10))
image1=maze_to_image(env.maze,[])
plt.subplot(3,1,1)
plt.imshow(image1)
plt.title('original maze')
_,path=env.solve_maze(env.maze,env.start,env.end)
image2=maze_to_image(env.maze,path)
plt.subplot(3,1,2)
plt.imshow(image2)
plt.title('BFS')
image3=maze_to_image(env.maze,env.path)
plt.subplot(3,1,3)
plt.imshow(image3)
plt.title('QL')
 
plt.show()
 

借鉴：基于RL(Q-Learning)的迷宫寻路算法 - N3ptune - 博客园 (cnblogs.com)