Digger: A Graph Contraction Algorithm for Patrolling Games
文献类型：期刊论文
| 作者 | Han, Jinpeng1; Wang, Zhen2 ; Chen, Xiaoguang3; Yang, Manzhi3; Wang, Fei-Yue4,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. |
| WOS关键词 | SECURITY |
| 资助项目 | 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研究方向 | Computer Science ; Engineering |
| 语种 | 英语 |
| WOS记录号 | WOS:001112034100001 |
| 出版者 | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC |
| 资助机构 | 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. |
入库方式： OAI收割
来源：自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。