{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T08:02:54Z","timestamp":1767772974273,"version":"3.38.0"},"reference-count":47,"publisher":"SAGE Publications","issue":"10","license":[{"start":{"date-parts":[[2017,8,10]],"date-time":"2017-08-10T00:00:00Z","timestamp":1502323200000},"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":[[2017,9]]},"abstract":"<jats:p> We develop a computationally efficient approach for evaluating the information-theoretic term within belief space planning (BSP), where during belief propagation the state vector can be constant or augmented. We consider both unfocused and focused problem settings, whereas uncertainty reduction of the entire system or only of chosen variables is of interest, respectively. State-of-the-art approaches typically propagate the belief state, for each candidate action, through calculation of the posterior information (or covariance) matrix and subsequently compute its determinant (required for entropy). In contrast, our approach reduces runtime complexity by avoiding these calculations. We formulate the problem in terms of factor graphs and show that belief propagation is not needed, requiring instead a one-time calculation that depends on (the increasing with time) state dimensionality, and per-candidate calculations that are independent of the latter. To that end, we develop an augmented version of the matrix determinant lemma, and show that computations can be re-used when evaluating impact of different candidate actions. These two key ingredients and the factor graph representation of the problem result in a computationally efficient (augmented) BSP approach that accounts for different sources of uncertainty and can be used with various sensing modalities. We examine the unfocused and focused instances of our approach, and compare it with the state of the art, in simulation and using real-world data, considering problems such as autonomous navigation in unknown environments, measurement selection and sensor deployment. We show that our approach significantly reduces running time without any compromise in performance. <\/jats:p>","DOI":"10.1177\/0278364917721629","type":"journal-article","created":{"date-parts":[[2017,8,11]],"date-time":"2017-08-11T05:48:17Z","timestamp":1502430497000},"page":"1088-1130","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":16,"title":["No belief propagation required: Belief space planning in high-dimensional state spaces via factor graphs, the matrix determinant lemma, and re-use of calculation"],"prefix":"10.1177","volume":"36","author":[{"given":"Dmitry","family":"Kopitkov","sequence":"first","affiliation":[{"name":"Technion Autonomous Systems Program (TASP), 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":[[2017,8,10]]},"reference":[{"key":"bibr1-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913501564"},{"key":"bibr2-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2016.7759289"},{"key":"bibr3-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(96)00018-0"},{"key":"bibr4-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2014.2347571"},{"key":"bibr5-0278364917721629","first-page":"2667","volume-title":"IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)","author":"Carlone L","year":"2014"},{"key":"bibr6-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2015.7353653"},{"key":"bibr7-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2009.07.010"},{"key":"bibr8-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024079"},{"key":"bibr9-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2005.29"},{"key":"bibr10-0278364917721629","unstructured":"Dellaert F (2012) Factor graphs and GTSAM: A hands-on introduction. Technical Report GT-RIM-CP&R-2012-002, Georgia Institute of Technology."},{"key":"bibr11-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(80)90156-1"},{"key":"bibr12-0278364917721629","unstructured":"Guivant J, Nieto J, Nebot E (2012) Victoria park dataset. Available at: http:\/\/www-personal.acfr.usyd.edu.au\/nebot\/victoria_park.htm"},{"key":"bibr13-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1998.10485214"},{"key":"bibr14-0278364917721629","first-page":"150","volume-title":"Proceedings of the European Conference on Mobile Robots (ECMR)","author":"Huang G","year":"2012"},{"key":"bibr15-0278364917721629","first-page":"1091","volume-title":"IEEE International Conference on Robotics and Automation (ICRA)","author":"Huang S","year":"2005"},{"key":"bibr16-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139841"},{"key":"bibr17-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2009.2034435"},{"volume-title":"Proceedings of the International Symposium on Robotics Research (ISRR)","year":"2015","author":"Indelman V","key":"bibr18-0278364917721629"},{"key":"bibr19-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2015.7171095"},{"key":"bibr20-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2016.2518224"},{"key":"bibr21-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914561102"},{"key":"bibr22-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00023-X"},{"key":"bibr23-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2009.06.008"},{"key":"bibr24-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911430419"},{"key":"bibr25-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2008.2006706"},{"key":"bibr26-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914547893"},{"key":"bibr27-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2016.7759286"},{"volume-title":"IEEE International Conference on Robotics and Automation (ICRA) and IEEE Robotics and Automation Letters (RA-L), Mutual Submission","year":"2017","author":"Kopitkov D","key":"bibr28-0278364917721629"},{"key":"bibr29-0278364917721629","first-page":"235","volume":"9","author":"Krause A","year":"2008","journal-title":"Journal of Machine Learning Research"},{"key":"bibr30-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912455072"},{"key":"bibr31-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/18.910572"},{"key":"bibr32-0278364917721629","first-page":"2211","author":"Levine D","year":"2013","journal-title":"Advances in Neural Information Processing Systems (NIPS)"},{"key":"bibr33-0278364917721629","first-page":"1","author":"Mazuran M","year":"2014","journal-title":"Robotics: Science and Systems (RSS)"},{"journal-title":"Robotics: Science and Systems (RSS)","year":"2015","author":"Mu B","key":"bibr34-0278364917721629"},{"key":"bibr35-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(81)90232-9"},{"key":"bibr36-0278364917721629","first-page":"515","volume-title":"International Workshop on the Algorithmic Foundations of Robotics (WAFR)","author":"Patil S","year":"2014"},{"key":"bibr37-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487268"},{"key":"bibr38-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2078"},{"key":"bibr39-0278364917721629","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2010.VI.037"},{"key":"bibr40-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1177\/0278364909341659"},{"key":"bibr41-0278364917721629","first-page":"65","author":"Stachniss C","year":"2005","journal-title":"Robotics: Science and Systems (RSS)"},{"key":"bibr42-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2013.2257577"},{"key":"bibr43-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912456319"},{"key":"bibr44-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2011.6095128"},{"key":"bibr45-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2015.7353681"},{"key":"bibr46-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1198\/108571106X99751"},{"key":"bibr47-0278364917721629","doi-asserted-by":"publisher","DOI":"10.1002\/env.769"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364917721629","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364917721629","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364917721629","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,2]],"date-time":"2025-03-02T19:03:05Z","timestamp":1740942185000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364917721629"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,10]]},"references-count":47,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["10.1177\/0278364917721629"],"URL":"https:\/\/doi.org\/10.1177\/0278364917721629","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"type":"print","value":"0278-3649"},{"type":"electronic","value":"1741-3176"}],"subject":[],"published":{"date-parts":[[2017,8,10]]}}}