攻防对抗问题是军事和安全领域一个长期而关键的问题。现实当中很多包含对抗和竞争的问题可以用攻防对抗进行建模。攻防对抗博弈模型以及相关的计算方法作为攻防对抗问题的核心被广泛的应用于各个领域,包括反恐,关键基建设施保护,机场安全巡逻,计算机网络防护和环保领域反偷猎等。现实中,很多攻防对抗问题发生在网络结构领域上,攻守双方的行为依托于网络结构,相互之间的竞争对抗交互也发生在网络之上。此类场景中存在着许多有待解决的关键问题和挑战,包括目标阈值对博弈模型的影响,攻防博弈中的不确定性和概率性等。尽管目标结构下的攻防对抗博弈问题研究已经考虑了其中一部分问题,但是受制于网络结构对agent之间的交互的影响,网络上的攻防对抗行为要复杂的多,传统方法难以直接处理网络结构问题。本文立足于网络结构领域,采用斯坦伯格领导者–追随者博弈模型对攻击者和防守者之间的对抗交互进行建模仿真,为防守者提供有效的资源分配策略防范各种潜在的攻击者威胁。在对攻防对抗博弈的建模过程中,重点考虑资源的有限性约束和问题中的不确定性因素。文章的主要创新点和贡献概括为以下五个方面:(1)提出了一种网络攻防对抗博弈的建模框架。本文首先从网络流的角度阐述网络攻防对抗博弈的定义,基于斯坦伯格博弈,给出网络攻防对抗博弈问题的基本建模框架,包括边和路径两种表示形式;根据博弈论中的极大极小定理,说明网络攻防对抗博弈中强斯坦伯格均衡的存在性和普遍性,将其作为博弈框架的核心解概念用以求解大规模博弈问题。(2)提出了一种新的阈值最短路网络阻断博弈的模型和求解算法。针对防守者防御资源的稀缺性,论文引入阈值约束作为阻断性能和资源消耗之间的权衡,并利用斯坦伯格领导者–追随者博弈模型定义了一种新的最短路网络阻断模型。然后分别基于本德斯分解和拉格朗日对偶给出两种基本的求解算法;在两种基本算法的基础之上,进一步考虑完全阻断和大阈值支配两种特定情形,分别给出了对应的集合覆盖算法和拉格朗日松弛算法。(3)提出了一种随机阈值最短路网络阻断博弈的模型和求解算法。攻防对抗交互的天然对抗性导致领域中存在大量的不确定性,例如采取特定行动时的最终结果成功与否。基于阈值约束下的最短路网络阻断模型,论文进一步考虑阻断的成功概率,将确定型阻断模型扩展到随机阻断模型。基于本德斯分解方法,论文提出了一种基于主从问题迭代的分解算法框架。为了提高分解算法的可扩展性和鲁棒性,论文进一步设计了一种基于对偶子图的主问题加速算法和一种基于局部搜索的更优应对子问题加速算法。增强的分解算法为求解现实规模的攻防对抗博弈问题提供了可行的求解方法。(4)研究了概率网络逃避阻断的博弈模型和求解算法。上述研究所给出的策略是确定型的保守策略,在最大化可靠路径的研究基础之上,本文提出了一种新的网络逃避阻断问题模型,充分考虑攻防双方之间对抗带来的不确定性,为防守者提供概率化的混合防守策略。根据极大极小原理,设计了基于Double Oracle的求解框架;分别从集合覆盖问题约减和3-SAT问题约减说明了防守者oracle和攻击者oracle子问题的NP难复杂度。为了进一步改进Double Oracle算法,分别基于防守者资源分配的子模特性,给出了防守者的贪婪启发更优应对子算法,基于变量临近搜索框架,给出了攻击者的启发式更优应对子算法,并以更优应对oracle替换攻守双方的最优应对oracle。Double Oracle框架由极大极小定理保证收敛性,子oracle可以通过合适的优化方法进一步加速,是求解大规模网络攻防对抗博弈问题的合适求解框架。(5)验证了论文模型和算法在现实道路网络上的可扩展性。论文采用不同类型、拓扑、规模和参数的人工仿真网络对模型和算法进行评估测试,验证算法的可扩展性和参数敏感度。在此基础之上,采用更大规模的现实道路网络上对文章所提算法的可扩展性进行进一步的验证。实验结果表明算法能够提供数量级上的加速,从而证明了论文的改进迭代求解框架能够使得论文的模型扩展应用到实际的网络领域。本文聚焦于攻防对抗博弈在网络结构领域的应用,重点考虑资源的稀缺性和行为的不确定性对模型的影响,构建更为贴近现实场景的博弈模型。针对不同的模型,论文设计各种创新性的基于分解和迭代的方法用以提升算法的可扩展性和鲁棒性。实验结果显示,本文的研究成果可以解决现实规模的网络问题,能够为现实网络攻防对抗博弈问题提供满意的资源分配策略。