基于隐马尔可夫模型路径规划方法
2019-03-11邓旭赵连军郇静
邓旭 赵连军 郇静
摘要：针对复杂迷宫环境的目标体具体位置与路径规划问题为对象，提出了一种基于隐马尔可夫模型的粒子滤波算法。该方法通过隐马尔可夫模型的概率计算、粒子滤波算法时间流逝、观察、抽样策略，推理出目标体可能范围，通过A·算法将目标捕获。仿真结果表明，与普通的概率计算目标体位置，粒子滤波算法计算的目标体位置，大大减少了总步数，形成了最短路径。
关键词：路径规划：隐马尔可夫模型：粒子滤波
0引言
人工智能在越来越多的领域得到了应用。近几年人工智能的发展异常迅猛。Hinton等的卷积神级网络在计算机视觉领域的图形分类做出了重要贡献，并且在2015优化成深度学习。
Silver，D等在2016使用深度神经网络在有监督算法下训练的AlphaGo战胜韩国棋手李世石。AlphaGo Zero则实现了更进一步的提升，在不使用人类知识的情况下学习到了一个超人水平的计算机围棋程序。
人工智能在迷宫搜索方面有着广泛的应用。但是，自主移动机器人如何在未知的、复杂的环境中自主规划从起点到终点的路径，并且躲避障碍，或者通过路径规划捕获具体目标始终是复杂的技术难题。因此，进行移动机器人路径规划算法的研究，具有一定的理论意义和工程应用意义。迷宫机器人是移动机器人的典型应用，也是检验路径规划算法较好的平台
目前，在迷宫搜索方面，取得了很多有效的进展。但是目前的Agent迷宫搜索都是静态的单个目标搜索。在多个动态目标搜索方面存在着明显不足。
隐马尔可夫模型是统计模型。用来描述含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。利用这些参数作进一步的分析。其在语音技术和手写字符识别应用中广泛使用，但在迷宫搜索领域用得较少。
通过隐马尔可夫模型的应用，可以有效地确认多个动态目标位置，通过A*算法寻找和捕获目标。
1 研究现状
李庆中等提出的基于遗传算法，简单、有效的移动机器人实时动态避障路径规划方法，利用遗传算法实时、稳定地进行动态路径规划。仿真实验表明：动态路径规划方法可实时、稳定地产生移动机器人运动的最佳局部规划路径，且具有良好的动态避障性能。
顾新艳等研究移动机器人利用栅格法创建环境地图时，在其计算资源有限的情况下，比较利用迷宫八方向搜索思想，实现最短路径规划的Dijkstra算法，提出采用基于栅格划归地图的A*算法，能更快实现移动机器人的无碰最短路径规划。
温如春等对传统蚁群算法收敛性较慢的问题进行了改进。通过计算机仿真和电脑鼠机器人实际行走实验表明，在场地复杂的情况下，该算法可以有效地规划出全局最优路径。
李道新等研究移动机器人的历史与现状基础上，重点在移动机器人避障与路径选择规划中常用的算法中选取栅格法、势场法、遗传算法等方法进行分析比较：并以自行设计的一款微型机器人为例，探讨了基于红外感知的未知环境特征提取方法和安全避障距离选取的原则，给出了一种深广结合算法的移动机器人避障策略：描述了深广结合算法在机器人迷宫地图中最优路径规划实现中的应用。
Shazhaev Ilman（伊勒曼）基于多NAO机器人搭建实验平台，研究了机器人的定位模型、路径规划和走迷宫寻径问题。根据所建立的图像处理方法和定位模型得到了相应的图形信息，利用图像处理技术，完成了位置特征和环境特征的识别。基于NAO机器人坐标系，获取环境特征的定位信息，通过定位实验，验证了定位模型和路径规划的可行性。基于建立的典型迷宫结构图，进行了多机器人协同迷宫寻径的研究。实验完成了多机器人之间的信息交换，并可实时分享周围的环境信息。建立了相应的算法，根据编制的程序，利用分享的信息，机器人可以决定如何在迷宫中进行下一步行動。由于决策信息的实时共享，多个机器人比单个机器人更高效快捷地走出迷宫。
2 实验方法
本实验通过隐马尔可夫模型的粒子滤波算法和A*算法在复杂迷宫环境下找到动态目标。
2.1 马尔科夫链
马尔科夫链为状态空间中。经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质：下一状态的概率分布只能由当前状态决定，在时间序列中与前面的事件均无关。这种特定类型的“无记忆性”称作马尔可夫性质。在马尔可夫链的每一步，系统根据概率分布，可以从一个状态变到另一个状态，也可以保持当前状态。状态的改变叫做转移，与不同的状态改变相关的概率叫做转移概率，如随机漫步就是马尔可夫链的例子。随机漫步中每一步的状态是在图形中的点。可以移动到任何一个相邻的点。在这里移动到每一个点的概率都是相同的（无论之前漫步的路径如何）。
实验为了追踪所考虑的粒子随时间的变化。需要了解马尔科夫链的含义。其是在时间t=0的初始分布，以及某种过渡模型，用于描述在时间步长之间从一种状态迁移到另一种状态的可能性。如图l所示马尔可夫模型的初始分布，由Pr（P0）给出的概率，从状态i到i+1的转变模型由Pr（Pi+1|Pi）给出。此过渡模型暗示的值是有条件的，其仅取决于Pi的值。换句话说，在时间t=i+1时的粒子位置满足马尔可夫性质或无记忆性，并且与除t=i以外的所有其它时间步长的粒子位置无关。如果用以下方法重建p0，p1，p2之间的联合，使用马尔可夫模型链式规则如下：
Pr（P0，P1，P2）=Pr（P0）Pr（P1|P0）Pr（P2|P1，P0），（1）
假设Markov属性为true，并且W0W2| W1成立，则联合简化为：
Pr（P0，P1，P2）=Pr（Pn）Pr（P1|P0）Pr（P2|P1）。（2）
马尔科夫模型中，通常做出的最后一个假设是过渡模型是固定的。换句话说，对于所有i值，Pr（Pi+1|Pi）是相同的。在此可以用两个表来表示马尔可夫模型：一个用于Pr（Pn），一个用于Pr（Pi+1|Pi）。
通过马尔可夫模型，看到了如何通过一系列随机变量，将随着时间的变化纳入其中。例如，若想知道第1步的位置，可以从初始分布Pr（P0）开始，并在过渡模型中使用小前向算法计算Pr（P10）。但在时间t=0和t=10之间，可能会收集新的位置信息，这些证据可能会影响对任何给定位置概率分布的看法。
2.2 隐马尔可夫模型
与马尔科夫链不同。隐马尔可夫模型有两种不同类型的节点。为了区别起见，将每个pi称为状态变量，并将每个Ei称为证据变量。由于pi是第i步的位置概率分布，自然得出第i步的具体位置，有条件地依赖于这一概率。马尔科夫链如图1所示。正如马尔可夫模型一样。隐马尔可夫模型假设过渡模型是平稳的，具体模型如图2所示。隐马尔可夫模型对传感器模型做出了Pr（Pi+1|Pi）额外的简化，假设Pr（Ei+1|Pi）也是固定的。因此，任何隐马尔可夫模型都可以用3个概率表来紧凑地表示：初始分布、过渡模型和传感器模型。作为符号的最后一点，将定义时间i的概率分布，并给出所有证据Ei，…，Ei，且观察至B（Pi）=Pr（Pi|E1，…，Ei）。
同样，将B0（Pi）定义为在时间i处的概率分布，并观察到证据E1，…Ei，B（Pi）=Pr（Pi|E1，…，Ei）将Ei定义为在时间步i观察到的证据，有时会用以下形式重新表达时间步1≤i≤t的证据汇总：E1：t=E1，…Et，在这种表示法下，Pr（Pi|E1，…Ei）。经过时间的更新，将新的证据迭代地纳入粒子模型中。
2.3粒子滤波算法
对于贝叶斯网络，使用一种采样技术是有效估算所需概率分布的可行选择。隐藏的马尔可夫模型具有相同的缺点一运行需要时间。贝叶斯净采样的过程称为粒子滤波，其涉及模拟一组粒子的运动，通过状态图来近似表述随机变量的概率（信度）分布。
粒子过滤模拟始于粒子初始化，可以随机地、均匀地或从一些初始分布中采样粒子。一旦对初始粒子列表进行了采样，在每个时间步进行观察更新，更新是根据过渡模型，更新每个粒子的值。处于状态Pi的粒子，可从Pr（Pi+1|Pi）给出的概率分布中采样，得到更新后的值。更新与使用贝叶斯网络进行采样的相似性，因为任何给定的粒子的频率反映了转移概率。
使用传感器模型Pr（Ei|Pi），根據观察到的证据所指示的概率和粒子的状态对每个粒子进行加权。对于状态为Pi且传感器读数为Ei颗粒，分配Pr（Ei| Pi）的权重。观测更新的算法如下：
（1）如上所述计算所有颗粒的权重。
（2）计算每种状态的总权重。
（3）如果所有状态的所有权重之和为0，重新初始化所有粒子。
（4）否则，标准化总权重分布，并从该分布重新采样粒子列表。注意观察更新与似然加权的相似性，在此根据证据再次降低样本的权重。具体过程如图3所示。
3 实验结果与分析
3.1实验设置
为了验证实验的有效性，文本为Agent的路径规划设置了虚拟环境。本文制造了不同大小阻碍环境，其中障碍物和目标点都是随机生成的。如图4所示，实验设置了7个障碍，1个Agent，2个不可见目标点的7×7大小的原始环境地图。
由于实验的目标体是不可见的，通过粒子来代替一个具体个体，通过隐马尔可夫模型的粒子滤波算法找到不可见点的具体位置，如图5所示。
如图6所示，当粒子向不可见的点合拢时，智能体能找到具体目标，通过A*算法直接找到最近不可见的点，再找到另外一个不可见的点。
3.2 实验结果
为了使实验结果具有更好的准确性，将实验分成3组，分别在小迷宫、中迷宫、大迷宫的环境下寻找2个不可见目标点，通过10次实验，取其均值，其结果见表1.
通过实验结果可见，基于粒子滤波算法的路径规划比概率计算的路径规划，效率大幅度提升。
4 结束语
通过对复杂迷宫环境下的Agent寻找不可见目标的研究，提出了一种基于隐马尔可夫模型的粒子滤波算法，Agent通过粒子滤波算法确认不可见目标，通过A*算法最短路径找到最近目标。本实验使用粒子滤波结合A*算法，比普通的概率计算结合A*算法效率更高。下一步将研究多个智能体协同合作，实现多智能体在复杂环境下合作路径规划。
