Computing worst-case robust strategies in pursuit-evasion games (PEGs) is time-consuming, especially when real-world factors like partial observability are considered. While important for general security purposes, real-time applicable pursuit strategies for graph-based PEGs are currently missing when the pursuers only have imperfect information about the evader's position. Although state-of-the-art reinforcement learning (RL) methods like Equilibrium Policy Generalization (EPG) and Grasper provide guidelines for learning graph neural network (GNN) policies robust to different game dynamics, they are restricted to the scenario of perfect information and do not take into account the possible case where the evader can predict the pursuers' actions. This paper introduces the first approach to worst-case robust real-time pursuit strategies (R2PS) under partial observability. We first prove that a traditional dynamic programming (DP) algorithm for solving Markov PEGs maintains optimality under the asynchronous moves by the evader. Then, we propose a belief preservation mechanism about the evader's possible positions, extending the DP pursuit strategies to a partially observable setting. Finally, we embed the belief preservation into the state-of-the-art EPG framework to finish our R2PS learning scheme, which leads to a real-time pursuer policy through cross-graph reinforcement learning against the asynchronous-move DP evasion strategies. After reinforcement learning, our policy achieves robust zero-shot generalization to unseen real-world graph structures and consistently outperforms the policy directly trained on the test graphs by the existing game RL approach.

翻译：在追逃博弈中计算最坏情况鲁棒策略通常耗时较长，尤其在考虑现实世界因素如部分可观测性时更为明显。尽管对通用安全目的至关重要，但当前基于图的追逃博弈中，当追捕方仅掌握逃逸者位置的不完全信息时，仍缺乏可实时应用的追捕策略。虽然最先进的强化学习方法（如均衡策略泛化与Grasper）为学习对多种博弈动态具有鲁棒性的图神经网络策略提供了指导，但这些方法仅限于完全信息场景，且未考虑逃逸者可能预测追捕方行动的情况。本文首次提出部分可观测性下最坏情况鲁棒实时追捕策略的方法。我们首先证明传统动态规划算法在逃逸者异步移动条件下仍能保持求解马尔可夫追逃博弈的最优性。随后，提出关于逃逸者可能位置的信念保持机制，将动态规划追捕策略扩展至部分可观测场景。最后，将信念保持机制嵌入最先进的均衡策略泛化框架，构建完整的R2PS学习方案，通过跨图强化学习对抗异步移动动态规划逃逸策略，实现实时追捕策略。经强化学习训练后，我们的策略在未见过的现实世界图结构上实现鲁棒的零样本泛化能力，其性能持续优于现有博弈强化学习方法直接在测试图上训练得到的策略。