马尔科夫理论在无人系统中的研究现状

严浙平，杨泽文，王璐，岳立冬，潘晓丽

哈尔滨工程大学 自动化学院，黑龙江 哈尔滨 150001

0 引 言

随着人工智能技术的快速发展，智能系统已经渗透到日常生活的各个方面，并逐渐发挥着重要作用。智能体理论为智能系统的建模、设计和实现提供了统一的框架。智能体必须能够自主地综合各种传感器提供的感知信息，做出实时决策，并与环境进行交互。传感器收集到的信息是不全面的，并夹杂各种噪声，同时无人平台的输出效果也具有不可预知性，存在误差。这种不确定性为智能体的规划和感知任务带来了很大的挑战。基于马尔科夫过程的决策理论为这类问题提供了基本的理论框架。

1870年，俄国数学家马尔科夫建立了马尔科夫模型，又于1906年发表了《大数定律关于相依变量的扩展》一文，为1907年提出的马尔科夫过程奠定了理论基础，给出了研究离散事件动态系统状态空间的重要方法。由此，马尔科夫理论也成为随机过程中概率论的重要组成部分，被广泛应用于科学技术领域。随后，又形成了了马尔科夫链理论，经过进一步发展，建立了隐马尔科夫模型。由于马尔科夫链和隐马尔科夫模型具有良好的数学基础支撑，至今仍是各国学者研究的热点；其在语音语义识别［1-2］、机器学习［3］、无人系统［4］、经济学［5］、物理学、化学、生物学、气象学、通信等学科领域都产生了连锁性的反应，涌现出一系列新的课题、新的理论和新的学科。例如，在经济学方面，预测产品销售和利率的变化，分析和预测股市的走势等；在物理学方面，将泊松过程、弗瑞过程作为实际级联的近似，以及更新过程的应用等；在化学方面，对化学反应的动力学模型和生灭过程的描述等；在生物数学方面，可以构造生物现象模型，包括种群迁移模型、生灭型随机模型、性别变化模型等，且应用于传染病流行问题、生物遗传问题等方面；在通信、探测等领域，应用于传递信号与接收信号过程中的噪声消除；在空间科学和工业生产的自动化技术中，需要用到信息论和控制理论，且在研究带随机干扰的控制问题时也要应用马尔科夫随机过程［6-7］。

无人系统领域的研究经常会用到马尔科夫理论，如自主决策和调度、任务规划、路径跟踪、感知与避碰、导航制导、计算机视觉等。以马尔科夫决策过程和部分可观察的马尔科夫决策过程为代表的马尔科夫决策理论，可以解决满足马尔科夫性质的不确定性环境下的感知、规划和学习问题，并能提供统一的理论框架和丰富的数学模型。在预测方面，可利用经验概率来创建初始概率分布和状态转移矩阵以构造马尔科夫模型，进而进行具体问题的预测研究。无人系统中，马尔科夫理论在不确定环境下的决策规划、目标识别以及预测算法等中起重要作用。本文拟针对马尔科夫理论在无人系统中的应用，分别从无人机（UAV）、无人车（UGV）以及自主式水下机器人（AUV）等无人平台的角度进行研究，归纳总结国内外无人系统中应用对象的发展现状。

1 马尔科夫理论

在概率学中，随机过程是描述不确定系统的基础。在状态空间S中，设定随机过程，是关于时间的序列，其中

当时间和状态都是离散量时，马尔科夫过程（Markov process）又被称为马尔科夫链（Markov chain），是具有无后效性的时间序列。所谓无后效性，是指序列的将来状态只与其当前所处状态有关，而与其过去状态无关。图1所示为马尔科夫链，假设当前系统处于A状态，那么在下一时刻，系统有60%的概率转移到B状态，且有40%的概率依旧处于A状态；同理，如果当前系统处于B状态，那么在下一时刻，系统有80%的概率转移到A状态，有20%的概率处于B状态。X∈S，T={0，1，2，…，n}，马尔科夫的一般表达形式为［8］：

根据状态和时间的连续型和离散型分类，可以将马尔科夫过程分为如表1所示的4类。

表1 马尔科夫过程Table 1 Markov process

如果一个马尔科夫链的状态是部分可观察的，则称这个马尔科夫链为隐马尔科夫模型（Hidden Markov Model，HMM）。HMM观察虽然跟系统状态直接相关，但观察一般具有不确定性，不足以推断系统的真实状态，即给定状态下只能按照一定的概率获得不同的观察。与马尔科夫链相比，HMM是双重随机过程，即状态转移之间是个随机事件，状态和输出之间也是一个随机过程。为了更好地理解HMM，采用2个系统状态量和3个系统观察值举例说明，如图2所示。图中：X1，X2为系统状态；Y1，Y2，Y3为系统观察值；a为状态转移概率；b为观察值概率。当引入智能体和智能体行动时，一个受控的马尔科夫过程就转化为一个马尔科夫决策过程（Markov Decision Process，MDP）。状态转移概率不仅依赖于当前的状态，还依赖于作用于当前状态的动作，具有行动不确定性。类似地，一个受控的HMM构成一个部分可观察马尔科夫决策过程（Particularly-Observable MDP，POMDP）。表2简明总结了以上4种马尔科夫模型。

表2 马尔科夫模型Table 2 Markov model

2 UAV

随着UAV的飞速发展，其已被广泛应用于监视、巡逻、目标跟踪和紧急救援等自主任务。此外，在民用领域也出现了成熟的UAV产品。近年来，UAV快递运输逐渐兴起，尤其在处理自然灾害、事故灾难以及社会安全事件等方面发挥了重要作用。图3和图4展示的分别为军用UAV和民用固定翼UAV。

2.1 决策规划

在复杂环境中进行任务规划是UAV应用的重要组成部分之一。单/多UAV侦察监视问题的决策和规划，是人工智能与机器人领域的研究热点。如图5所示，针对具体问题，首先通过规划器规划得到智能体的行为策略，然后通过控制器执行智能体的行动并与环境进行交互。然而，在对问题进行建模时，传统规划方法往往假设任务及环境具有完全可观和静态的特征。马尔科夫决策理论为不确定性规划提供了具有理论支撑的形式化描述手段。而对于多智能体规划，可以将马尔科夫过程细分为多智能体部分可观察马尔科夫决策过程（Multi-agent POMDP，MPOMDP）和分散式部分可观察的马尔科夫决策过程（Decentralized POMDP）。

在单UAV的应用研究方面，主要针对不确定环境或环境信息不完整的情况，完成了行动规划、导航规划和路径规划等。在进行UAV运动规划时，传感器产生的噪声、机器人的状态感知以及因不可预测的外力导致的机器人运动，都会引起运动状态的不确定性。Ji等［9］提出了一种基于POMDP的固定翼UAV在感知和运动不确定性条件下的规划框架，通过地图和噪声传感器进行导航，避开障碍物到达目标位置。但上述方法不能执行大规模的复杂任务。通过建立基于MDP的规划，学习重点自适应控制器之间的密切反馈，可以搭建一个适用于长期、复杂任务的感知规划框架［10］。在任务管理系统层面，可以采用基于分层任务网络的符号规划器的混合体系结构，与基于MDP的策略生成器协同工作，以减少数字路径规划器的搜索空间［11］。

在UAV集群的应用研究方面，UAV集群在执行决策时需要对单体进行任务分配，陈少飞［12］将部分可观察马尔科夫决策过程与一种近似最优的在线规划算法相结合，以解决多智能体合理依次分配任务策略的问题。UAV在执行作战任务时不确定程度较高，需要解决动态任务问题，李月娟等［13］将动态任务分配模型等效为多智能体的马尔科夫决策过程，结合遗传算法确定最优任务分配策略，提高了任务分配的效率。针对多个UAV执行监视任务的流程，Jeong等［14］提出了一种减小决策空间而不损失问题关键特征的方法，可以将监视区域的不确定性维持在较低水平。

2.2 目标跟踪

随着硬件研发条件的成熟，UAV开始向智能自主化方向发展，其应具备的基本能力之一就是对地面多机动目标的自主检测和跟踪。由于目标的运动具有不确定性，可以利用马尔科夫模型对目标进行预测。

利用HMM可以对目标区域内多地面目标的全局态势进行估计，利用Baum-Welch算法训练隐马尔科夫模型参数，得到相应的预测模型，并预测多目标的全局态势，进而提供UAV搜寻和跟踪目标的决策依据［15］。在考虑UAV跟踪移动目标的最佳路径时，局限性之一是当目标移动速度比UAV的最小速度慢得多时缺乏悬停能力，这就要求UAV保持着围绕目标的轨道。Baek等［16］提出了一种寻找UAV的最优策略，使移动目标的位置不确定性最小化，但此方法仅针对单一目标。Ragi等［17］提出了一种UAV跟踪多个地面目标的路径规划算法。Vanegas等［18-20］利用部分可观察马尔科夫决策过程解决UAV导航和目标发现问题，每次迭代后重新规划路径，以减少在有障碍环境中运动的不确定性和GPS信号干扰等。由于单UAV视野的局限性，难以胜任对大范围移动目标的搜索，而UAV集群协同搜索目标则可明显提高拦截概率［21］，搜索用时也较短，因此UAV集群协同任务逐渐成为该领域的研究重点。

2.3 其他应用

UAV感知与避碰、动态巡逻以及作战、UAV攻击决策等，都需要将马尔科夫过程作为模型基础来设计算法。基于马尔科夫决策过程可以完成UAV避碰决策机制及避碰策略［22］，确保UAV自主避碰多个入侵者［23］。Krishnamoorthy等［24］开发了一种降阶的动态规划方法，有效计算了一类受控马尔科夫链的最优策略和价值函数，较好地解决了UAV集群巡视随机最优控制问题。由于数据传输存在延迟，因此不能及时对当前作战情况做出准确决策，而采用状态外推算法和马尔科夫加速模型则可对UAV与机动目标状态进行预测，弥补因数据滞后所引起的战场形势预测不准确问题［25］。

3 UGV

UGV主要通过智能驾驶仪来实现无人驾驶。其一般利用车载传感器来感知车辆周围环境，然后根据感知获取的道路、车辆位置和障碍物信息控制车辆的方向和速度，从而保证车辆安全行驶。图6所示为谷歌公司于2017年研发的“萤火虫”UGV。

马尔科夫理论在UGV研究领域的的应用十分广泛。UGV在完成路况识别、网络通信、道路检测和跟踪以及车辆避碰等各项任务时，都需要利用马尔科夫模型进行辅助设计。

3.1 路况识别

无人车需要识别和解读路面车辆情况、交通标志以及信号。在车辆随机换道意图识别的模型估计、交通标志牌的图像分析和交通信号识别的模型研究中，可以结合马尔科夫模型进行研究。

根据美国国家公路交通安全管理局（NHTSA）的定义，可以将无人驾驶分为5个级别（0～4级）［26］。0级：无自动化，没有任何自动驾驶功能、技术，司机对汽车的所有功能拥有绝对控制权；1级：驾驶支援，向司机提供基本的技术性帮助；2级：部分自动化，实现数种功能的自动控制；3级：有条件自动化，在有限情况下实现自动控制；4级：完全自动化（无人驾驶）。目前的UGV多集中在第3级，并不能完全实现真正的自动驾驶。第3级无人驾驶多应用在高速公路中。在高速公路中，最基础的2类驾驶模式是车辆换道和车辆保持。在车辆换道识别时，利用支持向量机和高斯混合HMM，可以建立高速公路中汽车换道意图的识别模型［27］。车道保持要求自主驾驶的汽车不能偏离原有的车道，对其他车辆车道偏离行为进行预测并向驾驶员发出警报。高振海等［28］基于高斯混合马尔科夫模型，提出了一人一车特性的无意识车道偏离的识别模型，提高了识别的效率与准确性。

除了对车道保持和车辆换道的识别，UGV在行驶过程中对交通标志牌、交通信号灯状态的识别也具有重要的现实意义。密集深度图像恢复技术在UGV领域的应用受到越来越多的关注。Zeng等［29］提出利用双边滤波框架生成密集深度图像，然后采用马尔科夫随机场对其进行细化，在复杂场景下，可以获得密集的深度图像，简化了图像分割以及目标跟踪、分类和识别。利用HMM算法可以进行交通信号灯状态的信息预测，有利于设计和实现交通信号灯识别与交通标志识别系统［30］。UGV高效地识别信号可以保障其信号灯通过性，更好地完成自动驾驶任务。

3.2 网络通信

UGV完成安全自主驾驶和复杂任务的重要基础是畅通的网络通信，但实际的通信环境不一定满足要求，因此在网络延时、间断连接、数据包丢失等恶劣环境下的通信研究尤为重要。

为了应对网络延时，并避免数据包无序的情况，Cuenca等［31］考虑了马尔科夫链驱动的网络控制系统场景，设计了保证网络控制系统稳定性的控制策略。与在无线通信网络中使用资源预留协议相比，集成马尔科夫链和资源预留协议算法可以保证更高的带宽和更好的服务质量［32］。而针对通信中断这一情况，可以将高斯—马尔科夫状态空间模型用于节点动力学，结合扩展卡尔曼滤波器，在网络连接间歇性中断的条件下完成实时路径规划［33］。

3.3 其他应用

在智能交通、无人驾驶和驾驶员安全辅助等系统中，马尔科夫模型在道路检测和跟踪、车辆避碰等方面具有重要作用。为了让UGV更好地完成自主驾驶任务，首先需要对车道进行检测，利用齐次马尔科夫链建立车道场景序列模型，并预测模型参数［34］。车辆避碰是保障UGV安全行驶的重要技术。针对匝道入口的避碰问题，王诗源［35］通过V2V通信技术获得其他汽车的行驶状态，利用多维HMM预估其他车辆的驾驶意图，解决了具体场景中的安全避碰问题。

UGV利用导航技术到达设定的目标地点，其中定位技术是关键。针对地图构建和同时定位的问题，可以利用马尔科夫链蒙特卡罗法进行采样，并用序贯蒙特卡罗算法构建分布策略解决［36］。

4 AUV

AUV应用范围广，是实现海洋科学调查、海下煤油勘探、深水探查和海洋目标探查等的重要工具。

在开展路径规划、目标识别、声呐通信、海洋数据采集、故障检测、位置估计等任务时，AUV可利用马尔科夫原理建立决策过程和不确定性因素的估计。其在水声通信建模中的应用也具有不可替代的优势。图7所示为“蓝鳍金枪鱼”号AUV。

4.1 路径规划

路径规划首先要使无人系统能够从设定的出发点到达预定的目标点，然后在运动过程中能经过指定点并且躲避障碍物。

由于海洋环境情况大多未知，在路径规划的同时应考虑未知环境与障碍物的避碰情况，因此需要利用离线马尔科夫决策过程的运动规划结果进行目标路径跟踪和避碰，完成实时避碰的目标路径跟踪［37］。

马尔科夫理论也被应用于多AUV路径规划。由于没有GPS信号，水下导航具有挑战性。定位误差会随着时间的推移而增加，一种减少误差的方式是在其中一个AUV上配备高精度导航传感器，将其位置以声学方式传送给其他AUV。在位置误差不断积累的情况下，基于马尔科夫决策过程框架，通过交叉熵方法学习路径规划策略，可以使AUV在有限的位置误差内航行［38］。另一种方式是多AUV合作完成路径规划，用动态规划和马尔科夫决策过程算法最小化来减少AUV的累积定位误差，并通过声学距离测量的辅助使AUV间距保持最小误差［39］。在水下航行时，路径规划和避碰是AUV的基本功能。洪晔等［40］讨论了一种基于部分可观察马尔科夫决策过程的全局路径规划方式，利用短期预测和长期预测这2种方法，预测了障碍物的运动轨迹，并通过仿真验证了该方法的有效性。

4.2 目标识别

在水中，主要依靠声呐传感器来对物体进行探测和识别。为了解决单个声呐探测范围的局限性，最直接的方法是增加声呐数量。传统的信息融合方法大多忽略了声呐各个节点的相关性，其搜索效果并不理想。温涛等［41］提出了利用连续HMM进行多基地水下目标识别的方法，其对4类目标进行了识别，和多基地声呐单节点的最高识别率相比，提高了30%。在反潜武器装备体系中，搜索并发现目标的能力尤为重要，这是无人系统自身防御和对敌攻击等决策的前提，基于HMM的联合搜索方法，可以提高反潜系统优化搜索以及搜索行为决策的效率，更好地辅助作战系统对战况进行在线分析［42］。为进一步提高识别效率，Myers等［43-44］解决了从多视角的声呐图像中分类目标的问题，将其模拟为部分可观察的马尔科夫决策过程，充分利用声呐获得的多视图信息，给出了准确性优于采用多个预定视角的方法，并对图像中的目标进行了分类。

环境噪声干扰对声呐识别有严重影响，因此需要对声呐信息进行处理。将卡尔曼滤波与马尔科夫过程相结合可以更好地识别目标。詹艳梅等［45］针对环境噪声大、传输距离远、识别目标小等问题，将自适应加权的卡尔曼滤波器与Lainiotis算法结合，提高了声呐对目标运动的分析与估计的性能。王彪等［46］提出了一种基于改进粒子滤波算法的目标运动分析方法，分析了粒子滤波算法（EKF-PF）的优势，并充分考虑粒子的退化现象，将马尔科夫链蒙特卡罗方法与EKF-PF算法相结合，提高了声呐对水中物体的识别精度。另一种提高识别精度的方式是增加识别频率，但是增加采样频率会增加带宽和计算量。贝叶斯高分辨率方位估计方法采用可逆跳变马尔科夫链蒙特卡罗方法执行贝叶斯计算，可以实现利用较少的采样拍数获得更好的目标估计［47］。

4.3 声呐通信

水下通信是AUV之间、AUV与水上操控平台之间进行信息交流和信息传达的保障，复杂环境中的声呐通信研究也依赖马尔科夫理论。随着水下通信和传感器技术的发展，水下移动通信网络的应用越来越广泛，其可靠性研究是信息传输效率和质量的重要保证。水下移动通信可靠性可以利用马尔科夫模型进行建模，通过计算网络稳定状态的概率，并与通信网络指标可靠性概率矩阵相乘，从而给出量化的可靠性。该方法可以简化运算，降低建模的复杂性［48］。然而，由于水声通信链路的开放性特征，使得水声信息很容易被敌方截获或施加人为干扰。因此，在保证通信速率的同时，如何提高通信的隐蔽性、可靠性、保密性和时效性是水声军事通信中面临的重要问题。刘友永［49］利用卷积码和马尔科夫链对差分跳频系统频率转移函数的性能进行了深入分析，结合水声信道特点提出了一种具有良好时效性的频率转移函数，从而保证了通信的隐蔽性和保密性。在此基础上，为了提高通信的可靠性和时效性，徐君锋［50］提出了一种在水下传感器网络中利用汉明编码提高通信可靠性和能量有效性的多路径基于向前纠错的编码机制（MS-FEC）。该编码机制使用决策反馈算法，减少了多路径的跳数，以减少网络流量，实现提高能量有效性并满足通信可靠性的要求。针对水下传感器网络通信过程存在能量效率低、误码率高等问题，钟贞魁［51］提出了一种基于优先级服务质量选择策略的水下网络中继算法，提高了能量效率和网络平均生命周期。

为了解决水下无线传感器网络的空间公平问题，有效实现多信道通信，通过马尔科夫链构建了控制信道的预约模型。在考虑预约碰撞的条件下，分析计算了多信道MAC协议（SFM-MAC）的理论吞吐量，结果表明，SFM-MAC可以有效提高网络吞吐量和网络公平性［52］。与无频谱预测和随机接入相比，基于马尔科夫链的水下频谱预测方法能有效降低数据碰撞概率，从而提高节点接入频道的准确率和频道利用率［53］。

4.4 导航与定位

AUV具有良好的隐蔽性和较强的机动性，在水下隐蔽作业时要求其自主导航并能修正误差。因此，精确的导航与定位能力是保证AUV完成水下作业任务的关键技术之一。迟凤阳［54］提出了一种基于马尔科夫链蒙特卡罗方法和正则化方法的粒子滤波重采样算法，该算法增加了粒子的多样性，通过仿真试验，可以验证该算法在惯导/重力异常组合导航系统中的准确性。对于高精度水下定位要求，陈鹏云［55］提出了一种基于马尔科夫随机场（MRF）的海底地形精确定位方法，并通过仿真试验证明，当初始定位误差比较小时，基于MRF的海底地形精确定位可以实现小于0.5个网格分辨率的地形匹配精确定位。

4.5 其他应用

马尔科夫理论在海洋数据采集分析、AUV故障检测等方面也有应用［56］。李利红等［57］利用马尔科夫模型预测了西门岛海洋滩涂湿地各景观类型的面积比例。李胜朋等［58］运用Copula方法处理转移概率矩阵，得到了多稳态转换的海洋生态系统的平稳概率，使控制参数最大化。De Lucas等［59］应用HMM，在模拟AUV推进器系统的试验台上进行故障检测和诊断，降低了系统的故障风险。ZHANG等［60］针对部分可观测环境下的AUV软件故障修复问题，提出了一种基于POMDP模型和微重启机制来修复AUV故障的方法。基于AUV层次结构的特点，建立了AUV软件自修复POMDP模型，并设计了多级微重启修复方法。采用点值迭代算法（PBVI）得到修复策略，在部分可观测环境下以较低的维修成本修复系统，并通过仿真实验结果证明了该算法的有效性和模型的适用性。由HMM定义的分布决策函数是异常值检测的基础，其不同于普通数据。利用一种基于微波HMM的离群值检测的惯性算法对前离群值进行重新检测；该算法可以处理传感器收集的不准确原始数据，以提高检测结果的准确性［61］。

5 展 望

随着人工智能的发展，给无人系统在未知环境中做出智能规划、决策以及识别提出了更高的要求，这也成为国内外学者研究的热点问题。针对马尔科夫理论在无人系统中的应用，对未来的研究重点展望如下：

1）复杂任务的智能决策。马尔科夫决策过程可以很好地处理不确定因素，但不能处理高复杂度的任务，因此可以将马尔科夫理论与人工智能、深度学习、机器学习等技术相结合，实现复杂任务中的智能决策。

2）集群运动规划。无人系统在单体平台的研究已很成熟，但是在集群中的发展还处于起步阶段。无人机集群可以完成单无人机不能完成的任务，如农业灌溉、地图测绘、救援等，需要无人机集群协同完成；再比如AUV应用于军事领域中执行反潜任务、水下围捕任务及护航任务等。因此，交互式的任务规划是实现上述应用的有效方法。集群任务形式复杂，且需要在线实时更新调整，基于马尔科夫的运动规划框架，可以实现在线任务的自动处理和重新规划，保证任务规划的可执行性。

3）意图识别。无人系统对外界物体的识别可以简单地理解成物体的运动意图。目前，无人系统对目标的识别还停留在判断识别物体的位置，意图识别是目标识别的下一步研究方向。意图识别可以准确识别出移动物体的运动状态，无人系统可以根据此信息进行避碰或交互，利用马尔科夫模型，可以针对不同意图获得物体的运动模型，提高避碰、跟踪、追捕等任务的精度。

4）引入信念状态解决感知问题。无人系统做出决策的关键在于对当前状态的感知，因此引入信念状态可以更好地解决感知问题。信念状态可以利用粒子滤波描述，结合蒙特卡罗法在信念空间中解决感知问题，最后，利用启发式搜索等方法实现计算。引入信念状态可以提高无人系统对当前状态的感知，从而保障无人系统在线规划和决策等任务的准确性。

5）基于卡尔曼滤波的信息处理。在利用马尔科夫建立通信模型时，可以结合卡尔曼滤波器处理环境干扰，减小环境噪声，提高通信信息的准确度。

6 结 语

本文首先阐述了马尔科夫理论及其相关概念，然后详细归纳了马尔科夫理论在UAV，UGV，AUV等平台的应用情况，最后针对无人系统未来的研究重点进行了展望。国内针对无人系统的研究才刚刚起步，对于无人系统在不确定性环境下的感知、规划和学习问题，还有很大的进步空间，这也说明马尔科夫理论有着广泛的研究空间。随着人工智能和机器人技术的兴起，马尔科夫理论的发展与应用前景是无限的。