{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:55:31Z","timestamp":1777715731210,"version":"3.51.4"},"reference-count":21,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2000,2,1]],"date-time":"2000-02-01T00:00:00Z","timestamp":949363200000},"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":[[2000,2]]},"abstract":"<jats:p>Optimal-path maps tell robots or people the best way to reach a goal point from anywhere in a known terrain area, eliminating most of the need to plan during travel. The authors address the construction of optimal-path maps for two-dimensional polygonal weighted-region terrain, terrain partitioned into polygonal areas such that the cost per unit of distance traveled is homogeneous and isotropic within each area. This is useful for overland route planning across varied ground surfaces and vegetation. The authors propose a new algorithm that recursively partitions terrain into regions of similar optimal-path behavior, and defines corresponding \u201cpath subspaces\u201d for these regions. This process constructs a piecewise-smooth function of terrain position whose gradient direction is everywhere the optimal-path direction, permitting quick path finding. The algorithm used is more complicated than the current path-caching and wavefront-propagation algorithms, but it gives more accurate maps requiring less space to represent. Experiments with an implementation confirm the practicality of the authors\u2019 algorithm.<\/jats:p>","DOI":"10.1177\/02783640022066761","type":"journal-article","created":{"date-parts":[[2004,12,17]],"date-time":"2004-12-17T20:23:10Z","timestamp":1103314990000},"page":"83-95","source":"Crossref","is-referenced-by-count":18,"title":["Finding Optimal-Path Maps for Path Planning across Weighted Regions"],"prefix":"10.1177","volume":"19","author":[{"given":"Neil C.","family":"Rowe","sequence":"first","affiliation":[{"name":"Computer Science Department, Code CS\/Rp, U.S. Naval Postgraduate School,                         Monterey, California 93943 USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert S.","family":"Alexander","sequence":"additional","affiliation":[{"name":"Computer Science Department, Code CS\/Rp, U.S. Naval Postgraduate School,                         Monterey, California 93943 USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2000,2,1]]},"reference":[{"key":"atypb1","unstructured":"Alexander, R. S. 1989 (September). Construction of optimal-path maps for homogeneous-cost-region path-planning problems. Ph.D. thesis, Department of Computer Science, U.S. Naval Postgraduate School, Monterey, CA."},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"Alexander, R. S. and Rowe, N. C. 1990 (May). Path planning by optimal-path-map construction for homogeneous-cost two-dimensional regions . Proceedings of IEEE International Conference on Robotics and Automation, Cincinnati, OH, pp. 1924\u20131929 .","DOI":"10.1109\/ROBOT.1990.126289"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"Chen, D. Z., Klenk, K. S., and Tu, H.Y. T. 1995. Shortest path queries among weighted obstacles in the rectilinear plane . Proceedings of the 11th Annual ACM Symposium on Computational Geometry, Vancouver, BC, pp. 370\u2013379 .","DOI":"10.1145\/220279.220319"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"Chew, L. P., and Drysdale, R. L. 1985 (June). Voronoi diagrams based on convex distance functions . ACM Symposium on Computational Geometry, Baltimore, MD, pp. 235\u2013244 .","DOI":"10.1145\/323233.323264"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/136035.136037"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"Kambhampati, S., and Davis, L.S. 1986. Multi resolution path planning for mobile robots . IEEE Journal of Robotics and Automation RA-2(3): 135\u2013145 .","DOI":"10.1109\/JRA.1986.1087051"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/0210006"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140304"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(88)90054-9"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"Mitchell, J.S.B. 1993 (May). Shortest paths among obstacles in the plane . Proceedings of the Ninth Annual ACM Symposium on Computational Geometry, San Diego, CA, pp. 308\u2013317 .","DOI":"10.1145\/160985.161156"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102784"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"Mitchell, J.S.B., Payton, D. W., and Keirsey, D. M. 1986. Planning and reasoning for autonomous vehicle control . International Journal of Intelligent Systems 11: 129\u2013198 .","DOI":"10.1002\/int.4550020204"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"Mobasseri, B. G. 1990 (November). Impact of uncertain terrain models on the weighted region problem . Proceedings of Mobile Robots V, SPIE (The International Society for Optical Engineering), vol. 1388, Boston, MA, pp. 269\u2013277 .","DOI":"10.1117\/12.25509"},{"key":"atypb14","unstructured":"Nilsson, N. 1980. Principles of Artificial Intelligence. Palo Alto, CA: Tioga ."},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"Parodi, A. M. 1985. Multi-goal real-time global path planning for an autonomous land vehicle using a high speed graph search processor. Proceedings of the 1985 IEEE Conference on Robotics and Automation. New York: IEEE Press , pp. 161\u2013167.","DOI":"10.1109\/ROBOT.1985.1087298"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"Payton, D. W., and Bihari, T. E. 1991 (August). Intelligent real-time control of robotic vehicles . Communications of the ACM 34(8): 48\u201363 .","DOI":"10.1145\/108515.108527"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/185675.185795"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1177\/027836499000900606"},{"key":"atypb19","unstructured":"Rowe, N. C., and Alexander, R. S. 1997 (January). Path planning across weighted regions using optimal-path maps. Technical report, U.S. Naval Postgraduate School, Monterey, CA ."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1177\/027836499000900605"},{"key":"atypb21","unstructured":"Schoppers, M. J. 1989 (Winter). In defense of reaction plans as caches . AI Magazine 10(4): 51\u201360 ."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783640022066761","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783640022066761","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:03Z","timestamp":1777457763000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783640022066761"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,2]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,2]]}},"alternative-id":["10.1177\/02783640022066761"],"URL":"https:\/\/doi.org\/10.1177\/02783640022066761","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,2]]}}}