{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:56:41Z","timestamp":1777715801496,"version":"3.51.4"},"reference-count":36,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"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":[[2001,1]]},"abstract":"<jats:p>This paper is concerned with the problem of sensor-based navigation in three dimensions. The robot, which is modeled as a \u201cbug\u201d or a \u201cpoint robot,\u201d has no a priori knowledge of the environment. It must rather use its sensors to perceive the environment and plan a collision-free path to various targets. The robot is further required to navigate in the most reactive way possible, retaining the smallest amount of information required for global convergence to the target. We assume a three-dimensional polyhedral environment and present two basic results for sensor-based navigation in this environment. First we establish sufficient conditions for range-sensor-based exploration of the entire surface of a general polyhedron and present a strategy for performing this task. Then we characterize the locally shortest path from the current robot location to the target and present a method for estimating this path in time that is linear with the problem size. Based on these results, we present a range-sensor-based navigation algorithm for a bug robot in a general three-dimensional polyhedral environment. The algorithm, called 3 DBug, strives to process the sensory data in the most reactive way possible, without sacrificing its global convergence guarantee. The algorithm uses two modes of motion, called motion-toward-the-target and obstacle- surface-traversal. During the first mode of motion, the robot follows the locally shortest path to the target in a purely reactive fashion. During the second mode of motion, the robot attempts to reach exit points along an obstacle surface, while simultaneously expanding its knowledge of the obstacle based on range data. We provide analysis of the algorithm, showing that if the target is reachable, the robot always finds obstacle exit points from which it reaches the target. Otherwise, the robot eventually possesses full knowledge of the obstacle blocking its path to the target and determines that the target is unreachable. We have also implemented and verified the algorithm on three-dimensional simulated environments. The simulation results show that 3 DBug generates paths that resemble the globally shortest path in simple scenarios and reasonably short paths in concave roomlike environments.<\/jats:p>","DOI":"10.1177\/02783640122067246","type":"journal-article","created":{"date-parts":[[2003,7,19]],"date-time":"2003-07-19T02:59:46Z","timestamp":1058583586000},"page":"6-25","source":"Crossref","is-referenced-by-count":7,"title":["Range-Sensor-Based Navigation in Three-Dimensional Polyhedral Environments"],"prefix":"10.1177","volume":"20","author":[{"given":"Ishay","family":"Kamon","sequence":"first","affiliation":[{"name":"CS Department, Technion\u2014Israel Institute of Technology,                         Technion City, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elon","family":"Rimon","sequence":"additional","affiliation":[{"name":"ME Department, Technion\u2014Israel Institute of Technology,                         Technion City, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ehud","family":"Rivlin","sequence":"additional","affiliation":[{"name":"CS Department, Technion\u2014Israel Institute of Technology,                         Technion City, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2001,1,1]]},"reference":[{"key":"atypb1","unstructured":"Blake, A., Zisserman, A., and Cipolla, R. 1992. Visual Exploration of Free-Space. Cambridge, MA: MIT Press ."},{"key":"atypb2","unstructured":"Canny, J. F. 1988. The Complexity of Robot Motion Planning. Cambridge, MA: MIT Press ."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0921-8890(96)81009-8"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"Choi, J., Sellen, J., and Yap, C. K. 1994. Approximate Euclidean shortest path in 3-space . 10th Annual ACM Symposium on Computational Geometry, pp. 41\u201348 .","DOI":"10.1145\/177424.177501"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"Choset, H., and Burdick, J. W. 1995. Sensor based planning, partii: Incremental construction of the generalized voronoi graph . IEEE Conference on Robotics and Automation, Nagoya, Japan, May, pp. 1643\u20131649 .","DOI":"10.1109\/ROBOT.1995.525510"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"Connoly, C. 1985. The determination of next best views . IEEE Conference on Robotics and Automation, pp. 432\u2013435 .","DOI":"10.1109\/ROBOT.1985.1087372"},{"key":"atypb7","unstructured":"Cox, J., and Yap, C. K. 1988. On-line motion planning: Moving a planar arm by probing an unknown environment . Technical report, Courant Institute of Mathematical sciences, New York University, July."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1002\/rob.4620080505"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/0165-1684(93)90034-8"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/70.210800"},{"key":"atypb11","unstructured":"Kamon, I. 1997.\n                      Locally Optimal Sensor-Based Robot Navigation\n                      . Ph.D. thesis, Technion\u2014Israel Institute of Technology, Technion City, Israel."},{"key":"atypb12","unstructured":"Kamon, I., Rimon, E., and Rivlin, E. Forthcoming. Tangent-bug: A range-sensor based navigation algorithm . International Journal on Robotic Research."},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"Kutulakos, K. N., Dyer, C. R., and Lumelsky, V. J. 1994. Provable strategies for vision-guided exploration in three dimensions . IEEE Conference on Robotics and Automation, San Diego, CA, May, pp. 1365\u20131372 .","DOI":"10.1109\/ROBOT.1994.351298"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"Kutulakos, K. N., Lumelsky, V. J., and Dyer, C. R. 1993. Vision guided exploration: A step toward general motion planning in three dimensions . IEEE Conference on Robotics and Automation, Atlanta, GA, May, pp. 289\u2013296 .","DOI":"10.1109\/ROBOT.1993.291997"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"Laubach, S. L., Burdick, J. W., and Matthies, L. 1998. An autonomous path planner implemented on the rocky7 prototype microrover . IEEE Conference on Robotics and Automation, pp. 292\u2013297 .","DOI":"10.1109\/ROBOT.1998.676401"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1177\/027836499201100409"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/359156.359164"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/70.68070"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840369"},{"key":"atypb20","unstructured":"March, E., and Chaumette, F. 1997. Active sensor placement for complete scene reconstruction and exploration . IEEE Conference on Robotics and Automation, pp. 743\u2013750 ."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1109\/34.211463"},{"key":"atypb22","unstructured":"Nayar, S. 1997. Catadioptric omnidirectional cameras. CVPR97, pp. 331\u2013339."},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"Noborio, H., and Yoshioka, T. 1993. Anon-lineanddeadlock-free path-planning algorithm based on world topology . IEEE\/RSJ Conference on Intelligent Robots and Systems, IROS, pp. 1425\u20131430 .","DOI":"10.1109\/IROS.1993.583806"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90029-8"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/56.812"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(90)90097-J"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523678"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90045-1"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"Sankaranarayanan, A., and Vidyasagar, M. 1991. Path planning for moving a point object amidst unknown obstacles in a plane: The universal lower bound on worst case path lengths and a classification of algorithms . IEEE Conference on Robotics and Automation, Sacramento, CA, April, pp. 1734\u20131941 .","DOI":"10.1109\/ROBOT.1991.131871"},{"key":"atypb30","unstructured":"Stentz, A. 1994. Optimal and efficient path planning for partially known environments . IEEE Conference on Robotics and Automation, San Diego, CA, May, pp. 3310\u20133317 ."},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"Svoboda, T., Pajdla, T., and Hlavac, V. 1998. Epipolar geometry for panoramic cameras. ECCV98, pp. 218\u2013231.","DOI":"10.1007\/BFb0055669"},{"key":"atypb32","unstructured":"Technion - Israel Institute of Technology. 1997. Irit 7.0 User\u2019s Manual. Technion City, Israel, www.cs.technion.ac.il\/irit, February."},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"Thorpe, J. A. 1979. Elementary Topics in Differential Geometry. New York: Springer-Verlag .","DOI":"10.1007\/978-1-4612-6153-7"},{"key":"atypb34","unstructured":"TITAN. 1996. A telerobotic manipulator for nuclear inspection and maintenance. Schilling Robotic Systems."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1109\/34.99237"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.2307\/1970070"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783640122067246","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783640122067246","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:28Z","timestamp":1777457788000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783640122067246"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1177\/02783640122067246"],"URL":"https:\/\/doi.org\/10.1177\/02783640122067246","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}