Who Let the Guards Out: Visual Support for Patrolling Games
Authors: 
Matěj Lang, Adam Štěpánek, Róbert Zvara, Vojtěch Řehák, Barbora KozlíkováAuthors Info & Claims
Pages 34 - 43
Abstract
Effective security patrol management is critical for ensuring safety in diverse environments such as art galleries, airports, and factories. The behavior of patrols in these situations can be modeled by patrolling games. They simulate the behavior of the patrol and adversary in the building, which is modeled as a graph of interconnected nodes representing rooms. The designers of algorithms solving the game face the problem of analyzing complex graph layouts with temporal dependencies. Therefore, appropriate visual support is crucial for them to work effectively. In this paper, we present a novel tool that helps the designers of patrolling games explore the outcomes of the proposed algorithms and approaches, evaluate their success rate, and propose modifications that can improve their solutions. Our tool offers an intuitive and interactive interface, featuring a detailed exploration of patrol routes and probabilities of taking them, simulation of patrols, and other requested features. In close collaboration with experts in designing patrolling games, we conducted three case studies demonstrating the usage and usefulness of our tool. The prototype of the tool, along with exemplary datasets, is available at https://gitlab.fi.muni.cz/formela/strategy-vizualizer.
References
[1]
International Phonetic Association. https://www.internationalphoneticassociation.org/. Accessed: 2024-06-12. 9.
[2]
N. Agmon, S. Kraus, and G. A. Kaminka. Multi-robot perimeter patrol in adversarial settings. In 2008 IEEE International Conference on Robotics and Automation, pp. 2339–2345, 2008. 3.
[3]
S. Alpern, A. Morton, and K. Papadaki. Patrolling games. Operations Research, 59(5):1246–1257, 2011. 1,2.
[4]
F. Bertault and M. Miller. An algorithm for drawing compound graphs. In Graph Drawing, vol. 1731, pp. 197–204. Springer, 1999. Series Title: Lecture Notes in Computer Science. 3.
[5]
B. Bošanský, V. Lisý, M. Jakob, and M. Pěchouček, Computing time-dependent policies for patrolling games with mobile targets. In The 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 3, AAMAS '11, p. 989–996. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2011. 2.
[6]
B. Bošanský, O. Vaněk, and M. Pěchouček, Strategy representation analysis for patrolling games. In AAAI Spring Symposium, No. 3: Game Theory for Security, Sustainability, and Health, Technical Report SS-12-03, pp. 9–12, 2012. 3.
[7]
P. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149–160, 1984. 3.
[8]
P. Eades, C. Gutwenger, S.-H. Hong, and P. Mutzel. Graph drawing algorithms, p. 6. Chapman & Hall/CRC, 2 ed., 2010. 3.
[9]
F. Fang, T. Nguyen, R. Pickles, W. Lam, G. Clements, B. An, A. Singh, M. Tambe, and A. Lemieux. Deploying PAWS: Field optimization of the protection assistant for wildlife security. Proceedings of the AAAI Conference on Artificial Intelligence, 30(2):3966–3973, 2016. 3.
[10]
F. M. D. Fave, A. X. Jiang, Z. Yin, C. Zhang, M. Tambe, S. Kraus, and J. P. Sullivan. Game-theoretic patrolling with dynamic execution uncertainty and a case study on a real transit system. Journal of Artificial Intelligence Research, 50:321–367, 2014. 3.
[11]
T. M. J. Fruchterman and E. M. Reingold. Graph drawing by force-directed placement. Software: Practice and Experience, 21(11):1129–1164, 1991. 3.
[12]
O. Häggström. Finite Markov chains and algorithmic applications, vol. 52. Cambridge University Press, 2002. 2.
[13]
M. Jacomy. Medialab/iwanthue: Colors for data scientists. https://github.com/medialab/iwanthue/, 2013. Accessed: 2024-03-15. 4, 7.
[14]
M. Jacomy, T. Venturini, S. Heymann, and M. Bastian. Forceatlas2, a continuous graph layout algorithm for handy network visualization designed for the gephi software. PloS ONE, 9(6):e98679, 2014. 3,5.
[15]
D. Klaška, A. Kučera, V. Musil, and V. Řehák. Regstar: efficient strategy synthesis for adversarial patrolling games. In C. De Campos and M. H. Maathuis eds, Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, vol. 161 of Proceedings of Machine Learning Research, pp. 471–481. PMLR, 2021. 3.
[16]
D. Klaška, A. Kučera, and V. Řehák. Adversarial patrolling with drones. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '20, p. 629–637. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2020. 3.
[17]
L. Lee McCarthy. p5.js. https://p5js.org/. Accessed: 2024-03-15. 7.
[18]
C. Nobre, M. Meyer, M. Streit, and A. Lex. The state of the art in visualizing multivariate networks. Computer Graphics Forum, 38(3):807–832, 2019. 3.
[19]
J. R. Norris. Markov Chains. Cambridge University Press, 1998. 2.
[20]
J. Pita, M. Jain, J. Marecki, F. Ordóñez, C. D. Portway, M. Tambe, C. Western, P. Paruchuri, and S. Kraus. Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport. In Adaptive Agents and Multi-Agent Systems, p. 125–132. International Foundation for Autonomous Agents and Multiagent Systems, 2008. 3.
[21]
H.-J. Schulz, T. Nocke, M. Heitzler, and H. Schumann. A design space of visualization tasks. IEEE Transactions on Visualization and Computer Graphics, 19(12):2366–2375, 2013. 4.
[22]
C. E. Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3):379–423, 1948. 9.
[23]
M. Sharir. A strong-connectivity algorithm and its applications in data flow analysis. Computers & Mathematics with Applications, 7(1):67–72, 1981. 6.
[24]
E. Shieh, B. An, R. Yang, M. Tambe, C. Baldwin, J. DiRenzo, B. Maule, and G. Meyer. PROTECT: a deployed game theoretic system to protect the ports of the united states. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 1, AAMAS '12, pp. 13–20, 2012. 3.
[25]
M. Tambe. Security and game theory: algorithms, deployed systems, lessons learned. Cambridge University Press, 2012. 2, 3.
[26]
S. Van Den Elzen and J. J. Van Wijk. Multivariate network exploration and presentation: From detail to overview via selections and aggregations. IEEE Transactions on Visualization and Computer Graphics, 20(12):2310–2319, 2014. 3.
[27]
C. Vehlow, F. Beck, and D. Weiskopf. The State of the Art in Visualizing Group Structures in Graphs. In R. Borgo, F. Ganovelli, and I. Viola eds,. Eurographics Conference on Visualization (EuroVis) - STARs. The Eurographics Association, 2015. 3.
[28]
Y. Vorobeychik, B. An, and M. Tambe. Adversarial patrolling games. In 2012 AAAI Spring Symposium Series, 2012. 2.
[29]
M. O. Ward. Multivariate data glyphs: Principles and practice. In C.-H. Chen, W. Härdle, and A. Unwin eds., Handbook of Data Visualization, pp. 179–198. Springer, 2008. 3.
[30]
H. Xu, B. Ford, F. Fang, B. Dilkina, A. Plumptre, M. Tambe, M. Driciru, F. Wanyama, A. Rwetsiba, M. Nsubaga, and J. Mabonga. Optimal patrol planning for green security games with black-box attackers. In S. Rass, B. An, C. Kiekintveld, F. Fang, and S. Schauer eds., Decision and Game Theory for Security, pp. 458–477. Springer International Publishing, 2017. 3.
[31]
Z. Yin, A. Jiang, M. Johnson, M. Tambe, C. Kiekintveld, K. Leyton-Brown, T. Sandholm, and J. Sullivan. TRUSTS: Scheduling randomized patrols for fare inspection in transit systems. In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 26, pp. 2348–2355, 2012. 3.
[32]
L. Zhang, G. Reniers, B. Chen, and X. Qiu. CCP game: A game theoretical model for improving the scheduling of chemical cluster patrolling. Reliability Engineering & System Safety, 191:106186, 2019. 3.
[33]
B. Zheng and F. Sadlo. On the visualization of hierarchical multivariate data. In 2021 IEEE 14th Pacific Visualization Symposium (PacificVis), pp. 136–145, 2021. 3.
Index Terms
- Who Let the Guards Out: Visual Support for Patrolling Games
Index terms have been assigned to the content through auto-classification.
Recommendations
Patrolling Games
A key operational problem for those charged with the security of vulnerable facilities (such as airports or art galleries) is the scheduling and deployment of patrols. Motivated by the problem of optimizing randomized, and thus unpredictable, patrols, ...
A Decision Support System for predictive police patrolling
In the current economic climate, many police agencies have reduced resources, especially personnel, with a consequential increase in workload and deterioration in public safety. A Decision Support System (DSS) can help to optimize effective use of the ...
Patrolling security games: Definition and algorithms for solving large instances with single patroller and single intruder
Security games are gaining significant interest in artificial intelligence. They are characterized by two players (a defender and an attacker) and by a set of targets the defender tries to protect from the attacker@?s intrusions by committing to a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1077-2626 © 2024 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Educational Activities Department
United States
Publication History
Published: 01 January 2025
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 16 Feb 2025