{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:42:40Z","timestamp":1777714960842,"version":"3.51.4"},"reference-count":10,"publisher":"SAGE Publications","issue":"6","license":[{"start":{"date-parts":[[1990,12,1]],"date-time":"1990-12-01T00:00:00Z","timestamp":660009600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[1990,12]]},"abstract":"<jats:p>\n                    We present an efficient algorithm for finding least-cost paths for an agent of negligible size across an important special case of two-dimensional terrain, terrain consisting of (1) a single isotropic homogeneous-cost-per-distance background region, (2) \"roads\" or narrow transportation corridors of low cost per distance, (3) \"rivers\" or narrow features of high crossing cost, and (4) untraversable \"obstacles. \" This work extends that of Mitchell (1987) by including rivers and new pruning heuristics for roads; our algorithm remains O(n\n                    <jats:sup>2<\/jats:sup>\n                    log n) in time complexity. We also show results of a first com puter implementation for this class of algorithms and analyze average-case performance and error sensitivity. This work applies primarily to high-level path planning for robots but also can help plan military maneuvers and guide construction of roads and pipelines.\n                  <\/jats:p>","DOI":"10.1177\/027836499000900606","type":"journal-article","created":{"date-parts":[[2007,3,4]],"date-time":"2007-03-04T20:24:06Z","timestamp":1173039846000},"page":"67-74","source":"Crossref","is-referenced-by-count":10,"title":["Roads, Rivers, and Obstacles: Optimal Two-Dimensional Path Planning around Linear Features for a Mobile Agent"],"prefix":"10.1177","volume":"9","author":[{"given":"Neil C.","family":"Rowe","sequence":"first","affiliation":[{"name":"Department of Computer Science U.S. Naval Postgraduate School Monterey, California 93943"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[1990,12,1]]},"reference":[{"key":"atypb1","volume-title":"Construction of optimal-path maps for homogeneous-cost-region path-planning problems. Ph.D. Thesis","author":"Alexander, R.","year":"1989"},{"key":"atypb2","first-page":"1777","volume":"24","author":"de Champeaux, B.","year":"1977","journal-title":"J. ACM"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"Chavez, R., and Meystel, A. 1984 (Atlanta) Structure of intelligence for an autonomous vehicle. IEEE International Conference on Robotics and Automation. New York: IEEE, pp. 584-591.","DOI":"10.1109\/ROBOT.1984.1087160"},{"key":"atypb4","volume-title":"Proceedings of the Fourth Annual ACM Symposium on Computational Geometry","author":"Gewali, L."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/359156.359164"},{"key":"atypb6","volume-title":"Paper delivered at the Joint National Meeting of TIMS\/ORSA","author":"Mitchell, J.S.B."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(88)90054-9"},{"key":"atypb8","volume-title":"SPIE Conference on Applications of Artificial Intelligence","author":"Mitchell, J.S.B."},{"key":"atypb9","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Richbourg, R."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1177\/027836499000900605"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836499000900606","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836499000900606","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:13:24Z","timestamp":1777457604000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/027836499000900606"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,12]]},"references-count":10,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1990,12]]}},"alternative-id":["10.1177\/027836499000900606"],"URL":"https:\/\/doi.org\/10.1177\/027836499000900606","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,12]]}}}