Digger: A Graph Contraction Algorithm for Patrolling Games

doi:10.1109/TR.2023.3329958

CORC > 自动化研究所 > 中国科学院自动化研究所 > 多模态人工智能系统全国重点实验室

	Digger: A Graph Contraction Algorithm for Patrolling Games
	Han, Jinpeng 1; Wang, Zhen 2; Chen, Xiaoguang 3; Yang, Manzhi 3; Wang, Fei-Yue 4,5
刊名	IEEE TRANSACTIONS ON RELIABILITY
	2023-11-14
页码	13
关键词	Games Security Game theory Resource management Runtime Roads Cyberspace Graph contraction minimum vertex cut patrolling game security game Stackelberg game
ISSN号	0018-9529
DOI	10.1109/TR.2023.3329958
通讯作者	Wang, Fei-Yue(feiyue@ieee.org)
英文摘要	In security games, the patrolling problem is usually modeled as a Stackelberg game to obtain patrol schemes. However, solving Stackelberg games is challenging, as the player strategy space grows exponentially with patrolling scenarios that expand in space and time. Recent work on reducing the player strategy space does not consider adversarial graph features, making the process of solving the Stackelberg game inefficient. To address this issue, we propose a novel algorithm called "Digger," and the following important findings are made: the defender's optimal strategy can prevent an attacker from reaching a target, and this is achieved by a set of available interdiction vertices that separate the attacker from the target. The defender can arrive at the interdiction vertices earlier than the attacker. After arriving at the set of interdiction vertices, the next defender action subgraphs are not all useful, and the expected utility of the related player's pure strategy is not optimal. Finally, we build a player support set that does not contain useless strategies to improve the speed of the security game algorithm. An experimental evaluation of warehouse graphs demonstrates that Digger dramatically improves the existing algorithms.
资助项目	National Key R&D Program of China[2018AAA0101502] ; Joint Science and Technology Project of SGCC (State Grid Corporation of China): The Fundamental Theory of Human-in-the-Loop Hybrid-Augmented Intelligence for Power Grid Dispatch and Control
WOS关键词	SECURITY
WOS研究方向	Computer Science ; Engineering
语种	英语
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
WOS记录号	WOS:001112034100001
资助机构	National Key R&D Program of China ; Joint Science and Technology Project of SGCC (State Grid Corporation of China): The Fundamental Theory of Human-in-the-Loop Hybrid-Augmented Intelligence for Power Grid Dispatch and Control
内容类型	期刊论文
源URL	[http://ir.ia.ac.cn/handle/173211/55080]
专题	多模态人工智能系统全国重点实验室
通讯作者	Wang, Fei-Yue
作者单位	1.Xi An Jiao Tong Univ, Sch Software Engn, Xian 710049, Peoples R China 2.Hangzhou Dianzi Univ, Sch Cyberspace, Hangzhou 310018, Peoples R China 3.Macau Univ Sci & Technol, Macau Inst Syst Engn, Macau 999078, Peoples R China 4.Chinese Acad Sci, State Key Lab Management & Control Complex Syst, Beijing 100190, Peoples R China 5.Macau Univ Sci & Technol, Macau Inst Syst Engn, Macau 999078, Peoples R China
推荐引用方式 GB/T 7714	Han, Jinpeng,Wang, Zhen,Chen, Xiaoguang,et al. Digger: A Graph Contraction Algorithm for Patrolling Games[J]. IEEE TRANSACTIONS ON RELIABILITY,2023:13.
APA	Han, Jinpeng,Wang, Zhen,Chen, Xiaoguang,Yang, Manzhi,&Wang, Fei-Yue.(2023).Digger: A Graph Contraction Algorithm for Patrolling Games.IEEE TRANSACTIONS ON RELIABILITY,13.
MLA	Han, Jinpeng,et al."Digger: A Graph Contraction Algorithm for Patrolling Games".IEEE TRANSACTIONS ON RELIABILITY (2023):13.