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

资源描述：

downloaded from www.ship- 第 6 期收稿日期 2 0 1 8 - 0 2 - 2 3 网络首发时间 2 0 1 8 - 1 0 - 1 9 1 4 1 6 基金项目国家自然科学基金资助项目（ 5 1 6 7 9 0 5 7 ）；黑龙江省杰出青年科学基金资助项目（ J 2 0 1 6 J Q 0 0 5 2 ）作者简介严浙平，男， 1 9 7 2 年生，教授，博士生导师。研究方向水下无人航行器集成与控制，无人现场智能控制杨泽文（通信作者），男， 1 9 9 1 年生，博士生。研究方向水下无人航行器智能控制。 E - m a i l y z w f o r e v e r 1 2 6 . c o m 期刊网址 w w w . s h i p - r e s e a r c h . c o m 网络首发地址 h t t p / / k n s . c n k i . n e t / k c m s / d e t a i l / 4 2 . 1 7 5 5 . T J . 2 0 1 8 1 0 1 8 . 0 9 5 3 . 0 0 7 . h t m l 引用格式严浙平，杨泽文，王璐，等 . 马尔科夫理论在无人系统中的研究现状［ J ］ . 中国舰船研究， 2 0 1 8 ， 1 3 （ 6 ） 9 - 1 8 . Y A N Z P ， Y A N G Z W ， W A N G L ， e t a l . R e s e a r c h s t a t u s o f M a r k o v t h e o r y i n u n m a n n e d s y s t e m s ［ J ］ . C h i n e s e J o u r n a l o f S h i p R e s e a r c h ， 2 0 1 8 ， 1 3 （ 6 ） 9 - 1 8 . 0 引言随着人工智能技术的快速发展，智能系统已经渗透到日常生活的各个方面，并逐渐发挥着重要作用。智能体理论为智能系统的建模、设计和实现提供了统一的框架。智能体必须能够自主地综合各种传感器提供的感知信息，做出实时决策，并与环境进行交互。传感器收集到的信息是不全面的，并夹杂各种噪声，同时无人平台的输出效果也具有不可预知性，存在误差。这种不确定性为马尔科夫理论在无人系统中的研究现状严浙平，杨泽文，王璐，岳立冬，潘晓丽哈尔滨工程大学自动化学院，黑龙江哈尔滨 1 5 0 0 0 1 摘要随着人工智能技术的发展，无人系统面临的任务愈发复杂，通常要求系统在未知环境下自主完成给定任务。为了解决无人系统在未知及不确定性问题方面的规划与决策，可以利用马尔科夫理论进行建模与估计，解决在无人平台中任务决策与规划、目标跟踪与识别，以及平台系统间通信等复杂问题。分别介绍马尔科夫理论在无人机（ U A V ）、无人车（ U G V ）以及自主式水下机器人（ A U V ）中的研究进展以及应用现状，指出当前存在的问题，并展望未来的发展趋势和研究热点。关键词无人系统；马尔科夫理论；无人机；无人车；自主式水下机器人中图分类号 T P 1 8 文献标志码 A D O I 1 0 . 1 9 6 9 3 / j . i s s n . 1 6 7 3 - 3 1 8 5 . 0 1 1 9 9 R e s e a r c h s t a t u s o f M a r k o v t h e o r y i n u n m a n n e d s y s t e m s Y A N Z h e p i n g ， Y A N G Z e w e n ， W A N G L u ， Y U E L i d o n g ， P A N X i a o l i C o l l e g e o f A u t o m a t i o n ， H a r b i n E n g i n e e r i n g U n i v e r s i t y ， H a r b i n 1 5 0 0 0 1 ， C h i n a A b s t r a c t W i t h t h e d e v e l o p m e n t o f a r t i f i c i a l i n t e l l i g e n c e t e c h n o l o g y ， t h e m i s s i o n s t o b e p e r f o r m e d b y u n m a n n e d s y s t e m s a r e m o r e a n d m o r e c o m p l i c a t e d ， a n d t h e s y s t e m s a r e r e q u i r e d t o c o m p l e t e g i v e n m i s s i o n s i n d e p e n d e n t l y i n a n u n k n o w n e n v i r o n m e n t . I n o r d e r t o s o l v e t h e p l a n n i n g a n d d e c i s i o n - m a k i n g o f u n k n o w n a n d u n c e r t a i n p r o b l e m s i n u n m a n n e d s y s t e m s ， M a r k o v t h e o r y c a n b e u s e d f o r m o d e l i n g a n d e s t i m a t i o n t o s o l v e s u c h c o m p l i c a t e d i s s u e s a s m i s s i o n d e c i s i o n - m a k i n g a n d p l a n n i n g ， t a r g e t t r a c k i n g a n d i d e n t i f i c a t i o n ， a n d p l a t f o r m - t o - s y s t e m c o m m u n i c a t i o n i n u n m a n n e d p l a t f o r m s . T h i s p a p e r i n t r o d u c e s t h e r e s e a r c h p r o g r e s s a n d t h e p r a c t i c a l a p p l i c a t i o n o f M a r k o v t h e o r y i n U n m a n n e d A e r i a l V e h i c l e （ U A V ）， U n m a n n e d G r o u n d V e h i c l e （ U G V ） a n d A u t o n o m o u s U n d e r w a t e r V e h i c l e （ A U V ） r e s p e c t i v e l y ， p r e s e n t s t h e c u r r e n t p r o b l e m s a n d t h e p r o s p e c t s o f f u t u r e d e v e l o p m e n t a n d r e s e a r c h . K e y w o r d s u n m a n n e d s y s t e m ； M a r k o v t h e o r y ； U n m a n n e d A e r i a l V e h i c l e （ U A V ）； U n m a n n e d G r o u n d V e h i c l e （ U G V ）； A u t o n o m o u s U n d e r w a t e r V e h i c l e （ A U V ）第 1 3 卷第 6 期 2 0 1 8 年 1 2 月中国舰船研究 Chinese Journalof Ship Research V o l . 1 3 N o . 6 D e c . 2 0 1 8downloaded from www.ship- 中国舰船研究第 1 3 卷智能体的规划和感知任务带来了很大的挑战。基于马尔科夫过程的决策理论为这类问题提供了基本的理论框架。 1 8 7 0 年，俄国数学家马尔科夫建立了马尔科夫模型，又于 1 9 0 6 年发表了大数定律关于相依变量的扩展一文，为 1 9 0 7 年提出的马尔科夫过程奠定了理论基础，给出了研究离散事件动态系统状态空间的重要方法。由此，马尔科夫理论也成为随机过程中概率论的重要组成部分，被广泛应用于科学技术领域。随后，又形成了了马尔科夫链理论，经过进一步发展，建立了隐马尔科夫模型。由于马尔科夫链和隐马尔科夫模型具有良好的数学基础支撑，至今仍是各国学者研究的热点；其在语音语义识别［ 1 - 2 ］、机器学习［ 3 ］、无人系统［ 4 ］、经济学［ 5 ］、物理学、化学、生物学、气象学、通信等学科领域都产生了连锁性的反应，涌现出一系列新的课题、新的理论和新的学科。例如，在经济学方面，预测产品销售和利率的变化，分析和预测股市的走势等；在物理学方面，将泊松过程、弗瑞过程作为实际级联的近似，以及更新过程的应用等；在化学方面，对化学反应的动力学模型和生灭过程的描述等；在生物数学方面，可以构造生物现象模型，包括种群迁移模型、生灭型随机模型、性别变化模型等，且应用于传染病流行问题、生物遗传问题等方面；在通信、探测等领域，应用于传递信号与接收信号过程中的噪声消除；在空间科学和工业生产的自动化技术中，需要用到信息论和控制理论，且在研究带随机干扰的控制问题时也要应用马尔科夫随机过程［ 6 - 7 ］。无人系统领域的研究经常会用到马尔科夫理论，如自主决策和调度、任务规划、路径跟踪、感知与避碰、导航制导、计算机视觉等。以马尔科夫决策过程和部分可观察的马尔科夫决策过程为代表的马尔科夫决策理论，可以解决满足马尔科夫性质的不确定性环境下的感知、规划和学习问题，并能提供统一的理论框架和丰富的数学模型。在预测方面，可利用经验概率来创建初始概率分布和状态转移矩阵以构造马尔科夫模型，进而进行具体问题的预测研究。无人系统中，马尔科夫理论在不确定环境下的决策规划、目标识别以及预测算法等中起重要作用。本文拟针对马尔科夫理论在无人系统中的应用，分别从无人机（ U A V ）、无人车（ U G V ）以及自主式水下机器人（ A U V ）等无人平台的角度进行研究，归纳总结国内外无人系统中应用对象的发展现状。 1 马尔科夫理论在概率学中，随机过程是描述不确定系统的基础。在状态空间 S 中，设定随机过程 { } X t |t ÎT ，是关于时间的序列，其中 X ÎS T {0 1 2   n} ，马尔科夫的一般表达形式为［ 8 ］ P{X t n 1 |X t 0 X t 1   X t n } P{X t n 1 |X t n } （ 1 ）当时间和状态都是离散量时，马尔科夫过程（ M a r k o v p r o c e s s ）又被称为马尔科夫链（ M a r k o v c h a i n ），是具有无后效性的时间序列。所谓无后效性，是指序列的将来状态只与其当前所处状态有关，而与其过去状态无关。图 1 所示为马尔科夫链，假设当前系统处于 A 状态，那么在下一时刻，系统有 6 0 的概率转移到 B 状态，且有 4 0 的概率依旧处于 A 状态；同理，如果当前系统处于 B 状态，那么在下一时刻，系统有 8 0 的概率转移到 A 状态，有 2 0 的概率处于 B 状态。根据状态和时间的连续型和离散型分类，可以将马尔科夫过程分为如表 1 所示的 4 类。如果一个马尔科夫链的状态是部分可观察的，则称这个马尔科夫链为隐马尔科夫模型（ H i d d e n M a r k o v M o d e l ， H M M ）。 H M M 观察虽然跟系统状态直接相关，但观察一般具有不确定性，不足以推断系统的真实状态，即给定状态下只能按照一定的概率获得不同的观察。与马尔科夫链相比， H M M 是双重随机过程，即状态转移之间是个随机事件，状态和输出之间也是一个随机过程。为了更好地理解 H M M ，采用 2 个系统状态量和 3 个系统观察值举例说明，如图 2 所示。图中 X 1 ，X 2 为系统状态； Y 1 ， Y 2 ， Y 3 为系统观察值； a 为状态转移概率； b 为观察值概率。当引入智能体和智能图 1 马尔科夫链 F i g . 1 M a r k o v c h a i n B A 0 . 8 0 . 6 0 . 2 0 . 4 离散 n 1 ， 2 ，连续 t ≥ 0 离散型马尔科夫链可列马尔科夫过程连续型马尔科夫序列马尔科夫过程表 1 马尔科夫过程 T a b l e 1 M a r k o v p r o c e s s 1 0downloaded from www.ship- 第 6 期体行动时，一个受控的马尔科夫过程就转化为一个马尔科夫决策过程（ M a r k o v D e c i s i o n P r o c e s s ， M D P ）。状态转移概率不仅依赖于当前的状态，还依赖于作用于当前状态的动作，具有行动不确定性。类似地，一个受控的 H M M 构成一个部分可观察马尔科夫决策过程（ P a r t i c u l a r l y - O b s e r v a b l e M D P ， P O M D P ）。表 2 简明总结了以上 4 种马尔科夫模型。 2 U A V 随着 U A V 的飞速发展，其已被广泛应用于监视、巡逻、目标跟踪和紧急救援等自主任务。此外，在民用领域也出现了成熟的 U A V 产品。近年来， U A V 快递运输逐渐兴起，尤其在处理自然灾害、事故灾难以及社会安全事件等方面发挥了重要作用。图 3 和图 4 展示的分别为军用 U A V 和民用固定翼 U A V 。 2 . 1 决策规划在复杂环境中进行任务规划是 U A V 应用的重要组成部分之一。单 / 多 U A V 侦察监视问题的决策和规划，是人工智能与机器人领域的研究热点。如图 5 所示，针对具体问题，首先通过规划器规划得到智能体的行为策略，然后通过控制器执行智能体的行动并与环境进行交互。然而，在对问题进行建模时，传统规划方法往往假设任务及环境具有完全可观和静态的特征。马尔科夫决策理论为不确定性规划提供了具有理论支撑的形式化描述手段。而对于多智能体规划，可以将马尔科夫过程细分为多智能体部分可观察马尔科夫决策过程（ M u l t i - a g e n t P O M D P ， M P O M D P ）和分散式部分可观察的马尔科夫决策过程（ D e c e n t r a l i z e d P O M D P ）。在单 U A V 的应用研究方面，主要针对不确定环境或环境信息不完整的情况，完成了行动规划、导航规划和路径规划等。在进行 U A V 运动规划时，传感器产生的噪声、机器人的状态感知以及因不可预测的外力导致的机器人运动，都会引起运动状态的不确定性。 J i 等［ 9 ］提出了一种基于 P O M D P 的固定翼 U A V 在感知和运动不确定性条件下的规划框架，通过地图和噪声传感器进行导航，避开障碍物到达目标位置。但上述方法不能执行大规模的复杂任务。通过建立基于 M D P 的规划，学习重点自适应控制器之间的密切反馈，可以搭建一个适用于长期、复杂任务的感知规划框架［ 1 0 ］。在任务管理系统层面，可以采用基于分层任务网络的符号规划器的混合体系结构，与基于 M D P 的策略生成器协同工作，以减少数字路径规划器的搜索空间［ 1 1 ］。在 U A V 集群的应用研究方面， U A V 集群在执行决策时需要对单体进行任务分配，陈少飞［ 1 2 ］将部分可观察马尔科夫决策过程与一种近似最优的在图 2 隐马尔科夫模型 F i g . 2 H M M b 1 1 b 2 1 b 1 2 b 2 2 a 2 1 b 1 3 b 2 3 a 1 2 X 1 X 2 Y 2 Y 3 Y 1 系统自主系统受控状态完全可观马尔科夫链 M D P 状态部分可观 H M M P O M D P 表 2 马尔科夫模型 T a b l e 2 M a r k o v m o d e l 图 3 军用无人机 F i g . 3 M i l i t a r y U A V 图 4 固定翼无人机 F i g . 4 F i x e d - w i n g U A V 图 5 规划器求解实际问题过程 F i g . 5 P r o c e s s o f p l a n n e r f o r s o l v i n g t h e a c t u a l p r o b l e m 具体问题规划器控制器外界环境严浙平等马尔科夫理论在无人系统中的研究现状 1 1downloaded from www.ship- 中国舰船研究第 1 3 卷线规划算法相结合，以解决多智能体合理依次分配任务策略的问题。 U A V 在执行作战任务时不确定程度较高，需要解决动态任务问题，李月娟等［ 1 3 ］将动态任务分配模型等效为多智能体的马尔科夫决策过程，结合遗传算法确定最优任务分配策略，提高了任务分配的效率。针对多个 U A V 执行监视任务的流程， J e o n g 等［ 1 4 ］提出了一种减小决策空间而不损失问题关键特征的方法，可以将监视区域的不确定性维持在较低水平。 2 . 2 目标跟踪随着硬件研发条件的成熟， U A V 开始向智能自主化方向发展，其应具备的基本能力之一就是对地面多机动目标的自主检测和跟踪。由于目标的运动具有不确定性，可以利用马尔科夫模型对目标进行预测。利用 H M M 可以对目标区域内多地面目标的全局态势进行估计，利用 B a u m - W e l c h 算法训练隐马尔科夫模型参数，得到相应的预测模型，并预测多目标的全局态势，进而提供 U A V 搜寻和跟踪目标的决策依据［ 1 5 ］。在考虑 U A V 跟踪移动目标的最佳路径时，局限性之一是当目标移动速度比 U A V 的最小速度慢得多时缺乏悬停能力，这就要求 U A V 保持着围绕目标的轨道。 B a e k 等［ 1 6 ］提出了一种寻找 U A V 的最优策略，使移动目标的位置不确定性最小化，但此方法仅针对单一目标。 R a g i 等［ 1 7 ］提出了一种 U A V 跟踪多个地面目标的路径规划算法。 V a n e g a s 等［ 1 8 - 2 0 ］利用部分可观察马尔科夫决策过程解决 U A V 导航和目标发现问题，每次迭代后重新规划路径，以减少在有障碍环境中运动的不确定性和 G P S 信号干扰等。由于单 U A V 视野的局限性，难以胜任对大范围移动目标的搜索，而 U A V 集群协同搜索目标则可明显提高拦截概率［ 2 1 ］，搜索用时也较短，因此 U A V 集群协同任务逐渐成为该领域的研究重点。 2 . 3 其他应用 U A V 感知与避碰、动态巡逻以及作战、 U A V 攻击决策等，都需要将马尔科夫过程作为模型基础来设计算法。基于马尔科夫决策过程可以完成 U A V 避碰决策机制及避碰策略［ 2 2 ］，确保 U A V 自主避碰多个入侵者［ 2 3 ］。 K r i s h n a m o o r t h y 等［ 2 4 ］开发了一种降阶的动态规划方法，有效计算了一类受控马尔科夫链的最优策略和价值函数，较好地解决了 U A V 集群巡视随机最优控制问题。由于数据传输存在延迟，因此不能及时对当前作战情况做出准确决策，而采用状态外推算法和马尔科夫加速模型则可对 U A V 与机动目标状态进行预测，弥补因数据滞后所引起的战场形势预测不准确问题［ 2 5 ］。 3 U G V U G V 主要通过智能驾驶仪来实现无人驾驶。其一般利用车载传感器来感知车辆周围环境，然后根据感知获取的道路、车辆位置和障碍物信息控制车辆的方向和速度，从而保证车辆安全行驶。图 6 所示为谷歌公司于 2 0 1 7 年研发的 “ 萤火虫 ” U G V 。马尔科夫理论在 U G V 研究领域的的应用十分广泛。 U G V 在完成路况识别、网络通信、道路检测和跟踪以及车辆避碰等各项任务时，都需要利用马尔科夫模型进行辅助设计。 3 . 1 路况识别无人车需要识别和解读路面车辆情况、交通标志以及信号。在车辆随机换道意图识别的模型估计、交通标志牌的图像分析和交通信号识别的模型研究中，可以结合马尔科夫模型进行研究。根据美国国家公路交通安全管理局（ N H T S A ）的定义，可以将无人驾驶分为 5 个级别（ 0 4 级）［ 2 6 ］。 0 级无自动化，没有任何自动驾驶功能、技术，司机对汽车的所有功能拥有绝对控制权； 1 级驾驶支援，向司机提供基本的技术性帮助； 2 级部分自动化，实现数种功能的自动控制； 3 级有条件自动化，在有限情况下实现自动控制； 4 级完全自动化（无人驾驶）。目前的 U G V 多集中在第 3 级，并不能完全实现真正的自动驾驶。第 3 级无人驾驶多应用在高速公路中。在高速公路中，最基础的 2 类驾驶模式是车辆换道和车辆保持。在车辆换道识别时，利用支持向量机和高斯混合 H M M ，可以建立高速公路中汽车换道意图的识别模型［ 2 7 ］。车道保持要求自主驾驶的汽车不能偏离原图 6 “ 萤火虫 ” 无人车 F i g . 6 “ F i r e f l y ” U G V 1 2downloaded from www.ship- 第 6 期有的车道，对其他车辆车道偏离行为进行预测并向驾驶员发出警报。高振海等［ 2 8 ］基于高斯混合马尔科夫模型，提出了一人一车特性的无意识车道偏离的识别模型，提高了识别的效率与准确性。除了对车道保持和车辆换道的识别， U G V 在行驶过程中对交通标志牌、交通信号灯状态的识别也具有重要的现实意义。密集深度图像恢复技术在 U G V 领域的应用受到越来越多的关注。 Z e n g 等［ 2 9 ］提出利用双边滤波框架生成密集深度图像，然后采用马尔科夫随机场对其进行细化，在复杂场景下，可以获得密集的深度图像，简化了图像分割以及目标跟踪、分类和识别。利用 H M M 算法可以进行交通信号灯状态的信息预测，有利于设计和实现交通信号灯识别与交通标志识别系统［ 3 0 ］。 U G V 高效地识别信号可以保障其信号灯通过性，更好地完成自动驾驶任务。 3 . 2 网络通信 U G V 完成安全自主驾驶和复杂任务的重要基础是畅通的网络通信，但实际的通信环境不一定满足要求，因此在网络延时、间断连接、数据包丢失等恶劣环境下的通信研究尤为重要。为了应对网络延时，并避免数据包无序的情况， C u e n c a 等［ 3 1 ］考虑了马尔科夫链驱动的网络控制系统场景，设计了保证网络控制系统稳定性的控制策略。与在无线通信网络中使用资源预留协议相比，集成马尔科夫链和资源预留协议算法可以保证更高的带宽和更好的服务质量［ 3 2 ］。而针对通信中断这一情况，可以将高斯马尔科夫状态空间模型用于节点动力学，结合扩展卡尔曼滤波器，在网络连接间歇性中断的条件下完成实时路径规划［

展开阅读全文

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

最新标签