IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v277y2019i1p255-268.html
   My bibliography  Save this article

A Monte Carlo Tree Search approach to finding efficient patrolling schemes on graphs

Author

Listed:
  • Karwowski, Jan
  • Mańdziuk, Jacek

Abstract

In this paper, we propose an evader-defender type of game for modeling multi-step patrolling scenarios on a graph. The game utilizes a specifically designed graph-based setting which captures spatial arrangements of the protected area, for instance industrial premises or warehouses, wherein certain valuable assets are stored. The game is played by two sides: the evader who attempts to steal or destroy the assets and the defender whose aim is to intercept the evader and prevent him/her from accomplishing his/her goal.

Suggested Citation

  • Karwowski, Jan & Mańdziuk, Jacek, 2019. "A Monte Carlo Tree Search approach to finding efficient patrolling schemes on graphs," European Journal of Operational Research, Elsevier, vol. 277(1), pages 255-268.
    • Handle: RePEc:eee:ejores:v:277:y:2019:i:1:p:255-268
    DOI: 10.1016/j.ejor.2019.02.017
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719301456
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.02.017?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Eghbal Rashidi & Hugh Medal & Aaron Hoskins, 2018. "An attacker‐defender model for analyzing the vulnerability of initial attack in wildfire suppression," Naval Research Logistics (NRL), John Wiley & Sons, vol. 65(2), pages 120-134, March.
    2. Hohzaki, Ryusuke & Maehara, Hiroki, 2010. "A single-shot game of multi-period inspection," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1410-1418, December.
    3. McKelvey Richard D. & Palfrey Thomas R., 1995. "Quantal Response Equilibria for Normal Form Games," Games and Economic Behavior, Elsevier, vol. 10(1), pages 6-38, July.
    4. Gerald G. Brown & W. Matthew Carlyle & Robert C. Harney & Eric M. Skroch & R. Kevin Wood, 2009. "Interdicting a Nuclear-Weapons Project," Operations Research, INFORMS, vol. 57(4), pages 866-877, August.
    5. Saksena, J. P., 1979. "Beat patrolling in urban areas A case study," European Journal of Operational Research, Elsevier, vol. 3(3), pages 199-206, May.
    6. Manish Jain & Jason Tsai & James Pita & Christopher Kiekintveld & Shyamsunder Rathi & Milind Tambe & Fernando Ordóñez, 2010. "Software Assistants for Randomized Patrol Planning for the LAX Airport Police and the Federal Air Marshal Service," Interfaces, INFORMS, vol. 40(4), pages 267-290, August.
    7. Juan S. Borrero & Oleg A. Prokopyev & Denis Sauré, 2016. "Sequential Shortest Path Interdiction with Incomplete Information," Decision Analysis, INFORMS, vol. 13(1), pages 68-98, March.
    8. Andrew Romich & Guanghui Lan & J. Cole Smith, 2015. "Algorithms for optimizing the placement of stationary monitors," IISE Transactions, Taylor & Francis Journals, vol. 47(6), pages 556-576, June.
    9. Eghbal Rashidi & Hugh Richard Medal & Aaron Hoskins, 2018. "Mitigating a pyro-terror attack using fuel treatment," IISE Transactions, Taylor & Francis Journals, vol. 50(6), pages 499-511, June.
    10. Juan S. Borrero & Oleg A. Prokopyev & Denis Sauré, 2019. "Sequential Interdiction with Incomplete Information and Learning," Operations Research, INFORMS, vol. 67(1), pages 72-89, January.
    11. Baykal-Gürsoy, Melike & Duan, Zhe & Poor, H. Vincent & Garnaev, Andrey, 2014. "Infrastructure security games," European Journal of Operational Research, Elsevier, vol. 239(2), pages 469-478.
    12. Bo An & Fernando Ordóñez & Milind Tambe & Eric Shieh & Rong Yang & Craig Baldwin & Joseph DiRenzo & Kathryn Moretti & Ben Maule & Garrett Meyer, 2013. "A Deployed Quantal Response-Based Patrol Planning System for the U.S. Coast Guard," Interfaces, INFORMS, vol. 43(5), pages 400-420, October.
    13. Gerald Brown & Matthew Carlyle & Javier Salmerón & Kevin Wood, 2006. "Defending Critical Infrastructure," Interfaces, INFORMS, vol. 36(6), pages 530-544, December.
    14. David Silver & Julian Schrittwieser & Karen Simonyan & Ioannis Antonoglou & Aja Huang & Arthur Guez & Thomas Hubert & Lucas Baker & Matthew Lai & Adrian Bolton & Yutian Chen & Timothy Lillicrap & Fan , 2017. "Mastering the game of Go without human knowledge," Nature, Nature, vol. 550(7676), pages 354-359, October.
    15. Zoroa, N. & Fernández-Sáez, M.J. & Zoroa, P., 2012. "Patrolling a perimeter," European Journal of Operational Research, Elsevier, vol. 222(3), pages 571-582.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Wang, Jian & Cui, Lei, 2023. "Patrolling games with coordination between monitoring devices and patrols," Reliability Engineering and System Safety, Elsevier, vol. 233(C).
    2. Casorrán, Carlos & Fortz, Bernard & Labbé, Martine & Ordóñez, Fernando, 2019. "A study of general and security Stackelberg game formulations," European Journal of Operational Research, Elsevier, vol. 278(3), pages 855-868.
    3. Deniz Preil & Michael Krapp, 2022. "Artificial intelligence-based inventory management: a Monte Carlo tree search approach," Annals of Operations Research, Springer, vol. 308(1), pages 415-439, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Nguyen, Di H. & Smith, J. Cole, 2022. "Network interdiction with asymmetric cost uncertainty," European Journal of Operational Research, Elsevier, vol. 297(1), pages 239-251.
    2. Yan, Xihong & Ren, Xiaorong & Nie, Xiaofeng, 2022. "A budget allocation model for domestic airport network protection," Socio-Economic Planning Sciences, Elsevier, vol. 82(PB).
    3. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    4. Wei, Ningji & Walteros, Jose L., 2022. "Integer programming methods for solving binary interdiction games," European Journal of Operational Research, Elsevier, vol. 302(2), pages 456-469.
    5. M. Hosein Zare & Oleg A. Prokopyev & Denis Sauré, 2020. "On Bilevel Optimization with Inexact Follower," Decision Analysis, INFORMS, vol. 17(1), pages 74-95, March.
    6. Ketkov, Sergey S. & Prokopyev, Oleg A., 2020. "On greedy and strategic evaders in sequential interdiction settings with incomplete information," Omega, Elsevier, vol. 92(C).
    7. Juan S. Borrero & Leonardo Lozano, 2021. "Modeling Defender-Attacker Problems as Robust Linear Programs with Mixed-Integer Uncertainty Sets," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1570-1589, October.
    8. Smith, J. Cole & Song, Yongjia, 2020. "A survey of network interdiction models and algorithms," European Journal of Operational Research, Elsevier, vol. 283(3), pages 797-811.
    9. Thanh Hong Nguyen & Amulya Yadav, 2022. "A Complete Analysis on the Risk of Using Quantal Response: When Attacker Maliciously Changes Behavior under Uncertainty," Games, MDPI, vol. 13(6), pages 1-24, December.
    10. Juan S. Borrero & Oleg A. Prokopyev & Denis Sauré, 2019. "Sequential Interdiction with Incomplete Information and Learning," Operations Research, INFORMS, vol. 67(1), pages 72-89, January.
    11. Cheung, Kam-Fung & Bell, Michael G.H., 2021. "Improving connectivity of compromised digital networks via algebraic connectivity maximisation," European Journal of Operational Research, Elsevier, vol. 294(1), pages 353-364.
    12. Bhuiyan, Tanveer Hossain & Moseley, Maxwell C. & Medal, Hugh R. & Rashidi, Eghbal & Grala, Robert K., 2019. "A stochastic programming model with endogenous uncertainty for incentivizing fuel reduction treatment under uncertain landowner behavior," European Journal of Operational Research, Elsevier, vol. 277(2), pages 699-718.
    13. G. Quijano, Eduardo & Ríos Insua, David & Cano, Javier, 2018. "Critical networked infrastructure protection from adversaries," Reliability Engineering and System Safety, Elsevier, vol. 179(C), pages 27-36.
    14. Jing Yang & Juan S. Borrero & Oleg A. Prokopyev & Denis Sauré, 2021. "Sequential Shortest Path Interdiction with Incomplete Information and Limited Feedback," Decision Analysis, INFORMS, vol. 18(3), pages 218-244, September.
    15. Matthews, Logan R. & Gounaris, Chrysanthos E. & Kevrekidis, Ioannis G., 2019. "Designing networks with resiliency to edge failures using two-stage robust optimization," European Journal of Operational Research, Elsevier, vol. 279(3), pages 704-720.
    16. Fischetti, Matteo & Monaci, Michele & Sinnl, Markus, 2018. "A dynamic reformulation heuristic for Generalized Interdiction Problems," European Journal of Operational Research, Elsevier, vol. 267(1), pages 40-51.
    17. Bo An & Fernando Ordóñez & Milind Tambe & Eric Shieh & Rong Yang & Craig Baldwin & Joseph DiRenzo & Kathryn Moretti & Ben Maule & Garrett Meyer, 2013. "A Deployed Quantal Response-Based Patrol Planning System for the U.S. Coast Guard," Interfaces, INFORMS, vol. 43(5), pages 400-420, October.
    18. Ríos Insua, David & Cano, Javier & Pellot, Michael & Ortega, Ricardo, 2016. "Multithreat multisite protection: A security case study," European Journal of Operational Research, Elsevier, vol. 252(3), pages 888-899.
    19. Cheung, Kam-Fung & Bell, Michael G.H., 2021. "Attacker–defender model against quantal response adversaries for cyber security in logistics management: An introductory study," European Journal of Operational Research, Elsevier, vol. 291(2), pages 471-481.
    20. Keskin, Burcu B. & Griffin, Emily C. & Prell, Jonathan O. & Dilkina, Bistra & Ferber, Aaron & MacDonald, John & Hilend, Rowan & Griffis, Stanley & Gore, Meredith L., 2023. "Quantitative Investigation of Wildlife Trafficking Supply Chains: A Review," Omega, Elsevier, vol. 115(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:277:y:2019:i:1:p:255-268. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.