阮晓钢^1,2, 刘鹏飞^1,2, 朱晓庆^1,2
1. 北京工业大学 信息学部, 北京 100124;
2. 计算智能与智能系统北京市重点实验室, 北京 100124
收稿日期：2020-04-27
基金项目：国家自然科学基金资助项目（61773027）；北京市自然科学基金资助项目（4202005）；北京市教育委员会科技计划一般项目（KM201810005028）
作者简介：阮晓钢(1958-), 男, 教授
通讯作者：朱晓庆, 讲师, E-mail: alex.zhuxq@bjut.edu.cn

摘要：Q-learning作为一种无模型的值迭代强化学习算法，被广泛应用于移动机器人在非结构环境下的导航任务中。针对Q-learning在移动机器人导航中环境探索和利用存在矛盾关系导致收敛速度慢的问题，该文在Q-learning算法的基础上，受啮齿类动物可以利用嗅觉线索来进行空间定向和导航的启发，提出一种基于气味奖励引导的Q-learning环境认知策略。该算法通过改善Q-learning中的动作选择策略来减少对环境的无用探索，在动作选择策略中融入了环境气味奖励的引导，并提出了嗅觉因子来平衡动作选择策略中Q-learning和气味奖励引导的权重关系。为了验证算法的有效性，在Tolman老鼠实验所用的迷宫环境中进行了仿真实验，动态仿真结果表明，相比Q-learning算法，基于气味奖励引导的Q-learning算法在环境认知过程中，可减少对环境的无用探索，并增强对环境的认知学习能力，且提高算法的收敛速度。
关键词：机器人导航环境认知Q-learning嗅觉因子
Q-learning environment recognition method based on odor-reward shaping
RUAN Xiaogang^1,2, LIU Pengfei^1,2, ZHU Xiaoqing^1,2
1. Faculty of Information Technology, Beijing University of Technology, Beijing 100124, China;
2. Beijing Key Laboratory of Computational Intelligence and Intelligent System, Beijing 100124, China

Abstract: Q-learning is a model-free iterative reinforcement learning algorithm that is widely used for navigating mobile robots in unstructured environments. However, the exploration and utilization of the environmental data limits the Q-learning convergence speed for mobile robot navigation. This study used the Q-learning algorithm and the fact that rodents use olfactory cues for spatial orientation and navigation to develop a Q-learning environmental cognitive strategy based on odor-reward shaping. This algorithm reduces useless exploration of the environment by improving the Q-learning action selection strategy. Environmental odor information is integrated into the algorithm with the olfactory factor used to weight the Q-learning and the odor-reward shaping in the action selection strategy. The algorithm effectiveness is evaluated in a simulation of movement in the labyrinth environment used in the Tolman mouse experiment. The results show that the Q-learning algorithm with odor-reward shaping reduces useless exploration of the environment, enhances cognitive learning of the environment, and improves the algorithm convergence speed.
Key words: robot navigationenvironment recognitionQ-learningolfactory factor
移动机器人未知环境探索是实现移动机器人智能性和自主性的关键技术之一^[1]。它要求机器人更加智能地面对和适应未知的、复杂的、动态变化的环境，因此需要对环境的时间信息、地理信息、生物信息等内容进行探索。在复杂的变化的未知环境下，移动机器人必须具有较强的自学习和自组织能力，才能在变化的环境中实时地学习和认知环境。
强化学习最初用于博弈论、信息论、控制论和运筹学等学科。随着技术的发展，它已被用于自主移动机器人的导航。强化学习可用于根据一系列奖励和惩罚在未知环境中导航。被称为智能体的机器人将获得无碰撞动作的奖励，并在与障碍物碰撞时受到惩罚^[2]。
Q-learning是一种无模型的值迭代强化学习方法，涉及奖励和惩罚的原理，以及机器人与环境的相互作用^[3]。智能体(即移动机器人)在环境中执行操作，并立即收到所采取动作的奖励或惩罚。根据接收到的奖励或惩罚不断更新Q值，并且将Q值最高的状态视为移动机器人的最佳动作路径。在自主移动机器人中使用Q-learning的主要优点是，自主移动机器人可以通过自我学习来应对非结构化环境，并在无碰撞的路径中导航至目标位置^[4]。
虽然Q-learning在移动机器人导航方面已经表现出不错的效果，但是也存在对环境的探索和利用两者关系的矛盾，从而使收敛速度下降。针对这个问题可以从两方面来改善，一是初始Q值，二是增加环境的启发式信息。Khriji等^[5]将先验知识用于Q-learning中，并将导航行为划分为便于设计和实现的小动作来降低导航问题的复杂性，从而加快算法的收敛速度。Song等^[6]通过使用动态波扩展神经网络指定初始Q值来加快Q-learning的学习速度。Low等^[7]引入了花授粉算法(FPA)用于改善Q-learning的初始化，实验表明当使用FPA适当初始化Q值时，可以加快Q-learning学习的收敛性。在启发式引导方面，Pang等^[8]提出了一种基于A^*和Q-learning的仿生自学习算法，启发式搜索A^*算法用于全局路径规划，当本地环境发生变化时，将使用Q-learning进行本地路径规划。Li等^[9]提出了一种基于改进的Q-learning算法和启发式搜索的移动机器人导航策略。Ni等^[10]提出了一种基于生物启发神经网络(BNN)的改进的Q-learning算法，该方法将一种新颖的BNN模型作为Q-learning学习算法的奖励函数，可以减少奖励函数对收敛速度的影响。
啮齿动物的实验表明，视觉提示在控制海马位置细胞和空间导航中起着重要作用^[11]。然而，老鼠也可能依赖听觉、嗅觉和体感刺激进行定向^[12]。众所周知，老鼠可以追踪气味或自身产生的气味痕迹，来寻找食物来源^[13]。因此，对于自然环境中的导航，考虑其他感官输入似乎是合理的，啮齿动物可以基于嗅觉线索形成空间表示并将该信息用于空间定向和导航^[14]。为了适应这些发现，本文将生物的嗅觉信息与强化学习相结合提出了一种导航机制，该机制通过将气味信息的引导策略融入到Q-learning算法的最优动作选择策略中来改善算法的收敛速度。实验结果验证了该算法可以不断地学习环境并且提高Q-learning算法的收敛速度。
1 基于气味奖励引导策略的Q-learning算法1.1 Q-learning算法Q-learning是一种无模型的值迭代强化学习算法，主要针对符合有限Morkov决策过程的学习问题，学习时状态值函数是根据其他状态的值函数进行逼近，通过优化一个可迭代计算的行为价值函数Q来获得最优策略，是一种增量式的离线学习算法。该行为价值函数Q迭代计算方程如下所示：

$\begin{array}{*{20}{c}}{Q\left( {{S_t},{A_t}} \right) \leftarrow Q\left( {{S_t},{A_t}} \right) + }\\{\alpha \left[ {{R_{t + 1}} + \gamma \mathop {\max }\limits_a Q\left( {{S_{t + 1}},a} \right) - Q\left( {{S_t},{A_t}} \right)} \right].}\end{array}$

(1)

在动作选择的策略中采用ε贪心算法(0 < ε < 1)，该算法的使用可以平衡环境学习过程中环境探索和利用的关系，一般选择一个渐变的贪心策略，在认知环境的初始阶段缺乏对环境的先验知识，可以较大概率的采用随机选择动作的策略实现对环境的探索，避免陷入局部最优，随着探索环境知识的积累，渐渐地以一个较大的概率采用选择最大行为价值的动作策略实现对已学习到的环境的利用。
在环境探索的初始阶段，机器人不具备对于环境的先验知识，其初始化的Q-table中所有状态的动作值都为0，无法选择出最大的动作值执行下一步动作，机器人只能进行随机的动作选择进行探索环境。而且在探索过程中机器人会以ε的概率进行随机的动作选择，虽然这在一定程度上使机器人不会陷入局部最优解，但同时也降低了算法的收敛速度，导致机器人进行无用的空间探索。

图 1 Q-learning算法

图选项

针对上述问题，本文从生物体的嗅觉系统获取灵感，在机器人执行动作之前，将机器人的嗅觉信息奖励纳入到机器人的动作选择策略中。与之前无先验知识的Q-learning相比，机器人嗅觉奖励的引导减少了机器人对无用环境的探索，从而提高了算法的收敛速度。
1.2 气味奖励引导策略所有运动型生物都可以利用周围环境的空间分布的化学特征来指导其行为，鸽子通过辨认栖息地附近地区物体的气味，据此在头脑中构建出一幅方位清晰的气味路标图来进行导航；昆虫可以通过跟踪气味羽流来检测和定位远处的气味源^[15]；老鼠可以通过嗅觉和体感刺激追踪空气中食物的气味来进行定向，以寻找食物来源。本文从生物的气味引导策略获取灵感，并从强化学习的角度对此进行了建模。
当食物放于环境中时，食物散发出的气味就散布于空气之中，假设在理想情况下，气味的浓度在距离食物相等位置的浓度分布均匀，建立气味在环境中的弥散函数：

$O(d) = {O_0}{{\rm{e}}^{ - \lambda d}}.$

(2)

其中：d为当前位置与食物位置之间的距离，λ为气味衰减因子，O₀为食物位置处的气味强度。
基于环境中气味的弥散函数，可以建立环境的全局气味信息。本文对弥散函数进行了离散化的处理，当前位置与目标点位置之间的距离采用Manhattan距离：

$d = |x_{\rm{s}}^{\rm{c}} - x_{\rm{s}}^{\rm{g}}| + |y_{\rm{s}}^{\rm{c}} - y_{\rm{s}}^{\rm{g}}|.$

(3)

其中：$\left(x_{\mathrm{s}}^{\mathrm{c}}, y_{\mathrm{s}}^{\mathrm{c}}\right) $表示当前位置的坐标，$ \left(x_{\mathrm{s}}^{\mathrm{g}}, y_{\mathrm{s}}^{\mathrm{g}}\right)$表示目标点位置的坐标。
在老鼠的生态行为中，可以通过移动身体在更远的距离上嗅探，通过移动头部在更近的距离上嗅探^[16]，并且能够从每个鼻孔中分离出信息，从而可以准确地锁定气味的来源。本文对老鼠的该生态行为进行了简单化建模，结合建立的栅格环境，假设老鼠可以在自己所在位置嗅到一步之内的气味强度的差异，故可以建立老鼠在某一位置的嗅觉状态表O_t：

$\begin{array}{*{20}{c}}{{O_t} = \left\{ {(i,j):\left\{ {‘ {u’ }:{O_{(i,j - 1)}}{,‘ }{r’ }:{O_{(i + 1,j)}}} \right\},} \right.}\\{\left. {\left. {‘ {d’ }:{O_{(i,j + 1)}}{,‘ }{l’ }:{O_{(i - 1,j)}}} \right\}} \right\}.}\end{array}$

(4)

其中：(i, j)表示当前的位置，‘u’、‘r’、‘d’、‘l’分别表示向前、向右、向后、向左嗅，O_{(i, j－1)}、O_{(i+1, j)}、O_{(i, j+1)}、O_{(i－1, j)}分别表示向前、向右、向后、向左嗅到的气味强度。
同样地，在状态S_t下的动作选择采用贪婪策略：

${A_t} = \mathop {{\rm{max}}}\limits_a ({O_t}({S_t},a)).$

(5)

图 2 气味奖励引导算法

图选项

气味奖励引导策略仅仅依靠智能体的嗅觉信息，缺乏自主学习能力，当在智能体当前位置和目标点位置的路径上存在障碍物时，容易陷入局部最优问题而无法到达目标点位置。
1.3 气味奖励引导策略的Q-learning算法为了改善经典Q-learning算法收敛速度慢的局限性，本文提出了基于气味奖励引导的Q-learning算法。该算法的核心为：在从当前状态向下一时刻状态转移时，将同时采用Q-learning算法和气味奖励引导算法的动作选择策略。
为了平衡动作选择策略中学习行为和气味奖励引导策略的关系，引入嗅觉因子σ(0≤σ≤1)，基于气味奖励引导的Q-learning算法的动作选择策略为

${A_t} = (1 - \sigma ) \mathop {{\rm{max}}}\limits_a Q({S_t},a) + \sigma \mathop {{\rm{max}}}\limits_a ({O_t}({S_t},a)).$

(6)

图 3 气味奖励引导策略的Q-learning算法

图选项

2 环境模型本文用Tolman老鼠实验来对所提出基于气味奖励引导的Q-learning算法进行测试，从而探索智能体对环境的学习和认知能力，并且将基于气味奖励引导的Q-learning算法与经典的Q-learning算法进行比较。
Tolman为了探索动物在学习过程中的认知变化，进行了老鼠学习方位的迷宫实验。实验的迷宫如图 4所示，迷宫中有到达食物箱的3条长短不等的通道^[17]。若3条通道畅通，白鼠会选择通道1到达食物箱；若堵塞A处，白鼠会选择走通道2；若B处阻塞，则白鼠会选择走通道3。

图 4 Tolman迷宫

图选项

常见的地图表示方法有3种：栅格地图、拓扑地图和几何特征地图。栅格表示法易于实现建模、更新与处理，所以也是目前最常用的简单、有效的环境表达方法。建立一个9×9的栅格地图来模拟Tolman实验中的迷宫环境，栅格地图简化了实际的环境情况，一个栅格代表智能体的一个状态，实线代表墙壁，无法穿越。如图 5所示，每个网格的位置通过Cartesian平面进行标记，水平方向为x轴，竖直方向为y轴，坐标以(x, y)格式表示，左上角为坐标系的原点即(0, 0)点，出发点为图中老鼠的位置，坐标为(4, 9)，目标点位置为图中蛋糕的位置，坐标为(4, 1)。通道1的路径长度为9，通道2的路径长度为13，通道3的路径长度为17。其中，设定气味信息在环境中散布的最大距离为5，不同颜色的状态表示该位置的气味强度不同，距离食物越近的颜色表示气味强度越大，如图 5c所示。

图 5 (网络版彩图)Tolman栅格地图

图选项

3 实验结果智能体的动作集包括上、下、左、右4个动作，且动作的步长为一个栅格，智能体得到的奖励来自于与外界环境的交互反馈，碰到墙壁时的奖励为-10；到达食物位置即终点时得到的奖励为50；每走一步得到的奖励为-0.1。
3.1 参数设定在Q-learning算法中，式(1)中的学习率定义了一个旧的Q值将从新的Q值学到的新Q值占自身的比重。值为0意味着旧的信息是重要的，值为1意味着学习到的新的信息是唯一重要的信息。折扣因子γ是Q-learning算法中确定奖励类型的另一个重要参数，它定义了未来奖励的重要性。γ=0意味着只考虑短期奖励，γ=1意味着更重视长期奖励。在本研究中在Tolman地图上进行了关于学习率α、折扣因子γ的参数选择的实验，对Tolman地图的3种情况分别做了100次的实验，每次训练30个回合，每个回合最多走150步或满足停止条件为止。并以老鼠所走的步数作为评价，求取每一个参数下老鼠所走步数的平均值，实验结果如图 6所示。

图 6 (网络版彩图)不同学习率α，折扣因子γ的实验结果

图选项

随着学习率α、折扣因子γ的值逐渐增大，智能体所走的总步数逐渐减少，说明算法的收敛速度越快。本研究中，取α=0.9，γ=0.9，折扣因子较高时可使智能体进行更多的探索，并在一定程度上防止Q-learning陷入局部最优状态。
3.2 环境认知学习首先对智能体在未知环境中的学习能力分别在3个地图中进行了测试，智能体模仿Tolman实验中的老鼠在迷宫寻找食物，对于智能体来说，整个环境的地图信息是未知的，智能体只能通过自己的嗅觉系统来嗅觉空气中食物的气味信息，并利用自己的智能来寻找放置于环境中的食物，同时在寻找的过程中建立自己的行为认知地图，且在学习的过程中实时更新行为认知地图。
图 7展示了智能体分别在无阻塞、A处阻塞、B处阻塞情况下，分别用Q-learning算法和基于气味奖励引导的Q-learning算法进行的实验图。图中的箭头表示机器人下一次到达该位置时将要采取的动作。如图 7a和7b所示，Epoch 1是智能体进行学习认知环境的第一个回合，表示智能体学习的初始阶段，图 7a中(No Block, Epoch 1)、(Block A, Epoch 1)、(Block B, Epoch 1)和图 7b中(No Block, Epoch 1)、(Block A, Epoch 1)、(Block B, Epoch 1)部分中红色框框选出了智能体的行为动作，没有给智能体视觉功能，所以智能体不能像老鼠一样看到前方障碍和食物，在实验的初始阶段，智能体会有撞墙的行为，在经过一段时间学习之后，可以通过图 7a中(No Block, Epoch 5)、(Block A, Epoch 5)、(Block B, Epoch 5)和图 7b中(No Block, Epoch 5)、(Block A, Epoch 5)、(Block B, Epoch 5)部分发现，智能体对撞墙位置处的行为动作已进行了更新，使下一次采取的动作不再撞墙。撞墙位置处的行为动作的优化更新体现了分别采用Q-learning算法和基于气味奖励引导策略的Q-learning算法的智能体具备一定的对环境的认知学习能力。

图 7 (网络版彩图)行为学习的比较实验图

图选项

如图 7a中(No Block, Epoch 30)、(Block A, Epoch 30)、(Block A, Epoch 30)和图 7b中(No Block, Epoch 30)、(Block A, Epoch 30)、(Block A, Epoch 30)所示，基于2种算法的智能体经过一段时间的学习后均能找到一条路径最短的线路到达食物的位置。在Tolman迷宫环境无阻塞时，智能体找到最短路径通道1，在通道1的A处阻塞后，智能体能够找到最短路径通道2，在通道1的B处阻塞后，智能体能够找到最短路径通道3，动态实验见视频1(https://v.youku.com/v_show/id_XNDcxMDc1NzI2OA==.html)。如图 7a中(No Block, Epoch 1)、(No Block, Epoch 5)、(No Block, Epoch 30)和图 7b中(No Block, Epoch 1)、(No Block, Epoch 5)、(No Block, Epoch 30)部分所示，在Tolman的迷宫环境中，不同的认知学习阶段，无气味奖励引导的Q-learning算法的智能体建立的行为认知地图均比基于气味奖励引导的Q-learning算法的智能体建立的行为认知地图的范围大，这体现了在当前环境中基于气味奖励引导的Q-learning算法相比无气味奖励引导的Q-learning算法可以减少智能体对无用环境的探索，从而提高算法的快速性。
3.3 算法收敛性实验为了展示算法的收敛性，图 8展示了智能体在无阻塞的Tolman地图中迭代学习的步数。在迭代初期，智能体主要在探索未知环境，经过初期的探索和学习后，智能体对环境信息有了一定的认识，在后面过程中开始利用初期学习到的环境信息来不断优化自己的行为认知地图，直至找到一条从起点到终点的最优路径。

图 8 (网络版彩图)收敛速度对比图

图选项

基于气味奖励引导的Q-learning算法的收敛性要优于经典的Q-learning算法，这是由于智能体在选择下一个动作时，不仅仅采用学习到的环境信息作为自己的动作选择策略，而且还将在当前状态下通过嗅觉嗅到的环境信息作为自己的动作选择策略。两种动作选择策略的线性组合在一定程度上引导智能体更有效地从起始位置寻找并到达目标位置，动态对比实验见视频2(https://v.youku.com/v_show/id_XNDcxMDc3MzM1Ng==.html)。
4 结论Q-learning算法在环境认知学习的过程中存在环境探索和利用的矛盾关系导致算法收敛速度慢的问题。为了提高移动机器人在非结构化环境中的认知学习能力，提高算法的收敛速度，本文提出基于气味奖励引导的Q-learning环境认知方法，主要工作有以下3点：
1) 受啮齿类动物可以利用嗅觉线索来进行空间定向和导航的启发，提出了气味奖励引导策略。
2) 对Q-learning算法加以改进，将气味奖励引导策略与Q-learning算法相融合，在环境探索过程中优化动作选择策略，将环境中气味奖励信息的引导引入Q-learning算法的动作选择策略中。
3) 提出嗅觉因子来平衡动作选择策略中Q-learning和气味奖励引导策略的权重关系，从而提高对环境的认知学习能力。
通过在Tolman迷宫环境下的仿真实验证明，基于气味奖励引导的Q-learning算法可以减少对无用环境的探索，提高算法的收敛速度。在后续研究中，将引入视觉信息来使移动机器人具有更高的环境认知能力。

参考文献

[1]	王志文, 郭戈. 移动机器人导航技术现状与展望[J]. 机器人, 2003, 25(5): 470-474. WANG Z W, GUO G. Present situation and future development of mobile robot navigation technology[J]. Robot, 2003, 25(5): 470-474. (in Chinese)
[2]	SUTTON R S, BARTO A G. Reinforcement learning: An introduction[M]. Cambridge, MA: MIT Press, 2018.
[3]	WATKINS C J C H, DAYAN P. Q-learning[J]. Machine Learning, 1992, 8(3-4): 279-292. DOI:10.1007/BF00992698
[4]	YUAN R P, ZHANG F H, WANG Y, et al. A Q-learning approach based on human reasoning for navigation in a dynamic environment[J]. Robotica, 2019, 37(3): 445-468. DOI:10.1017/S026357471800111X
[5]	KHRIJI L, TOUATI F, BENHMED K, et al. Mobile robot navigation based on Q-learning technique[J]. International Journal of Advanced Robotic Systems, 2011, 8(1): 4. DOI:10.5772/10528
[6]	SONG Y, LI Y B, LI C H, et al. An efficient initialization approach of Q-learning for mobile robots[J]. International Journal of Control, Automation and Systems, 2012, 10(1): 166-172. DOI:10.1007/s12555-012-0119-9
[7]	LOW E S, ONG P, CHEAH K C. Solving the optimal path planning of a mobile robot using improved Q-learning[J]. Robotics and Autonomous Systems, 2019, 115: 143-161. DOI:10.1016/j.robot.2019.02.013
[8]	PANG T, RUAN X G, WANG E S, et al. Based on A* and Q-learning search and rescue robot navigation[J]. Telkomnika Indonesian Journal of Electrical Engineering, 2012, 10(7): 1889-1896.
[9]	LI S D, XU X, ZUO L. Dynamic path planning of a mobile robot with improved Q-learning algorithm[C]//2015 IEEE International Conference on Information and Automation. Lijiang, China: IEEE, 2015: 409-414.
[10]	NI J J, LI X Y, HUA M G, et al. Bio inspired neural network based Q-learning approach for robot path planning in unknown environments[J]. Int J Robot Autom, 2016, 31(6): 4526-4590.
[11]	ITO M, MIYAKE S, SAWADA Y. A neural network model of hippocampus-based ganglia for rat navigation tasks[J]. Electronics and Communications in Japan (Part Ⅲ: Fundamental Electronic Science), 2004, 87(10): 66-80.
[12]	KULVICIUS T, TAMOSIUNAITE M, AINGE J, et al. Odor supported place cell model and goal navigation in rodents[J]. Journal of Computational Neuroscience, 2008, 25(3): 481-500. DOI:10.1007/s10827-008-0090-x
[13]	KHAN A G, SARANGI M, BHALLA U S. Rats track odour trails accurately using a multi-layered strategy with near-optimal sampling[J]. Nature Communications, 2012, 3: 703. DOI:10.1038/ncomms1712
[14]	WALLACE D G, KOLB B, WHISHAW I Q. Odor tracking in rats with orbital frontal lesions[J]. Behavioral Neuroscience, 2003, 117(3): 616-620. DOI:10.1037/0735-7044.117.3.616
[15]	LIU A N, PAPALE A E, HENGENIUS J, et al. Mouse navigation strategies for odor source localization[J]. Frontiers in Neuroscience, 2020, 14: 218. DOI:10.3389/fnins.2020.00218
[16]	LI C Y, DONG H B, ZHAO K. Dual functions of insect wings in an odor-guided aeronautic navigation[J]. Journal of Fluids Engineering, 2020, 142(3): 030902. DOI:10.1115/1.4045946
[17]	TOLMAN E C. Cognitive maps in rats and men[J]. Psychological Review, 1948, 55(4): 189. DOI:10.1037/h0061626