引用本文

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

Chen Ling-Min, Feng Yu, Li Yong-Qiang. Distance information based pursuit-evasion strategy: Continuous stochastic game with belief state. Acta Automatica Sinica, 2024, 50(4): 828−840 doi: 10.16383/j.aas.c230018

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c230018

关键词

追逃问题，信念区域状态，连续随机博弈，马尔科夫决策过程，强化学习 

摘要

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

文章导读

近年来, 追逃问题在飞行器、移动机器人等领域一直广受关注, 如无人机围捕搜查[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节是全文总结.

图 1  追逃问题环境

图 2  (a) L个区域; (b) 追捕群体的划分

图 3  警戒区域

本文针对仅有距离信息的多智能体追逃问题, 提出了一种基于连续随机博弈与马尔科夫决策过程的最优策略求解方法. 在求解追捕策略中, 为了弥补位置信息的缺失, 通过引入信念区域状态对逃逸者位置进行估计, 并且使用测量距离对信念区域状态进行修正. 由此搭建了基于信念区域状态的连续随机博弈, 并证明了此博弈平稳纳什均衡策略的存在性. 在求解逃逸者策略时, 根据追捕群体的最优策略与混合状态, 建立了最优贝尔曼方程, 并给出了基于强化学习的追逃策略求解算法. 通过与已有算法的对比, 验证了本文方法的有效性. 此外, 通过追逃群体间简单的任务分配, 可将本文算法直接应用于多对多的追捕问题. 但如何在围捕过程中构建有效的智能体交互与任务切换机制, 以实现多对多环境下的高效追捕还有待于进一步研究.

作者简介

陈灵敏

浙江工业大学信息工程学院硕士研究生. 2020年获得绍兴文理学院学士学位. 主要研究方向为博弈论与机器学习在决策问题中的应用. E-mail: 2112003096@zjut.edu.cn

冯宇

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

李永强

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