{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T10:06:39Z","timestamp":1777716399872,"version":"3.51.4"},"reference-count":31,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2013,10,4]],"date-time":"2013-10-04T00:00:00Z","timestamp":1380844800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>\n                    In this paper, we consider the problem of planning a path for a robot to monitor a known set of features of interest in an environment. We represent the environment as a graph with vertex weights and edge lengths. The vertices represent regions of interest, edge lengths give travel times between regions and the vertex weights give the importance of each region. As the robot repeatedly performs a closed walk on the graph, we define the weighted latency of a vertex to be the maximum time between visits to that vertex, weighted by the importance (vertex weight) of that vertex. Our goal is to find a closed walk that minimizes the maximum weighted latency of any vertex. We show that there does not exist a polynomial time algorithm for the problem. We then provide two approximation algorithms; an O(log n)-approximation algorithm and an O(log \u03c1\n                    <jats:sub>G<\/jats:sub>\n                    )-approximation algorithm, where \u03c1\n                    <jats:sub>G<\/jats:sub>\n                    is the ratio between the maximum and minimum vertex weights. We provide simulation results which demonstrate that our algorithms can be applied to problems consisting of thousands of vertices and a case study for patrolling a city for crime.\n                  <\/jats:p>","DOI":"10.1177\/0278364913504011","type":"journal-article","created":{"date-parts":[[2013,10,4]],"date-time":"2013-10-04T23:07:00Z","timestamp":1380928020000},"page":"138-154","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":89,"title":["Persistent monitoring in discrete environments: Minimizing the maximum weighted latency between observations"],"prefix":"10.1177","volume":"33","author":[{"given":"Soroush","family":"Alamdari","sequence":"first","affiliation":[{"name":"Department of Computer Science, Cornell University, Ithaca, NY, USA"}]},{"given":"Elaheh","family":"Fata","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Waterloo, Canada"}]},{"given":"Stephen L","family":"Smith","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Waterloo, Canada"}]}],"member":"179","published-online":{"date-parts":[[2013,10,4]]},"reference":[{"key":"bibr1-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36279-8_9"},{"key":"bibr2-0278364913504011","unstructured":"Arvelo E, Kim E, Martins NC (2012) Memoryless control design for persistent surveillance under safety constraints. arXiv.org. Submitted: 26 September 2012. Available at: http:\/\/arxiv.org\/abs\/1209.5805."},{"key":"bibr3-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2008.4586976"},{"key":"bibr4-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2010.5531611"},{"key":"bibr5-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5"},{"key":"bibr6-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2011.2158181"},{"key":"bibr7-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2104510"},{"key":"bibr8-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2011.6160379"},{"key":"bibr9-0278364913504011","first-page":"302","volume-title":"IEEE\/WIC\/ACM international conference intelligent agent technology","author":"Chevaleyre Y","year":"2004"},{"key":"bibr10-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016639210559"},{"key":"bibr11-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140205"},{"key":"bibr12-0278364913504011","unstructured":"Cook WJ (2009) National travelling salesman problems. Available at: http:\/\/www.tsp.gatech.edu\/index.html."},{"key":"bibr13-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2007.363817"},{"key":"bibr14-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(02)00110-4"},{"key":"bibr15-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20807-2_19"},{"key":"bibr16-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1109\/TCST.2007.899155"},{"key":"bibr17-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1090.0301"},{"key":"bibr18-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.498"},{"key":"bibr19-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6631066"},{"key":"bibr20-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2011.6095174"},{"key":"bibr21-0278364913504011","first-page":"1","volume-title":"IEEE Aerospace Conference","author":"Nigram N","year":"2008"},{"key":"bibr22-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.1.1"},{"key":"bibr23-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2012.2201293"},{"key":"bibr24-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2179580"},{"key":"bibr25-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1002\/rob.20405"},{"key":"bibr26-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2010.5717132"},{"key":"bibr27-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2174493"},{"key":"bibr28-0278364913504011","doi-asserted-by":"publisher","DOI":"10.1109\/CASE.2011.6042503"},{"key":"bibr29-0278364913504011","doi-asserted-by":"publisher","DOI":"10.3182\/20050703-6-CZ-1902.00361"},{"key":"bibr30-0278364913504011","doi-asserted-by":"crossref","unstructured":"Tulabandhula T, Rudin C, Jaillet P (2011) Machine learning and the traveling repairman. Available at: http:\/\/arxiv.org\/abs\/1104.5061.","DOI":"10.1007\/978-3-642-24873-3_20"},{"key":"bibr31-0278364913504011","volume-title":"Approximation Algorithms","author":"Vazirani VV","year":"2004"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364913504011","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364913504011","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364913504011","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:18:15Z","timestamp":1777457895000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364913504011"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,4]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1177\/0278364913504011"],"URL":"https:\/\/doi.org\/10.1177\/0278364913504011","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,4]]}}}