{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,20]],"date-time":"2026-06-20T02:12:27Z","timestamp":1781921547797,"version":"3.54.5"},"reference-count":71,"publisher":"American Association for the Advancement of Science (AAAS)","issue":"80","content-domain":{"domain":["www.science.org"],"crossmark-restriction":true},"short-container-title":["Sci. Robot."],"published-print":{"date-parts":[[2023,7,12]]},"abstract":"<jats:p>We propose a dual-resolution scheme to achieve time-efficient autonomous exploration with one or many robots. The scheme maintains a high-resolution local map of the robot\u2019s immediate vicinity and a low-resolution global map of the remaining areas of the environment. We believe that the strength of our approach lies in this low- and high-resolution representation of the environment: The high-resolution local map ensures that the robots observe the entire region in detail, and because the local map is bounded, so is the computation burden to process it. The low-resolution global map directs the robot to explore the broad space and only requires lightweight computation and low bandwidth to communicate among the robots. This paper shows the strength of this approach for both single-robot and multirobot exploration. For multirobot exploration, we also introduce a \u201cpursuit\u201d strategy for sharing information among robots with limited communication. This strategy directs the robots to opportunistically approach each other. We found that the scheme could produce exploration paths with a bounded difference in length compared with the theoretical shortest paths. Empirically, for single-robot exploration, our method produced 80% higher time efficiency with 50% lower computational runtimes than state-of-the-art methods in more than 300 simulation and real-world experiments. For multirobot exploration, our pursuit strategy demonstrated higher exploration time efficiency than conventional strategies in more than 3400 simulation runs with up to 20 robots. Last, we discuss how our method was deployed in the DARPA Subterranean Challenge and demonstrated the fastest and most complete exploration among all teams.<\/jats:p>","DOI":"10.1126\/scirobotics.adf0970","type":"journal-article","created":{"date-parts":[[2023,7,19]],"date-time":"2023-07-19T18:02:31Z","timestamp":1689789751000},"update-policy":"https:\/\/doi.org\/10.34133\/aaas_crossmark","source":"Crossref","is-referenced-by-count":67,"title":["Representation granularity enables time-efficient autonomous exploration in large, complex worlds"],"prefix":"10.1126","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4192-7641","authenticated-orcid":true,"given":"C.","family":"Cao","sequence":"first","affiliation":[{"name":"Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1227-4047","authenticated-orcid":true,"given":"H.","family":"Zhu","sequence":"additional","affiliation":[{"name":"Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Z.","family":"Ren","sequence":"additional","affiliation":[{"name":"Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2266-8744","authenticated-orcid":true,"given":"H.","family":"Choset","sequence":"additional","affiliation":[{"name":"Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4692-5645","authenticated-orcid":true,"given":"J.","family":"Zhang","sequence":"additional","affiliation":[{"name":"Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"221","reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2006.1678135"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10846-013-9822-x"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556359"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","unstructured":"B. J. Englot F. S. Hover Sampling-based coverage path planning for inspection of complex structures in International Conference on Automated Planning and Scheduling (AAAI 2012) pp. 29\u201337.","DOI":"10.1609\/icaps.v22i1.13529"},{"key":"e_1_3_2_6_2","unstructured":"DARPA DARPA Subterranean Challenge (2021); www.subtchallenge.com\/."},{"key":"e_1_3_2_7_2","doi-asserted-by":"crossref","unstructured":"A. Bircher M. Kamel K. Alexis H. Oleynikova R. Siegwart Receding horizon\" next-best-view\" planner for 3D exploration in IEEE International Conference on Robotics and Automation (ICRA) (IEEE 2016) pp. 1462\u20131468.","DOI":"10.1109\/ICRA.2016.7487281"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/rob.21993"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","unstructured":"M. Dharmadhikari T. Dang L. Solanka J. Loje H. Nguyen N. Khedekar K. Alexis Motion primitives-based path planning for fast and agile exploration using aerial robots in IEEE International Conference on Robotics and Automation (ICRA) (IEEE 2020) pp. 179\u2013185.","DOI":"10.1109\/ICRA40945.2020.9196964"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2021.3062008"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/70.938381"},{"key":"e_1_3_2_12_2","first-page":"1","article-title":"A probabilistic approach to concurrent mapping and localization for mobile robots","volume":"5","author":"Thrun S.","year":"1998","unstructured":"S. Thrun, W. Burgard, D. Fox, A probabilistic approach to concurrent mapping and localization for mobile robots. Mach. Learn. Auton Robots. 5, 1\u201325 (1998).","journal-title":"Mach. Learn. Auton Robots."},{"key":"e_1_3_2_13_2","unstructured":"D. Fox W. Burgard F. Dellaert S. Thrun Monte Carlo Localization: Efficient position estimation for mobile robots in Proceedings of the National Conference on Artificial Intelligence (AAAI 1999) pp. 343\u2013349."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1177\/02783640022066770"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-010-9200-5"},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","unstructured":"K. Masaba A. Q. Li GVGExp: Communication-constrained multi-robot exploration system based on generalized Voronoi graphs in International Symposium on Multi-Robot and Multi-Agent Systems (IEEE 2021) pp. 146\u2013154.","DOI":"10.1109\/MRS50823.2021.9620554"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364909100586"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/70.105395"},{"key":"e_1_3_2_19_2","unstructured":"F. Bourgault A. A. Makarenko S. B. Williams B. Grocholsky H. F. Durrant-Whyte Information based adaptive robotic exploration paper presented at the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS) Lausanne Switzerland 30 September to 4 October 2002."},{"key":"e_1_3_2_20_2","doi-asserted-by":"crossref","unstructured":"C. Stachniss G. Grisetti W. Burgard Information gain-based exploration using Rao-blackwellized particle filters in Robotics: Science and Systems (MIT Press 2005) pp. 1\u201310.","DOI":"10.15607\/RSS.2005.I.009"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2009.11.005"},{"key":"e_1_3_2_22_2","doi-asserted-by":"crossref","unstructured":"W. Tabib M. Corah N. Michael R. Whittaker Computationally efficient information-theoretic exploration of pits and caves paper presented at the 2016 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS) Daejeon Korea 09 to 14 October 2016.","DOI":"10.1109\/IROS.2016.7759548"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","unstructured":"S. Bai J. Wang F. Chen B. Englot Information-theoretic exploration with Bayesian optimization paper presented at the 2016 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS) Daejeon Korea 9 to 14 October 2016.","DOI":"10.1109\/IROS.2016.7759289"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1177\/027836499701600401"},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","unstructured":"F. Amigoni Experimental evaluation of some exploration strategies for mobile robots in 2008 IEEE International Conference on Robotics and Automation (IEEE 2008) pp. 2818\u20132823.","DOI":"10.1109\/ROBOT.2008.4543637"},{"key":"e_1_3_2_26_2","unstructured":"D. Holz N. Basilico F. Amigoni S. Behnke Evaluating the efficiency of frontier-based exploration strategies paper presented at the 41st International Symposium on Robotics (ISR) and 6th German Conference on Robotics (ROBOTIK) Munich Germany 7 to 9 June 2010."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/MIS.2017.4531226"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s43154-022-00090-9"},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","unstructured":"M. Meghjani G. Dudek Combining multi-robot exploration and rendezvous in Canadian Conference on Computer and Robot Vision (IEEE 2011) pp. 80\u201385.","DOI":"10.1109\/CRV.2011.18"},{"key":"e_1_3_2_30_2","doi-asserted-by":"crossref","unstructured":"B. L. Wellman S. Dawson J. de Hoog M. Anderson Using rendezvous to overcome communication limitations in multirobot exploration in 2011 IEEE International Conference on Systems Man and Cybernetics (IEEE 2011) pp. 2401\u20132406.","DOI":"10.1109\/ICSMC.2011.6084037"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011219024159"},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","unstructured":"M. Meghjani G. Dudek Multi-robot exploration and rendezvous on graphs in 2012 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IEEE 2012) pp. 5270\u20135276.","DOI":"10.1109\/IROS.2012.6386049"},{"key":"e_1_3_2_33_2","unstructured":"J. de Hoog S. Cameron A. Visser Autonomous multi-robot exploration in communication-limited environments in Conference Towards Autonomous Robotic Systems (UKAEA 2010) pp. 68\u201375."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2012.120610"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.conengprac.2006.08.007"},{"key":"e_1_3_2_36_2","doi-asserted-by":"crossref","unstructured":"R. Rathnam A. Birk Distributed communicative exploration under underwater communication constraints in 9th IEEE International Symposium on Safety Security and Rescue Robotics (SSRR) (IEEE 2011) pp. 339\u2013344.","DOI":"10.1109\/SSRR.2011.6106767"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2019.2897368"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2022.3192765"},{"key":"e_1_3_2_39_2","doi-asserted-by":"crossref","unstructured":"G. Best R. Garg J. Keller G. A. Hollinger S. Scherer Resilient multi-sensor exploration of multifarious environments with a team of aerial robots paper presented at the Robotics: Science and Systems Conference (RSS) New York City NY 27 June to 1 July 2022.","DOI":"10.15607\/RSS.2022.XVIII.004"},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","unstructured":"Y. Pei M. W. Mutka Steiner traveler: Relay deployment for remote sensing in heterogeneous multi-robot exploration in 2012 IEEE International Conference on Robotics and Automation (IEEE 2012) pp. 1551\u20131556.","DOI":"10.1109\/ICRA.2012.6225347"},{"key":"e_1_3_2_41_2","doi-asserted-by":"crossref","unstructured":"K. Otsu S. Tepsuporn R. Thakker T. S. Vaquero J. A. Edlund W. Walsh G. Miles T. Heywood M. T. Wolf A. A. Agha-Mohammadi Supervised autonomy for communication-degraded subterranean exploration by a robot team in 2020 IEEE Aerospace Conference Proceedings (IEEE 2020) pp. 1\u20139.","DOI":"10.1109\/AERO47225.2020.9172537"},{"key":"e_1_3_2_42_2","doi-asserted-by":"crossref","unstructured":"C. Cao H. Zhu H. Choset J. Zhang Exploring large and complex environments fast and efficiently paper presented at the 2021 IEEE International Conference on Robotics and Automation (ICRA) Xi\u2019an China 30 May 2021 to 5 June 2021.","DOI":"10.1109\/ICRA48506.2021.9561916"},{"key":"e_1_3_2_43_2","doi-asserted-by":"crossref","unstructured":"C. Cao H. Zhu H. Choset J. Zhang TARE: A hierarchical framework for efficiently exploring complex 3D environments paper presented at the Robotics: Science and Systems Conference (RSS) Virtual 12 to 16 July 2021.","DOI":"10.15607\/RSS.2021.XVII.018"},{"key":"e_1_3_2_44_2","unstructured":"J. O\u2019Rourke Art Gallery Theorems and Algorithms (Oxford Univ. Press 1987) vol. 57 p. 282."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1137\/0221030"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.6.1.80"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2020.103745"},{"key":"e_1_3_2_48_2","unstructured":"E. Gat On three-layer architectures in Artificial Intelligence and Mobile Robots: Case Studies of Successful Robot Systems D. Kortenkamp R. P. Bonnasso R. Murphy Eds. (MIT Press 1997) pp. 195\u2013210."},{"key":"e_1_3_2_49_2","unstructured":"R. Firby Adaptive Execution in Complex Dynamic Worlds (Yale Univ. 1989)."},{"key":"e_1_3_2_50_2","doi-asserted-by":"crossref","unstructured":"N. Koenig A. Howard Design and use paradigms for gazebo an open-source multi-robot simulator in Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS) (IEEE 2004) pp. 2149\u20132154.","DOI":"10.1109\/IROS.2004.1389727"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1002\/rob.21809"},{"key":"e_1_3_2_52_2","doi-asserted-by":"crossref","unstructured":"W. Tabib K. Goel J. Yao M. Dabhi C. Boirum N. Michael Real-time information-theoretic exploration with Gaussian mixture model maps paper presented at the Robotics: Science and Systems Conference (RSS) Messe Freiburg Germany 22 June to 26 June 2019 .","DOI":"10.15607\/RSS.2019.XV.061"},{"key":"e_1_3_2_53_2","unstructured":"S. M. LaValle Rapidly-exploring random trees: A new tool for path planning (Tech. Rep. 98-11 Iowa State Univ. 1998)."},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.55417\/fr.2022023"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(96)00161-0"},{"key":"e_1_3_2_57_2","doi-asserted-by":"crossref","unstructured":"M.\u00a0Roberts D.\u00a0Dey A.\u00a0Truong S.\u00a0Sinha S.\u00a0Shah A.\u00a0Kapoor P.\u00a0Hanrahan N.\u00a0Joshi Submodular trajectory optimization for aerial 3D scanning in IEEE International Conference on Computer Vision (IEEE 2017) pp. 5334\u20135343.","DOI":"10.1109\/ICCV.2017.569"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.43.2.367"},{"key":"e_1_3_2_59_2","unstructured":"D. Li X. Sun Nonlinear Integer Programming (Springer 2006) vol. 84."},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-014-9238-1"},{"key":"e_1_3_2_61_2","unstructured":"S. Russell P. Norvig Artificial Intelligence: A Modern Approach (Pearson Education Inc. 2010)."},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2019.2927938"},{"key":"e_1_3_2_63_2","unstructured":"S. G. Johnson The NLopt nonlinear-optimization package (2014); http:\/\/github.com\/stevengj\/nlopt."},{"key":"e_1_3_2_64_2","doi-asserted-by":"crossref","unstructured":"T. Schouten E. L. van den Broek Incremental distance transforms (IDT) paper presented at the International Conference on Pattern Recognition Istanbul Turkey 23\u201326 August 2010.","DOI":"10.1109\/ICPR.2010.67"},{"key":"e_1_3_2_65_2","unstructured":"S. Quinlan O. Khatib Elastic bands: Connecting path planning and control in Proceedings of the IEEE International Conference on Robotics and Automation (IEEE 1993) pp. 802\u2013807."},{"key":"e_1_3_2_66_2","unstructured":"K. Helsgaun An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems (Roskilde Univ. 2017)."},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90008-6"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00047-6"},{"key":"e_1_3_2_69_2","doi-asserted-by":"crossref","unstructured":"F. Ferri M. Gianni M. Menna F. Pirri Dynamic obstacles detection and 3D map updating in Proceedings of the 2015 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS) (IEEE 2015) pp. 5694\u20135699.","DOI":"10.1109\/IROS.2015.7354185"},{"key":"e_1_3_2_70_2","doi-asserted-by":"crossref","unstructured":"V. Indelman A. Melim F. Dellaert Incremental light bundle adjustment for robotics navigation in Proceedings of the 2013 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IEEE 2013) pp. 1952\u20131959.","DOI":"10.1109\/IROS.2013.6696615"},{"key":"e_1_3_2_71_2","doi-asserted-by":"crossref","unstructured":"A. Chang A. Dai T. Funkhouser M. Halber M. Niessner M. Savva S. Song A. Zeng Y. Zhang Matterport3D: Learning from RGB-D data in indoor environments paper presented at the International Conference on 3D Vision (3DV) Qingdao China 10 to 12 October 2017.","DOI":"10.1109\/3DV.2017.00081"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1002\/rob.21952"}],"container-title":["Science Robotics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.science.org\/doi\/pdf\/10.1126\/scirobotics.adf0970","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,24]],"date-time":"2024-10-24T13:58:20Z","timestamp":1729778300000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.science.org\/doi\/10.1126\/scirobotics.adf0970"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,12]]},"references-count":71,"journal-issue":{"issue":"80","published-print":{"date-parts":[[2023,7,12]]}},"alternative-id":["10.1126\/scirobotics.adf0970"],"URL":"https:\/\/doi.org\/10.1126\/scirobotics.adf0970","relation":{},"ISSN":["2470-9476"],"issn-type":[{"value":"2470-9476","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,12]]},"assertion":[{"value":"2022-10-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"eadf0970"}}