{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T07:48:52Z","timestamp":1776844132210,"version":"3.51.2"},"reference-count":88,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"National Science and Technology Council","award":["111-2222-E-008-008-MY2, NSTC 114-2222-E-A49-014, NSTC 114-2221-E-008-049, NSF DMS-1737812, CNS-1618391, CNS-1553273, and CCF-1535900"],"award-info":[{"award-number":["111-2222-E-008-008-MY2, NSTC 114-2222-E-A49-014, NSTC 114-2221-E-008-049, NSF DMS-1737812, CNS-1618391, CNS-1553273, and CCF-1535900"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Cyber-Phys. Syst."],"published-print":{"date-parts":[[2026,4,30]]},"abstract":"<jats:p>\n                    We study the Patrol Security Game (PSG), a robotic patrolling problem formulated as an extensive-form Stackelberg game, in which the attacker strategically selects the timing, location, and duration of an attack. The defender\u2019s goal is to compute an infinite-horizon patrolling policy that minimizes the attacker\u2019s expected payoff. By restricting the defender\u2019s strategy to a time-homogeneous first-order Markov chain, we show that PSG can be reformulated as a combinatorial minimax problem. We prove that the optimal strategy under zero-penalty scenarios corresponds to minimizing either the expected hitting time or return time, depending on the attacker\u2019s visibility model. These optimal policies are closed-form and can be computed efficiently. On the other hand, in high-penalty cases, we observe that the patrolling schedule with high randomness can minimize the attacker\u2019s expected gain. However, in general, the minimax objective becomes non-convex. To address this, we introduce a bi-criteria optimization framework that jointly considers the\n                    <jats:italic toggle=\"yes\">expected maximum reward<\/jats:italic>\n                    (EMR) and\n                    <jats:italic toggle=\"yes\">entropy rate<\/jats:italic>\n                    of the patrolling policy. We propose three graph-based algorithms and a deep reinforcement learning model to efficiently balance these two objectives. Each algorithm demonstrates distinct strengths under different configurations, such as varying penalty scales and cost function settings. The extensive experiments on both synthetic and real-world crime datasets validate the effectiveness of our approaches, demonstrating superior performance and scalability compared to state-of-the-art baselines.\n                  <\/jats:p>","DOI":"10.1145\/3785138","type":"journal-article","created":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T18:28:35Z","timestamp":1765823315000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Patrol Security Game: Defending against Adversary with Freedom in Attack Timing, Location, and Duration"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4463-1616","authenticated-orcid":false,"given":"Hao-Tsung","family":"Yang","sequence":"first","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Central University, Zhongli, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-2981-4343","authenticated-orcid":false,"given":"Ting-Kai","family":"Weng","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Central University, Zhongli, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-6764-7827","authenticated-orcid":false,"given":"Ting-Yu","family":"Chang","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Central University, Zhongli, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2670-2727","authenticated-orcid":false,"given":"Kin Sum","family":"Liu","sequence":"additional","affiliation":[{"name":"Department of Ads Quality, DoorDash, Inc., San Francisco, California, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6362-2972","authenticated-orcid":false,"given":"Shan","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Stony Brook University, Stony Brook, New York, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5083-6082","authenticated-orcid":false,"given":"Jie","family":"Gao","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Stony Brook University, Stony Brook, New York, USA and Department of Computer Science, Rutgers University, New Jersey, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-8043-5384","authenticated-orcid":false,"given":"Shih-Yu","family":"Tsai","sequence":"additional","affiliation":[{"name":"Department of Information Management and Finance, National Yang Ming Chiao Tung University, Hsinchu, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,21]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.23919\/ECC54610.2021.9654432"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-66723-8_7"},{"key":"e_1_3_2_4_2","volume-title":"Proceedings of the 38th International Symposium on Computational Geometry (SoCG \u201922)","author":"Afshani Peyman","year":"2022","unstructured":"Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten L\u00f6ffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, and Hao Tsung Yang. 2022. On cyclic solutions to the min-max latency multi-robot patrolling problem. In Proceedings of the 38th International Symposium on Computational Geometry (SoCG \u201922). Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.5555\/2208436.2208459"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.65109\/GOBR8877"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913504011"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1609\/aimag.v33i4.2401"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.6.B279"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548458"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2016.7526682"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46521-9_1"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225139"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s43154-022-00078-5"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2017.02.007"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.65109\/FWGB5185"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2012.03.003"},{"key":"e_1_3_2_19_2","unstructured":"Irwan Bello Hieu Pham Quoc V. Le Mohammad Norouzi and Samy Bengio. 2016. Neural combinatorial optimization with reinforcement learning. arXiv:1611.09940. Retrieved from https:\/\/arxiv.org\/abs\/1611.09940"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581256"},{"key":"e_1_3_2_21_2","first-page":"989","volume-title":"Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems","volume":"3","author":"Bo\u0161ansk\u1ef3 Branislav","year":"2011","unstructured":"Branislav Bo\u0161ansk\u1ef3, Viliam Lis\u1ef3, Michal Jakob, and Michal P\u011bchou\u010dek. 2011. Computing time-dependent policies for patrolling games with mobile targets. In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems, Vol. 3. International Foundation for Autonomous Agents and Multiagent Systems, 989\u2013996."},{"key":"e_1_3_2_22_2","unstructured":"Am\u00edlcar Branquinho Ana Foulqui\u00e9-Moreno Manuel Ma\u00f1as Carlos \u00c1lvarez-Fern\u00e1ndez and Juan E. Fern\u00e1ndez-D\u00edaz. 2021. Multiple orthogonal polynomials and random walks. arXiv:2103.13715. Retrieved from https:\/\/arxiv.org\/abs\/2103.13715"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2017.01.034"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2019.11.002"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.26650\/ekoist.2023.39.1221032"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2104510"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0483(02)00059-2"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2021.04.015"},{"key":"e_1_3_2_29_2","volume-title":"Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem","author":"Nicos Christofides","year":"1976","unstructured":"Nicos Christofides. 1976. Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem. Technical Report. Management Sciences Research Group, Carnegie-Mellon University Pittsburgh, PA."},{"key":"e_1_3_2_30_2","volume-title":"Denver Open Data Catalog","author":"City and County of Denver","year":"2016","unstructured":"City and County of Denver. 2016. Denver Open Data Catalog. City and County of Denver."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.3390\/math9101148"},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","unstructured":"Xiaoming Duan Mishel George and Francesco Bullo. 2018. Markov chains with maximum return time entropy for robotic surveillance. arXiv:1803.07705. Retrieved from https:\/\/arxiv.org\/abs\/1803.07705","DOI":"10.1109\/CDC.2018.8619715"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCNS.2021.3058932"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.65109\/JWHV3222"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/2484920.2485072"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-20624-5_14"},{"key":"e_1_3_2_37_2","first-page":"403","volume-title":"Proceedings of the European Conference on Artificial Intelligence","author":"Gatti Nicola","year":"2008","unstructured":"Nicola Gatti. 2008. Game theoretical insights in strategic patrolling: Model and algorithm in normal-form. In Proceedings of the European Conference on Artificial Intelligence, 403\u2013407."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2018.2844120"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2005.1582488"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i5.16495"},{"key":"e_1_3_2_41_2","volume-title":"Proceedings of theInternational Conference on Learning Representations","author":"Hottung Andr\u00e9","unstructured":"Andr\u00e9 Hottung, Bhanu Bhandari, and Kevin Tierney. n.d. Learning a latent search space for routing problems using variational autoencoders. In Proceedings of the International Conference on Learning Representations."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cose.2019.101660"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2023.04.009"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2011.6094844"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v24i1.7611"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.5555\/2030470.2030518"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.3390\/aerospace7010008"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.106.620"},{"key":"e_1_3_2_49_2","volume-title":"Finite Markov Chains","author":"Kemeny John G.","year":"1960","unstructured":"John G. Kemeny and J. Laurie Snell. 1960. Finite Markov Chains. D Van Nostad Co. Inc., Princeton, NJ."},{"key":"e_1_3_2_50_2","volume-title":"Finite Markov Chains: With a New Appendix \u201cGeneralization of a Fundamental Matrix\u201d","author":"Kemeny John G.","year":"1983","unstructured":"John G. Kemeny and J. Laurie Snell. 1983. Finite Markov Chains: With a New Appendix \u201cGeneralization of a Fundamental Matrix\u201d. Springer."},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.5555\/1558013.1558108"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(03)00133-4"},{"key":"e_1_3_2_53_2","first-page":"10418","article-title":"Learning collaborative policies to solve NP-hard routing problems","volume":"34","author":"Kim Minsu","year":"2021","unstructured":"Minsu Kim and Jinkyoo Park. 2021. Learning collaborative policies to solve NP-hard routing problems. In Advances in Neural Information Processing Systems, Vol. 34, 10418\u201310430.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-66151-9_7"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2010.07.016"},{"key":"e_1_3_2_56_2","unstructured":"Wouter Kool Herke Van Hoof and Max Welling. 2018. Attention learn to solve routing problems! arXiv:1803.08475. Retrieved from https:\/\/arxiv.org\/abs\/1803.08475"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(92)90192-C"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2020.2988367"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2018.2798817"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCEA50009.2020.00126"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8056961"},{"key":"e_1_3_2_62_2","volume-title":"Proceedings of the AAAI Workshop on Deep Learning on Graphs: Methodologies and Applications","author":"Ma Qiang","year":"2020","unstructured":"Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. 2020. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. In Proceedings of the AAAI Workshop on Deep Learning on Graphs: Methodologies and Applications."},{"key":"e_1_3_2_63_2","volume-title":"Proactive Policing: Effects on Crime and Communities","author":"Majmundar Malay K.","year":"2018","unstructured":"Malay K. Majmundar and David Weisburd. 2018. Proactive Policing: Effects on Crime and Communities. National Academies Press."},{"key":"e_1_3_2_64_2","first-page":"229","volume-title":"Proceedings of the 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM \u201917)","volume":"10139","author":"Min Jie","year":"2017","unstructured":"Jie Min and Tomasz Radzik. 2017. Bamboo garden trimming problem. In Proceedings of the 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM \u201917), Vol. 10139. Springer, 229."},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1198\/jasa.2011.ap09546"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00325-9"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-31323-8_16"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2015.2426317"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.08.015"},{"key":"e_1_3_2_71_2","first-page":"125","volume-title":"Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems: Industrial Track","author":"Pita James","year":"2008","unstructured":"James Pita, Manish Jain, Janusz Marecki, Fernando Ord\u00f3\u00f1ez, Christopher Portway, Milind Tambe, Craig Western, Praveen Paruchuri, and Sarit Kraus. 2008. Deployed ARMOR protection: The application of a game theoretic model for security at the Los Angeles international airport. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems: Industrial Track. International Foundation for Autonomous Agents and Multiagent Systems, 125\u2013132."},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1109\/SSRR.2011.6106761"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1177\/1729881419839596"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2022.05.013"},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-021-04167-0"},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-89332-5"},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.5555\/2343576.2343578"},{"key":"e_1_3_2_78_2","first-page":"346","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence","author":"Shieh Eric","year":"2013","unstructured":"Eric Shieh, Manish Jain, Albert Xin Jiang, and Milind Tambe. 2013. Efficiently solving joint activity based security games. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence. AAAI Press, 346\u2013352."},{"key":"e_1_3_2_79_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCST.2022.3207671"},{"key":"e_1_3_2_80_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/775"},{"key":"e_1_3_2_81_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-50670-3_4"},{"key":"e_1_3_2_82_2","doi-asserted-by":"publisher","DOI":"10.1109\/CASE.2011.6042503"},{"key":"e_1_3_2_83_2","unstructured":"Jason Tsai Christopher Kiekintveld Fernando Ordonez Milind Tambe and Shyamsunder Rathi. 2009. IRIS\u2014A tool for strategic security allocation in transportation networks. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems."},{"key":"e_1_3_2_84_2","first-page":"2692","article-title":"Pointer networks","volume":"28","author":"Vinyals Oriol","year":"2015","unstructured":"Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015. Pointer networks. In Proceedings of the Advances in Neural Information Processing Systems, Vol. 28, 2692\u20132700.","journal-title":"Proceedings of the Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_85_2","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v24i1.13614"},{"key":"e_1_3_2_86_2","doi-asserted-by":"publisher","DOI":"10.5555\/3398761.3399135"},{"key":"e_1_3_2_87_2","doi-asserted-by":"publisher","DOI":"10.65109\/LQOZ9863"},{"key":"e_1_3_2_88_2","doi-asserted-by":"publisher","DOI":"10.5555\/3306127.3331819"},{"key":"e_1_3_2_89_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.21564"}],"container-title":["ACM Transactions on Cyber-Physical Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3785138","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T06:35:32Z","timestamp":1776839732000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3785138"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,21]]},"references-count":88,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4,30]]}},"alternative-id":["10.1145\/3785138"],"URL":"https:\/\/doi.org\/10.1145\/3785138","relation":{},"ISSN":["2378-962X","2378-9638"],"issn-type":[{"value":"2378-962X","type":"print"},{"value":"2378-9638","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,21]]},"assertion":[{"value":"2024-09-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-22","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}