目录

摘要

二.文献综述

三.移动机器人路径规划利用强化学习

四.假设

五.方法论

5.1环境模型

5.2奖励函数

5.3价值函数

5.4策略

5.4.1. Q-learning训练算法

5.4.机器人导航算法采用学习策略

六.仿真和结果

6.1模拟的场景

6.1.1训练阶段

6.2.测试阶段

6.2.1.测试场景(1)

6.2.2.测试场景(2)

6.点击/损失利率

6.3.1.训练效果

6.3.2.障碍数量的影响

6.4.比较势场法

6.5.实验结果

七.结论

---

摘要

针对未知动态环境下移动机器人路径规划问题，提出了基于q学习的新方法。q学习算法被广泛应用于解决实际问题，特别是在机器人领域，因为它简单成熟的理论被证明可以提供可靠高效的解决方案。然而，大多数试图使用q学习来解决移动机器人导航问题的研究人员都是在静态环境中进行的；他们避免在动态环境中使用它，因为它是一个更复杂的问题，有无限的多个状态。这么多的状态使得训练智能体非常困难。基于状态空间的新定义，Q学习算法应用于解决动态环境下移动机器人的导航问题。因此，增加导航算法的速度可以降低q表的大小。实验法在动态环境下具有较强的移动机器人导航能力。结果表明，该方法命中率高，机器人在大多数情况下都能成功实现目标，这是所有导航算法中最理想的特征。

一.介绍

近年来，研究和工业兴趣专注于在没有任何人类干预的情况下长期开发智能机器，如机器人。这包括在危险和敌对环境中执行特定任务。移动机器人是一种能够完成这些无聊任务的智能机器。这些机器人用于服务机器人、监控和探索[1]等机器人导航和承担某些任务的领域。

移动机器人导航在未知环境中存在两个主要问题：定位和路径规划[5,6]。定位是确定机器人相对于周围环境的位置和方向的过程。机器人需要识别周围的物体。它需要将每个物体识别为目标或障碍。激光测距仪、声纳测距仪、超声波传感器、红外传感器、视觉传感器、车载或车载GPS解决这个定位问题。使用摄像机网络时，需要更大的环境视图。

另一个问题是路径规划。机器人需要找到一条从起点到终点的无碰撞路径。为了找到路径，机器人需要运行一个合适的路径规划算法来计算任何两点[7]之间的路径。

许多研究人员研究了避障机器人路径规划问题，并提出了许多解决方案[8、9]。由于现实世界的性质，机器人在动态场中的运动具有一定的随机性，在所有条件下都不能给出准确的结果。近年来，在积累经验的基础上，采用人工智能提高机器人自主性的趋势。一般来说，人工智能方法的计算成本低于传统方法。

针对移动机器人在动态环境中运动的路径规划，提出了基于q学习算法的新路径规划方法。q -学习算法具有许多特点，适用于解决动态环境下的移动机器人导航问题。首先，Q-learning agent是强化学习[29]agent，以前不知道自己的工作环境。它通过与环境的互动来了解环境。这类学习智能体被称为无监督学习智能体。

由于假设移动机器人之前对其工作环境没有任何知识，Q-learning agent为解决动态环境下移动机器人的导航问题提供了良好的选择。其次，Q-learning agent是一种在线学习agent。它通过试错学习每种状态下采取的最佳行动。它随机选择动作，并在特定状态下计算动作值。它可以通过评估每个状态和行动对来建立在环境中工作的策略。在移动机器人导航问题中，机器人需要在每个状态下找到最好的行动，以便找到无碰撞路径。它需要在导航环境中在线学习这些知识。因为Q-learning很简单，这是一个非常吸引人的[10]替代方案。

二.文献综述

在过去的十年里，许多经典的解决方案都试图解决机器人的路径规划问题。最常用的解决方案是势场法[22]及其变体[12，14]。该方法已被学者广泛研究。它最常见的形式是由Borenstein和Koren[11]介绍。这种方法的基本思想是在机器人环境中填充一个势场。在这个势场中，机器人被吸引到目标位置，并相互排斥障碍物。在任何位置，机器人计算整体排斥力最小的位置，并将该方法重复到目标位置。这种方法有很多变化，比如Ge和Cui[12、13]提出的方法解决了当目标非常接近障碍物[12]时无法实现的问题，并提出了机器人动态场路径规划的解决方案。势场法是机器人导航的好方法，但局部问题很小。当机器人的引力和斥力之和为零时，机器人停止运动。除非机器人达不到目标，除非机器人的环境发生变化。

由于机器人在动态环境中的导航是一个非常复杂的问题，环境难以建模，经典解决方案在一定条件下有效，但在环境中发生紧急情况或变化时无效。因此，在解决机器人路径规划问题时，有一种向人工智能解决方案发展的趋势。许多人工智能技术被用来解决这个问题，如模糊逻辑、神经网络和遗传算法。1999年，Pratihar等人[9]提出了一种用遗传模糊解决这个问题的新方法。机器人领域的假设是动态的，而目标假设是静态的。在这种方法中，机器人根据移动障碍物最近的位置行动。在某些情况下，这可能会导致行动不当。2001年，Mucientes等人[4]为机器人避开运动物体提出了一种新的模糊控制系统。

在该系统中，机器人使用模糊的时间规则来估计障碍物的运动趋势。2005年孟Joo和Chang Deng[15]提出了一种新的混合学习方法并在仿真环境下开发了一种基于监督学习的神经模糊控制器。前面所有的方法都是针对障碍物移动但目标是静态的环境。

其他一些方法尝试解决机器人在动态环境下的导航问题，但它们都适应于机器人足球环境。极限环法是[16]方法中的一种，它是一种依赖于感计划-行为环的反应性方法。这种方法假设目标的轨迹是预先知道的，所以机器人不是完全不知道环境。这个假设使得它适合于机器人足球。在[17]中提出了另一种使用自适应q学习算法开发自学习智能体的方法，该方法仅适用于机器人足球。这些方法不能应用于任意环境，因为它们在导航算法的实现中使用了足球游戏的规则。

三.文献中利用强化学习进行移动机器人路径规划

该方法利用q学习求解机器人路径规划问题。这种方法最早由Watkins[18]提出，用于从延迟的奖惩中学习。在文献中，有很多尝试使用强化学习算法来解决移动机器人路径规划问题。这些方法学习导航的最优策略，以选择产生最大累积奖励的动作。

Smart和Kaelbling[23,24]将q学习用于移动机器人导航和避障。所使用的奖励函数将1值分配给目标状态，-1值分配给碰撞状态，0值分配给所有其他状态。环境对系统的感知是机器人与目标之间的距离以及机器人与环境中所有其他障碍物之间的距离。实验对机器人进行多次训练，然后将机器人置于一个静态目标和一个静态障碍物的环境中，对所获得的信息进行评估。该方法考虑命中率小，导航到目标的时间长。然而，所进行的实验表明，使用强化学习控制机器人完成不同的任务是有希望的。

Aranibar和Alsina[19]，利用强化学习求解三维环境下的移动机器人路径规划问题。他们使用了q -学习和神经q -学习他们将它与使用贪婪搜索算法的动态规划进行了比较。我们所使用的奖励函数与Smart和Kaelbling[23]所使用的奖励函数相同，但添加了无效状态的定义，即工作环境之外的状态，并将其奖励值设为0。

他们发现动态规划更适合用于小状态空间。q -学习更适合中型空间，而神经q -学习更适合大型空间，但它们只适用于静态的三维环境。

一些算法试图将无监督强化学习与模糊逻辑和神经网络等其他学习技术相结合。Boem和Cho[25]提出了一种利用模糊逻辑和强化学习的混合方法。该方法是一种环境勘探法(EEM)。

导航算法由回避行为和目标寻求行为两个基本模块组成。每个行为在设计状态下独立设计，在运行状态下组合为行为选择。回避行为和目标寻找行为都是模糊引擎，它们将传感器读数提供的环境输入状态映射到模糊输出，即理想的行为。

模糊规则库的建立采用强化学习方法，不需要成千上万的训练数据，而只需简单的评估数据。

Yung和Ye[26]提出了一种基于模糊逻辑和强化学习的移动机器人导航混合学习方法。导航器由三个基本模块组成:避障、移动目标和模糊行为监督器。避障模块采用强化学习的方法学习避障模糊规则。它感知模糊的感官输入，然后使用强化学习来构建规则。在做出决定之后，去模糊化生成输出动作。move-to-goal模块使用了相同的步骤。第三模块感知其他两个模块的输出，输出相应的运动动作。本文将规则学习和实际导航分为两个阶段。在第一阶段，规则学习是使用一个小的示例环境完成的。在实际导航阶段，使用自调优模块对传感器输入的话语进行调优。因此，在一个样本环境中训练机器人后，学习到的规则可以推广到任何其他环境中。与模糊EEM方法相比，该方法具有更高的性能，并且不存在局部最小问题。但是，这两种方法都只适用于静态环境，不能用于动态环境。

由Er和Zhou[27]提出了另一种混合方法。该方法采用了一种用于自动生成模糊推理系统(FISs)的增强动态自生成模糊q学习(EDSGFQL)方法。利用无监督强化学习实现了FISs的结构识别和参数估计。使用Q-learning对生成FISs的输入空间进行聚类。并利用强化学习技术，利用强化信号动态调整和删除模糊规则。采用EDSGFQL对Khepera移动机器人进行控制。通过对移动机器人墙体跟随和避障任务的仿真研究，验证了该方法的有效性。但与以前的方法一样，本文提出的方法仅适用于静态环境。

采用Er和Deng[28]实现了基于广义动态模糊神经网络学习算法构建的模糊推理系统的混合学习避障方法。在对神经模糊控制器进行监督学习后，采用了一种基于模糊行为-批评学习算法的强化方法，使系统能够在不需要人为干预的情况下重新适应新环境。采用强化学习的方法对模糊规则前项参数进行优化。在静态环境下对该方法进行了仿真测试，结果表明该方法能够较好地解决避障问题。

Yang等人[20]使用连续q学习算法求解自主移动机器人的路径规划问题。他们使用多层前馈神经网络来近似q学习值函数。为了使机器人能够在无障碍物碰撞的路径中导航通过环境，它需要多次穿过环境，直到到达目标。该方法适用于静态环境。

Macek et al.[29]提出了另一种使用神经网络和q学习的混合方法。在他们的方法中，使用离散q学习而不是连续q学习。利用Kohonen神经网络将连续状态空间转化为离散状态空间。该学习基于对输入数据的聚类，以便对相似的输入进行分组，并分离不相似的输入。该方法还采用了离散作用空间。该方法比有争议的q学习方法具有更好的收敛速度和更快的性能。但是，此方法仅适用于静态环境。

Park等人[30]提出了一种将概率路线图法(PRM)与Q-Learning方法相结合的移动机器人导航混合方法。PRM是一种流行的路径规划方法，它通过在自由配置空间中绘制随机节点构建路线图，将机器人的起始位置与目标位置连接起来。该方法在静态环境下具有较强的鲁棒性，但在动态环境会降低性能。在动态环境中，当障碍物阻碍预定路径时，使用Qlearning算法来确定在每个状态下采取的最佳行动。该方法采用图像处理的方法，通过比较系统的两幅图像来检测系统的动态性。图像处理也用于生成Cspace映射。

Lin[31]提出了一种分层q -学习算法(HQ-L)，解决移动机器人导航问题。该算法由一组Q-learning agent组成;每个agent学习一个主要问题的子问题。对于每个特定的状态，agent建议一个行动。然后选择一个获胜者并执行它的操作。决策agent学习state- agent对的q值，选择q值最高的agent的动作。Humpheryes[34]将标准的q -学习代理与HQ-L代理进行了家庭机器人应用仿真。研究发现，多智能体HQ-L系统比标准的Q-learning系统占用更少的内存。

移动机器人在多智能体系统中的另一个应用是在机器人足球比赛中[17,32]。但在这些系统中，q学习并不是直接用于避障，而是用于策略选择和角色分配。

从以往的综述中可以看出，研究者倾向于使用强化学习来解决移动机器人导航问题，因为强化学习更适合于具有较大不确定性的未知系统。Qlearning在解决移动机器人导航问题方面显示出良好的效果。该方法适用于未知的、不确定的马尔可夫系统。

本课题主要研究未知环境下的移动机器人路径规划问题。移动机器人通常有不同类型的传感器和驱动器，如:声纳，红外，激光或相机，在任何未知环境中自由导航，从其初始位置开始，通过一个无碰撞路径寻求达到其移动目标。现实世界的未知环境对于移动机器人来说并不总是一成不变的，正如之前不同的研究所指出的[1 - 4,33]。机器人周围的环境由不同的障碍物组成，有的是静态的，有的是动态的，比如另一个机器人在相同的室内环境甚至是人的运动。本文通过对环境状态的新定义，将q学习算法应用到动态环境中。

四.假设

给机器人预先定义了机器人的初始位置和目标，机器人会尝试以自由碰撞路径到达目标，即使在机器人周围的环境中存在障碍物。机器人到达目标时的速度没有预先设定的假设，这意味着它是一个硬着陆机器人。

在本文中，假设机器人配备了所有必要的传感器，为机器人提供了在导航时间的任意时刻对其导航环境的完整信息和视觉所需的所有必要的感知数据。因此，假设环境对学习agent(机器人)是完全可观察的。基于此假设，我们对导航环境有以下修改后的[13]假设:

假设1。机器人在每个时刻的位置p和速度v都是已知的。

假设2。在每个时刻，已知目标的位置ptar和速度vtar。

假设3。障碍物pobsi的位置和速度vobsi, i¼1,2,y,n，其中n为每一时刻已知的障碍物总数。

假设4。在每个时刻瞬间，机器人的速度大于或等于目标9v9Z9vtar9的速度。

假设5。在每个时刻瞬间，机器人的速度大于等于每个障碍物的速度9v9Z9vobsi9, i¼1,2,y, n，其中n为障碍物总数。

假设6。在每一个瞬间，机器人都知道目标和障碍物的形状。

五.方法论

为了应用q -学习算法，需要解决四个主要部分:工作环境、奖励函数、价值函数和适应策略。在下面的小节中，将详细解释每一部分。

5.1环境模型

机器人的环境由目标和障碍物组成。目标和障碍可以是静态的，也可以是动态的。机器人的任务是通过q -学习算法找到一条无碰撞的路径在这个环境中导航。在这种环境下应用Q-learning算法的第一步是定义状态和动作空间。

对于在静态环境中导航的机器人，其状态集可以完全由机器人的位置或坐标来定义。

在动态环境中则不是这样，在动态环境中，机器人的坐标并不能反映其环境的状态，因为环境变化很快。

因此，除了机器人的位置或障碍物之外，环境状态的另一个信息应该被使用。

当一个人试图在一个动态的环境中安全地行走以达到一个特定的目标时，他/她不会关心他/她的特定位置，也不会关心他/她到目标或障碍物的特定距离。

他/她会关心他与目标之间，以及他与最近的障碍物之间的相对或近似的距离和方向;因为他/她会尝试一次解决一个障碍。

新方法的目标是使学习主体模仿人类的推理。因此，在每一个时刻，机器人都被认为是宇宙的中心，并将其周围的环境划分为四个正交区域:R1、R2、R3和R4，如图1所示。每一时刻的环境状态由包含目标的区域和包含离机器人最近的障碍物的区域决定。例如，在tn时刻，目标在R2中，最近的障碍物在R4中，则此时的状态为sn=(R2,R4)，但这种状态的定义对于避障过程是不够的。障碍物和目标可能在同一个区域，这可能会给机器人造成混淆。增加机器人与门线和障碍物线之间的夹角来解决这种混淆。图1显示了角为theta的四个区域R1、R2、R3和R4。

为了计算theta，我们考虑机器人在任意时刻的位置为:P=[Px Py]T，目标位置为:Ptar=[Ptar-x Ptar-y]T，最近的障碍物位置为:Pobs=[Pobs-x pobs-y] T。机器人和目标之间的距离dr-t如下式所示:

机器人与障碍物之间的距离dr-O为下式:

 机器人到目标线的方程为

 

式(3)是基于求出机器人到目标线的斜率(m)，根据点与直线的正交距离方程计算出障碍物与机器人到目标线的距离为:

角theta可以用等式来计算。(2)、(4):theta=sin-1(D/dr-o)

theta的取值范围是区间[0,2Π]。添加这个角度可以解决目标和障碍物在同一区域时的问题，但可能会产生无限多个状态。

此外，学习智能体不需要知道这个角度的确切值。它只需要知道这个角的范围。为了减少状态数，将区间划分为八个角度区域:

其中G为当前角度区域，G1到G8为该区域的可能值。这八个区域如图2所示。

利用这些定义，将任意时刻实例的状态完全定义为目标区域、最近障碍物区域和角度范围的组合

其中st为t时刻环境的状态，Rg为目标或目标的区域，Ro为最近的障碍物区域，Gn为障碍物到目标线与机器人到障碍物线的角度区域。

定义状态空间之后，应该指定每个状态中允许的操作。假设机器人为非完整约束，定义机器人运动的三个动作:前进、右转和左转。这三个动作取决于机器人的方向。机器人的姿态角是由目标位置决定的。机器人在每一个时刻都改变自己的方向，使其能够沿着最短路径的直线向前移动到目标。左转和右转动作是用来避障的。转向向左或向右的程度可以根据情况和所需的躲避程度而变化。

5.2奖励函数

奖励函数是在给定状态下所采取行动的即时评估器。它是一个指示器，显示在特定情况下执行的动作有多好或有多坏。用于计算决定机器人在不同状态下行为的值函数。为了定义奖励函数，对状态集进行分类如下:

*机器人与环境中任何障碍物发生碰撞的可能性很小或没有碰撞的状态集被认为是安全状态(SS)。

*机器人很有可能与环境中的任何障碍物发生碰撞的状态集被认为是非安全状态(NS)。

*定义了两种终止状态:

a.机器人达到目标时的状态被认为是获胜状态(WS)。

b.机器人与障碍物碰撞时的状态被认为是丢失状态或失败状态FS (Failure state)。

为使机器人在环境中安全导航，奖励函数定义如下:

*从非安全状态转移到安全状态的奖励是r=1。

*从安全状态转移到非安全状态的奖励是r=-1。

*从非安全状态移动到非安全状态但更接近障碍的奖励是r=-1

*从非安全状态移动到非安全状态并摆脱障碍的奖励是r=0。

*移动到胜利州的奖励是r=2。

*进入失败状态的奖励是r=-2。

这个奖励功能让机器人倾向于待在安全区域，直到它到达胜利状态，并让它远离障碍。

机器人与障碍物之间的距离dr-O和机器人和目标dr之间的那个?确定机器人的过渡状态。非安全区域在障碍物dmin周围的半径可以根据环境和障碍物的性质来确定。此外，还需要计算障碍物周围碰撞区域的半径dcol，它决定了障碍物的影响范围。这些距离如图3所示。

dmin、dcol、dr-O和反映目标影响区域的目标周围获胜区域的半径dwin一起决定了机器人当前的过渡状态:

 其中S为机器人当前进入的新的过渡状态。根据这个转场状态的定义，可以将奖励函数重写为:

5.3价值函数

在Q-learning算法中，值函数存储在一个包含q值的表中。表格中的行是机器人在学习过程中所经过的不同状态。表中的列是机器人执行的动作。该表最初被设置为所有0。然后在训练机器人时，通过更新状态-动作对的q值来填充表项。该值是在一种状态下所采取的行动的即时奖励，以及在新的结果状态下所采取的所有行动的最大先前奖励[10,21]:

其中st为时刻t的状态，at为机器人在该时刻所做的动作。R (st, at)是前一节所述的即时奖励。Max(Q, st +1)是在前一时刻对新状态采取所有可能行动时计算出的最大Q值。G是折现系数。在训练机器人时，通过将机器人暴露在动态环境的不同场景中来计算价值函数。当机器人被设定在真实环境中工作时，机器人利用表中存储的信息到达目标[23,24]。

5.4策略

在不同环境和不同条件下训练机器人后，机器人会有一个可供未来导航使用的策略。如果机器人在安全区域航行，就不需要遵循这个策略。当处于安全状态时，要遵循的简单政策是改变它的方向，然后朝着目标前进。当进入非安全区域时，将使用存储在q表中的策略。在这种情况下，机器人将采取当前状态下q值最高的动作。

5.4.1. Q-learning训练算法

训练移动机器人是通过让它接触不同的动态环境场景来完成的，每一个场景都被称为一个插曲。每一集假设不同的目标运动。此外，每一集都使用了不同数量的障碍。假设有些障碍物是静止的，有些是移动的。静态障碍物的位置是在每一集中随机选择的。假设动态障碍物的运动在所有事件中都是随机的。用于训练机器人的剧集数量越多，机器人在动态环境中的导航性能越好。

用于移动机器人训练的Q-learning算法如图4所示。从流程图中可以看出，训练算法会重复多次，直到完成所有的片段。这一集从计算环境的当前状态开始。目标位置和障碍物位置通过传感器提供给机器人。这些数据结合机器人当前的位置用来查找环境的当前状态。

之后，检查当前状态，如果是安全状态，机器人改变朝向目标位置，向前移动一步，以最短路径到达目标位置。如果这一步实现了目标，这一集就完成了，新的一集就开始了。如果还没有到达目标，机器人就会计算新的当前状态，并重复这个过程。

如果当前状态为非安全状态，机器人会比较任意一个动作的预期结果:右转和左转，并选择一个离目标更近的位置。然后，机器人检查操作产生的瞬态状态，并相应地更新q表。如果该动作达到了胜利状态，即机器人通过该动作到达了目标，则该动作的奖励将如前所述为2。如果行动导致安全状态，奖励将是1。如果行动导致非安全状态，奖励是0，如果它导致与障碍物的碰撞奖励为-1。然后计算q值如式(10)所示，并更新q表。

之后，机器人继续计算新的电流状态和暂态状态。如果最后一个动作导致一个章节的结束，就像在获胜状态或终止状态的情况下，该章节将被终止并开始一个新的章节。如果是最后一集，整个学习过程就终止了。

每一集都有特定的时间段。机器人需要在这个时间段内到达目标。如果机器人的时间不够了，没有到达目标，就会终止这一集，开始新的一集。

应用前一种算法得到的结果是一个存储在Q-table中的策略。该策略用于机器人在任何动态环境下的未来导航。

5.4.2机器人导航算法采用学习策略

在不同的动态环境下训练机器人后，得到的策略可以被机器人用于未来的任何导航。图4的流程图显示了机器人在遵循学习到的策略时的行为。

从图表中可以看出，机器人通过寻找自己的当前状态和当前的瞬态状态开始在环境中导航。如果当前的瞬态状态是安全状态，机器人改变其朝向目标并向前移动一步。它继续这样做，直到当前暂态为Non-Safe。在这种情况下，机器人检查q表中当前状态的行，并根据存储的q值构建右转或左转的决策。如果“向右转”动作的q值较高，机器人就会以特定的角度向右转，然后向前移动一步。另一方面，如果左转动作有更高的q值，机器人左转并向前移动一步。如果两个动作的q值相同，机器人将向任意一个方向转动。

之后，机器人找到新的暂态。如果是终止状态，则检测到冲突并终止导航进程。如果它是一个获胜国，那么目标已经达到，导航过程结束。如果是安全状态或非安全状态，导航将继续。

六.仿真和结果

为了训练机器人，进行了广泛的仿真研究，并证明了新方法的有效性。利用MATLAB软件实现了仿真。针对不同的情况实施不同的场景，并使用这些场景的结果来评估提出的q学习解决方案的性能。

6.1模拟的场景

仿真分为两个阶段:训练阶段和测试阶段。在训练阶段，针对不同的环境实施不同的场景，实现不同的目标和障碍行为。学习发生在机器人导航通过每个场景的不同状态。如前所述，从不同场景中获得的信息会积累并存储在q表中。在学习阶段之后，测试阶段开始将机器人暴露在更复杂的环境中。测试场景有更多的障碍，一些是静态的，一些是动态的。设计了一些测试场景，用于测试算法的特殊常见问题，如局部最小值问题。其他一些测试场景是随机的。在这些随机场景中，静态障碍物的位置是随机选取的，动态障碍物的运动也是随机选取的。这些测试场景用于评估在模拟的第一阶段学习到的信息的价值。随机测试场景被广泛用于评估Q-learning算法在动态环境下移动机器人导航的有效性。

在开始展示所进行的模拟场景及其结果之前，需要确定一些参数，以用于不同的场景。第一个是左转和右转动作中的转弯角度。在我们所有的场景中，这个角度被设置为45度。

其他参数是机器人的速度，目标和障碍物。目标和障碍物的速度根据每个场景而变化，它们在场景中各自的位置。机器人的速度是恒定的，在整个测试场景中设置为1米/秒。机器人在每个时刻瞬间的位置由下式[18]决定:

其中PXN为瞬间(n)时刻机器人在x方向上的位置，pyn为瞬间(n)时刻机器人在y方向上的位置，px(n?1)和py(n?1)分别为瞬间(n?1)时刻机器人位置的x和y分量。机器人的速度v是常数，y是转角或方向角，DT是每次迭代的持续时间。

6.1.1训练阶段

进行了几个培训场景。在每个场景中假设不同的目标和障碍行为。每个训练场景由机器人、目标和一个障碍物组成。下面是对每个场景的描述。

6.1.1.1训练场景(1)

在第一个场景中，目标从70点开始做垂直运动50??T和速度vtar¼0 ?0:5?? T。障碍物在20点开始运动5??T和速度vobs¼0:5 0:5?? T。在这种情况下，机器人在10点开始运动10??T，通过应用q学习算法，机器人成功到达70点的目标12?T时刻76，如图5a所示，机器人以星号表示，目标为十字号，障碍物为方号。

在导航过程开始时，机器人利用其前进动作，沿着指向目标位置的平滑路径向目标移动，直到时间瞬间24。

此时机器人进入非安全区域，障碍物在区域R4，目标在区域R1。正如算法显示的那样，机器人可以选择向左或向右移动451。它可以随机选择任何一个动作，因为这是它第一次遇到这样的状态，所以它可以选择让自己更接近目标的动作。机器人选择向左移动，因为这个动作会导致一个点更接近目标。这个动作也有助于避开障碍物，所以机器人得到的强制力很高，这个动作在这个状态下的q值也增加了。下次机器人通过这个状态时，它还是会选择向左移动。

6.1.1.2训练的场景 (2).

在第二个训练场景中目标做垂直运动从70点开始运动50?T是第一种情况。目标vtar的速度[0 0.5] T。障碍从[30 25]T及其速度为[-0.5 -0.5]T。在这种情况下，机器人在[10 10]T开始运动,通过应用Q-learning算法机器人未能达到如图5b所示的目标。

在导航过程的开始，机器人沿着一条平滑的路径向目标移动，直到时间13。此时机器人进入非安全区域，障碍物在R1区域，目标也在R1区域。根据算法，机器人可以选择向左或向右移动45°，以避开障碍物，并试图回到安全区域。因为这是它第一次遇到这样的状态，所以它可以随机选择行动，也可以像我们这样选择让自己更接近目标的行动。机器人选择向左移动，因为这个动作可以让机器人靠近目标点。

这个动作在时间15产生了与障碍物的直接碰撞。因此，机器人在该状态下执行该动作得到负强化，状态-动作对的q值减小。下一次机器人通过这个状态时，它会选择向右移动。由于机器人遇到碰撞，导航过程停止，训练场景终止。

6.1.1.3.(3)训练场景。

在第三种情况下，目标沿着水平线从[50 35]T。靶体的速度为vtar=[0.5 0]T。障碍物速度为1 / 4 [0.5 0.5]T，在[20 5]T开始运动。机器人在[10 10]T，通过应用q学习算法，机器人成功到达目标点[94 35]T在时刻88，如图5c所示。

在这个场景的开始，机器人沿着一条平滑的路径向目标移动，直到时间瞬间23。在那一刻，机器人进入了一个非安全区域，也就是障碍物所在的区域R4和区域R1的目标。正如算法显示的那样，机器人可以选择向左或向右移动45°。机器人执行了一个让它更接近目标的动作，所以它向左转。机器人的这个动作得到了积极的奖励。因为它不是第一次遇到这样的国家。这与场景1中遇到的状态相同，动作-状态对的q值再次增加。机器人成功地避开了障碍物。如果在测试阶段遇到这个状态，机器人将使用这个q值。

6.1.1.4.(4)训练场景。

在第四种情况下，目标从[50 25]T开始沿着水平线以速度vtar=[0.5 0]T移动。在这个场景中障碍物的速度是vobs=[-0.5 -0.5]T，它从[120 45]T移动。在这种情况下，机器人从[120 40]T开始运动。，这是一个接近障碍物的位置。使用q -学习算法，机器人在第64时刻成功到达目标点[83.5 25]T，如图5d所示。

在这种情况下，机器人从一个不安全的区域出发。从图中可以看出，机器人来回弹跳，试图到达目标，同时试图避开障碍物。在一个步骤中，机器人离开非安全区域到安全区域。然后在接下来的步骤中，它再次进入非安全区域，并试图以最短路径向目标移动。机器人的弹跳状态一直持续到[100 25]T在那里它可以完全避开障碍，然后它开始沿着一条平滑的线向它的目标移动。

对机器人的训练可以根据需要进行不同的目标和障碍行为。我们对机器人训练得越多，我们期望在未来得到更好的结果。

 图6所示。在第一个测试场景中，机器人的路径:(a)直到时间瞬间n=15和(b)时间瞬间n=77。

6.2.测试阶段

在训练阶段之后，测试阶段从更复杂的情况和场景开始。模拟了不同类型的目标运动，并在每个场景中增加了更多的障碍物，有些是静态的，有些是动态的。选择静态障碍物的位置，使其中一部分能够干扰机器人的运动。对于动态障碍物，通过选择障碍物的起始点和跟随路径来干扰机器人的运动。在最后的测试场景中，随机选择静态障碍物的位置，并使用随机行走模型随机确定动态障碍物跟随的路径。下面是我们为评估移动机器人导航新方法而进行的一些测试场景的描述。

然而，需要注意的是，测试场景本身也可以被认为是训练场景，因为机器人每次导航到一个新的环境时都会不断更新它的q表。因此，学习到的信息一直在发展。

6.2.1.测试场景(1)

第一个测试场景与第二个训练场景相同。在第二个训练场景中，机器人没有达到目标。目的是检查训练后机器人是否能成功到达目标。让事情变得有点困难;我们在60点添加了一个新的静态障碍物[60 22]T。这个测试场景的结果可以在图6a和b中看到。

从图6b可以看出，机器人这次成功地到达了目标。这证明了机器人从之前的环境经验中学习。在训练场景中，机器人没有重复导致碰撞的动作。

当机器人到达第一个障碍物周围的非安全区域时，它这次向右转弯，而不是像第一次那样向左转弯。因为它确实知道在这种状态下左转会导致碰撞，因此左转动作被赋予了一个较低的q值。当机器人面对同样的状态时，它选择了右转动作，因为这一次它的q值更高。

图6a显示机器人在瞬间n=15成功避开了动态障碍物。它也能够避开静态障碍。从图6b中可以清楚地看到，静态障碍物的存在迫使机器人通过更长的路径来避免与该障碍物的碰撞，但在仿真时间结束前，机器人成功地在瞬间n=77到达了目标。

当机器人到达静态障碍物时，如果向右转弯，而不是向左转弯，那么到达目标的路径应该更短。

但当时的目标是[75 30]T，所以机器人选择向左转，试图到达目标。机器人不知道目标的运动信息，也不做任何假设。每次机器人只看目标的当前位置。它不会查看之前的位置来估计下一个新位置将是什么。

图6所示。在第一个测试场景中，机器人的路径:(a)直到时间瞬间n=15和(b)时间瞬间n=77。

6.2.2.测试场景(2)

第二个测试场景是随机的。它包含六个障碍，两个静态障碍和四个动态障碍。障碍物1和2是位于点[13 17]T和[14 47]T的静态障碍物。障碍3、4、5和6是动态障碍。它们的随机路径由随机游走模型决定。动态障碍物的起始点和静态障碍物的位置也是随机选择的。

障碍物3在[72.1 33.3]T，障碍4的起点是[65.9 34.7]。T，第5障碍在第[80.2  28.5]T点开始行走和障碍物6在[96.2 43.4]T。在这种情况下，目标运动是一个正弦运动。从[75 25]T开始运动。机器人在[10,10]T点以恒定的速度v=1m/s开始导航。

该环境下机器人的完整轨迹如图7a所示。从图中可以看出，机器人成功到达了其正弦目标，导航过程持续时间为83个时间实例。如图7b所示，机器人在开始运动时就成功避开了障碍物1，并在轨迹末端成功避开了障碍物5。其他障碍物没有干扰目标的运动。

图7d展示了另一个测试场景，目标和机器人的起点相同，目标的速度和运动相同。这次的不同之处在于，机器人没有遇到任何障碍物。在这个场景中，当机器人不受任何干扰地直接移动到目标时，需要82个时间实例才能到达目标。如果将该场景的时间与前一个场景的时间进行比较，可以清楚地看到机器人的延迟只有一个时间瞬间。尽管机器人必须避开两个障碍，但延迟非常小。前面的讨论显示了新解决方案的效率。

即使机器人在没有任何干扰的情况下直接移动到目标位置，它所走的路径也不是最短的。但正如我们假设的，机器人不知道目标的运动。它只能找到目标在每个时刻的位置和速度。这就是机器人不能走更短路径的原因。

图7所示。(a)第三测试场景机器人的路径，(b)第三测试场景显示机器人在时间瞬间3后避开第一障碍物的路径，(c)第三测试场景显示机器人避开障碍物5的路径，(d)机器人没有避开任何障碍物的路径。

6.3点击/损失利率

命中率是机器人成功到达目标的所有试验的比例。因此，失误率是机器人未能达到目标的所有试验的比例。使用提出的q学习方法从机器人到障碍物的路径不是唯一的，并依赖于训练的数量;由于这种训练为机器人建立了应对不同情况的经验，所以期望机器人接受的训练越多，其性能越好，从而提高命中率。本节将介绍培训对命中率的影响。

用于研究命中率的测试场景是随机测试场景。在这些测试场景中，目标的运动是正弦的。我们选择目标的这种运动，是因为我们认为它是一个复杂的运动，目标的运动方向随着时间不断改变。在这些测试场景中，机器人的速度为2m /s，左转和右转角度为451。随机选择静态障碍物的位置和动态障碍物的起始点，利用随机行走模型确定动态障碍物的运动。

6.3.1.训练效果

首先，我们会研究训练量对命中率和失误率的影响。为了研究这种影响，机器人被训练使用不同数量的随机场景。然后用500个随机场景对机器人进行了测试。计算每次训练的命中次数，计算失误率。研究结果如表1所示。

从表中可以看出，随着训练量的增加，失误率下降。一开始，我们只从五个训练场景开始，其中失误率为18.2%。之后我们开始增加训练量，直到达到75训练场景。遗漏率是2%，这是一个非常小的遗漏率。

从表中还可以看出，对超过75个场景的机器人进行过度训练会增加失误率。这是由于过度训练导致的过度拟合导致系统专注于某些情况。训练量和命中率之间的关系如图8和图9所示。

6.3.2.障碍数量的影响

研究的另一个参数是障碍物的数量。我们研究了增加障碍物数量对命中率的影响。这一次，机器人被训练了50次，然后使用500个随机测试场景进行测试。我们从3个障碍开始，2个是动态的，1个是静态的。然后我们开始增加障碍的数量，每次增加一个动态障碍和一个静态障碍。在每次试验中，我们统计命中次数并计算失误率。本研究结果见表2。

从表中我们可以看出，增加障碍的数量会增加失误率。当障碍数为3时，失误率为2%这是一个非常低的失误率。随着障碍物数量的增加，失误率开始增加，当障碍物数量为13时，失误率达到24.4%，这不是一个理想的失误率。这是一个正常的结果，因为障碍物数量的增加会给机器人带来更困难的场景，并增加碰撞的概率。因此，如果预期在工作环境中会有大量的障碍，就应该增加培训的数量，以降低失误率。

障碍物数量与命中/失误率之间的关系如图10和11所示。从图中可以看出，只要障碍物的数量小于10，命中率就会近似不变，如果在机器人环境中添加更多的障碍物，命中率就会开始下降。当障碍数小于10时，缺失率是一个非常低的失误率，然后开始增加，直到达到24.4%。

6.4.与势场法的比较

将采用q -学习的机器人导航方法与势场方法进行了性能比较。在Ge和Cui[13]的工作中，作者介绍了势场法在动态环境中的应用。在这种方法中，假设机器人在两个势场力的作用下移动。目标产生的吸引势场产生一个吸引力(Fatt)，将机器人一直吸引到目标的位置。另一个场是障碍物产生的斥力场。这个磁场产生一个斥力(Frep)，使机器人远离障碍物。机器人在两个力之和(Ftotal)[13]的虚力下运动。

 排斥力计算为环境中所有障碍物产生的所有排斥力之和，如下[13]:

式中n为环境中障碍物总数，Frepi为第i个障碍物产生的排斥力。关于动态环境势场法的详细信息和方程的推导可以在[13]中找到。

在上述研究中，对势场法在动态环境下进行了仿真测试。针对包含一个移动目标和六个障碍物的特定环境，设计了一个测试场景。有些障碍是静态的，有些是动态的。为了将新提出的人工智能方法与机器人领域中最常用的机器人导航方法之一的势场方法进行比较，使用q学习算法重复相同的测试场景。

该场景假设机器人在一个动态环境中运动，目标以恒定的速度运动，vtar¼[0.1 -0.05]T从10点开始运动。[10 10]T。

在这个环境中有6个障碍物:障碍物1、2、3是动态障碍物，障碍物4、5、6是静止障碍物。障碍物1从[5 0]T开始运动,和恒定速度[0.0 0.28]障碍物2以[-0.29 0]T的速度从[9.4 4.5]T开始移动。障碍物3从[19 10]T开始以速度[-0.05 -0.065]T移动。在点[8 10.5]T，障碍物5位于点[18 4.5]T，障碍物6位于点20 7?? T。机器人从11点开始运动?? T。

图12所示。(a)采用q学习算法，机器人速度为¼0.2 m/s的机器人、目标和障碍物的路径;(b)采用q学习算法，机器人速度为¼0.35 m/s的机器人、目标和障碍物的路径。

图12显示了使用Q-learning方法应用相同场景的结果。应用相同场景的唯一问题是机器人的速度。使用势场法的机器人的速度随净势场的强度而变化。另一方面，使用Q-learning方法的机器人使用常数vrob按照Eq.(9)运动。

然而，为了进行有效的比较，我们用通过的总距离除以时间来计算机器人在势场场景中的平均速度，并以比这个平均速度更慢的速度移动机器人。在势场场景中，机器人的平均速度为vx¼0.236米/秒和vy¼0.472米/秒。在我们的场景中，我们选择vrob¼0.2 m/s。

从图12可以看出，机器人成功完成了在[20.9 4.55]T点捕获目标的任务。机器人用了109秒到达目标。这大约是使用势场法机器人到达目标所需时间的一半。

在这个场景中，机器人不需要避开任何障碍物，因为它的速度非常慢，所以障碍物1和2在机器人到达交点之前相交并通过了它们的道路。另外，障碍物3在机器人接近障碍物之前已经通过，所以没有发生回避。这证明了在我们的场景中，机器人的移动速度要慢得多，但它能够在势场法所需时间的一半的情况下完成任务。

进一步将机器人速度提高到vrob¼0.35 m/s，使其面对障碍物1和2并进行躲避步骤。

图12b展示了在相同场景下应用该机器人速度的结果。可以看出机器人的速度与势场法中机器人的速度非常接近。这个场景中的机器人避开了障碍1。障碍物2更快，没有发生回避。机器人到达目标的时间为46 s，大大缩短了势场法所需的时间。这证明了新方法的有效性。

从前面的讨论可以看出，新方法是一种非常有效的方法，可以在更短的时间内完成导航过程。当机器人、目标和障碍物在同一条线上，障碍物在目标和机器人之间时，势场法会出现局部最小问题，如图13[13]所示。

从图中可以看出，当障碍物靠近机器人时，斥力大于或等于引力，所以总力会使机器人远离目标，如果总力为零，机器人就会停止运动。使用的潜场法，机器人会等待障碍物改变位置，离开路径到达目标。另一方面，新的q学习方法没有遭受这样的问题，因为它不处理力。图14为机器人、障碍物和目标在同一直线上时的机器人路径;障碍物在机器人和目标之间。

在这张图中，目标在[90 25]T障碍物以速度[0.5 0]从50点开始运动。?T和速度[0.5 0]T，即与目标相同的速度。机器人从25点开始运动。T和机器人vrob的速度¼2米/秒。

可以看到，机器人能够避开障碍物到达目标。从图中我们可以看到，直到第15秒，机器人一直在直线移动。此时机器人进入移动障碍物的非安全区域，机器人向左转。由于在障碍物仍在前进的情况下执行这个动作，机器人进入了Safe区域。机器人改变了指向目标的方向。这个动作将机器人返回到非安全区域。机器人再次向左转弯，沿着这个方向直线移动，直到第21秒。此时，机器人在点[61 30.6]T，障碍物在点61 25?? T。机器人与障碍物之间的距离为5.6米，如我们之前所述，非安全区域的边界为5米。因此，这个动作使机器人回到了安全区域，因此机器人改变了朝向目标的方向。在此之后，机器人没有再次进入非安全区域，并开始朝着目标前进，直到在46秒时抓住目标。

由前面的讨论可以得出结论，机器人可以处理困难的情况，并在短时间内到达目标。它比势场法更有效。在本节中，机器人在应用比较测试之前进行了75次训练。

6.5.实验结果

在实验评价中，我们将多机器人足球系统视为一个动态环境，如图15(a)所示。该系统主要由主机、视觉系统、射频通信模块、轮式移动机器人等部分组成。

该机器人是一种差动驱动轮式移动机器人，内置微处理器，两个带编码器的直流电机和一个射频通信模块。给出了差动驱动移动机器人在无滑动、纯滚动和无滑动约束下的运动学表达式。

其中P为姿态向量，如图16所示，v为机器人平移速度，o为机器人相对于机器人中心定义的旋转速度。根据两轮转动速度确定机器人整体平移和旋转速度如下:

 

式中or、ol分别为机器人左右车轮角速度，r为车轮公称半径，L为两车轮中心距离，如图16所示。

通过确定左右轮平移速度(vr和vl)来控制机器人更新姿态。该方法根据所选择的状态以最小的误差驱动机器人到所期望的方向(yd):

用于更新机器人姿态的控制命令是基于方程中的比例控制。(18)和式(19)，其中K为比例增益常数:

在对所提出方法的实验评估过程中，机器人(1)在跟踪运动目标机器人(4)的同时要避开障碍物(2)和(3)，如图15b所示。

障碍物(2)为移动障碍物，障碍物(3)为静止障碍物。白色箭头表示机器人、目标和移动障碍物的运动方向。实验示意图如图17a-e所示。

如图17a和b所示，机器人(机器人1)从初始位置开始向运动目标(机器人4)在确定的安全状态下移动。

如图17c所示，机器人在遇到移动障碍物(机器人2)时进入非安全状态，此时机器人成功更新位置并避开障碍物，如图17c所示。机器人再次进入安全状态后，再次向目标移动并与目标相遇，如图17d和e所示。所进行的实验验证了动态环境下移动机器人路径规划新方法的有效性。

七.结论

本文提出了一种基于q学习算法的移动机器人动态导航新方法。由于环境对机器人来说是完全未知的，q学习算法可以在不需要环境模型的情况下解决运动规划问题。之前对环境或关于目标或障碍物的运动没有以前的约束。为了将该算法应用于动态环境中，对状态空间进行了新的定义。这个新的定义试图模仿人类处理这种未知环境的推理。

通过不同的模拟测试场景，测试机器人对不同类型动态环境的处理能力。在测试场景中实现了不同类型的目标运动和不同数量的障碍物以及不同的动态模式。测试场景展示了机器人应对不同环境情况的能力，并始终达到目标。计算出的缺失率为2%，随着障碍物数量的增加，缺失率开始增加，当障碍物数量为13时，缺失率达到24.4%。比较了基于q学习的机器人导航方法与势场方法在动态环境中的性能;采用该方法，机器人完成导航过程的时间大大缩短，约为机器人完成导航所需时间的一半使用势场法到达目标。实验结果和仿真结果表明，该方法具有较强的适应性，可用于机器人在未知动态环境下的导航。