目录

一.摘要

二.路径规划技术的研究进展

1.研究现状

2.算法分类

 2.1 全局路径规划算法

2.2 局部路径规划算法

三.本文采用的路径规划算法——强化学习

1. 概念

 2. 与其他机器学习方式的区别

 3. 强化学习模型

4.马尔可夫决策过程

5. Q-learning算法

四．算法设计及代码实现

 1.UI设计

 2.机器人路径规划算法设计

 2.1 机器人行进方式

 2.2 变量设置：

 2.3 算法步骤

五． 算法训练结果分析

 1.训练参数

          2.训练结果

六．实践过程    
    
    
 、体会与反思

七．算法改进和研究展望

1.基于Q-learning算法改进研究现状

2.本文算法的后期改进展望

一.摘要

       移动机器人路径规划一直是热门的研究领域    
    
    
 ，相关的算法丰富多样    
    
    
。本实践前期对机器人路径规划算法做了详细调研


     


     


     ，检索并阅读了相关文献
 




 




 




，了解了可视图法


     


     


     、人工势场法
 




 




 




、启发式算法   

   

   

、神经网络算法等算法在机器人路径规划中的具体应用   

   

   

，本文采用强化学习中的 Q-learning 算法规划机器人的运动路径 

     

     

     ，做了算 法概念学习 

     

     

     、算法代码设计

  




  




  



、算法参数调优  


  


  


、算法训练测试等具体工作

  




  




  



，查阅相 关开发资料后  


  


  


，决定应用 QT Creator 5.0.2 作为开发环境  
     
     
    ，采用栅格建模作为算 法应用情景  
     
     
    、开发语言为 C++语言     


     


     


 。

        在完成上述算法设计和算法应用情景开发后


   




   




   


，对算法进行仿真验证 



 



 



，训练次 数分别为 200


   




   




   


、1000 



 



 



、5000 次                ，障碍物比例分别设置为 0.2                、0.3



    




    




    

、0.5



    




    




    

，仿真后导 出数据绘制出普通折线图和堆积折线图














，呈现结果                ，也发现了算法收敛速度慢














、 初始次数搜索效率低等特点




 




 




 。 最后对本次实践做出总结和反思



     



     



     
，对算法改进的方向做了描述














，检索并阅读 了大量有关改进强化学习算法规划机器人运动路径的文献    
    
    
 ，对这些文献一一做了 简要概括
   

   

   

。并且对本文算法的未来改进计划做出了初步设想     

     

     

。 

   关键词：移动机器人 路径规划 强化学习 Q-learning

二.路径规划技术的研究进展

1.研究现状

     路径规划是指在规定区域内规划出一条从起始点到目标点的最优解路径


     


     


     ，且 要保证与障碍物无碰撞 




  




  




  。机器人路径规划存在的难点问题主要有环境建模问题                、 算法收敛速度慢以及容易陷入局部最优解问题

  


  


  

。[1]

2.算法分类

     路径规划可以分为传统算法路径规划和智能仿生算法路径规划两类
 




 




 




，其中传统路径规划算法又可以分为全局路径规划算法和局部路径规划算法     
     
     
。

 2.1 全局路径规划算法

全局路径规划算法主要包括可视图法



     



     



     
、栅格法和自由空间法  




   




   




  。

（1） 可视图法

       可视图法由 Lozano-Perez 和 Wesley 于 1979 年在论文：《An Algorithm for Planning Collision-Free Paths among Polyhedral Obstacles.》中提出


 



 



 

。将机器人看作是一个 质点   

   

   

，障碍物看作是规则的多边形 

     

     

     ，分别把初始点














、各多边形的各个顶点和目标 点之间用直线相连

  




  




  



，直线不能穿过障碍物  


  


  


，这样得到的一张图即为可视图               。[2] 再经过优化  
     
     
    ，把一些不必要的连线去掉


   




   




   


，由出发点沿着所连的直线就可以到达目 标点 



 



 



，该路径就是一条无碰撞的可行路径                ，这就是可视图法   




    




    




  。如图所示















。

 （2） 栅格法

       采用正方形栅格表示环境



    




    




    

，每个栅格有一个表征值 CV














，表示在此方格中障 碍物对于机器人的危险程度                ，对于高 CV 值的栅格位置



     



     



     
，机器人优先躲避














，CV 值按其距机器人的距离被事先划分为若干等级               。每个等级对机器人的躲避方向会 产生不同影响    



     



     



  。

       障碍物的位置一旦被确定    
    
    
 ，就按照一定的衰减方式赋给障碍物本身及其周围栅格一定的值


     


     


     ，每个栅格的值代表了该位置有障碍物的可能性















。栅格具有简单    
    
    
 、 实用


     


     


     、操作方便的特点
 




 




 




，完全能够满足使用要求    
    
    
。

（3） 自由空间法

      主要思想是把障碍物按照一定的比例进行扩大   

   

   

，再把机器人按照合适比例缩小 

     

     

     ，再用设定好的凸多边形来描述机器人和环境

  




  




  



，以此来解决路径规划问题  


  


  


，优点是构建连通图方便  
     
     
    ，缺点是当障碍物比较多的时候


   




   




   


，算法复杂度较高 



 



 



，运行效率低下     


     


     


 。

2.2 局部路径规划算法

2.2.1启发式算法

（1）遗传算法

         Holland 于 1975 年首次提出遗传算法                ，是模仿生物进化中的基因遗传和优胜劣汰等过程的一种仿生学优化搜索算法




 




 




 。遗传算法通过模拟一个人工种群进化过程



    




    




    

，通过选择( Selection)
 




 




 




、交 叉 ( Crossover) 以及变异( Mutation) 等机制














，不断迭代搜索出近似最优解                ，进而达到求解的目的
   

   

   

。 遗传算法进行搜索时首先要对种群进行初始化



     



     



     
，而且需要确定问题求解的编码和解码过程














，一般情况下采取实数编码或二进制编码    
    
    
 ，对于每一次迭代过程


     


     


     ，遗传算法需要计算个体的适应度
 




 




 




，也就是个体对于问题的匹配程度     

     

     

。适应度的值越大   

   

   

，解的质量就越高 




  




  




  。 每一次迭代 

     

     

     ，种群需要经历选择   

   

   

、交叉 

     

     

     、变异三个步骤

  


  


  

。选择即从种群中选出适应性较好的个体

  




  




  



，淘汰适应性较差的个体传入下一代种群     
     
     
。交叉即对个体对中的基因序列进行交换  


  


  


，通过交叉  
     
     
    ，遗传算法对解的搜索能力得到有效提高  




   




   




  。[3]  变异即对个体基因序列中的基因值进行变动


   




   




   


，使得算法具有局部的随机搜索能力 



 



 



，并能够维持群体的多样性                ，防止算法出现过早收敛的情况


 



 



 

。 在迭代次数或者种群中最优个体的适应度达到一定阈值后算法终止               。种群中适应度最高的个体就 是求得的相对最优解   




    




    




  。

(2)粒子群算法

粒子群算法是一种基于群智能的随机优化算法



    




    




    

，于1995 年由Kennedy和Eberhart提出















。 该算法具有高效并行

  




  




  



、流程简单  


  


  


、易于编程实现等特点














，适于非线性优化问题的求解               。 其思想来源于对鸟群捕食行为的模拟                ，优化问题的潜在解通常称为“粒子    
    
    
”



     



     



     
，粒子属性可通过位置  
     
     
    、速度和适应度函数进行描述    



     



     



  。

(3)蚁群算法

又称蚂蚁算法














，是一种用来在图中寻找优化路径的机率型算法















。它由Marco Dorigo于1992年在他的博士论文“Ant system: optimization by a colony of cooperating agents     


     


     


 ”中提出    
    
    
 ，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为    
    
    
。蚁群算法是一种模拟进化算法


     


     


     ，初步的研究表明该算法具有许多优良的性质     


     


     


 。针对PID控制器参数优化设计问题
 




 




 




，将蚁群算法设计的结果与遗传算法设计的结果进行了比较   

   

   

，数值仿真结果表明 

     

     

     ，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值




 




 




 。

2.2.2 神经网络算法

       人工神经网络（Artificial Neural Networks

  




  




  



，ANN）系统是 20 世纪 40 年代后出现的
   

   

   

。它是由众多的神经元可调的连接权值连接而成  


  


  


，具有大规模并行处理


   




   




   


、分布式信息存储 



 



 



、良好的自组织自学习能力等特点     

     

     

。BP（Back Propagation）算法又称为误差 反向传播算法  
     
     
    ，是人工神经网络中的一种监督式的学习算法 




  




  




  。BP 神经网络算法在理论上可以逼近任意函数


   




   




   


，基本的结构由非线性变化单元组成 



 



 



，具有很强的非线性映射能力

  


  


  

。而且网络的中间层数                、各层的处理单元数及网络的学习系数等参数可根据具体情况设定                ，灵活性很大



    




    




    

，在优化



    




    




    

、信号处理与模式识别














、智能控制                、故障诊断等许 多领域都有着广泛的应用前景     
     
     
。

2.2.3 人工势场法

        人工势场实际上是对机器人运行环境的一种抽象描述  




   




   




  。在势场中包含斥力和引力极














，不希望机器人进入的区域的障碍物属于斥力极                ，子目标及建议机器人进入的区域为引力极


 



 



 

。引力极和斥力极的周围由势函数产生相应的势场               。机器人在势场中具有一定的抽象势能



     



     



     
，它的负梯度方向表达了机器人系统所受到抽象力的方向














，正是这种抽象力    
    
    
 ，促使机器人绕过障碍物


     


     


     ，朝目标前进   




    




    




  。人工势场法规划出的路径一般平滑且安全
 




 




 




，结构简单



     



     



     
、易于实现   

   

   

，但是有产生局部最优的问题















。

三.本文采用的路径规划算法——强化学习

1.概念

           强化学习（Reinforcement Learning ,RL） 

     

     

     ，是一种重要的机器学习方法

  




  




  



，机器学习分为监督学习














、无监督学习    
    
    
 、强化学习三种               。强化学习是系统从环境到行为映射的学习  


  


  


，目的是使奖励信号（强化信号）函数值最大    



     



     



  。[4] 换句话说  
     
     
    ，强化学习是一种学习如何从状态映射到行为以使得获取的奖励最大的学习机制















。一个动作需要不断在环境中进行实验


   




   




   


，环境对动作做出奖励 



 



 



，系统通过环境的奖励不断优化行为                ，反复实验



    




    




    

，延迟奖励    
    
    
。

 2. 与其他机器学习方式的区别

      也就是说与监督学习


     


     


     、无监督学习有什么不同之处     


     


     


 。监督学习的训练集中














，每一个样本都被打上标签                ，标签指代的是正确的结果




 




 




 。监督学习让系统按照每个样本所对应的标签推断出应有的反馈机制



     



     



     
，进而在没有打过标签的样本上也能计算出正确结果
   

   

   

。典型算法有：决策树
 




 




 




、支持向量机（SVM）   

   

   

、k-近邻算法（KNN）等     

     

     

。无监督学习是从无标签的数据集中发现隐藏的结构














，典型的例子就是聚类问题 




  




  




  。常见算法有k-均值(K-means) 

     

     

     、DBSCAN密度聚类算法

  




  




  



、最大期望算法等

  


  


  

。

       强化学习在交互中不存在监督学习中的正确标签    
    
    
 ，而是在自身的经验中去学习     
     
     
。强化学习的目标也不是寻找隐藏的结构


     


     


     ，而是最大化奖励  




   




   




  。

 3. 强化学习模型

            主体(Agent)通过与环境(environment)交互进行学习
 




 




 




，交互包括行动（action）   

   

   

，奖励(reward) 

     

     

     ，状态(state)


 



 



 

。交互过程表述如下：每一步主体都根据策略选择一个行动方式执行

  




  




  



，比如说向前走  


  


  


、向后走  


  


  


，然后感知做出该行动后的立即奖励  
     
     
    ，还有下一步的状态


   




   




   


，该状态也就是环境的状态 



 



 



，通过已有的经验再修改自己的策略做出下一个动作                ，经验就是根据这一步一步的动作学习来的



    




    




    

，每一步都积累一些奖励值(立即奖励)














，目标就是让累积的奖励值最大               。

假设主体所处的环境被描述为状态集S                ，可以执行的任意的动作集合A   




    




    




  。下面描述强化学习模型运作过程：

        强化学习系统(在主体上运作)接受环境状态的输入s



     



     



     
，根据内部的推理机制














，系统给出相应的动作a    
    
    
 ，环境在系统动作a下由s变迁到新的状态s’  


     


     


     ，系统再接受环境新状态的输入
 




 




 




，同时得到环境对于系统刚才动作的立即奖励r















。每次在某状态下执行动作   

   

   

，主体会收到一个立即奖励 

     

     

     ，环境变迁到新的状态               。如此产生了一系列的状态

  




  




  



，动作和立即奖励的集合  


  


  


，如图： 

         强化学习系统的目标是学习一个行为策略Π：S—>A  
     
     
    ，这个策略不是具体的某个动作


   




   




   


，更像是一种决策的经验集合 



 



 



，根据这个策略                ，系统每一步都能做出让环境奖励累积值达到最大的动作    



     



     



  。这个环境奖励累积值可以表示为：+γ++…(0<=γ<1)



    




    




    

，其中γ为折扣因子














，因为主体可能需要若干步才能到达目标                ，在这个过程中



     



     



     
，每一步环境给主体的奖励是要打折扣的















。

4.马尔可夫决策过程

     上述对强化学习模型的描述其实就是马尔可夫决策过程














，但是对一些值还要详细描述    
    
    
。环境给出的立即奖励=r(,)    
    
    
 ，产生后继状态函数+1=ℳ(,)


     


     


     ，该函数也叫状态转移函数     


     


     


 。在马尔可夫决策过程中
 




 




 




，r(,)和ℳ(,)只依赖于当前的动作和状态




 




 




 。

 主体的任务是学习到策略Π：S—>A   

   

   

，()=
   

   

   

。该策略从初始状态开始获得的累积奖励值为：

 我们的目的是让上面的(st)值最大 

     

     

     ，则这个策略就是最优策略

  




  




  



，表示为

最优策略Π*的值函数为*(s)  


  


  


，记为V*(s)     

     

     

。V*(s)给出了当主体从状态s开始时可获得的最大折算累积回报 




  




  




  。

      上图给出一个格状环境  
     
     
    ，每个箭头代表主体可采取的一个动作


   




   




   


，从一个状态转移到另一个

  


  


  

。每个箭头关联的数值代表主体执行该动作后的立即奖励r(s,a)     
     
     
。状态G可以看成是目标状态 



 



 



，主体只有进入该状态才有大于0的奖励值                ，进入其他状态的奖励值都为0



    




    




    

，一旦主体进入G就只能留在其中  




   




   




  。

       如图显示了每个状态的V*(s)值


 



 



 

。假设γ=90














，我们上面知道V*(s)给出了当主体从状态s（该格子）开始时可获得的最大折算累积回报                ，我们看下方中间的格子



     



     



     
，它的V*(s)为90














，从该格子走到目标状态的最优决策为先右后上（先上后右也一样）    
    
    
 ，这时可计算出折算累积回报为0+γ*100+*0+*0+…=90


     


     


     ，所以此格子用最优决策走到目标状态所能获得的最大累积回报就是90               。

5.Q-learning算法

        Q-learning是强化学习的算法之一   




    




    




  。Q-learning的主要目的就是学习状态动作价值函数的Q ( s , a )
 




 




 




，其中Q ( s , a )表示的是在给定当前状态s和采取动作a之后能够获得的收益期望















。Q-learning利用状态s和动作a张成一个Q表来储存Q值   

   

   

，然后根据Q值来选取能够获得最大收益的动作               。Q-learning采用是值迭代的方法进行求解 

     

     

     ，其核心的迭代公式为

      其中 ( s,a )是第k + 1次迭代函数

  




  




  



，s和a分别表示的是当前的状态和执行的动作并且它们分别属于状态空间S和动作空间A  


  


  


，r ( s , a )表示的是在状态s执行动作a后的即时奖励  
     
     
    ，s^和a ^表示的是下一个的状态和行为


   




   




   


，γ表示的是折扣系数    



     



     



  。

 举个例子：

        图3.6是主体的初始状态和初始假设中几个相关的Q值 



 



 



，如Q(,)=73                ，其中指代主体向右的动作















。主体执行动作后



    




    




    

，受到立即奖励为0














，并转换到下一状态                ，然后它基于对新状态的Q估计更新其Q(,)



     



     



     
，这里γ=0.9    
    
    
。

       每次主体从旧状态前进到新状态














，Q-learning会从新状态到旧状态向后传播其Q值     


     


     


 。同时    
    
    
 ，主体收到的此转换的立即奖励被用于扩大这些传播的Q值


     


     


     ，可以证明Q值在训练中永远不会下降




 




 




 。

     Q的演化过程如下：初始Q值都为0
 




 




 




，算法不会改变任何Q表项   

   

   

，直到它恰好到达目标状态并且收到非零奖励 

     

     

     ，这导致通向目标状态的转换的Q值被精化;在下一个情节中

  




  




  



，如果经过这些与目标状态相邻的状态  


  


  


，那么其非零的Q值会导致与目的相差两步的状态中值的变化; 以此类推  
     
     
    ，最终得到一个Q表
   

   

   

。

      如果系统是一个确定性的马尔可夫决策过程


   




   




   


，则立即奖励值都是有限的 



 



 



，主体选择动作的方式为它无限  
     
     
    、频繁地访问所有可能的状态-动作对                ，那么算法会收敛到一个等于真实Q函数值的Q（近似）     

     

     

。

四．算法设计及代码实现

开发环境：Qt Creator 5.0.2   C++语言开发

参考了CSDN博主“榕林子




 




 




 ”



    




    




    

，“~在下小吴
   

   

   

”的文章

程序架构等设计参考了榕林子的文章














，链接如下：

文献[5]人工智能学习之机器人路径规划优化_榕林子的博客-CSDN博客_人工智能路径规划

算法设计参考了~在下小吴的文章                ，链接如下：

文献[6]基于Q-learning的无人机三维路径规划（含完整C++代码）_～在下小吴的博客-CSDN博客_无人机三维路径规划

程序架构：

        Mainwindow中放置了按钮的槽函数



     



     



     
，以及强化学习的训练流程














，控制的是主页面    
    
    
 ，Mainwindow.ui也是绘制的主页面


     


     


     ，messagecontrol控制的是单元格
 




 




 




，它的ui是绘制单元格的效果   

   

   

，messagecontrol.cpp中定义了鼠标事件函数和单元格颜色更改函数 

     

     

     ，q_learning不需要ui

  




  




  



，里面定义了强化学习的action函数  


  


  


，用来控制机器人行动  
     
     
    ，定义了函数actpunish()


   




   




   


，用来初始化一些特殊位置的Q值 



 



 



，定义了get_expected_max_reward()                ，用来返回下一步选择的最大Q值



    




    




    

，也就是对应公式中的

 1.UI设计

      为机器人设置了行走的空间














，以表格的形式展现                ，这里使用了控件TableWidget,分成23行



     



     



     
，15列














，但是第一行第一列的坐标都是从0开始    
    
    
 ，所以最后一个格子（右下角）的坐标是（22,14） 




  




  




  。

      这里注意


     


     


     ，在手动设置UI时
 




 




 




，要保证TableWidget足够大   

   

   

，否则在运行程序时 

     

     

     ，一部分表格会显示不全

  




  




  



，我在开发程序的时候  


  


  


，想为起始点（0  
     
     
    ，0）设置颜色


   




   




   


，弄了很长时间 



 



 



，换了好几种配置颜色的方式                ，都发现没效果



    




    




    

，最后才发现是在.ui那个文件中














，TableWidget不够大                ，遮挡了一部分格子

  


  


  

。

画面右侧设置了几个按钮



     



     



     
，逐一介绍：

（1）设置障碍物

鼠标点击单元格














，可以选中变色    
    
    
 ，效果如下：

 变色的格子就是鼠标点击选中的


     


     


     ，如果后悔不想要选中这个
 




 




 




，再点击一次   

   

   

，就可以取消 

     

     

     ，选中需要设置障碍物的格子之后

  




  




  



，点击按钮“设置障碍物     

     

     

”  


  


  


，格子就会变成灰色  
     
     
    ，效果如下：

如果想改变障碍物位置


   




   




   


，可以再点击一次格子 



 



 



，会从灰色变成刚才选中的状态                ，相当于取消了设置成障碍物     
     
     
。

（2）清除按钮

点击后可以清除所有的障碍物和行走轨迹  




   




   




  。

（3）开始寻路

该按钮点击后



    




    




    

，机器人从起始点出发开始寻径














，按钮文字会从“开始寻路（Enter） 




  




  




  ”变为“停止寻路 (Enter)

  


  


  

”                ，再次点击按钮



     



     



     
，寻径就会暂停














，可以随时切换状态


 



 



 

。

（4）清空Q表记录

点击该按钮之后    
    
    
 ，本地记录Q表值的文本文件就会被清空


     


     


     ，可以防止数据冗余
 




 




 




，方便后续的算法测试               。

此处代码用到Qfile里面的读写

1. QFile file("D:/Qt/project/robotpath/algorithmdata.txt"); 2. //对文件进行写操作 3. file.open(QIODevice::WriteOnly|QIODevice::Truncate); 4. file.close();

 这里面QIODevice::Truncate代表的是打开文件时清空文件所有内容   




    




    




  。

（5）清空Qtable

后面训练要用到这个按钮   

   

   

，否则每次都要重新运行















。

（6）剩余按钮

剩余三个按钮从上至下分别是“打印训练次数     
     
     
”


   




   




   


、“打印步数  




   




   




  ” 



 



 



、“打印成功走到终点的总次数


 



 



 

”               。用的控件都是LineExit

“打印训练次数               ”是当训练次数是10的倍数时才打印出来 

     

     

     ，“打印步数   




    




    




  ”也一样    



     



     



  。

此处用的代码都是：

1. char buffer1[256]; 2. sprintf(buffer1,"步数为: %d\n",j); 3. ui->lineEdit_2->setText(buffer1);

 用sprintf函数把整形变量转化为字符型

  




  




  



，存在字符数组中再显示在控件上















。

各种点的UI  


  


  


，包括起始点  
     
     
    ，轨迹


   




   




   


，终止点 



 



 



，障碍物                ，选中点：

先上代码：

enum CellType 2. { 3. Null = 0 , Barrier = 1 , Candidate = 2, Path = 3, Selected=4, Start=5 ,End=6, Win=7 4. } type; 5. 6. void MessageControl::setCellType(CellType type) 7. { 8. 9. this->type = type; 10. if(type == MessageControl::Null) 11. { 12. 13. ui->widget->setStyleSheet(QString("background-color:%1;").arg(defaultColor.name())); // 设置背景色 14. 15. } 16. if(type == MessageControl::Barrier) 17. { 18. ui->widget->setStyleSheet(QString("background-color:%1;").arg(barrierColor.name())); // 设置背景色 19. 20. 21. } 22. if(type == MessageControl::Candidate) 23. { 24. ui->widget->setStyleSheet(QString("background-color:%1;").arg(candidateColor.name())); // 设置背景色 25. 26. } 27. if(type == MessageControl::Path) 28. { 29. 30. ui->widget->setStyleSheet(QString("background-color:%1;").arg(pathColor.name())); // 设置背景色 31. 32. } 33. if(type == MessageControl::Selected) 34. { 35. ui->widget->setStyleSheet(QString("background-color:%1;").arg(selectedColor.name())); // 设置背景色 36. 37. } 38. if(type == MessageControl::Start) 39. { 40. MessageControl::palette.setBrush(QPalette::Active, QPalette::Base, QBrush(Qt::green)); // 设置背景色 41. this->setPalette(palette); 42. } 43. if(type == MessageControl::End) 44. { 45. MessageControl::palette.setBrush(QPalette::Active, QPalette::Base, QBrush(Qt::blue)); // 设置背景色 46. this->setPalette(palette); 47. } 48. if(type == MessageControl::Win) 49. { 50. ui->widget->setStyleSheet(QString("background-color:%1;").arg(winColor.name())); // 设置背景色 51. } 52. }

     思路就是为函数setCellType(CellType type)传进去一个参数



    




    




    

，这个参数的数据类型在.h文件中定义过了














，是一个元素类型                ，有起始点(Start)                、终止点(End)



    




    




    

、障碍物(barrier)














、轨迹(Path)等



     



     



     
，都可以用数字来表示














，传到函数中之后    
    
    
 ，函数会根据type来设置对应的颜色    
    
    
。那么如何跟单元格选中关联起来呢


     


     


     ，如何通过鼠标触发呢？

     QT有一个与众不同的“信号和槽















”机制
 




 




 




，用connect函数可以将两个不同文件中的函数连接在一起   

   

   

，一个函数作为信号发出者 

     

     

     ，在发送方.h文件中定义为signal

  




  




  



，另一个函数作为槽  


  


  


，接收信号  
     
     
    ，在接收方.h文件中定义为slot     


     


     


 。

比如：

发送方： messagecontrol文件

 接收方：  mainwindow文件

 关于QT信号与槽机制具体内容可以查看参考文献[7]




 




 




 。

1. //鼠标控制栅格选择 2. void MessageControl::mousePressEvent(QMouseEvent *event) //摁住鼠标事件 3. { 4. if(this->type == MessageControl::Selected) //如果已经选中了
   

   

   

。再次点击及取消选中状态 5. { 6. this->setCellType(MessageControl::Null); 7. emit this->selectedCancelIndex(pos_y,pos_x); //给mainwindows类发送一个信号 8. } 9. else 10. { 11. this->setCellType(MessageControl::Selected); 12. emit this->selectedCellIndex(pos_y,pos_x); //给mainwindows类发送一个信 13. } 14. }

         鼠标选中单元格时


   




   




   


，会把该单元格坐标pos_x,pos_y传入信号函数 



 



 



，发送给mainwindow                ，这里emit就是发送信号的意思



    




    




    

，mainwindow中的对应槽函数就会接收到参数














，将该单元格坐标加入到已选中坐标数组中                ，同时给setCellType传入颜色参数



     



     



     
，使其变色     

     

     

。

 2.机器人路径规划算法设计

 2.1 机器人行进方式

 八叉树的方式行进














，可以有八个运动方向：

 用八个常量代表八个方向：

1. const int up=1; 2. const int down =2; 3. const int Left =3; 4. const int Right=4; 5. const int leftup=5; 6. const int leftdown=6; 7. const int rightup=7; 8. const int rightdown=8;

 2.2变量设置：

1. double R=0.8; //折扣因子 2. int flag=1; //用来记录机器人是否位置改变    
    
    
 ，1为改变 3. int over; //判定是否到达终点 4. double length=0.0; //打印路径长度 5. double Qtable[TABLE_COLUMN+2][TABLE_ROW+2][8]={0.0}; //存放奖励函数Q的表


     


     


     ，每次训练更新一遍
 




 




 




，8(方向)+1(障碍)+4(边沿)=13 6. double r[TABLE_COLUMN+2][TABLE_ROW+2]={0.0}; 7. double action(int act , int& x,int& y,int& den); 8. void initplace(int& x,int& y,int& den); 9. double get_expected_max_reward(int x,int y); 10. void actpunish();  R：折扣因子   

   

   

，用来为每一次的延迟奖励打折扣； flag: 用来判定机器人目前位置相对于上次的位置是否发生改变 

     

     

     ，初始设置为1

  




  




  



，代表发生改变； over: 判断机器人是否到终点的值； Qtable: Q值表  


  


  


，每一个单元格有八个对应的Q值  
     
     
    ，分别代表向一个方向行进的Q值是多少 




  




  




  。比如Qtable[0][0][1]就代表在坐标(0,0)处


   




   




   


，向上走的Q值是多少； r[][]: 立即奖励值 



 



 



，每走到一个单元格                ，环境都给一个立即奖励； Initplace：初始化



    




    




    

，把起始点                、终止点



     



     



     
、over都初始化；

剩下几个函数前面介绍过了

  


  


  

。

！注意：

      采用 ε- 贪心策略选择动作 a














，在状态 s 下执行当前动作 a                ，得到新状态 s 和奖励 R     
     
     
。贪心系数Greedy =0.2  




   




   




  。Q-learning本质上是贪心算法


 



 



 

。但是如果每次都取预期奖励最高的行为去做



     



     



     
，那么在训练过程中可能无法探索其他可能的行为














，甚至会进入“局部最优               ”    
    
    
 ，无法完成游戏               。所以


     


     


     ，由贪心系数
 




 




 




，使得机器人有Greedy的概率采取最优行为   

   

   

，也有一定概率探索新的路径   




    




    




  。

2.3 算法步骤

   （1）Action:机器人从起始点出发 

     

     

     ，有一定概率随机选择运动方向

  




  




  



，否则向Q值最大的方向前进

   （2）Reward:如果遇到边界或障碍  


  


  


，机器人不动  
     
     
    ，返回一个惩罚值


   




   




   


，使该处该动作的Q值减小 



 



 



，下次尽量不做出该动作















。

Environment:如果正常前进                ，根据做出的动作



    




    




    

，由公式

算出上一步所在格子的Q表值               。

（4）超过步数限制（200步）














，则寻径失败    



     



     



  。

算法流程图如下（一次训练）：

 算法代码：

1. //强化学习寻径算法 2. void MainWindow::Reinforce() 3. { 4. 5. Q.actpunish(); //初始化边界惩罚值 6. int wintimes=0; //定义成功次数变量 7. int traintimes = QInputDialog::getInt(this, 8. "QInputdialog_Name", 9. "请输入要训练的次数", 10. QLineEdit::Normal, 11. 1, 12. 5000); 13. 14. for(int i=1;i<=traintimes;i++) //训练循环                ，traintimes为次数 15. { 16. Q.over=0; //成功与否判定变量 17. Q.initplace(start_x,start_y,Q.over); //初始化



     



     



     
，保险 18. Q.arrived_xy.clear(); //清空暂存所在格子坐标的数组 19. Q.arrived_xy.append(QPoint(start_x,start_y)); //把起始点加入暂存所在格子坐标的数组 20. int op=0; //动作的代号 21. 22. //每次训练清空前一次的轨迹 23. for(int i=0;i<=TABLE_ROW;i++) 24. { 25. for(int j=0;j<=TABLE_COLUMN;j++) 26. { 27. MessageControl* t_MessageControl =( MessageControl*) ui->tableWidget->cellWidget(i,j); 28. t_MessageControl->setCellType(MessageControl::Null); 29. if(i==0 && j==0) 30. t_MessageControl->setCellType(MessageControl::Start); 31. if(i==TABLE_ROW && j==TABLE_COLUMN) 32. t_MessageControl->setCellType(MessageControl::End); 33. 34. } 35. } 36. 37. 38. //障碍物标记保留 39. for(auto t:Q.barrier_xy) 40. { 41. MessageControl* t_MessageControl =(MessageControl *)(ui->tableWidget->cellWidget(t.x(),t.y())); 42. t_MessageControl->setCellType(MessageControl::Barrier) 43. } 44. 45. 46. //当训练次数为10的倍数时














，打印在框里 47. if(i % 10 == 0) 48. { 49. char buffer[256]; 50. sprintf(buffer,"训练次数为: %d\n",i); 51. ui->lineEdit->setText(buffer); 52. } 53. 54. //设置一个messagecontrol对象在目前所在格子 55. MessageControl* t_MessageControl =(MessageControl*) ui->tableWidget->cellWidget(Q.arrived_xy.at(0).x(),Q.arrived_xy.at(0).y()); 56. 57. for(int j = 0; j <= 100;j++) //一次训练最大不超过100步 58. { 59. 60. //走到10倍数次步数时打印步数 61. if(j % 10 == 0) 62. { 63. char buffer1[256]; 64. sprintf(buffer1,"步数为: %d\n",j); 65. ui->lineEdit_2->setText(buffer1); 66. } 67. 68. int regx=Q.arrived_xy.at(0).x(); int regy=Q.arrived_xy.at(0).y(); //提取此时坐标    
    
    
 ，后面传参要用 69. int regtwicex=regx; int regtwicey=regy; //再次暂存此时坐标


     


     


     ，后面更新Q表要用 70. double nextmax = -100; 71. 72. if(Q.flag==1) 73. { 74. MessageControl* t_MessageControl =(MessageControl*) ui->tableWidget->cellWidget(Q.arrived_xy.at(0).x(),Q.arrived_xy.at(0).y()); 75. //如果位置改变显示轨迹 76. t_MessageControl->setCellType(MessageControl::Path); 77. 78. } 79. //有概率随机产生一个动作 80. if(rand() % 80 > Greedy) 81. { 82. op = rand() % 8 + 1; 83. } 84. 85. //如果不随机
 




 




 




，寻找Q值最大的动作走 86. else 87. { 88. for (int m = 1; m <= 8; m++) 89. { 90. nextmax = max(nextmax + 0.0, Q.Qtable[regx][regy][m]); //遍历各个动作的Qtable值   

   

   

，寻找最大的那个值 91. } 92. for (int m = 1; m <= 8; m++) 93. { 94. 95. if (nextmax == Q.Qtable[regx][regy][m]) //寻找Q值最大的那个动作 96. op = m; 97. } 98. } 99. int reward = Q.action(op, regx ,regy, Q.over); //做出动作 

     

     

     ，并存下获得的奖励值 100. 101. Q.Qtable[regtwicex][regtwicey][op] += reward; 102. 103. if (Q.over == 1) 104. { 105. wintimes++; //如果成功

  




  




  



，加1 106. 107. MessageControl* t_MessageControl =(MessageControl*) ui->tableWidget->cellWidget(Q.arrived_xy.at(0).x(),Q.arrived_xy.at(0).y()); 108. t_MessageControl->setCellType(MessageControl::Win); 109. QMessageBox MyBox(QMessageBox::NoIcon,"提示","正确,寻径成功"); 110. MyBox.exec(); 111. break; 112. } 113. 114. 115. } 116. char bufferwintimes[256]; 117. sprintf(bufferwintimes,"成功次数为: %d\n",wintimes); //展示成功次数 118. ui->lineEdit_wintimes->setText(bufferwintimes); 119. 120. if(Q.over != 1) 121. { 122. QMessageBox::critical(this,"错误","找不到路径"); 123. //控件还原 124. ui->tableWidget->setEnabled(true); 125. ui->pushButton_barrier->setEnabled(true); 126. ui->pushButton_clear->setEnabled(true); 127. ui->lineEdit->setEnabled(true); 128. ui->pushButton_find->setText("开始寻路 (Enter)"); 129. } 130. 131. 132. //打印Qtable 133. //创建文件对象  


  


  


，指定文件位置 134. QFile file("D:/Qt/project/robotpath/algorithmdata.txt"); 135. //对文件进行写操作 136. if(!file.open(QIODevice::WriteOnly|QIODevice::Text|QIODevice::Append)) 137. { 138. QMessageBox::information(this,"警告","请选择正确的文件！"); 139. } 140. else 141. { 142. QTextStream stream( &file ); 143. stream<<QString::number(i)<<endl; 144. if(Q.over==1) 145. stream<<"Win"<<endl<<endl; 146. else 147. stream<<"fail"<<endl<<endl; 148. for(int j=0;j<=TABLE_COLUMN;j++) { for(int i=0;i<=TABLE_ROW;i++) 149. { 150. stream<<QString::number(i)<<" "<<QString::number(j)<<":"<<" "; //打印格子坐标 151. for(int k=1;k<=8;k++) 152. { 153. stream<<QString::number(Q.Qtable[i][j][k])<<" "; //打印Qtable值 154. } 155. stream<<endl; 156. 157. } 158. } 159. stream<<endl; 160. } 161. } 162. } 163. 164. 165. void Q_learning::actpunish() 166. { 167. for(int i=0;i<=TABLE_COLUMN;i++) 168. { 169. Qtable[0][i][leftup] = S; 170. Qtable[0][i][rightup] = S; 171. Qtable[0][i][up] = S; 172. Qtable[TABLE_ROW][i][down] = S; 173. Qtable[TABLE_ROW][i][leftdown] = S; 174. Qtable[TABLE_ROW][i][rightdown] = S; 175. } 176. for(int i=0;i<=TABLE_ROW;i++) 177. { 178. 179. Qtable[i][0][Left] = S; 180. Qtable[i][0][leftup] = S; 181. Qtable[i][0][leftdown] = S; 182. Qtable[i][TABLE_COLUMN][Right] = S; 183. Qtable[i][TABLE_COLUMN][rightup] = S; 184. Qtable[i][TABLE_COLUMN][rightdown] = S; 185. } 186. Qtable[TABLE_ROW][TABLE_COLUMN][Right] = 0; 187. Qtable[TABLE_ROW][TABLE_COLUMN][down] = 0; 188. Qtable[TABLE_ROW][TABLE_COLUMN][rightdown] = 0; 189. 190. srand(time(0)); //种一个随机种子  
     
     
    ，后面选择动作要用 191. } 192. 193. 194. 195. //判断下一步选择中最大的奖励值 196. void Q_learning::initplace(int& x,int& y,int& den) //初始化机器人位置 197. { 198. x=0; 199. y=0; 200. den=0; //是否到终点


   




   




   


，不到都为0; 201. } 202. double Q_learning::get_expected_max_reward(int x,int y) //得到最大期望Q值 



 



 



，用来后面传播到旧状态改变其Q值 203. { 204. double Nexstpmaxrd = -100; 205. for(int i=1;i<=8;i++) 206. { 207. Nexstpmaxrd = max(Nexstpmaxrd,Qtable[x][y][i]); 208. } 209. return Nexstpmaxrd; 210. } 211. 212. //行为函数 213. double Q_learning::action(int act , int& x,int& y,int& den) 214. { 215. //边界的惩罚 216. if((x==0 && act == Left) || (x==0 && act == leftup) || (x==0 && act == leftdown)) 217. { 218. flag=0; 219. return S; //S为遇到边界和障碍的惩罚值                ，会在main函数或别处全局定义



    




    




    

，统一值为-5; 220. } 221. if((x==TABLE_ROW && act == Right ) || (x==TABLE_ROW && act == rightup) || (x==TABLE_ROW && act == rightdown)) 222. { 223. flag=0; 224. return S; 225. } 226. if((y ==0 && act == up) || (y==0 && act == leftup) || (y==0 && act == rightup)) 227. { 228. flag=0; 229. return S; 230. } 231. if((y==TABLE_COLUMN && act == down) || (y==TABLE_COLUMN && act == leftdown) || (y==TABLE_COLUMN && act == rightdown)) 232. { 233. flag=0; 234. return S; 235. } 236. //障碍物惩罚 237. if((barrier_xy.contains(QPoint(x+1,y)) && (act==Right || act == rightup || act==rightdown)) || (barrier_xy.contains(QPoint(x,y+1)) && (act==down || act == rightdown || act==leftdown)) || (barrier_xy.contains(QPoint(x,y-1)) && (act== ( up || rightup || leftup) )) || (barrier_xy.contains(QPoint(x-1,y)) && (act==Left || act == leftup || act==leftdown)) 238. || (barrier_xy.contains(QPoint(x+1,y+1)) && (act==rightdown)) || (barrier_xy.contains(QPoint(x-1,y+1)) && (act==leftdown)) || (barrier_xy.contains(QPoint(x+1,y-1)) && (act== rightup )) || (barrier_xy.contains(QPoint(x-1,y-1)) && (act==leftup ))) 239. //格子为障碍物














，barrier为vector类型                ，在其他类中定义



     



     



     
，里面存储了障碍物的横纵坐标（points) 240. { 241. flag=0; 242. return S; 243. } 244. 245. //其他行为














，（正常行走）,八叉树 246. if(act == up) 247. y--; 248. if(act == down) 249. y++; 250. if(act == Left) 251. x--; 252. if(act == Right) 253. x++; 254. if(act == leftup) 255. { 256. x--; 257. y--; 258. } 259. if(act == leftdown) 260. { 261. x--; 262. y++; 263. } 264. if(act == rightup) 265. { 266. x++; 267. y--; 268. } 269. if(act == rightdown) 270. { 271. x++; 272. y++; 273. } 274. 275. //走到障碍周围一圈的格子    
    
    
 ，立即奖励-1


     


     


     ，因为贴近障碍
 




 




 




，该行为不好 276. if((barrier_xy.contains(QPoint(x+1,y)))|| (barrier_xy.contains(QPoint(x,y+1)) ) || (barrier_xy.contains(QPoint(x,y-1))) || (barrier_xy.contains(QPoint(x-1,y))) 277. || (barrier_xy.contains(QPoint(x+1,y+1)) ) || (barrier_xy.contains(QPoint(x-1,y+1)) ) || (barrier_xy.contains(QPoint(x+1,y-1)) && (act== rightup )) || (barrier_xy.contains(QPoint(x-1,y-1)) )) 278. //格子为障碍物   

   

   

，barrier为vector类型 

     

     

     ，在其他类中定义

  




  




  



，里面存储了障碍物的横纵坐标（points) 279. { 280. r[x][y]=-1; 281. } 282. 283. flag=1; 284. 285. arrived_xy.clear(); //清空旧位置 286. arrived_xy.append(QPoint(x,y)); //追加新位置 287. if(x == TABLE_ROW && y == TABLE_COLUMN ) //到达终点 288. { 289. den = 1; 290. return 100; //终点的奖励; 291. } 292. else if(x >= 0 && x < TABLE_ROW && y >= 0 && y < TABLE_COLUMN ) //正常走  


  


  


，非终点 293. { 294. double noractrew = get_expected_max_reward(x,y); 295. return r[x][y] + R * noractrew ; //计算最大奖励值 296. } 297. else 298. return 0; 299. }

五． 算法训练结果分析

主要的几个关键量：

（1）贪心因子greedy：

如果过大  
     
     
    ，随机选择一个动作的概率更高


   




   




   


，机器人不根据Q值做决策 



 



 



，偏向于探索                ，寻找到终点的速度变慢甚至走不到终点



    




    




    

，过小偏向于执行已知的最优策略














，易陷入局部最优















。这个量的设置问题在强化学习中叫作“探索与利用的平衡问题    



     



     



  ”

（2）障碍物比例

障碍物单元格数量占单元格总数量的比重                ，如果过高



     



     



     
，机器人要避障














，寻找到终点的速度变慢甚至走不到终点    
    
    
 ，过小算法收敛过快    
    
    
。

（3）惩罚值

走到边界的惩罚值与走到障碍物周围一圈的立即回报值     


     


     


 。

（4）折扣因子

设置为0.8




 




 




 。

先展示寻径成功与失败的效果：

 1.训练参数

决定训练次数分别设置为200


     


     


     ，1000
 




 




 




，2000
   

   

   

。

每个训练集障碍物比例设置为0.2（69块）   

   

   

，0.3（104块（约）） 

     

     

     ，0.5（173块（约））

训练结束之后     

     

     

。绘制最短路径长度随成功次数变化的曲线图

  




  




  



，并导出最后的Q表 




  




  




  。

下面展示障碍物比例分别为0.2














、0.3    
    
    
 、0.5时的地图：

障碍物比例为0.2时：  障碍物比例为0.3时：  障碍物比例为0.5时：

2.训练结果

（1）训练次数为200次

障碍物比例为20%时

共成功到达目标点15次  


  


  


，算法搜索效率很低  
     
     
    ，第一次成功规划路径是第2次训练


   




   




   


，共耗费88步走到目标点 



 



 



，路径长度为99.0538                ，但是后面的训练中成功到达目标点时



    




    




    

，花费的步数都高于88














，且起伏很大                ，算法并未收敛



     



     



     
，而且成功率很低














，体现了Q-learning算法的学习效率低的特点

  


  


  

。

 最后一次寻径成功是第171次    
    
    
 ，Q表值如下：

       每一排的前两个数是横纵坐标


     


     


     ，后面8个数分别表示机器人在该坐标处
 




 




 




，向上（向前）


     


     


     、下（向后）
 




 




 




、左上（左前）   

   

   

、左下（左后） 

     

     

     、右上（右前）

  




  




  



、右下（右后）行走的Q值     
     
     
。可以观察到训练后期   

   

   

，Q值已经变成位数很大的数据 

     

     

     ，我发现在训练20次左右的时候

  




  




  



，数据就开始突然变大  


  


  


，然后指数倍的增长  
     
     
    ，不知是什么原因


   




   




   


，所产生的数据完全与算法规则不符 



 



 



，突变出大型数值                ，导致后期规划混乱



    




    




    

，算法不收敛














，后面的训练都有这种状况  




   




   




  。

Q表值： 171 Win 132.61 0 0: -540 -5.91553e+09 -540 -1.28085e+11 -545 -555 -555 -1.16307e+11 1 0: -195 -6.1787e+10 -8.58994e+09 3.99978e+09 -205 -7.91668e+09 -230 -5.55515e+10 2 0: -545 -1.10888e+11 -1.3556e+11 -1.27496e+10 -525 -8.66903e+10 -535 -1.27769e+11 3 0: -490 -1.02349e+11 -1.15065e+09 -8.76738e+10 -495 -1.32569e+11 -485 -1.37798e+11 4 0: -170 -4.81268e+10 2.99004e+09 -3.59575e+10 -125 -4.24382e+10 -125 -5.26335e+10 5 0: -110 -4.5614e+10 -2.72063e+10 5.35786e+09 -60 -3.55193e+10 -105 -3.95195e+10 6 0: -320 -6.43811e+10 -4.29076e+10 -3.53212e+08 -325 -9.23418e+10 -320 -4.9942e+10 7 0: -205 -2.74853e+10 -3568 -4.23358e+10 -210 -5.29111e+10 -210 -4.49555e+10 8 0: -95 -2.21518e+10 1.90651e+09 5.46094e+09 -100 -2.11154e+10 -90 -4.66222e+10 9 0: -355 -1.15964e+11 -1.10417e+11 -7.09791e+10 -355 -8.54327e+10 -355 -6.67622e+10 10 0: -110 -2.14416e+10 3.57581e+09 -75 -100 -2.62768e+10 -85 -90 11 0: -5 0 0 0 -5 0 -5 0 12 0: -5 0 0 0 -5 0 -5 0 13 0: -5 0 0 0 -5 0 -5 0 14 0: -5 1.48284e+09 0 0 -5 0 -5 0 15 0: -5 0 -1 2.51721e+08 -10 0 -10 6.71069e+06 16 0: -15 0 2.68428e+06 2.40997e+09 -5 0 -15 -1 17 0: -5 0 0 0 -5 3.94824e+09 -5 -10 18 0: -5 0 0 0 -5 0 -5 0 19 0: -5 0 0 0 -5 0 -5 0 20 0: -5 0 0 0 -5 0 -5 0 21 0: -5 0 0 0 -5 0 -5 0 22 0: -5 0 0 -5 -5 0 -5 -5 0 1: -1.88066e+10 -2.1268e+10 -220 -9.74996e+10 -215 -215 -6.6572e+10 4.03973e+08 1 1: -1.00372e+11 -6.50058e+09 -7.58131e+09 -6.70237e+10 -5.83244e+10 -4.43726e+10 -4.46713e+09 6.87142e+09 2 1: -1.84638e+09 4.86814e+09 -7.08167e+10 -5.98703e+10 -7.45157e+10 -6.13059e+09 2.02657e+09 8.3264e+09 3 1: -4.94324e+09 1.20598e+09 -5.87107e+10 -7.53579e+10 9.48906e+08 8.83364e+09 -5.82448e+10 -6.8701e+10 4 1: -5.52235e+10 -3.67045e+10 -7.47185e+10 -2.98746e+10 8.39503e+09 4.07926e+09 -4.58165e+10 -4.22648e+10 5 1: -3.91606e+10 -2.83787e+10 -5.26321e+10 -3.73781e+10 -2.27742e+10 -3.70459e+10 3.67323e+09 -7.67153e+09 6 1: 4.36288e+09 -8.52213e+08 -3.27019e+10 -2.25191e+10 -4.14815e+10 -3.08243e+10 2.24586e+09 -3.7972e+09 7 1: 4.91081e+08 -4.11664e+09 -3.00648e+10 -3.37096e+10 1.56681e+09 1.55488e+07 -2.344e+10 -3.49186e+10 8 1: -3.81581e+10 -2.58559e+10 -3.18528e+10 -5.39406e+10 1.83811e+09 -2.44116e+09 1.56579e+09 -3.9917e+09 9 1: 4.69681e+09 3.03283e+08 -1.77255e+10 -4.81095e+10 -4.72446e+10 -3.58218e+10 -2.4228e+10 -3.69386e+09 10 1: -3.09596e+10 -1110 -4.08022e+10 -115 3.16912e+09 -1.8026e+09 -55 -115 11 1: 0 0 0 0 0 0 0 0 12 1: 0 0 0 0 0 0 0 0 13 1: 0 0 0 0 0 0 0 0 14 1: 0 -3.01819e+08 0 -4.29497e+09 0 -10 5.36855e+06 -2.93935e+08 15 1: 2.01377e+08 3.41316e+09 1.47653e+09 1.32909e+09 0 -4.29497e+09 2.14742e+06 -5.75121e+09 16 1: 0 -4.29497e+09 -2.14748e+09 1.38474e+09 5.36855e+06 -2.14748e+09 1.66136e+09 4.91642e+08 17 1: -1 -5 0 -25 0 -4.16554e+08 -15 -5 18 1: 0 0 0