{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T20:39:09Z","timestamp":1773520749304,"version":"3.50.1"},"reference-count":82,"publisher":"SAGE Publications","issue":"2-3","license":[{"start":{"date-parts":[[2019,1,22]],"date-time":"2019-01-22T00:00:00Z","timestamp":1548115200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2019,3]]},"abstract":"<jats:p> Estimation-over-graphs (EoG) is a class of estimation problems that admit a natural graphical representation. Several key problems in robotics and sensor networks, including sensor network localization, synchronization over a group, and simultaneous localization and mapping (SLAM) fall into this category. We pursue two main goals in this work. First, we aim to characterize the impact of the graphical structure of SLAM and related problems on estimation reliability. We draw connections between several notions of graph connectivity and various properties of the underlying estimation problem. In particular, we establish results on the impact of the weighted number of spanning trees on the D-optimality criterion in 2D SLAM. These results enable agents to evaluate estimation reliability based only on the graphical representation of the EoG problem. We then use our findings and study the problem of designing sparse SLAM problems that lead to reliable maximum likelihood estimates through the synthesis of sparse graphs with the maximum weighted tree connectivity. Characterizing graphs with the maximum number of spanning trees is an open problem in general. To tackle this problem, we establish several new theoretical results, including the monotone log-submodularity of the weighted number of spanning trees. We exploit these structures and design a complementary greedy\u2013convex pair of efficient approximation algorithms with provable guarantees. The proposed synthesis framework is applied to various forms of the measurement selection problem in resource-constrained SLAM. Our algorithms and theoretical findings are validated using random graphs, existing and new synthetic SLAM benchmarks, and publicly available real pose-graph SLAM datasets. <\/jats:p>","DOI":"10.1177\/0278364918823086","type":"journal-article","created":{"date-parts":[[2019,1,22]],"date-time":"2019-01-22T15:48:55Z","timestamp":1548172135000},"page":"260-298","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":52,"title":["Reliable Graphs for SLAM"],"prefix":"10.1177","volume":"38","author":[{"given":"Kasra","family":"Khosoussi","sequence":"first","affiliation":[{"name":"Laboratory for Information and Decision Systems (LIDS), Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"given":"Matthew","family":"Giamou","sequence":"additional","affiliation":[{"name":"Laboratory for Information and Decision Systems (LIDS), Massachusetts Institute of Technology, Cambridge, MA, USA"}]},{"given":"Gaurav S","family":"Sukhatme","sequence":"additional","affiliation":[{"name":"Department of Computer Science Viterbi School of Engineering, University of Southern California, Los Angeles, CA, USA"}]},{"given":"Shoudong","family":"Huang","sequence":"additional","affiliation":[{"name":"Centre for Autonomous Systems (CAS), University of Technology Sydney, Sydney, Australia"}]},{"given":"Gamini","family":"Dissanayake","sequence":"additional","affiliation":[{"name":"Centre for Autonomous Systems (CAS), University of Technology Sydney, Sydney, Australia"}]},{"given":"Jonathan P","family":"How","sequence":"additional","affiliation":[{"name":"Laboratory for Information and Decision Systems (LIDS), Massachusetts Institute of Technology, Cambridge, MA, USA"}]}],"member":"179","published-online":{"date-parts":[[2019,1,22]]},"reference":[{"key":"bibr1-0278364918823086","first-page":"19","volume":"365","author":"Bailey RA","year":"2009","journal-title":"Surveys in Combinatorics"},{"key":"bibr2-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2006.1678144"},{"key":"bibr3-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/MCS.2007.384125"},{"key":"bibr4-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1987.1086075"},{"key":"bibr5-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1002\/net.20300"},{"key":"bibr6-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"bibr7-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(96)85158-4"},{"key":"bibr8-0278364918823086","author":"Cadena C","year":"2016","journal-title":"Preprint arXiv:1606.05830"},{"key":"bibr9-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2014.2347571"},{"key":"bibr10-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630690"},{"key":"bibr11-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914523689"},{"key":"bibr12-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2013.2291626"},{"key":"bibr13-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2017.7989448"},{"key":"bibr14-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"bibr15-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80028-7"},{"key":"bibr16-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2009.07.010"},{"key":"bibr17-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139839"},{"key":"bibr18-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2017.2650153"},{"key":"bibr19-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100064239"},{"key":"bibr20-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718881"},{"key":"bibr21-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2005.29"},{"key":"bibr22-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906072768"},{"key":"bibr23-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7140012"},{"key":"bibr24-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.845330"},{"key":"bibr25-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015269615729"},{"key":"bibr26-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2010.5649205"},{"key":"bibr27-0278364918823086","doi-asserted-by":"crossref","unstructured":"Frey KM, Steiner TJ, How JP (2018) Complexity analysis and efficient measurement selection primitives for high-rate graph SLAM. In: IEEE International Conference on Robotics and Automation (ICRA). https:\/\/arxiv.org\/abs\/1709.06821.","DOI":"10.1109\/ICRA.2018.8460708"},{"key":"bibr28-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1093\/biostatistics\/kxm045"},{"key":"bibr29-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2012.2197158"},{"key":"bibr30-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913491297"},{"key":"bibr31-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1137\/050645452"},{"key":"bibr32-0278364918823086","doi-asserted-by":"crossref","unstructured":"Giamou M, Khosoussi K, How JP (2018) Talk resource-efficiently to me: Optimal communication planning for distributed loop closure detection. In: IEEE International Conference on Robotics and Automation (ICRA). https:\/\/arxiv.org\/abs\/1709.06675 .","DOI":"10.1109\/ICRA.2018.8460783"},{"key":"bibr33-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706098"},{"key":"bibr34-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0163-9"},{"key":"bibr35-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1080\/00268978300102731"},{"key":"bibr36-0278364918823086","unstructured":"H\u00e4hnel D (2003) Intel Research Lab dataset. https:\/\/svn.openslam.org\/data\/svn\/g2o\/trunk\/data\/2d\/intel\/intel.g2o. (accessed 10 May 2017)."},{"key":"bibr37-0278364918823086","volume-title":"Approximation algorithms for NP-hard problems","author":"Hochbaum DS","year":"1996"},{"key":"bibr38-0278364918823086","volume-title":"Matrix analysis","author":"Horn RA","year":"1990"},{"key":"bibr39-0278364918823086","unstructured":"Howard A, Roy N (2003) The robotics data set repository (radish). http:\/\/radish.sourceforge.net\/ ."},{"key":"bibr40-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/ECMR.2013.6698835"},{"key":"bibr41-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2009.2034435"},{"key":"bibr42-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2008.2007095"},{"key":"bibr43-0278364918823086","volume-title":"Incremental Smoothing and Mapping","author":"Kaess M","year":"2008"},{"key":"bibr44-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2009.06.008"},{"key":"bibr45-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2008.2006706"},{"key":"bibr46-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<177::AID-RSA11>3.0.CO;2-L"},{"key":"bibr47-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6942932"},{"key":"bibr48-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487264"},{"key":"bibr49-0278364918823086","volume-title":"2016 International Workshop on the Algorithmic Foundations of Robotics (WAFR)","author":"Khosoussi K","year":"2016"},{"issue":"12","key":"bibr50-0278364918823086","first-page":"941","volume":"9","author":"Kim N","year":"2013","journal-title":"WSEAS Transactions on Mathematics"},{"key":"bibr51-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2010.5649043"},{"key":"bibr52-0278364918823086","first-page":"19","volume":"3","author":"Krause A","year":"2012","journal-title":"Tractability: Practical Approaches to Hard Problems"},{"key":"bibr53-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912455072"},{"key":"bibr54-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5979949"},{"key":"bibr55-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"key":"bibr56-0278364918823086","unstructured":"Li H, Patterson S, Yi Y, Zhang Z (2018) Maximizing the number of spanning trees in a connected graph. Preprint arXiv:1804.02785."},{"key":"bibr57-0278364918823086","unstructured":"L\u00f6fberg J (2004) Yalmip: A toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference. Taipei, Taiwan. http:\/\/users.isy.liu.se\/johanl\/yalmip ."},{"key":"bibr58-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915581629"},{"key":"bibr59-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719512"},{"key":"bibr60-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0006528"},{"key":"bibr61-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2015.2463671"},{"key":"bibr62-0278364918823086","volume-title":"Proceedings of International Conference on Graph Theory, Combinatorics, Algorithms, and Applications","author":"Myrvold W","year":"1996"},{"key":"bibr63-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"bibr64-0278364918823086","volume-title":"Robust and Efficient Robotic Mapping","author":"Olson E","year":"2008"},{"key":"bibr65-0278364918823086","first-page":"40","volume-title":"RSS Workshop on Good Experimental Methodology in Robotics","author":"Olson E","year":"2009"},{"key":"bibr66-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487268"},{"key":"bibr67-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139227"},{"key":"bibr68-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00095-4"},{"key":"bibr69-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2014.6859421"},{"key":"bibr70-0278364918823086","volume-title":"Optimal design of experiments","volume":"50","author":"Pukelsheim F","year":"1993"},{"key":"bibr71-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2010.5717225"},{"key":"bibr72-0278364918823086","doi-asserted-by":"publisher","DOI":"10.6028\/jres.078B.023"},{"key":"bibr73-0278364918823086","volume-title":"Parameter estimation: principles and problems","author":"Sorenson H","year":"1980"},{"key":"bibr74-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045479"},{"key":"bibr75-0278364918823086","doi-asserted-by":"crossref","unstructured":"Tian Y, Khosoussi K, Giamou M, How JP, Kelly J (2018) Near-optimal budgeted data exchange for distributed loop closure detection. In: Proceedings of Robotics: Science and Systems. Pittsburgh, PA, accepted.","DOI":"10.15607\/RSS.2018.XIV.071"},{"key":"bibr76-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0347-5"},{"key":"bibr77-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2018.2798283"},{"key":"bibr78-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896303430"},{"key":"bibr79-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2011.6095128"},{"key":"bibr80-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230240504"},{"key":"bibr81-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1109\/ECMR.2013.6698816"},{"key":"bibr82-0278364918823086","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579435"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364918823086","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364918823086","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364918823086","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T22:02:16Z","timestamp":1740866536000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364918823086"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,22]]},"references-count":82,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["10.1177\/0278364918823086"],"URL":"https:\/\/doi.org\/10.1177\/0278364918823086","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,22]]}}}