{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:59:58Z","timestamp":1777715998008,"version":"3.51.4"},"reference-count":78,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2023,12,20]],"date-time":"2023-12-20T00:00:00Z","timestamp":1703030400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:p>Determining a globally optimal solution of belief space planning (BSP) in high-dimensional state spaces directly is computationally expensive, as it involves belief propagation and objective function evaluation for each candidate action. However, many problems of interest, such as active SLAM, exhibit structure that can be harnessed to expedite planning. Also, in order to choose an optimal action, an exact value of the objective function is not required as long as the actions can be sorted in the same way. In this paper we leverage these two key aspects and present the topological belief space planning (t-bsp) concept that uses topological signatures to perform this ranking for information-theoretic cost functions, considering only topologies of factor graphs that correspond to future posterior beliefs. In particular, we propose a highly efficient topological signature based on the von Neumann graph entropy that is a function of graph node degrees and supports an incremental update. We analyze it in the context of active pose SLAM and derive error bounds between the proposed topological signature and the original information-theoretic cost function. These bounds are then used to provide performance guarantees for t-bsp with respect to a given solver of the original information-theoretic BSP problem. Realistic and synthetic simulations demonstrate drastic speed-up of the proposed method with respect to the state-of-the-art methods while retaining the ability to select a near-optimal solution. A proof of concept of t-bsp is given in a small-scale real-world active SLAM experiment.<\/jats:p>","DOI":"10.1177\/02783649231204898","type":"journal-article","created":{"date-parts":[[2023,12,20]],"date-time":"2023-12-20T04:44:16Z","timestamp":1703047456000},"page":"69-97","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":8,"title":["Topological belief space planning for active SLAM with pairwise Gaussian potentials and performance guarantees"],"prefix":"10.1177","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4183-2896","authenticated-orcid":false,"given":"Andrej","family":"Kitanov","sequence":"first","affiliation":[{"name":"Department of Aerospace Engineering, Technion - Israel Institute of Technology, Haifa, Israel"}]},{"given":"Vadim","family":"Indelman","sequence":"additional","affiliation":[{"name":"Department of Aerospace Engineering, Technion - Israel Institute of Technology, Haifa, Israel"}]}],"member":"179","published-online":{"date-parts":[[2023,12,20]]},"reference":[{"key":"bibr1-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913501564"},{"key":"bibr2-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2009.5152501"},{"key":"bibr3-02783649231204898","first-page":"5","volume-title":"Congressus Numerantium","volume":"115","author":"Archdeacon D","year":"1996"},{"key":"bibr4-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139863"},{"key":"bibr5-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/5.5968"},{"key":"bibr6-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/MCS.2007.384125"},{"key":"bibr7-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2015.2412051"},{"key":"bibr8-02783649231204898","doi-asserted-by":"crossref","unstructured":"Bian F, Kempe D, Govindan R (2006) Utility based sensor selection. In Proceedings of the 5th Intl Conference On Information Processing in Sensor Networks, Nashville, TN, USA, 2006, pp. 11\u201318.","DOI":"10.1109\/IPSN.2006.244032"},{"key":"bibr9-02783649231204898","volume-title":"Algebraic Graph Theory","author":"Biggs N","year":"1993","edition":"2"},{"key":"bibr10-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2018.8460641"},{"key":"bibr11-02783649231204898","volume-title":"Spectra of Graphs","author":"Brouwer AE","year":"2011"},{"key":"bibr12-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2014.2347571"},{"key":"bibr13-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6224890"},{"key":"bibr14-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2018.8460864"},{"key":"bibr15-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8793632"},{"key":"bibr16-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2020.3001718"},{"key":"bibr17-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/70.928558"},{"key":"bibr18-02783649231204898","volume-title":"Spectral Graph Theory","author":"Chung FR","year":"1997"},{"key":"bibr19-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00312-7_14"},{"key":"bibr20-02783649231204898","volume-title":"Technical Report GT-RIM-CP&R-2012-002","author":"Dellaert F","year":"2012"},{"key":"bibr21-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1561\/2300000043"},{"key":"bibr22-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/AIM.2011.6027142"},{"key":"bibr23-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2017.7989437"},{"key":"bibr24-02783649231204898","unstructured":"Elimelech K, Indelman V (2017b) Fast action elimination for efficient decision making and belief space planning using bounded approximations. In Proc Of the Intl Symp of Robotics Research (ISRR). Puerto Varas, Chile, 2017."},{"key":"bibr25-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2017.8206456"},{"key":"bibr26-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2004.1307180"},{"key":"bibr27-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-006-9043-2"},{"key":"bibr28-02783649231204898","unstructured":"Frey B, Kschischang F, Loeliger HA, et al. (1997) Factor graphs and algorithms. In Proc 35th Allerton Conf Communications, Control, and Computing, University of Illinois, 1997, pp. 666\u2013680"},{"key":"bibr29-02783649231204898","volume-title":"Topological Graph Theory","author":"Gross JL","year":"1987"},{"key":"bibr30-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2012.03.016"},{"key":"bibr31-02783649231204898","volume-title":"Matrix Analysis","author":"Horn RA","year":"2013","edition":"2"},{"key":"bibr32-02783649231204898","author":"Hovland GE","year":"1997","journal-title":"IEEE Intl. Conf. on Robotics and Automation (ICRA)"},{"key":"bibr33-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2005.1570261"},{"key":"bibr34-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2015.7171095"},{"key":"bibr35-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2016.2518224"},{"key":"bibr36-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914561102"},{"key":"bibr37-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2008.2007095"},{"key":"bibr38-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2008.2006706"},{"key":"bibr39-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17452-0_10"},{"key":"bibr40-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911430419"},{"key":"bibr41-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"bibr42-02783649231204898","volume-title":"Robotics: Science and Systems (RSS). Workshop on the Problem of Mobile Sensors","author":"Khosoussi K","year":"2015"},{"key":"bibr43-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918823086"},{"key":"bibr44-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914547893"},{"key":"bibr45-02783649231204898","unstructured":"Kim S, Bhattacharya S, Ghrist R, et al. (2013) Topological exploration of unknown and partially known environments. In IEEE\/RSJ Intl Conf On Intelligent Robots and Systems (IROS), Tokyo, Japan, 03-07 November 2013, pp. 3851\u20133858."},{"key":"bibr46-02783649231204898","doi-asserted-by":"crossref","unstructured":"Kitanov A, Indelman V (2018) Topological multi-robot belief space planning in unknown environments, In IEEE Intl Conf On Robotics and Automation (ICRA), Brisbane, QLD, 21-25 May 2018, pp. 5726\u20135732.","DOI":"10.1109\/ICRA.2018.8460772"},{"key":"bibr47-02783649231204898","volume-title":"Probabilistic Graphical Models: Principles and Techniques","author":"Koller D","year":"2009"},{"key":"bibr48-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1177\/0278364917721629"},{"key":"bibr49-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1177\/0278364919875199"},{"key":"bibr50-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912455072"},{"key":"bibr51-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/18.910572"},{"key":"bibr52-02783649231204898","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2008.IV.009"},{"key":"bibr53-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1988.tb01721.x"},{"key":"bibr54-02783649231204898","first-page":"871","volume-title":"Graph Theory, Combinatorics, and Applications","author":"Mohar B","year":"1991"},{"key":"bibr55-02783649231204898","doi-asserted-by":"publisher","DOI":"10.3390\/e14030559"},{"key":"bibr56-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.441"},{"key":"bibr57-02783649231204898","unstructured":"Paskin M (2003) Thin junction tree filters for simultaneous localization and mapping. In Intl Joint Conf On AI (IJCAI). San Francisco, CA, USA, August 2003, pp. 1157\u20131164."},{"key":"bibr58-02783649231204898","doi-asserted-by":"publisher","DOI":"10.4018\/jats.2009071005"},{"key":"bibr59-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509587"},{"key":"bibr60-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-2012-0_7"},{"key":"bibr61-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2078"},{"key":"bibr62-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2023.3248510"},{"key":"bibr63-02783649231204898","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2010.VI.037"},{"key":"bibr64-02783649231204898","first-page":"2329","volume":"7","author":"Porta JM","year":"2006","journal-title":"Journal of Machine Learning Research"},{"key":"bibr65-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1177\/0278364909341659"},{"key":"bibr66-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1177\/0278364910393287"},{"key":"bibr67-02783649231204898","volume-title":"Autonomous Robots Special Issue on Online Decision Making in Multi-Robot Coordination","author":"Regev T","year":"2017"},{"key":"bibr68-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2021.3068947"},{"key":"bibr69-02783649231204898","volume-title":"Parameter Estimation: Principles and Problems","volume":"9","author":"Sorenson HW","year":"1980"},{"key":"bibr70-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2004.1389609"},{"key":"bibr71-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-6699-3"},{"key":"bibr72-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30301-5_38"},{"key":"bibr73-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2012.6385637"},{"key":"bibr74-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406562"},{"key":"bibr75-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912456319"},{"key":"bibr76-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139774"},{"key":"bibr77-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2008.03.011"},{"key":"bibr78-02783649231204898","doi-asserted-by":"publisher","DOI":"10.1137\/0602010"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231204898","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649231204898","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231204898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:06Z","timestamp":1777457826000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649231204898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,20]]},"references-count":78,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["10.1177\/02783649231204898"],"URL":"https:\/\/doi.org\/10.1177\/02783649231204898","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,20]]}}}