【视频专栏】基于距离信息的追逃策略:信念状态连续随机博弈

文摘   科技   2023-12-22 17:46   北京  

点击上方蓝字关注我们


陈灵敏, 冯宇, 李永强. 基于距离信息的追逃策略: 信念状态连续随机博弈. 自动化学报, DOI: 10.16383/j.aas.c230018 

1

摘要

       追逃问题的研究在对抗、追踪以及搜查等领域极具现实意义. 借助连续随机博弈与马尔科夫决策过程, 研究使用测量距离求解多对一追逃问题的最优策略. 在此追逃问题中, 追捕群体仅领导者可测量与逃逸者间的相对距离, 而逃逸者具有全局视野. 追逃策略求解被分为追博弈与马尔科夫决策(Markov decision process, MDP)两个过程. 在求解追捕策略时, 通过分割环境引入信念区域状态以估计逃逸者位置, 同时使用测量距离对信念区域状态进行修正, 构建起基于信念区域状态的连续随机追博弈, 并借助不动点定理证明了博弈平稳纳什均衡策略的存在性. 在求解逃逸策略时, 逃逸者根据全局信息建立混合状态下的马尔科夫决策过程及相应的最优贝尔曼方程. 同时给出了基于强化学习的平稳追逃策略求解算法, 并通过案例验证了该算法的有效性.


2

引言

      近年来, 追逃问题在飞行器, 移动机器人等领域一直广受关注, 如无人机围捕搜查[1], 机器人协同对抗[2], 搜索救援[3]等. 在典型追逃问题中追捕方试图快速捕获或逼近逃逸方, 而逃逸方则试图远离追捕方以避免被捕获. 自上世纪六十年代提出一对一追逃问题以来[4], 学术界对其进行了充分探索[5-8], 并逐步演变为当下的多对一[9-11]、多对多[12-14]对抗问题的研究.


追逃问题可视为智能体间的对抗与合作问题, 因此博弈论[15-17]被广泛用于此类问题的求解[18-20]. 文献[21]在追逃双方具有无限视野下建立了线性二次型微分博弈模型, 将多追捕者与多逃逸者问题转化为多组两人零和微分博弈. 文献[22]基于非零和博弈框架, 研究了针对三种不同类型追捕者的追逃问题, 并分析了可捕获性、纳什均衡以及捕获时间. 文献[23]在确保每个时刻都至少有一个追捕者具有全局视野的情况下, 提出了基于微分模型的追捕策略. 不同于无限视野的结果, 文献[24]在有限视野下设计了追捕群体快速逼近逃逸者的分布式算法, 并根据初始分布及速度比推导了捕获条件. 文献[25]采用图论方式研究了有限感知的追捕问题, 为每个智能体求解了分布式最优策略.

上述研究均基于模型求解追逃策略, 然而现实中由于不确定因素的存在, 构建准确的模型极为困难, 而强化学习可通过无模型的方式寻求最优策略, 因此其与追逃问题的结合也成为当下研究热点[6-7, 26]. 针对某一方使用固定策略的追捕问题, 文献[8]利用视野图像引入逃逸者位置的信念状态, 并基于Soft actor-critic算法获取最优追捕策略. 文献[27]基于深度Q网络, 并借助人工势场法对奖励函数进行改造以获取逃逸策略. 而对于追逃双方通过对抗学习进行智能追捕的问题, 文献[28]在无限视野下, 提出了Q(λ)-learning算法以求解追逃策略. 文献[29]则在有限视野下基于深度确定性策略梯度, 提出了两种网络拓扑结构来快速求解策略, 降低了多智能体算法的复杂度. 文献[30]对深度确定性策略梯度公式进行向量化拓展, 提出了一种多智能体协同目标预测网络, 保证了追捕群体对目标轨迹预测的有效性.

上述绝大多数追逃问题求解均基于定位信息, 但在特定环境下此类信息无法获取. 如水下航行器在固定海域中执行巡航与入侵驱逐任务时, 由于无线电信号在海水中迅速衰减, 此时航行器无法借助无线电导航系统对入侵者实现水下远距离、大范围的定位[31-32], 在此情况下, 借助轻便且低频的测距传感器实现追捕的研究是极为重要的. 文献[33]研究了单个追捕者基于距离构造几何图形以估计逃逸者的追逃问题, 并提出了在三维环境下使用两个追捕者估计逃逸者位置的方法. 在固定信标的帮助下, 文献[34]基于三角定位进行逃逸者位置估计, 并提出了对测量距离进行去噪处理的方法以获得精准定位. 文献[35]借助凸优化方法, 提出一种基于测量距离的梯度算法实现对逃逸者的定位. 文献[36]针对固定规则下的单移动机器人目标跟踪问题, 提出了一种利用测量距离与距离变化率求解追捕策略的方法. 此外, 文献[37]基于距离变化率提出了自适应切换算法, 证明了该算法稳定性与收敛性, 并在距离变化率不可用时将其扩展为使用观测器补偿的算法, 通过移动机器人围捕实验验证了其有效性.


综上所述, 基于距离的追逃问题已有较多研究成果, 但部分结果仍基于模型求解[32, 35-37], 或只针对固定策略的逃逸者[36], 亦或是需要借助额外设备如信标等[34]. 因此在无模型情况下针对智能逃逸者, 仅利用距离信息来实现追捕的问题仍有待于进一步探索. 本文将基于距离信息的N对1围捕问题与随机博弈相结合, 研究最优追逃策略. 在此问题中, 追捕群体仅领导者可测量与逃逸者间的相对距离, 其他跟随者通过领导者的共享获取此信息, 而逃逸者则拥有无限视野. 为求解追捕策略, 将环境分割引入信念区域状态以估计逃逸者位置. 同时根据相对距离, 对信念区域状态进行修正. 领导者借助信念引入想象逃逸者, 建立了信念区域状态下的连续随机追博弈, 并使用不动点定理证明此博弈平稳纳什均衡策略的存在性. 为求解逃逸策略, 由于逃逸者具有全局信息优势, 在追捕群体最优策略的基础上, 建立基于混合状态的MDP与相应最优的贝尔曼方程. 最后给出了基于强化学习的追逃策略求解算法.


本文结构安排如下: 第1节对追逃问题作出具体描述; 第2节证明基于信念区域状态的追博弈存在平稳纳什均衡策略, 并构建逃逸者的混合状态MDP与最优贝尔曼方程; 第3节给出求解追逃问题平稳策略的算法; 第4节通过数值仿真与对比, 验证本文方法的有效性; 第5节是全文总结.


符号说明. Rm表示m维欧几里得空间; ei表示第i个元素为1, 其余为0的列向量; ‖⋅‖表示欧几里得范数; Δ(A)表示在集合A上概率测度的集合.


3

正文框架

1. 问题描述

2. 非完全信息追逃问题

  2.1 信念区域状态和重心距离

  2.2 基于信念区域状态的追博弈

  2.3 逃逸者的决策过程

3. 策略求解

4. 数值仿真

5. 结论


部分文献


[1] 杜永浩, 邢立宁, 蔡昭权. 无人飞行器集群智能调度技术综述. 自动化学报, 2020, 46(2): 222-241

Du Yong-Hao, Xing Li-Ning, Cai Zhao-Quan. Survey on intelligent scheduling technologies for unmanned flying craft clusters. Acta Automatica Sinica, 2020, 46(2): 222-241


[2] 寇立伟, 项基. 基于输出反馈线性化的多移动机器人目标包围控制. 自动化学报, 2022, 48(5): 1285-1291

Kou Li-Wei, Xiang Ji. Target fencing control of multiple mobile robots using output feedback linearization. Acta Automatica Sinica, 2022, 48(5): 1285-1291


[3] Ferrari S, Fierro R, Perteet B, Cai C H, Baumgartner K. A geometric optimization approach to detecting and intercepting dynamic targets using a mobile sensor network. SIAM Journal on Control and Optimization, 2009, 48(1): 292-320 doi: 10.1137/07067934X


[4] Isaacs R. Differential Games. New York: Wiley, 1965.


[5] Osborne M J, Rubinstein A. A Course in Game Theory. Cambridge: MIT Press, 1994.


[6] 施伟, 冯旸赫, 程光权, 黄红蓝, 黄金才, 刘忠, 等. 基于深度强化学习的多机协同空战方法研究. 自动化学报, 2021, 47(7): 1610-1623.

Shi Wei, Feng Yang-He, Cheng Guang-Quan, Huang Hong-Lan, Huang Jin-Cai, Liu Zhong, et al. Research on multi-aircraft cooperative air combat method based on deep reinforcement learning. Acta Automatica Sinica, 2021, 47(7): 1610-1623


[7] 耿远卓, 袁利, 黄煌, 汤亮. 基于终端诱导强化学习的航天器轨道追逃博弈. 自动化学报, DOI: 10.16383/j.aas.c220204

Geng Yuan-Zhuo, Yuan Li, Huang Huang, Tang Liang. Terminal-guidance based reinforcement-learning for orbital pursuit-evasion game of the spacecraft. Acta Automatica Sinica, DOI: 10.16383/j.aas.c220204


[8] Engin S, Jiang Q Y, Isler V. Learning to play pursuit-evasion with visibility constraints. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Prague, Czech Republic: IEEE, 2021. 3858−3863


[9] Al-Talabi A A. Multi-player pursuit-evasion differential game with equal speed. In: Proceedings of the IEEE International Automatic Control Conference (CACS). Pingtung, Taiwan, China: IEEE, 2017.1−6.


[10] Selvakumar J, Bakolas E. Feedback strategies for a reach-avoid game with a single evader and multiple pursuers. IEEE Transactions on Cybernetics, 2021, 51(2): 696-707 doi: 10.1109/TCYB.2019.2914869


[11] de Souza C, Newbury R, Cosgun A, Castillo P, Vidolov B, Kulić D. Decentralized multi-agent pursuit using deep reinforcement learning. IEEE Robotics and Automation Letters 2021, 6(3): 4552-4559 doi: 10.1109/LRA.2021.3068952


[12] Zhou Z J, Xu H. Decentralized optimal large scale multi-player pursuit-evasion strategies: A mean field game approach with reinforcement learning. Neurocomputing, 2022, 484: 46-58 doi: 10.1016/j.neucom.2021.01.141


[13] Garcia E, Casbeer D W, Von Moll A, Pachter M. Multiple pursuer multiple evader differential games. IEEE Transactions on Automatic Control, 2021, 66(5): 2345-2350 doi: 10.1109/TAC.2020.3003840


[14] Pierson A, Wang Z J, Schwager M. Intercepting rogue robots: An algorithm for capturing multiple evaders with multiple pursuers. IEEE Robotics and Automation Letters, 2017, 2(2): 530-537 doi: 10.1109/LRA.2016.2645516


[15] Gibbons R. A Primer in Game Theory. Harlow: Prentice Education Limited, 1992.


[16] Parthasarathy T. Discounted, positive, and noncooperative stochastic games. International Journal of Game Theory 1973, 2(1): 25-37 doi: 10.1007/BF01737555


[17] Maitra A, Parthasarathy T. On stochastic games. Journal of Optimization Theory and Applications, 1970, 5(4): 289-300 doi: 10.1007/BF00927915


[18] Liu S Y, Zhou Z Y, Tomlin C, Hedrick K. Evasion as a team against a faster pursuer. In: Proceedings of the American Control Conference. Washington, USA: IEEE, 2013. 5368−5373


[19] Huang L N, Zhu Q Y. A dynamic game framework for rational and persistent robot deception with an application to deceptive pursuit-evasion. IEEE Transactions on Automation Science and Engineering, 2022, 19(4): 2918-2932 doi: 10.1109/TASE.2021.3097286


[20] Qi D D, Li L Y, Xu H L, Tian In: Proceedings of the 40th Chinese Control Conference (CCC). Shanghai, China: IEEE, 2021. 1526−1531


[21] 刘坤, 郑晓帅, 林业茗, 韩乐, 夏元清. 基于微分博弈的追逃问题最优策略设计. 自动化学报, 2021, 47(8): 1840-1854.

Liu Kun, Zheng Xiao-Shuai, Lin Ye-Ming, Han Le, Xia Yuan-Qing. Design of optimal strategies for the pursuit-evasion problem based on differential game. Acta Automatica Sinica, 2021, 47(8): 1840-1854


[22] Xu Y H, Yang H, Jiang B, Polycarpou M M. Multiplayer pursuit-evasion differential games with malicious pursuers. IEEE Transactions on Automatic Control, 2022, 67(9): 4939-4946 doi: 10.1109/TAC.2022.3168430


[23] Lin W, Qu Z H, Simaan M A. Nash strategies for pursuit-evasion differential games involving limited observations. IEEE Transactions on Aerospace and Electronic Systems 2015, 51(2): 1347-1356 doi: 10.1109/TAES.2014.130569


[24] Fang X, Wang C, Xie L H, Chen J. Cooperative pursuit with multi-pursuer and one faster free-moving evader. IEEE Transactions on Cybernetics, 2022, 52(3): 1405-1414 (本条文献与第9条文献重复, 请确认) doi: 10.1109/TCYB.2019.2958548


[25] Lopez V G, Lewis F L, Wan Y, Sanchez E N, Fan L L. Solutions for multiagent pursuit-evasion games on communication graphs: Finite-time capture and asymptotic behaviors. IEEE Transactions on Automatic Control, 2020, 65(5): 1911-1923 doi: 10.1109/TAC.2019.2926554


[26] 郑延斌, 樊文鑫, 韩梦云, 陶雪丽. 基于博弈论及Q学习的多Agent协作追捕算法. 计算机应用, 2020, 40(6): 1613-1620.

Zheng Yan-Bin, Fan Wen-Xin, Han Meng-Yun, Tao Xue-Li. Multi-agent collaborative pursuit algorithm based on game theory and Q-learning. Journal of Computer Applications, 2020, 40(6): 1613-1620


[27] Zhu J G, Zou W, Zhu Z. Learning evasion strategy in pursuit-evasion by deep Q-network. In: Proceeding of the 24th International Conference on Pattern Recognition (ICPR). Beijing, China: IEEE, 2018. 67−72


[28] Bilgin A T, Kadioglu-Urtis E. An approach to multi-agent pursuit evasion games using reinforcement learning. In: Proceedings of the International Conference on Advanced Robotics (ICAR). Istanbul, Turkey: IEEE, 2015. 164−169


[29] Wang Y D, Dong L, Sun C Y. Cooperative control for multi-player pursuit-evasion games with reinforcement learning. Neurocomputing, 2020, 412: 101-114 doi: 10.1016/j.neucom.2020.06.031


[30] Zhang R L, Zong Q, Zhang X Y, Dou L Q, Tian B L. Game of drones: Multi-UAV pursuit-evasion game with online motion planning by deep reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, DOI: 10.1109/TNNLS.2022.3146976


[31] Coleman D, Bopardikar S D, Tan X B. Observability-aware target tracking with range only measurement. In: Proceedings of the American Control Conference (ACC). New Orleans, USA: IEEE, 2021. 4217−4224


[32] Chen W, Sun R S. Range-only SLAM for underwater navigation system with uncertain beacons. In: Proceedings of the 10th International Conference on Modelling, Identification and Control (ICMIC). Guiyang, China: IEEE, 2018. 1−5


[33] Bopardikar S D, Bullo F, Hespanha J P. A pursuit game with range-only measurements. In: Proceedings of the 47th IEEE Conference on Decision and Control. Cancun, Mexico: IEEE, 2008. 4233−4238


[34] Lima R, Ghose D. Target localization and pursuit by sensor-equipped UAVs using distance information. In: Proceedings of the International Conference on Unmanned Aircraft Systems (ICUAS). Miami, USA: IEEE, 2017. 383−392


[35] Fidan B, Kiraz F. On convexification of range measurement based sensor and source localization problems. Ad Hoc Networks, 2014, 20: 113-118 doi: 10.1016/j.adhoc.2014.04.003


[36] Chaudhary G, Sinha A. Capturing a target with range only measurement. In: Proceedings of the European Control Conference (ECC). Zurich, Switzerland: IEEE, 2013. 4400−4405


[37] Güler S, Fidan B. Target capture and station keeping of fixed speed vehicles without self-location information. European Journal of Control, 2018, 43: 1-11 doi: 10.1016/j.ejcon.2018.06.003


作者简介



陈灵敏,浙江工业大学信息工程学院硕士研究生. 2020年获得绍兴文理学院学士学位. 主要研究方向为博弈论与机器学习在决策问题中的应用.

冯宇,浙江工业大学信息工程学院教授. 2011 年获得法国南特矿业大学博士学位. 主要研究方向为网络化控制系统、分布式滤波、不确定系统的鲁棒分析与控制, 以及博弈论与机器学习在决策问题中的应用. 本文通信作者.

李永强,浙江工业大学信息工程学院副教授. 2014 年获得北京交通大学博士学位. 主要研究方向为强化学习, 非线性控制以及深度学习.

【视频专栏】城市固废焚烧过程智能优化控制研究现状与展望

【视频专栏】深度对比学习综述

【视频专栏】视网膜功能启发的边缘检测层级模型

【视频专栏】一种新的分段式细粒度正则化的鲁棒跟踪算法

【视频专栏】基于自适应多尺度超螺旋算法的无人机集群姿态同步控制

【视频专栏】基于分层控制策略的六轮滑移机器人横向稳定性控制

【视频专栏】基于改进YOLOX的移动机器人目标跟随方法

自动化学报创刊60周年专刊| 孙长银教授等:基于因果建模的强化学习控制: 现状及展望

【视频专栏】基于多尺度变形卷积的特征金字塔光流计算方法

自动化学报创刊60周年专刊| 柴天佑教授等:端边云协同的PID整定智能系统

【视频专栏】一种同伴知识互增强下的序列推荐方法

自动化学报创刊60周年专刊| 桂卫华教授等:复杂生产流程协同优化与智能控制

【视频专栏】 基于跨模态实体信息融合的神经机器翻译方法

自动化学报创刊60周年专刊| 王耀南教授等:机器人感知与控制关键技术及其智能制造应用

【视频专栏】机器人运动轨迹的模仿学习综述

自动化学报创刊60周年专刊| 于海斌研究员等:无线化工业控制系统: 架构、关键技术及应用

自动化学报创刊60周年专刊| 王飞跃教授等:平行智能与CPSS: 三十年发展的回顾与展望

自动化学报创刊60周年专刊| 陈杰教授等:非线性系统的安全分析与控制: 障碍函数方法

自动化学报创刊60周年专刊| 乔俊飞教授等:城市固废焚烧过程数据驱动建模与自组织控制

自动化学报创刊60周年专刊| 姜斌教授等:航天器位姿运动一体化直接自适应容错控制研究

自动化学报创刊60周年专刊| 王龙教授等:多智能体博弈、学习与控制

》自动化学报创刊60周年专刊| 刘成林研究员等:类别增量学习研究进展和性能评价

《自动化学报》创刊60周年专刊|杨孟飞研究员等:空间控制技术发展与展望

城市固废焚烧过程数据驱动建模与自组织控制

面向全量测点耦合结构分析与估计的工业过程监测方法

《自动化学报》多篇论文入选高影响力论文

》复杂网络能控性鲁棒性研究进展

》解耦表征学习综述

》考虑输出约束的冗余驱动绳索并联机器人预设性能控制 

》面向网络空间防御的对抗机器学习研究综述

【虚拟专题】机器人

》基于事件相机的机器人感知与控制综述

》《自动化学报》广受关注论文合集

2022年第01-07期综述

》【热点专题】多目标优化

》【热点专题】目标检测

》异构集群系统分布式自适应输出时变编队跟踪控制

》深海起重机系统的实时轨迹规划方法

》数据和知识驱动的城市污水处理过程多目标优化控制

》基于池的无监督线性回归主动学习

》基于非线性干扰观测器的飞机全电刹车系统滑模控制设计

综合集成研讨厅体系

传感器饱和的非线性网络化系统模糊H∞滤波

基于区块链的数字货币发展现状与展望
比特驱动的瓦特变革—信息能源系统研究综述

》《自动化学报》兼职编辑招聘启事

》《自动化学报》创刊六十周年学术研讨会第六期

》《自动化学报》创刊六十周年学术研讨会第五期

》自动化学报蝉联百种中国杰出期刊称号

》《自动化学报》20篇文章入选2023“领跑者5000”顶尖论文

》《自动化学报》创刊六十周年学术研讨会第三期

》《自动化学报》创刊六十周年学术研讨会第二期

》《自动化学报》创刊六十周年学术研讨会第一期

》《自动化学报》致谢审稿人(2022年度)

》《自动化学报》13篇文章入选2022“领跑者5000”顶尖论文

》自动化学报连续11年入选国际影响力TOP期刊榜单

》《自动化学报》影响因子6.627,影响因子和影响力指数排名第1

》JAS最新影响因子7.847,排名全球前10%

《自动化学报》17篇文章入选2021“领跑者5000”顶尖论文

》自动化学报多名作者入选爱思唯尔2021中国高被引学者

》自动化学报(英文版)和自动化学报入选计算领域高质量科技期刊T1类

》自动化学报多篇论文入选中国百篇最具影响国内论文和中国精品期刊顶尖论文

》JAS进入中科院分区工程技术和计算机科学类1区、Top期刊

》自动化学报蝉联百种中国杰出期刊称号,入选中国精品科技期刊
》《自动化学报》挺进世界期刊影响力指数Q1区
》《自动化学报》多名作者入选科睿唯安2020年度高被引科学家
》自动化学报排名第一,被评定为中国中文权威期刊
》2023年第11期
》2023年第10期
》2023年第09期
》2023年第08期
》2023年第07期
》2023年第06期
》2023年第05期
》2023年第04期
》《自动化学报》创刊60周年专刊
2023年第01期
2022年第10期
》2022年第09期
2022年第08期
》2022年第07期
2022年第01-06期
2021年第11期
2021年第10期

》2021年第09期

》2021年第08期
》2021年第07期
》2021年第06期
》2021年第05期
》2021年第04期
》2021年第03期
》2021年第02期
》2021年第01期



长按二维码|关注我们

IEEE/CAA Journal of Automatica Sinica (JAS)

长按二维码|关注我们

《自动化学报》服务号

联系我们

网站: 

http://www.aas.net.cn

https://www.ieee-jas.net

投稿: 

https://mc03.manuscriptcentral.com/aas-cn 

https://mc03.manuscriptcentral.com/ieee-jas 

电话:  010-82544653(日常咨询和稿件处理) 

           010-82544677(录用后稿件处理)

邮箱:  aas@ia.ac.cn(日常咨询和稿件处理)

           aas_editor@ia.ac.cn(录用后稿件处理)

博客: 

http://blog.sina.com.cn/aasedit

点击阅读原文 了解更多

自动化学报
《自动化学报》是由中国自动化学会、中国科学院自动化研究所共同主办的高级学术期刊。该公众服务号旨在发布学报网刊、期刊动态,为读者提供在线网刊、为作者提供在线查稿、为审者提供在线送审的服务。
 最新文章