Q-learning学习记

使用MATLAB生成m*n迷宫,输入起终点,通过Q-learning得到迷宫的跑法
使用MATLAB生成m*n迷宫,输入起终点,通过Q-learning得到迷宫的跑法

最先提出:Watkins&Dayan in 1992。

个人观点:它是通过通过重复随机试探得到在一定环境下的处于某个状态时的行为概率最优解。Q-learning得到的解一般是局部最优解。Q矩阵(训练后得到Q值表)与可能矩阵P,奖励矩阵R密切相关。在迷宫中,如果迷宫本身无解,Q-learning自然也不会得到结果;迷宫有解,Q-learning也未必能迅速得到结果,当然,具体实现时添加了一些Q-learning理论外的细节,未概括Q-learning的所有可能。

什么是Q-learning

入门可参考房间问题(中文)

图1 房间图

假设一栋建筑里面有5个房间,房间外通过门相连(如上图所示)。我们将这五个房间按照从0到4进行编号,且建筑的外围可认为是一个大的房间,编号为5.

图2 房间对应节点图
图3 房间问题起止点

设想一下,当一个人被困在房间中时,他是没有找到出路的,只有找到终点才算闯关成功。这个简单的Q-learning例子也是如此,只要没有到达终点就不会有任何奖励。

图4 节点图奖励

除了奖励,这里还有一些细节问题,就是当一个人在处在某个具体房间时,它只能到达与当前房间有门相连的房间。例如,当一个人在房间2时,只能去往房间3。当然,你也许会说也可以留在房间2,但是这在本例中没有意义,留在非终点房间会浪费本可以出去寻找出路的时间。对于这些并不联通的房间,我们应该如何使得机器人不走这些实际不存在的路径(如2直接到0)了,我们可以用6个向量(房间0到房间5有6个)来存储,每个向量表示可以走的房间,即处于某个状态时所能进行的行为。但这样过于复杂了,不如直接使用矩阵存储所有状态所能进行的所有行为。对于这个不存在的行为,可以将这些行为给与负奖励。对于那些可行的行为,可以给与0奖励或者正奖励。但是我不想进行那么多思考,我只给与最后到达终点的行为正奖励,其余的可行行为给与0奖励,让机器人自己去试探。

图5 奖励矩阵

我们添加一个与R矩阵同维的Q矩阵,经过训练后的Q矩阵就是我们需要的经验矩阵,即Q值表。

Q-learning学习的转移算法如下:

\(
\begin{align}
Q(state, action) = R(state, action) + \gamma * Max[Q(next state, all actions)]
\end{align}
\)

下面是整个Q-learning的步骤:

\(1.设定 \gamma 值和奖励矩阵R.\\2.初始化Q为与R同维的零矩阵. \\ 3.(For)对于每次探索: \\ \; \; 选择一个随机初始状态.\\ \; \; (do \ while)未到达目标时继续以下步骤: \\ \qquad \cdot 在当前状态下的所有可行action中挑选出一个.\\ \qquad \cdot使用该action,考虑下一个状态. \\ \qquad \cdot 对于下一个状态,基于所有可能action获得最大的Q值表.\\ \qquad \cdot 计算Q(state, action) = R(state, action) + \gamma * Max[Q(next state, all actions)].\\ \qquad \cdot 将下一个状态设为当前状态. \\ \; \,(end \ do) \\ \; \; (End \ For)\)

每次探索(成功从随机初始位置到达终点)都是一次训练,每次训练可能只是更新矩阵Q中的部分元素,但是由于每次探索的初始位置是随机的,因此理论上,训练越多,矩阵Q中被更新的元素也越多,训练次数过少,可能Q值表未收敛,但是至少需要训练多少次了,我不知道,目前只是采用一种估计的办法保证其能收敛。

\( \gamma (0 \le \gamma <1) \),\( \gamma \)越接近0,就越倾向于考虑当前状态的奖励,\( \gamma \)越接近1,就越倾向于关注长期的奖励。

机器人根据以上的算法不断尝试,只要能到达终点,Q值表就会被更新,有了Q值表,机器人下次做同样的任务就有了参考。

%MATLAB代码
gammar=0.8;%0<gammar<1即可。
R=[-1,-1,-1,-1,0,-1;
   -1,-1,-1,0,-1,100;
   -1,-1,-1,0,-1,-1;
   -1,0,0,-1,0,-1;
   0,-1,-1,0,-1,100;
   -1,0,-1,-1,0,100];
Q=zeros(size(R));
[row,column]=size(R);
for circulation=1:500
    episole=randi(row);
    for j=1:column
        if R(episole,j)>=0
            action=j;
            next_episole=action;
            Q(episole,action)=R(episole,action)+gammar*
             max(Q(next_episole,:));
        end
    end
end

Q-learning能做什么?

Q-learning非常适用于走迷宫,尤其是一维二维迷宫。将迷宫中的位置映射为Q矩阵的状态,行为映射为Q矩阵的行为,完全适配,Q-learning的方法简直就是为走迷宫而生的。三维或以上的迷宫也行,将三维位置矩阵重组为为一维位置向量,行为矩阵对应行为向量,位置向量和行为向量共同组成了Q矩阵。

Q-learning更详细版

前面提到了Q-learning的每次探索的更新公式,下面给出一个更全面的更新公式:

\( Q(state, action) = (1-\alpha)*Q(state,action) + \alpha*(R(state, action) + \gamma * Max[Q(next state, all actions)]) \)

其中,\( \alpha (0 < \alpha \le 1)\),\( \alpha\)(学习率)越大,Q值表更新依据过去经验越少,\( \alpha\)越小,Q值表更新一句过去的经验越大。

既然前面说到可以使用Q-learning走迷宫,下面就给一个可以解决二维迷宫问题的MATLAB程序。

程序输入:环境矩阵的行数,列数;起点位置;终点位置
程序输出:环境Figure图;每次成功探索的路径Figure图;最终最短路径Figure图;每次探索步数变化Figure图;在程序运行位置输出Q_learning_m_n.mp4

%% 程序信息
%%程序名:Q_learning_m_n.m
%%用途:用户输入行数、列数生成一个随机迷宫矩阵,并且输入起点坐标、终点坐标,
%%程序会自动得出最终路径,并会给出学习过程中的可行路径,并将学习路径生成MP4
%%保存,另外还会显示学习过程中成功到达终点的步数变化曲线。
%%目前已知BUG:因为环境矩阵是随机生成的,因此可能出现起终点在障碍物上或者完全
%%被障碍物包围的情况,此时是没有路径解的。
%%作者:zecazi(https://zecazi.com)
%%版本:beta
%% 清理
clear;
clc;
close;
%% 环境矩阵初始化
m=input("请输入环境行数m:");%%此处m其实就是下面的row
n=input("请输入环境列数n:");%%此处n其实就是下面的column
environment=ones(m,n);%%此处environment与下面的P密切相关
%设置障碍物
%%%%%%%environment=randsrc(m,n,[0,1;0.1,0.9]);%%没有买,用不了...555%%
%此处是绕远路随机生成一个矩阵environment,值为1时可通过,值为0时为障碍物。
environment_1=randi([0,1],m,n);
environment_2=randi([0,1],m,n);
environment_3=randi([0,1],m,n);
environment=environment-environment_1.*environment_2.*environment_3;
%% 指定机器人运动的起点和终点的x,y值
Start_point_x = input("请输入起点行数行数Start_point_x:"); 
Start_point_y = input("请输入起点行数列数Start_point_y:"); 
End_point_x = input("请输入终点行数行数End_point_x:"); 
End_point_y = input("请输入终点行数列数End_point_y:"); 
%指定起终点为-1
environment(Start_point_x,Start_point_y)=-1;
environment(End_point_x,End_point_y)=-1;
%% 初始化视频
v=VideoWriter('qlearning_m_n','MPEG-4');
v.FrameRate=1;
v.Quality=100;
open(v);
%% 展示生成的环境地图矩阵
disp('Environment matrix is:  (1 represents valid path,0 represents unvalid path, -1 represents start or goal)')
disp(environment);
figure(1);
imagesc(environment);
text(Start_point_y ,Start_point_x ,'SP','HorizontalAlignment','center');
text(End_point_y,End_point_x,'EP','HorizontalAlignment','center');
title('机器人运动环境地图');
axis tight;
%保存至视频
H=4096;
W=4096;
F=getframe(gcf);
F.cdata = imresize(F.cdata, [H W]);
writeVideo(v,uint8(F.cdata));%重复三帧
writeVideo(v,uint8(F.cdata));%
writeVideo(v,uint8(F.cdata));%
%% _________________________开始训练__________________________
%% 环境初始化
gammar=0.8;
alpha=0.5;
row=m;
column=n;
action_number=4;
P=ones(row*column,action_number);
start=(Start_point_x-1)*column+Start_point_y;
Goal=(End_point_x-1)*column+End_point_y;
Min_number_of_total_steps=column*row-1;
Max_number_of_total_steps=column*row;%%不会更新,只是说最多有多少步

Q=zeros(row*column,4);
circulation=ceil(4*sqrt(m*n));
len = zeros(1,circulation);

path_number=0;%视频录制的总图片数
%% 屏蔽地图边缘的试图越出地图线行为
for i=1:row
    for j=1:column
        if i==1
            P((i-1)*column+j,1)=0;%屏蔽上操作
        end
        if i==row
            P((i-1)*column+j,2)=0;%屏蔽下操作
        end
        if j==1
            P((i-1)*column+j,3)=0;%屏蔽左操作
        end
        if j==column
            P((i-1)*column+j,4)=0;%屏蔽右操作
        end
    end
end
%% 屏蔽掉障碍物点附近的移向障碍物点的操作及从黑名单点出发的操作
for i=1:row
    for j=1:column
        if environment(i,j)==0
            P((i-1)*column+j,:)=0;     %%屏蔽掉障碍物点附近的移向障碍物点的操作及从黑名单点出发的操作
            P((i-1)*column+j-1,4)=0;
            P((i-1)*column+j+1,3)=0;
            if i>=2
                P((i-2)*column+j,2)=0;
            end
            P((i+0)*column+j,1)=0;
        end
    end
end
%% 移向目标点的操作给与奖励
R=zeros(row*column,4);
if End_point_x==1
    R(End_point_x*column+End_point_y,1)=100;
elseif End_point_x<row
    R(End_point_x*column+End_point_y,1)=100;
    R((End_point_x-2)*column+End_point_y,2)=100;
elseif End_point_x==row
    R((End_point_x-2)*column+End_point_y,2)=100;
end
if End_point_y==1
    R((End_point_x-1)*column+End_point_y+1,3)=100;
elseif End_point_y<column
    R((End_point_x-1)*column+End_point_y-1,4)=100;
    R((End_point_x-1)*column+End_point_y+1,3)=100;
elseif End_point_y==column
    R((End_point_x-1)*column+End_point_y-1,4)=100;
end
%% 将P矩阵中0所对应R矩阵的值变成负数
for i=1:row*column
    for j=1:4
        if P(i,j)==0
            R(i,j)=-1;%%将P矩阵中0所对应R矩阵的值变成负数
        end
    end
end
%% 使用GPU运算
%%目前优化较差,不使用此段代码,见244行
%% 训练开始
for k=1:circulation
    initial=start;
    while(1)
        if initial==Goal
            break;
        end
        actions=find(P(initial,:)==1);
        action=actions(randi([1,length(actions)],1,1));
        if action==1
            next=initial-column;
        end
        if action==2
            next=initial+column;
        end
        if action==3
            next=initial-1;
        end
        if action==4
            next=initial+1;
        end 
        next_actions = find(R(next,:)>=0);
        max_q = 0;
        for j=1:length(next_actions)
            max_q = max(max_q,Q(next,next_actions(j)));
        end
        Q(initial,action) = (1-alpha)*Q(initial,action) + alpha*(R(initial,action) + gammar*max_q);
        initial=next;
    end
%% 判断训练的Q矩阵是否有效,即所有元素非负,至少有一个为正
    Q_positive=0;
    Q_negative=0;
    Q_valid=0;
    Q_positive=length(find(Q>0));
    Q_negative=length(find(Q<0));
    if Q_positive>0 && Q_negative==0
        Q_valid=1;
    end
%% 用Q-learning算法来进行路径规划 
    if Q_valid==1
        path=start;
        current=start;
        path_invalid=0;
        move=0;
        step=0;
        while(current~=Goal)
            initial=current;
            [~,move]=max(Q(current,:));
            if move==1 && P(current,move)==1
                current=current-column;
            end
            if move==2 && P(current,move)==1
                current=current+column;
            end
            if move==3 && P(current,move)==1
                current=current-1;
            end
            if move==4 && P(current,move)==1
                current=current+1;
            end
            if current~=initial
                step=step+1;
                path=[path,current];
            else
                path_invalid=1;
                break;
            end
        end
        if path_invalid==0
            path_number=path_number+1;
        end
%% 输出当前机器人的最短路径和最短路径步数
        if path_invalid==0
            if step<Min_number_of_total_steps && step~=0
                Min_number_of_total_steps=step;
                path_min=path;
            end
            if step~=0
                len(path_number)=step;
            end
%% 绘制机器人寻找最短路径过程
            figure('Name','机器人寻找最短路径过程');
            imagesc(environment,'Alphadata',0.5);
            text(Start_point_y ,Start_point_x ,'SP','HorizontalAlignment','center');
            text(End_point_y,End_point_x,'EP','HorizontalAlignment','center');
            title('机器人寻找最短路径可视化');
            axis tight;
            for k=1:length(path)
                path_row=ceil(path(k)/column);
                path_column=mod(path(k),column);
                if path_column==0
                    path_column=column;
                end
                text(path_column,path_row,'\bullet','Color','red','FontSize',20);
            end
            F=getframe(gcf);
            F.cdata = imresize(F.cdata, [H W]);
            writeVideo(v,uint8(F.cdata));%输出视频
            %%close all hidden;
        end
    end
end
%% 绘制机器人的最短路径
figure;
imagesc(environment,'Alphadata',0.5);
text(Start_point_y ,Start_point_x ,'SP','HorizontalAlignment','center');
text(End_point_y,End_point_x,'EP','HorizontalAlignment','center');
title('机器人最终的最短路径可视化');
axis tight;
for k=1:length(path_min)
    path_row=ceil(path_min(k)/column);
    path_column=mod(path_min(k),column);
    if path_column==0
        path_column=column;
    end
    text(path_column,path_row,'\bullet','Color','red','FontSize',20);
end
F=getframe(gcf);
F.cdata = imresize(F.cdata, [H W]);
writeVideo(v,uint8(F.cdata));%重复三帧
writeVideo(v,uint8(F.cdata));%
writeVideo(v,uint8(F.cdata));%
%% Q learning算法规划的路径长度变化趋势
figure;
plot(1:path_number,len(1:path_number),'-');
title('Q learning算法规划路径长度变化趋势');
hold on
F=getframe(gcf);
F.cdata = imresize(F.cdata, [H W]);
writeVideo(v,uint8(F.cdata));%重复三帧
writeVideo(v,uint8(F.cdata));%
writeVideo(v,uint8(F.cdata));%
close(v);
例子:

请输入环境行数m:10
请输入环境列数n:10
请输入起点行数行数Start_point_x:1
请输入起点行数列数Start_point_y:1
请输入终点行数行数End_point_x:10
请输入终点行数列数End_point_y:10

图6 机器人运动环境图
图7 机器人最终的最短路径可视化
注意事项:

如果环境超过50*50,推荐取消close all hidden(第230行)的注释,以免内存不够。

未填的坑:

  • 为什么Q-learning算法会收敛?
  • Q-learning真的一定会找到最优解么?
  • Q-learning程序的过程中一个关键是随机数,这个随机数实际上是一个伪随机数,即便是真随机数,它找到的不也只是某个状态,实际上也没有遍历所有状态,所以可能不是真最短路径。
  • Q-learning是否会出现在某次探索中出现死循环,以至于无法得到结果的情况?如果有,应该可以通过设定一个上限值,当走过上限步还没得到结果即跳出循环。
  • Q-learning中随机的是状态,如果把随机状态改为随机行为了?
  • Q-learning程序开始跑前的数据预处理。
  • Q-learning的后续算法。
  • MATLAB APP DESIGNER设计图形页面。

参考文献:
1.http://mnemstudio.org/path-finding-q-learning-tutorial.htm
2.https://blog.csdn.net/itplus/article/details/9361915
3.http://blog.sciencenet.cn/blog-3189881-1116209.html
4.https://blog.csdn.net/wffs_yz000/article/details/104067613
5.https://www.jianshu.com/p/a9a159da3d5b?from=singlemessage
6.https://www.cnblogs.com/pinard/p/9669263.html
7.https://analyticsindiamag.com/hands-on-guide-to-understand-and-implement-q-learning/
8.https://link.springer.com/content/pdf/10.1007/BF00992698.pdf


新手上路,难免有纰漏,如有纰漏,欢迎指正。

默认图片
admin
文章: 6

一条评论

  1. 这是一个匿名
    这是一个匿名

    嘿嘿嘿,踩踩!👻

留下评论