{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T17:38:08Z","timestamp":1784137088513,"version":"3.55.0"},"reference-count":34,"publisher":"SAGE Publications","issue":"10-11","license":[{"start":{"date-parts":[[2002,10,1]],"date-time":"2002-10-01T00:00:00Z","timestamp":1033430400000},"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":[[2002,10]]},"abstract":"<jats:p>In this paper, we investigate safe and efficient map-building strategies for a mobile robot with imperfect control and sensing. In the implementation, a robot equipped with a range sensor builds apolygonal map (layout) of a previously unknown indoor environment. The robot explores the environment and builds the map concurrently by patching together the local models acquired by the sensor into a global map. A well-studied and related problem is the simultaneous localization and mapping (SLAM) problem, where the goal is to integrate the information collected during navigation into the most accurate map possible. However, SLAM does not address the sensor-placement portion of the map-building task. That is, given the map built so far, where should the robot go next? This is the main question addressed in this paper. Concretely, an algorithm is proposed to guide the robot through a series of \u201cgood\u201d positions, where \u201cgood\u201d refers to the expected amount and quality of the information that will be revealed at each new location. This is similar to the next-best-view (NBV) problem studied in computer vision and graphics. However, in mobile robotics the problem is complicated by several issues, two of which are particularly crucial. One is to achieve safe navigation despite an incomplete knowledge of the environment and sensor limitations (e.g., in range and incidence). The other issue is the need to ensure sufficient overlap between each new local model and the current map, in order to allow registration of successive views under positioning uncertainties inherent to mobile robots. To address both issues in a coherent framework, in this paper we introduce the concept of a safe region, defined as the largest region that is guaranteed to be free of obstacles given the sensor readings made so far. The construction of a safe region takes sensor limitations into account. In this paper we also describe an NBV algorithm that uses the safe-region concept to select the next robot position at each step. The new position is chosen within the safe region in order to maximize the expected gain of information under the constraint that the local model at this new position must have a minimal overlap with the current global map. In the future, NBV and SLAM algorithms should reinforce each other. While a SLAM algorithm builds a map by making the best use of the available sensory data, an NBV algorithm, such as that proposed here, guides the navigation of the robot through positions selected to provide the best sensory inputs.<\/jats:p>","DOI":"10.1177\/0278364902021010834","type":"journal-article","created":{"date-parts":[[2003,4,28]],"date-time":"2003-04-28T06:25:30Z","timestamp":1051511130000},"page":"829-848","source":"Crossref","is-referenced-by-count":351,"title":["Navigation Strategies for Exploring Indoor Environments"],"prefix":"10.1177","volume":"21","author":[{"given":"H\u00e9ctor H.","family":"Gonz\u00e1lez-Ba\u00f1os","sequence":"first","affiliation":[{"name":"Honda R&D, Americas 800 California St. Suite 300 Mountain View, CA 94041, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jean-Claude","family":"Latombe","sequence":"additional","affiliation":[{"name":"Department of Computer Science Stanford University Stanford, CA 94305, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2002,10,1]]},"reference":[{"key":"bibr1-0278364902021010834","doi-asserted-by":"publisher","DOI":"10.1117\/12.222691"},{"key":"bibr2-0278364902021010834","doi-asserted-by":"crossref","unstructured":"Briggs A. J., and Donald B. R. 1994. Automatic sensor configuration for task-directed planning. In IEEE Int. Conf. on Robotics and Automation 1345\u20131350.","DOI":"10.1109\/ROBOT.1994.351301"},{"key":"bibr3-0278364902021010834","doi-asserted-by":"crossref","unstructured":"Burgard R., Moors M., Fox D., Simmons R., and Thrun S. 2000. Collaborative multi-robot exploration. In IEEE Int. Conf. Robotics & Automation, 476\u2013481.","DOI":"10.1109\/ROBOT.2000.844100"},{"key":"bibr4-0278364902021010834","volume-title":"Mobile Robot Localization and Map Building: A Multisensor Fusion Approach","author":"Castellanos J. A.","year":"2000"},{"key":"bibr5-0278364902021010834","unstructured":"Chatila R. 1985. Mobile robot navigation: Space modeling and decisional processes. In Proc. 3rd Int. Symp. on Robotics Research 373\u2013378."},{"key":"bibr6-0278364902021010834","doi-asserted-by":"crossref","unstructured":"Chatila R., and Laumond J. P. 1985. Position referencing and consistent world modeling for mobile robots. In Proc. IEEE Int. Conf. on Robotics and Automation 138\u2013143.","DOI":"10.1109\/ROBOT.1985.1087373"},{"key":"bibr7-0278364902021010834","unstructured":"Choset H., and Burdick J. 1996. Sensor based motion planning: The hierarchical generalized voronoi diagram. In Proc. 2nd Workshop on Algorithmic Foundations of Robotics, J.P. Laumond and M. Overmars, eds., A.K. Pe-ters, Wellesley, MA."},{"key":"bibr8-0278364902021010834","doi-asserted-by":"crossref","unstructured":"Conolly C. I. 1985. The determination of next best views. In IEEE Int. Conf. on Robotics and Automation 432\u2013435.","DOI":"10.1109\/ROBOT.1985.1087372"},{"key":"bibr9-0278364902021010834","doi-asserted-by":"crossref","unstructured":"Curless B., and Levoy M. August 1996. A volumetric method for building complex models from range images. In Proc. ACM SIGGRAPH 303\u2013312.","DOI":"10.1145\/237170.237269"},{"key":"bibr10-0278364902021010834","doi-asserted-by":"publisher","DOI":"10.1109\/70.938381"},{"key":"bibr11-0278364902021010834","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-0765-1_20"},{"key":"bibr12-0278364902021010834","doi-asserted-by":"publisher","DOI":"10.1109\/JRA.1987.1087096"},{"key":"bibr13-0278364902021010834","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(98)00008-X"},{"key":"bibr14-0278364902021010834","volume-title":"Planning robot motion strategies for efficient model construction.","author":"Gonz\u00e1lez-Banos H.","year":"1999"},{"key":"bibr15-0278364902021010834","doi-asserted-by":"crossref","unstructured":"Gonz\u00e1lez-Banos H., Guibas L. J., Latombe J. C., LaValle S. M., Lin D., Motwani R., and Tomasi C. 1998. Motion planning with visibility constraints. In Robotics Research: 8th Int. Symp., Y. Shirai and S. Hirose, eds. 95\u2013101.","DOI":"10.1007\/978-1-4471-1580-9_9"},{"key":"bibr16-0278364902021010834","volume-title":"Planning robot motions for range-image acquisition and automatic 3D model construction.","author":"Gonz\u00e1lez-Banos H.","year":"1998"},{"key":"bibr17-0278364902021010834","doi-asserted-by":"publisher","DOI":"10.1109\/70.938382"},{"key":"bibr18-0278364902021010834","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-3184-5_6"},{"key":"bibr19-0278364902021010834","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4022-9"},{"key":"bibr20-0278364902021010834","doi-asserted-by":"publisher","DOI":"10.1109\/70.88147"},{"key":"bibr21-0278364902021010834","doi-asserted-by":"publisher","DOI":"10.1109\/34.211463"},{"key":"bibr22-0278364902021010834","volume-title":"LEDA:A Platform of Combinatorial and Geometric Computing","author":"Mehlhorn K.","year":"1999"},{"key":"bibr23-0278364902021010834","first-page":"445","volume-title":"Handbook of Discrete and Computational Geometry","author":"Mitchell J. S. B.","year":"1997"},{"key":"bibr24-0278364902021010834","first-page":"85","volume-title":"Robotics Research: 5th Int. Symp.","author":"Moutarlier P.","year":"1989"},{"key":"bibr25-0278364902021010834","first-page":"467","volume-title":"Handbook of Discrete and Computational Geometry","author":"O'Rourke J.","year":"1997"},{"key":"bibr26-0278364902021010834","doi-asserted-by":"crossref","unstructured":"Pito R. May 1995. A solution to the next best view problem for automated CAD model acquisition of free-form objects using range cameras. Technical Report 95-23, GRASP Lab, Univ. of Pennsylvania.","DOI":"10.1117\/12.227230"},{"key":"bibr27-0278364902021010834","doi-asserted-by":"publisher","DOI":"10.1109\/ICPR.1996.546162"},{"key":"bibr28-0278364902021010834","volume-title":"Numerical Recipes in C.","author":"Press W. H.","year":"1994"},{"key":"bibr29-0278364902021010834","doi-asserted-by":"publisher","DOI":"10.1109\/5.163407"},{"key":"bibr30-0278364902021010834","doi-asserted-by":"publisher","DOI":"10.1177\/027836498600500404"},{"key":"bibr31-0278364902021010834","unstructured":"Teller S. 1998. Automated urban model acquisition: Project rationale and status. In Proc. 1998 DARPA Image Understanding Workshop 455\u2013462. DARPA."},{"key":"bibr32-0278364902021010834","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067435"},{"key":"bibr33-0278364902021010834","first-page":"387","volume-title":"Handbook on Computational Geometry","author":"Urrutia J.","year":"1997"},{"key":"bibr34-0278364902021010834","doi-asserted-by":"crossref","unstructured":"Wixson L. 1994. Viewpoint selection for visual search. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition, 800\u2013805.","DOI":"10.1109\/CVPR.1994.323902"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364902021010834","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364902021010834","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:40Z","timestamp":1777457800000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364902021010834"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,10]]},"references-count":34,"aliases":["10.1177\/027836402128964099"],"journal-issue":{"issue":"10-11","published-print":{"date-parts":[[2002,10]]}},"alternative-id":["10.1177\/0278364902021010834"],"URL":"https:\/\/doi.org\/10.1177\/0278364902021010834","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,10]]}}}