1932
0
  1. Home
  2. A-Z Publications
  3. Annual Review of Control, Robotics, and Autonomous Systems
  4. Volume 4, 2021
  5. Article

Annual Review of Control, Robotics, and Autonomous Systems

Volume 4, 2021

Markov Chain–Based Stochastic Strategies for Robotic Surveillance

Abstract

This article surveys recent advancements in strategy designs for persistent robotic surveillance tasks, with a focus on stochastic approaches. The problem describes how mobile robots stochastically patrol a graph in an efficient way, where the efficiency is defined with respect to relevant underlying performance metrics. We start by reviewing the basics of Markov chains, which are the primary motion models for stochastic robotic surveillance. We then discuss the two main criteria regarding the speed and unpredictability of surveillance strategies. The central objects that appear throughout the treatment are the hitting times of Markov chains, their distributions, and their expectations. We formulate various optimization problems based on the relevant metrics in different scenarios and establish their respective properties.

Keyword(s): entropy, hitting times, Markov chains, optimization, robotic surveillance
Loading

Article metrics loading...

/content/journals/10.1146/annurev-control-071520-120123
2021-05-03
2024-05-06
Loading full text...

Full text loading...

/deliver/fulltext/control/4/1/annurev-control-071520-120123.html?itemId=/content/journals/10.1146/annurev-control-071520-120123&mimeType=html&fmt=ahah

Literature Cited

  1. 1. 
    Yuan C, Zhang Y, Liu Z 2015. A survey on technologies for automatic forest fire monitoring, detection, and fighting using unmanned aerial vehicles and remote sensing techniques. Can. J. For. Res. 45:783–92 https://doi.org/10.1139/cjfr-2014-0347
    [Crossref] [Google Scholar]
  2. 2. 
    Shukla A, Karki H. 2016. Application of robotics in offshore oil and gas industry—a review part II. Robot. Auton. Syst. 75:508–24 https://doi.org/10.1016/j.robot.2015.09.013
    [Crossref] [Google Scholar]
  3. 3. 
    Di Paola D, Milella A, Cicirelli G, Distante A 2010. An autonomous mobile robotic system for surveillance of indoor environments. Int. J. Robot. Res. 7:19–26 https://doi.org/10.5772/7254
    [Crossref] [Google Scholar]
  4. 4. 
    Witwicki S, Castillo JC, Messias J, Capitán J, Melo FS et al. 2017. Autonomous surveillance robots: a decision-making framework for networked muiltiagent systems. IEEE Robot. Autom. Mag. 24:352–64 https://doi.org/10.1109/MRA.2017.2662222
    [Crossref] [Google Scholar]
  5. 5. 
    Räty TD. 2010. Survey on contemporary remote surveillance systems for public safety. IEEE Trans. Syst. Man Cybernet. C 40:493–515 https://doi.org/10.1109/TSMCC.2010.2042446
    [Crossref] [Google Scholar]
  6. 6. 
    Pasqualetti F, Durham JW, Bullo F 2012. Cooperative patrolling via weighted tours: performance analysis and distributed algorithms. IEEE Trans. Robot. 28:1181–88 https://doi.org/10.1109/TRO.2012.2201293
    [Crossref] [Google Scholar]
  7. 7. 
    Cassandras CG, Lin X, Ding X 2013. An optimal control approach to the multi-agent persistent monitoring problem. IEEE Trans. Autom. Control 58:947–61 https://doi.org/10.1109/TAC.2012.2225539
    [Crossref] [Google Scholar]
  8. 8. 
    Zhou N, Yu X, Anderson SB, Cassandras CG 2018. Optimal event-driven multiagent persistent monitoring of a finite set of data sources. IEEE Trans. Autom. Control 63:4204–17 https://doi.org/10.1109/TAC.2018.2829469
    [Crossref] [Google Scholar]
  9. 9. 
    Wang Y, Wei Y, Liu X, Zhou N, Cassandras CG 2019. Optimal persistent monitoring using second-order agents with physical constraints. IEEE Trans. Autom. Control 64:3239–52 https://doi.org/10.1109/TAC.2018.2879946
    [Crossref] [Google Scholar]
  10. 10. 
    Smith SL, Schwager M, Rus D 2012. Persistent robotic tasks: monitoring and sweeping in changing environments. IEEE Trans. Robot. 28:410–26 https://doi.org/10.1109/TRO.2011.2174493
    [Crossref] [Google Scholar]
  11. 11. 
    Yu J, Karaman S, Rus D 2015. Persistent monitoring of events with stochastic arrivals at multiple stations. IEEE Trans. Robot. 31:521–35 https://doi.org/10.1109/TRO.2015.2409453
    [Crossref] [Google Scholar]
  12. 12. 
    Rezazadeh N, Kia SS. 2019. A sub-modular receding horizon approach to persistent monitoring for a group of mobile agents over an urban area. 8th IFAC Workshop on Distributed Estimation and Control in Networked Systems D Gayme 217–22 IFAC-PapersOnLine Vol. 5220 Amsterdam: Elsevier https://doi.org/10.1016/j.ifacol.2019.12.161
    [Crossref] [Google Scholar]
  13. 13. 
    Yu X, Andersson SB, Zhou N, Cassandras CG 2020. Scheduling multiple agents in a persistent monitoring task using reachability analysis. IEEE Trans. Autom. Control 65:1499–513 https://doi.org/10.1109/TAC.2019.2922506
    [Crossref] [Google Scholar]
  14. 14. 
    Machado A, Ramalho G, Zucker JD, Drogoul A 2003. Multi-agent patrolling: an empirical analysis of alternative architectures. Multi-Agent-Based Simulation II J Simão Sichman, F Bousquet, P Davidsson 155–70 Berlin: Springer https://doi.org/10.1007/3-540-36483-8_11
    [Crossref] [Google Scholar]
  15. 15. 
    Chevaleyre Y. 2004. Theoretical analysis of the multi-agent patrolling problem. IEEE/WIC/ACM International Conference on Intelligent Agent Technology, 2004302–8 Piscataway, NJ: IEEE https://doi.org/10.1109/IAT.2004.1342959
    [Crossref] [Google Scholar]
  16. 16. 
    Elmaliach Y, Agmon N, Kaminka GA 2009. Multi-robot area patrol under frequency constraints. Ann. Math. Artif. Intell. 57:293–320 https://doi.org/10.1007/s10472-010-9193-y
    [Crossref] [Google Scholar]
  17. 17. 
    Pasqualetti F, Franchi A, Bullo F 2012. On cooperative patrolling: optimal trajectories, complexity analysis and approximation algorithms. IEEE Trans. Robot. 28:592–606 https://doi.org/10.1109/TRO.2011.2179580
    [Crossref] [Google Scholar]
  18. 18. 
    Alamdari S, Fata E, Smith SL 2014. Persistent monitoring in discrete environments: minimizing the maximum weighted latency between observations. Int. J. Robot. Res. 33:138–54 https://doi.org/10.1177/0278364913504011
    [Crossref] [Google Scholar]
  19. 19. 
    Asghar AB, Smith SL, Sundaram S 2019. Multi-robot routing for persistent monitoring with latency constraints. 2019 American Control Conference2620–25 Piscataway, NJ: IEEE https://doi.org/10.23919/ACC.2019.8814485
    [Crossref] [Google Scholar]
  20. 20. 
    Afshani P, Berg MD, Buchin K, Gao J, Loffler M et al. 2020. Approximation algorithms for multi-robot patrol-scheduling with min-max latency. arXiv:2005.02530 [cs.DS]. https://arxiv.org/pdf/2005.02530
  21. 21. 
    Srivastava K, Stipanovi DM, Spong MW 2009. On a stochastic robotic surveillance problem. Proceedings of the 48th IEEE Conference on Decision and Control Held Jointly with 2009 28th Chinese Control Conference8567–74 Piscataway, NJ: IEEE https://doi.org/10.1109/CDC.2009.5400569
    [Crossref] [Google Scholar]
  22. 22. 
    Kempe D, Schulman LJ, Tamuz O 2018. Quasi-regular sequences and optimal schedules for security games. ACM-SIAM Symposium on Discrete Algorithms1625–44 Philadelphia: Soc. Ind. Appl. Math https://doi.org/10.1137/1.9781611975031.106
    [Crossref] [Google Scholar]
  23. 23. 
    Cannata G, Sgorbissa A. 2011. A minimalist algorithm for multirobot continuous coverage. IEEE Trans. Robot. 27:297–312 https://doi.org/10.1109/TRO.2011.2104510
    [Crossref] [Google Scholar]
  24. 24. 
    Patel R, Agharkar P, Bullo F 2015. Robotic surveillance and Markov chains with minimal weighted Kemeny constant. IEEE Trans. Autom. Control 60:3156–67 https://doi.org/10.1109/TAC.2015.2426317
    [Crossref] [Google Scholar]
  25. 25. 
    Patel R, Carron A, Bullo F 2016. The hitting time of multiple random walks. SIAM J. Matrix Anal. Appl. 37:933–54 https://doi.org/10.1137/15M1010737
    [Crossref] [Google Scholar]
  26. 26. 
    George M, Jafarpour S, Bullo F 2019. Markov chains with maximum entropy for robotic surveillance. IEEE Trans. Autom. Control 64:1566–80 https://doi.org/10.1109/TAC.2018.2844120
    [Crossref] [Google Scholar]
  27. 27. 
    Duan X, George M, Bullo F 2020. Markov chains with maximum return time entropy for robotic surveillance. IEEE Trans. Autom. Control 65:72–86 https://doi.org/10.1109/TAC.2019.2906473
    [Crossref] [Google Scholar]
  28. 28. 
    Alvarenga CD, Basilico N, Carpin S 2019. Time-varying graph patrolling against attackers with locally limited and imperfect observation models. 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems4869–76 Piscataway, NJ: IEEE https://doi.org/10.1109/IROS40897.2019.8967770
    [Crossref] [Google Scholar]
  29. 29. 
    Basilico N, Carpin S. 2020. Balancing unpredictability and coverage in adversarial patrolling settings. Algorithmic Foundations of Robotics XIII M Morales, L Tapia, G Sánchez-Ante, S Hutchinson 762–77 Cham, Switz: Springer https://doi.org/10.1007/978-3-030-44051-0_44
    [Crossref] [Google Scholar]
  30. 30. 
    Agmon N, Kaminka GA, Kraus S 2011. Multi-robot adversarial patrolling: facing a full-knowledge opponent. J. Artif. Intell. Res. 42:887–916 https://www.jair.org/index.php/jair/article/view/10742
    [Google Scholar]
  31. 31. 
    Sless Lin E, Agmon N, Kraus S 2019. Multi-robot adversarial patrolling: handling sequential attacks. Artif. Intell. 274:1–25 https://doi.org/10.1016/j.artint.2019.02.004
    [Crossref] [Google Scholar]
  32. 32. 
    Basilico N, Gatti N, Amigoni F 2012. Patrolling security games: definition and algorithms for solving large instances with single patroller and single intruder. Artif. Intell. 184–85:78–123 https://doi.org/10.1016/j.artint.2012.03.003
    [Crossref] [Google Scholar]
  33. 33. 
    Asghar AB, Smith SL. 2016. Stochastic patrolling in adversarial settings. 2016 American Control Conference6435–40 Piscataway, NJ: IEEE https://doi.org/10.1109/ACC.2016.7526682
    [Crossref] [Google Scholar]
  34. 34. 
    Asghar AB, Smith SL. 2018. A patrolling game for adversaries with limited observation time. 2018 IEEE Conference on Decision and Control3305–10 Piscataway, NJ: IEEE https://doi.org/10.1109/CDC.2018.8619136
    [Crossref] [Google Scholar]
  35. 35. 
    Yang H, Tsai S, Liu KS, Lin S, Gao J 2019. Patrol scheduling against adversaries with varying attack durations. Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems1179–88 Richland, SC: Int. Found. Auton. Agents Multiagent Syst https://dl.acm.org/doi/abs/10.5555/3306127.3331819
    [Google Scholar]
  36. 36. 
    Sinha A, Fang F, An B, Kiekintveld C, Tambe M 2018. Stackelberg Security Games: looking beyond a decade of success. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence5494–501 Calif: IJCAI https://doi.org/10.24963/ijcai.2018/775
    [Crossref] [Google Scholar]
  37. 37. 
    Aldous D, Fill JA. 2002. Reversible Markov chains and random walks on graphs Unfinished monograph, recompiled 2014. https://www.stat.berkeley.edu/∼aldous/RWG/book.html
  38. 38. 
    Kemeny JG, Snell JL. 1976. Finite Markov Chains New York: Springer
  39. 39. 
    Norris JR. 1997. Markov Chains Cambridge, UK: Cambridge Univ. Press https://doi.org/10.1017/CBO9780511810633
    [Crossref]
  40. 40. 
    Cover TM, Thomas JA. 2012. Elements of Information Theory New York: Wiley & Sons
  41. 41. 
    Ekroot L, Cover TM. 1993. The entropy of Markov trajectories. IEEE Trans. Inf. Theory 39:1418–21 https://doi.org/10.1109/18.243461
    [Crossref] [Google Scholar]
  42. 42. 
    OpenStreetMap 2020. uMap. OpenStreetMap Wiki https://wiki.openstreetmap.org/wiki/UMap
    [Google Scholar]
  43. 43. 
    Duan X, George M, Patel R, Bullo F 2020. Robotic surveillance based on the meeting time of random walks. IEEE Trans. Robot. 36:1356–62 https://doi.org/10.1109/TRO.2020.2990362
    [Crossref] [Google Scholar]
  44. 44. 
    Hunter JJ. 2014. The role of Kemeny's constant in properties of Markov chains. Commun. Stat. Theory Methods 43:1309–21 https://doi.org/10.1080/03610926.2012.741742
    [Crossref] [Google Scholar]
  45. 45. 
    Kirkland S. 2014. On the Kemeny constant and stationary distribution vector for a Markov chain. Electron. J. Linear Algebra 27:354–72 https://doi.org/10.13001/1081-3810.1624
    [Crossref] [Google Scholar]
  46. 46. 
    Ghosh A, Boyd S, Saberi A 2008. Minimizing effective resistance of a graph. SIAM Rev 50:37–66 https://doi.org/10.1137/050645452
    [Crossref] [Google Scholar]
  47. 47. 
    Agharkar P, Bullo F. 2016. Quickest detection over robotic roadmaps. IEEE Trans. Robot. 32:252–59 https://doi.org/10.1109/TRO.2015.2506165
    [Crossref] [Google Scholar]
  48. 48. 
    Grant M, Boyd S. 2020. CVX: Matlab software for disciplined convex programming. CVX Research http://cvxr.com/cvx
    [Google Scholar]
  49. 49. 
    Jung K, Shah D, Shin J 2010. Distributed averaging via lifted Markov chains. IEEE Trans. Inf. Theory 56:634–47 https://doi.org/10.1109/TIT.2009.2034777
    [Crossref] [Google Scholar]
  50. 50. 
    Weichsel PM. 1962. The Kronecker product of graphs. Proc. Am. Math. Soc. 13:47–52 https://doi.org/10.2307/2033769
    [Crossref] [Google Scholar]
  51. 51. 
    Burda Z, Duda J, Luck JM, Waclaw B 2009. Localization of the maximal entropy random walk. Phys. Rev. Lett. 102:160602 https://doi.org/10.1103/PhysRevLett.102.160602
    [Crossref] [Google Scholar]
  52. 52. 
    Guiasu S, Shenitzer A. 1985. The principle of maximum entropy. Math. Intell. 7:42–48 https://doi.org/10.1007/BF03023004
    [Crossref] [Google Scholar]
  53. 53. 
    Wang H. 2019. RoboSurv. GitHub https://github.com/HanWang99/RoboSurv
    [Google Scholar]
/content/journals/10.1146/annurev-control-071520-120123
Loading
Markov Chain–Based Stochastic Strategies for Robotic Surveillance
Annual Review of Control, Robotics, and Autonomous Systems 4, 243 (2021); https://doi.org/10.1146/annurev-control-071520-120123
/content/journals/10.1146/annurev-control-071520-120123
/content/journals/10.1146/annurev-control-071520-120123
Loading

Data & Media loading...

  • Article Type: Review Article

Most Cited Most Cited RSS feed

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error