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

Stochastic strategies for patrolling a terrain with a synchronized multi-robot system

Author

Listed:
  • Caraballo, Luis E.
  • Díaz-Báñez, José M.
  • Fabila-Monroy, Ruy
  • Hidalgo-Toscano, Carlos

Abstract

A group of cooperative aerial robots can be deployed to efficiently patrol a terrain, in which each robot flies around an assigned area and shares information with the neighbors periodically in order to protect or supervise it. To ensure robustness, previous works on these synchronized systems propose sending a robot to the neighboring area in case it detects a failure. In order to deal with unpredictability and to improve on the efficiency in the deterministic patrolling scheme, this paper proposes random strategies to cover the areas distributed among the agents. First, a theoretical study of the stochastic process is addressed in this paper for two metrics: the idle time, the expected time between two consecutive observations of any point of the terrain and the isolation time, the expected time that a robot is without communication with any other robot. After that, the random strategies are experimentally compared with the deterministic strategy adding another metric: the broadcast time, the expected time elapsed from the moment a robot emits a message until it is received by all the other robots of the team. The simulations show that theoretical results are in good agreement with the simulations and the random strategies outperform the behavior obtained with the deterministic protocol proposed in the literature.

Suggested Citation

  • Caraballo, Luis E. & Díaz-Báñez, José M. & Fabila-Monroy, Ruy & Hidalgo-Toscano, Carlos, 2022. "Stochastic strategies for patrolling a terrain with a synchronized multi-robot system," European Journal of Operational Research, Elsevier, vol. 301(3), pages 1099-1116.
    • Handle: RePEc:eee:ejores:v:301:y:2022:i:3:p:1099-1116
    DOI: 10.1016/j.ejor.2021.11.049
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721010006
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.11.049?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. Evers, Lanah & Barros, Ana Isabel & Monsuur, Herman & Wagelmans, Albert, 2014. "Online stochastic UAV mission planning with time windows and time-sensitive targets," European Journal of Operational Research, Elsevier, vol. 238(1), pages 348-362.
    2. Sergey Bereg & Andrew Brunner & Luis-Evaristo Caraballo & José-Miguel Díaz-Báñez & Mario A. Lopez, 2020. "On the robustness of a synchronized multi-robot system," Journal of Combinatorial Optimization, Springer, vol. 39(4), pages 988-1016, May.
    3. Sergey Bereg & Luis-Evaristo Caraballo & José-Miguel Díaz-Báñez & Mario A. Lopez, 2018. "Computing the k-resilience of a synchronized multi-robot system," Journal of Combinatorial Optimization, Springer, vol. 36(2), pages 365-391, August.
    4. Alpern, Steve & Lidbetter, Thomas & Papadaki, Katerina, 2019. "Optimizing periodic patrols against short attacks on the line and other networks," European Journal of Operational Research, Elsevier, vol. 273(3), pages 1065-1073.
    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. Boris V. Rumiantsev & Rasul A. Kochkarov & Azret A. Kochkarov, 2023. "Graph-Clustering Method for Construction of the Optimal Movement Trajectory under the Terrain Patrolling," Mathematics, MDPI, vol. 11(1), pages 1-13, 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. Zajac, Sandra & Huber, Sandra, 2021. "Objectives and methods in multi-objective routing problems: a survey and classification scheme," European Journal of Operational Research, Elsevier, vol. 290(1), pages 1-25.
    2. Sergey Bereg & Andrew Brunner & Luis-Evaristo Caraballo & José-Miguel Díaz-Báñez & Mario A. Lopez, 2020. "On the robustness of a synchronized multi-robot system," Journal of Combinatorial Optimization, Springer, vol. 39(4), pages 988-1016, May.
    3. Darlington, Matthew & Glazebrook, Kevin D. & Leslie, David S. & Shone, Rob & Szechtman, Roberto, 2023. "A stochastic game framework for patrolling a border," European Journal of Operational Research, Elsevier, vol. 311(3), pages 1146-1158.
    4. Aldana-Galván, I. & Catana-Salazar, J.C. & Díaz-Báñez, J.M. & Duque, F. & Fabila-Monroy, R. & Heredia, M.A. & Ramírez-Vigueras, A. & Urrutia, J., 2020. "On optimal coverage of a tree with multiple robots," European Journal of Operational Research, Elsevier, vol. 285(3), pages 844-852.
    5. Bian, Zheyong & Liu, Xiang, 2018. "A real-time adjustment strategy for the operational level stochastic orienteering problem: A simulation-aided optimization approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 115(C), pages 246-266.
    6. Kyriakakis, Nikolaos A. & Marinaki, Magdalene & Matsatsinis, Nikolaos & Marinakis, Yannis, 2022. "A cumulative unmanned aerial vehicle routing problem approach for humanitarian coverage path planning," European Journal of Operational Research, Elsevier, vol. 300(3), pages 992-1004.
    7. Verbeeck, C. & Vansteenwegen, P. & Aghezzaf, E.-H., 2016. "Solving the stochastic time-dependent orienteering problem with time windows," European Journal of Operational Research, Elsevier, vol. 255(3), pages 699-718.
    8. He Luo & Zhengzheng Liang & Moning Zhu & Xiaoxuan Hu & Guoqiang Wang, 2018. "Integrated optimization of unmanned aerial vehicle task allocation and path planning under steady wind," PLOS ONE, Public Library of Science, vol. 13(3), pages 1-24, March.
    9. Qian, Qiuchen & Wang, Yanran & Boyle, David, 2024. "On solving close enough orienteering problems with overlapped neighborhoods," European Journal of Operational Research, Elsevier, vol. 318(2), pages 369-387.
    10. Peng, Rui, 2018. "Joint routing and aborting optimization of cooperative unmanned aerial vehicles," Reliability Engineering and System Safety, Elsevier, vol. 177(C), pages 131-137.
    11. Bijun Wang & Zheyong Bian & Mo Mansouri, 2023. "Self-adaptive heuristic algorithms for the dynamic and stochastic orienteering problem in autonomous transportation system," Journal of Heuristics, Springer, vol. 29(1), pages 77-137, February.
    12. Baston, Vic & Kikuta, Kensaku, 2019. "A search problem on a bipartite network," European Journal of Operational Research, Elsevier, vol. 277(1), pages 227-237.
    13. Wang, Jian & Cui, Lei, 2023. "Patrolling games with coordination between monitoring devices and patrols," Reliability Engineering and System Safety, Elsevier, vol. 233(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:301:y:2022:i:3:p:1099-1116. 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.