{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:55:32Z","timestamp":1777715732824,"version":"3.51.4"},"reference-count":22,"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>\n                    The hierarchical generalized Voronoi graph (HGVG) is a new roadmap developed for sensor-based exploration in unknown environments. This paper defines the HGVG structure: a robot can plan a path between two locations in its work space or configuration space by simply planning a path onto the HGVG, then along the HGVG, and finally from the HGVG to the goal. Since the bulk of the path planning occurs on the one-dimensional HGVG, motion planning in arbitrary dimensioned spaces is virtually reduced to a one-dimensional search problem. A bulk of this paper is dedicated to ensuring the HGVG is sufficient for motion planning by demonstrating the HGVG (with its links) is an arc-wise connected structure. All of the proofs in this paper that lead toward the connectivity result focus on a large subset of spaces in R\n                    <jats:sup>3<\/jats:sup>\n                    , but wherever possible, results are derived in R\n                    <jats:sup>m<\/jats:sup>\n                    . In fact, under a strict set of conditions, the HGVG (the GVG by itself) is indeed connected, and hence sufficient for motion planning. The chief advantage of the HGVG is that it possesses an incremental construction procedure, described in a companion paper, that constructs the HGVG using only line-of-sight sensor data. Once the robot constructs the HGVG, it has effectively explored the environment, because it can then use the HGVG to plan a path between two arbitrary configurations.\n                  <\/jats:p>","DOI":"10.1177\/02783640022066770","type":"journal-article","created":{"date-parts":[[2004,12,17]],"date-time":"2004-12-17T20:23:10Z","timestamp":1103314990000},"page":"96-125","source":"Crossref","is-referenced-by-count":212,"title":["Sensor-Based Exploration: The Hierarchical Generalized Voronoi Graph"],"prefix":"10.1177","volume":"19","author":[{"given":"Howie","family":"Choset","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Scaife Hall, Pittsburgh, Pennsylvania 15213 USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joel","family":"Burdick","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Mail Code 104-44, Pasadena,                         California 91125 USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2000,2,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"Abraham, R., Marsden, J. E., and Ratiu, T. 1988. Manifolds, Tensor Analysis, and Applications. 2d ed. New York: Springer-Verlag .","DOI":"10.1007\/978-1-4612-1029-0"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"atypb3","unstructured":"Avis, D., and Bhattacharya, B. K. 1983. Algorithms for computing D-dimensional Voronoi diagrams and their duals . Advances in Computing Research 1: 159\u2013180 ."},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"Brooks, R. A. 1986. A robust layered control system for a mobile robot . IEEE Journal on Robotics and Automation RA-2(March).","DOI":"10.1109\/JRA.1986.1087032"},{"key":"atypb5","unstructured":"Canny, J. F. 1988. The Complexity of Robot Motion Planning. Cambridge, MA: MIT Press ."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01891836"},{"key":"atypb7","unstructured":"Choset, H. 1998. Nonsmooth analysis, convex analysis, and their applications to motion planning . Special issue of Int. J. Comp. Geom. and Apps. To appear."},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"Choset, H., and Burdick, J. 2000. Sensor based exploration: Incremental construction of the hierarchical generalized Voronoi graph . International Journal of Robotics Research 19: 96\u2013118 .","DOI":"10.1177\/02783640022066770"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"Choset, H., and Burdick, J. W. 1994. Sensor based planning and nonsmooth analysis . Proc.IEEEInt.Conf.on Robotics and Automation, San Diego, CA, pp. 3034\u20133041 .","DOI":"10.1109\/ROBOT.1994.351103"},{"key":"atypb10","unstructured":"Choset, Howie. 1996. Sensor based motion planning: The hierarchical generalized Voronoi graph. Ph.D. thesis, California Institute of Technology, Pasadena."},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"Clarke, F. H. 1990. Optimization and Nonsmooth Analysis. Philadelphia, PA: Society of Industrial and Applied Mathematics .","DOI":"10.1137\/1.9781611971309"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"Gat, E., and Dorais, G. 1994 (May). Robot Navigation by Conditional Sequencing . Proc. IEEE Int. Conf. on Robotics and Automation, San Diego, CA, pp. 1293\u20131299 .","DOI":"10.1109\/ROBOT.1994.351308"},{"key":"atypb13","unstructured":"Kutulakos, K. N., Dyer, C. R., and Lumelsky, V. J. 1994 (May). Provable strategies for vision-guided exploration in three dimensions . IEEE Int. Conf. on Robotics and Automation, San Diego, CA."},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"Latombe, J. C. 1991. Robot Motion Planning. Boston, MA: Kluwer Academic .","DOI":"10.1007\/978-1-4615-4022-9"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840369"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90021-5"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"Rao, N.S.V., Kareti, S., Shi, W., and Iyenagar, S. S. 1993. Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms . Oak Ridge National Laboratory Technical Report ORNL\/TM-12410(July): 1\u201358 .","DOI":"10.2172\/10180101"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/70.97883"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"Rimon, E., and Canny, J. F. 1994. Construction of C-space roadmaps using local sensory data\u2014What should the sensors look for? Proc. IEEE Int. Conf. on Robotics and Automation, San Diego, CA, pp. 117\u2013124 .","DOI":"10.1109\/ROBOT.1994.351001"},{"key":"atypb20","unstructured":"Rowat, P. F. 1979. Representing the spatial experience and solving spatial problems in a simulated robot environment. Ph.D. thesis, University of British Columbia."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/BF00940519"},{"key":"atypb22","unstructured":"Schwartz, J. T., and Yap, C. K., eds. 1987. Advances in Robotics: Algorithmic and Geometric Aspects of Robotics. Vol. 1. Hillsdale, NJ: Lawrence Erlbaum ."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783640022066770","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783640022066770","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:04Z","timestamp":1777457764000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783640022066770"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,2]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,2]]}},"alternative-id":["10.1177\/02783640022066770"],"URL":"https:\/\/doi.org\/10.1177\/02783640022066770","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,2]]}}}