{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:55:33Z","timestamp":1777715733912,"version":"3.51.4"},"reference-count":15,"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>This paper prescribes an incremental procedure to construct roadmaps of unknown environments. Recall that a roadmap is a geometric structure that a robot uses to plan a path between two points in an environment. If the robot knows the roadmap, then it knows the environment. Likewise, if the robot constructs the roadmap, then it has effectively explored the environment. This paper focuses on the hierarchical generalized Voronoi graph (HGVG), detailed in the companion paper in this issue. The incremental construction procedure of the HGVG requires only local distance sensor measurements, and therefore the method can be used as a basis for sensor-based planning algorithms. Simulations and experiments using a mobile robot with ultrasonic sensors verify this approach.<\/jats:p>","DOI":"10.1177\/02783640022066789","type":"journal-article","created":{"date-parts":[[2004,12,17]],"date-time":"2004-12-17T20:23:10Z","timestamp":1103314990000},"page":"126-148","source":"Crossref","is-referenced-by-count":119,"title":["Sensor-Based Exploration: Incremental Construction of 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":"Sean","family":"Walker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunnayut","family":"Eiamsa-Ard","sequence":"additional","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","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":"atypb2","doi-asserted-by":"crossref","unstructured":"Borenstein, J., and Koren, J. 1990 (May). Real-time obstacle avoidance for fast mobile robots in cluttered environments . IEEE Conference of Robotics and Automation, pp. 572\u2013577 .","DOI":"10.1109\/ROBOT.1990.126042"},{"key":"atypb3","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":"atypb4","unstructured":"Canny, J. F. 1988. The Complexity of Robot Motion Planning Cambridge, MA: MIT Press ."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01891836"},{"key":"atypb6","unstructured":"Choset, H. 1996.\n                      Sensor Based Motion Planning: The Hierarchical Generalized Voronoi Graph\n                      . Ph.D. thesis, California Institute of Technology, Pasadena, CA."},{"key":"atypb7","unstructured":"Choset, H. 1998. Nonsmooth analysis, convex analysis, and their applications to motion planning . Special Issue of the Int. J. of Comp. Geom. and Apps., to appear."},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"Choset, H., and Burdick, J. W. 1994. Sensor based planning and nonsmooth analysis . Proc. IEEE Int. Conf. on Robotics and Automation, pp. 3034\u20133041 .","DOI":"10.1109\/ROBOT.1994.351103"},{"key":"atypb9","unstructured":"Choset, H., and Burdick, J. W. 1995. Sensor based planning, Part I: The generalized Voronoi graph . Proc. IEEE Int. Conf. on Robotics and Automation."},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"Choset, H., and Burdick, J. 2000. Sensor-based motion Exploration: The hierarchical generalized Voronoi graph . International Journal of Robotics Research 19: 119\u2013148 .","DOI":"10.1177\/02783640022066789"},{"key":"atypb11","unstructured":"Keller, H. B. 1987. Lectures on Numerical Methods in Bifurcation Problems. Bombay, India: Tata Institute of Fundamental Research ."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/0921-8890(91)90014-C"},{"key":"atypb13","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":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/70.97883"},{"key":"atypb15","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, pp. 117\u2013124 .","DOI":"10.1109\/ROBOT.1994.351001"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783640022066789","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783640022066789","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\/02783640022066789"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,2]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,2]]}},"alternative-id":["10.1177\/02783640022066789"],"URL":"https:\/\/doi.org\/10.1177\/02783640022066789","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,2]]}}}