{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T04:33:12Z","timestamp":1774499592141,"version":"3.50.1"},"reference-count":49,"publisher":"SAGE Publications","issue":"8","license":[{"start":{"date-parts":[[2017,7,1]],"date-time":"2017-07-01T00:00:00Z","timestamp":1498867200000},"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":[[2017,7]]},"abstract":"<jats:p> This paper computes a minimum-length pursuer trajectory that solves a visibility-based pursuit-evasion problem in which a single pursuer moving through a simply-connected polygonal environment seeks to locate an evader which may move arbitrarily fast, using an omni-directional field-of-view that extends to the environment boundary. We present a complete algorithm that computes a minimum-cost pursuer trajectory that ensures that the evader is captured, or reports in finite time that no such trajectory exists. This result improves upon the known algorithm of Guibas, Latombe, LaValle, Lin, and Motwani, which is complete but makes no guarantees about the quality of the solution. Our algorithm employs a branch-and-bound forward search that considers pursuer trajectories that could potentially lead to an optimal pursuer strategy. The search is performed on an exponential graph that can generate an infinite number of unique pursuer trajectories, so we must conduct meticulous pruning during the search to quickly discard pursuer trajectories that are demonstrably suboptimal. We describe an implementation of the algorithm, along with experiments that measure its performance in several environments with a variety of pruning operations. <\/jats:p>","DOI":"10.1177\/0278364917711535","type":"journal-article","created":{"date-parts":[[2017,7,21]],"date-time":"2017-07-21T11:50:40Z","timestamp":1500637840000},"page":"923-946","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":23,"title":["Complete and optimal visibility-based pursuit-evasion"],"prefix":"10.1177","volume":"36","author":[{"given":"Nicholas M","family":"Stiffler","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of South Carolina, USA"}]},{"given":"Jason M","family":"O\u2019Kane","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of South Carolina, USA"}]}],"member":"179","published-online":{"date-parts":[[2017,7,21]]},"reference":[{"key":"bibr1-0278364917711535","first-page":"5","volume":"59","author":"Alspach B","year":"2004","journal-title":"Matematiche"},{"key":"bibr2-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73424-6_2"},{"key":"bibr3-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/005\/02"},{"key":"bibr4-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1201\/b16132-68"},{"key":"bibr5-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1002\/rob.20216"},{"key":"bibr6-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574671"},{"key":"bibr7-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780612"},{"key":"bibr8-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-011-9260-1"},{"key":"bibr9-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.02.040"},{"key":"bibr10-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906065023"},{"key":"bibr11-0278364917711535","first-page":"923","volume":"25","author":"Golovach P","year":"1989","journal-title":"Differentsial\u2019nye Uraveniya (Differential Equations)"},{"key":"bibr12-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000273"},{"key":"bibr13-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1965.1098197"},{"key":"bibr14-0278364917711535","volume-title":"Differential Games","author":"Isaacs R","year":"1965"},{"issue":"21","key":"bibr15-0278364917711535","first-page":"864","volume":"5","author":"Isler V","year":"2005","journal-title":"IEEE Transactions on Robotics"},{"key":"bibr16-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2009.5354443"},{"key":"bibr17-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462364"},{"key":"bibr18-0278364917711535","first-page":"1195","volume-title":"Proceedings of the international conference on autonomous agents and multiagent systems","author":"Kleiner A","year":"2013"},{"key":"bibr19-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630990"},{"key":"bibr20-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2009.5354225"},{"key":"bibr21-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2009.2035737"},{"key":"bibr22-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"bibr23-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1109\/70.928565"},{"key":"bibr24-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1142\/S021819590200075X"},{"key":"bibr25-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00235-6"},{"key":"bibr26-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840369"},{"key":"bibr27-0278364917711535","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9407.001.0001"},{"key":"bibr28-0278364917711535","first-page":"263","volume-title":"Proceedings of the workshop on the algorithmic foundations of robotics, Springer tracts in advanced robotics","volume":"86","author":"Noori N","year":"2012"},{"key":"bibr29-0278364917711535","first-page":"443","volume-title":"Proceedings of the workshop on the algorithmic foundations of robotics, Springer tracts in advanced robotics","volume":"107","author":"Noori N","year":"2014"},{"key":"bibr30-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_38"},{"key":"bibr31-0278364917711535","first-page":"426","volume-title":"Theory and Application of Graphs","author":"Parsons TD","year":"1976"},{"key":"bibr32-0278364917711535","first-page":"1345","volume":"18","author":"Petrov NN","year":"1982","journal-title":"Differentsial\u2019nye Uraveniya (Differential Equations)"},{"key":"bibr33-0278364917711535","first-page":"1366","volume":"19","author":"Petrov NN","year":"1983","journal-title":"Differentsial\u2019nye Uraveniya (Differential Equations)"},{"key":"bibr34-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2001.932894"},{"key":"bibr35-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2013.2264868"},{"key":"bibr36-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904039610"},{"key":"bibr37-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00411-4"},{"key":"bibr38-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6225266"},{"key":"bibr39-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6907074"},{"key":"bibr40-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6942796"},{"key":"bibr41-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487621"},{"key":"bibr42-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1137\/0221051"},{"key":"bibr43-0278364917711535","doi-asserted-by":"publisher","DOI":"10.3103\/S1063454113020027"},{"key":"bibr44-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908097580"},{"key":"bibr45-0278364917711535","first-page":"332","volume-title":"Proceedings of the Candadian conference on computational geometry","author":"Vander Hook J","year":"2014"},{"key":"bibr46-0278364917711535","volume-title":"Approximation Algorithms","author":"Vazirani VV","year":"2001"},{"key":"bibr47-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735"},{"key":"bibr48-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2174494"},{"key":"bibr49-0278364917711535","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2016.2521429"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364917711535","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364917711535","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364917711535","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,27]],"date-time":"2025-01-27T23:46:32Z","timestamp":1738021592000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364917711535"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7]]},"references-count":49,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["10.1177\/0278364917711535"],"URL":"https:\/\/doi.org\/10.1177\/0278364917711535","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7]]}}}