开题报告
文献综述
路径规划问题[ 1 ]自提出以来，已有大量的研究成果，有学者从机器人感知环境的层面，将路径规划方法分为三类[ 2 ]：（1）基于环境模型的规划方法，（2）基于事例学习的规划方法和（3）基于行为的路径规划方法。从机器人在地图中规划的范围角度，亦可将其分为基于先验完全信息全局路径规划和基于机器人自身传感器信息的局部路径规划；从所处环境是否随着时间变化也可以分为静态的路径规划和动态路径规划。
在算法方面，人工势场（APF）[ 3 ]，A*[ 4 ]，动态A*[ 5 ][ 6 ]，快速爆炸随机树（RRT）[ 7 ]和其他算法已经被研究和开发多年。在这之中，由于A*的灵活性，A*算法一直是多年来相关研究的主导方法。虽然A*对于避免静态障碍物非常有效，但它可能不太适合动态环境，同时A*算法的复杂度很高，在环境未知多变的地图中还有无法求出有效解的可能。相较之下，APF模型可以描述障碍物的碰撞方位，并计算碰撞概率，从而找到一条可行的线路。然而，APF模型的主要问题是模型可能陷入局部极小。在这种情况下，目标很难正确地到达目的地。在这之后。相关的科研人员开发了RRT算法的扩展，以克服多路点路径规划的实际需求。RRT方法是一种基于抽样的方法的展开算法。RRT 的思想是快速扩张一群像树一样的路径以探索空间的大部分区域。对于狭窄通道，其截面积小，被碰到的概率低，导致RRT难以在有狭窄通道的环境找到路径，且它得到的路径一般质量都不是很好，不够光滑，通常也远离最优路径。除此之外，模拟退火算法也是一种通用的全局最优化算法，以一定的概率在解空间随机搜索并在一定程度上接受更差解。该方法描述简单、使用灵活、计算开销小、初始条件限制少，但由于其具有随机性，收敛速度相对较慢，且受参数设定影响。之后，遗传算法（GA）[ 8 ][ 9 ]被证明可以用于路径规划，该模型模拟了生物学中达尔文遗传选择和生物进化自然淘汰的过程。最大优点是容易与其他算法相结合，充分发挥自身迭代计算的优势，但计算效率不高，所以在路径规划的实际应用中较少使用。除上述以外，动态窗口方法（DWA）和近图（ND）也是路径规划或避免碰撞的常用方法。
如前所述，虽然这些算法在路径规划方面有自己的优势，但没有一种算法充分考虑到动态特性和路径合理性。因此，引入了Q-learning算法来解决路径规划问题，将路径规划视为是在得失权衡下的一个连续优化问题。Q-learning 是一种异策略结构，即该方法产生动作的策略和要评估改进的策略不同。决策行为动作的策略可以是贪婪策略或 ε minus; greedy 策略[ 10 ]等，这就足够确保状态 -动作值函数的收敛。此外，异策略还具有一个优点，利用其结构的先天优势，可以利用其他智能体的学习经验来学习出最优策略[ 11 ]。Q-learning是一种无模型强化学习的形式[ 12 ]，也可以看作是异步动态规划（D P）的一种方法。它不仅提供了通过体验行动的结果，同时具有学习最佳行动的能力，也不要求他们建立相关域的地图。但是随着状态维数增加，Q-learning 方法效率降低，计算维度上升，收敛速度变慢。
- learning被称为马尔可夫决策过程，当环境完全被可以观察到时，就可被描述为下面的变量：
S是一个有限的可能状态集。
A是一组有限的动作集.
P是状态转移概率矩阵，其中P()是在的条件下，到达状态的可能性。
R为奖励函数。
