{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T02:34:53Z","timestamp":1767753293421,"version":"3.48.0"},"reference-count":55,"publisher":"SAGE Publications","issue":"5","license":[{"start":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T00:00:00Z","timestamp":1648771200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["Grant 351\/15"],"award-info":[{"award-number":["Grant 351\/15"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:p>In this work, we introduce a new and efficient solution approach for the problem of decision making under uncertainty, which can be formulated as decision making in a belief space, over a possibly high-dimensional state space. Typically, to solve a decision problem, one should identify the optimal action from a set of candidates, according to some objective. We claim that one can often generate and solve an analogous yet simplified decision problem, which can be solved more efficiently. A wise simplification method can lead to the same action selection, or one for which the maximal loss in optimality can be guaranteed. Furthermore, such simplification is separated from the state inference and does not compromise its accuracy, as the selected action would finally be applied on the original state. First, we present the concept for general decision problems and provide a theoretical framework for a coherent formulation of the approach. We then practically apply these ideas to decision problems in the belief space, which can be simplified by considering a sparse approximation of their initial belief. The scalable belief sparsification algorithm we provide is able to yield solutions which are guaranteed to be consistent with the original problem. We demonstrate the benefits of the approach in the solution of a realistic active-SLAM problem and manage to significantly reduce computation time, with no loss in the quality of solution. This work is both fundamental and practical and holds numerous possible extensions.<\/jats:p>","DOI":"10.1177\/02783649221076381","type":"journal-article","created":{"date-parts":[[2022,6,2]],"date-time":"2022-06-02T07:03:22Z","timestamp":1654153402000},"page":"470-496","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":11,"title":["Simplified decision making in the belief space using belief sparsification"],"prefix":"10.1177","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1391-8956","authenticated-orcid":false,"given":"Khen","family":"Elimelech","sequence":"first","affiliation":[{"name":"Technion\u2014Israel Institute of Technology"}]},{"given":"Vadim","family":"Indelman","sequence":"additional","affiliation":[{"name":"Technion\u2014Israel Institute of Technology"}]}],"member":"179","published-online":{"date-parts":[[2022,6,2]]},"reference":[{"key":"e_1_3_5_2_1","doi-asserted-by":"crossref","unstructured":"Agarwal P Olson E (2012) Variable reordering strategies for slam. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems. Vilamoura-Algarve Portugal October 2012 IEEE: IROS pp. 3844\u20133850.","DOI":"10.1109\/IROS.2012.6385473"},{"key":"e_1_3_5_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2018.2838556"},{"key":"e_1_3_5_4_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913501564"},{"key":"e_1_3_5_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.121791"},{"issue":"13","key":"e_1_3_5_6_1","first-page":"1609","article-title":"Robust belief space planning under intermittent sensing via a maximum eigenvalue-based bound","volume":"35","author":"Bopardikar SD","year":"2016","unstructured":"Bopardikar SD, Englot B, Speranzon A, et al. (2016) Robust belief space planning under intermittent sensing via a maximum eigenvalue-based bound. International Journal of Research and Review 35(13): 1609\u20131626.","journal-title":"International Journal of Research and Review"},{"key":"e_1_3_5_7_1","unstructured":"Boyen X Koller D (1998) Tractable inference for complex stochastic processes. In: Proceedings of the Fourteenth Conference on Uncertainty in AI. Madison WI: UAI July 1998 pp. 33\u201342."},{"key":"e_1_3_5_8_1","doi-asserted-by":"crossref","unstructured":"Carlevaris-Bianco N Eustice RM (2014) Conservative edge sparsification for graph slam node removal. In: IEEE International Conference on Robotics and Automation. Hong Kong China June 2014 ICRA. pp. 854\u2013860.","DOI":"10.1109\/ICRA.2014.6906954"},{"key":"e_1_3_5_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2014.2347571"},{"key":"e_1_3_5_10_1","doi-asserted-by":"crossref","unstructured":"Chaves SM Eustice RM (2016) Efficient planning with the Bayes tree for active SLAM. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems. IEEE: IEEE pp. 4664\u20134671.","DOI":"10.1109\/IROS.2016.7759686"},{"key":"e_1_3_5_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718881"},{"key":"e_1_3_5_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1024074.1024079"},{"key":"e_1_3_5_13_1","volume-title":"Factor Graphs and GTSAM: A Hands-on Introduction","author":"Dellaert F","year":"2012","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":"e_1_3_5_14_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906072768"},{"key":"e_1_3_5_15_1","doi-asserted-by":"publisher","DOI":"10.1561\/2300000043"},{"key":"e_1_3_5_16_1","volume-title":"Efficient Decision Making under Uncertainty in High-Dimensional State Spaces","author":"Elimelech K","year":"2021","unstructured":"Elimelech K (2021) Efficient Decision Making under Uncertainty in High-Dimensional State Spaces, PhD thesis. Technion \u2013 Israel Institute of Technology, Haifa, Israel."},{"key":"e_1_3_5_17_1","doi-asserted-by":"crossref","unstructured":"Elimelech K Indelman V (2017a) Consistent sparsification for efficient decision making under uncertainty in high dimensional state spaces. In: IEEE International Conference on Robotics and Automation. Singapore May 2017 ICRA pp. 3786\u20133791.","DOI":"10.1109\/ICRA.2017.7989437"},{"key":"e_1_3_5_18_1","unstructured":"Elimelech K Indelman V (2017b) Fast action elimination for efficient decision making and belief space planning using bounded approximations. In: Proceedings of the International Symposium of Robotics Research (ISRR)\u2019. Puerto Varas Chile December 2017."},{"key":"e_1_3_5_19_1","doi-asserted-by":"crossref","unstructured":"Elimelech K Indelman V (2017c) Scalable sparsification for efficient decision making under uncertainty in high dimensional state spaces. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems. Vancouver BC Canada September 2017 IROS pp. 5668\u20135673.","DOI":"10.1109\/IROS.2017.8206456"},{"key":"e_1_3_5_20_1","unstructured":"Elimelech K Indelman V (2019) Introducing PIVOT: predictive incremental variable ordering tactic for efficient belief space planning. In: Proceedings of the International Symposium of Robotics Research (ISRR). Hanoi Vietnam October 2019."},{"key":"e_1_3_5_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2020.3048663"},{"key":"e_1_3_5_22_1","doi-asserted-by":"crossref","unstructured":"Frey KM Steiner TJ How JP (2017) Complexity analysis and efficient measurement selection primitives for high-rate graph slam. arXiv preprint arXiv:1709.06821.","DOI":"10.1109\/ICRA.2018.8460708"},{"key":"e_1_3_5_23_1","volume-title":"Numerical Mathematics","author":"H\u00e4mmerlin G","year":"2012","unstructured":"H\u00e4mmerlin G, Hoffmann K-H (2012) Numerical Mathematics. Berlin\/Heidelberg, Germany: Springer Science & Business Media."},{"key":"e_1_3_5_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1998.10485214"},{"key":"e_1_3_5_25_1","doi-asserted-by":"crossref","unstructured":"Hsiung J Hsiao M Westman E et al. (2018) Information sparsification in visual-inertial odometry. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems. IROS pp. 1146\u20131153.","DOI":"10.1109\/IROS.2018.8594007"},{"key":"e_1_3_5_26_1","doi-asserted-by":"crossref","unstructured":"Huang G Kaess M Leonard J (2012) Consistent sparsification for graph optimization. In: Proceedings of the European Conference on Mobile Robots. ECMR pp. 150\u2013157.","DOI":"10.1109\/ECMR.2013.6698835"},{"key":"e_1_3_5_27_1","doi-asserted-by":"crossref","unstructured":"Indelman V (2015) Towards information-theoretic decision making in a conservative information space. In: American Control Conference Chicago IL USA July 2015 pp. 2420\u20132426.","DOI":"10.1109\/ACC.2015.7171095"},{"key":"e_1_3_5_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2016.2518224"},{"key":"e_1_3_5_29_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914561102"},{"key":"e_1_3_5_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00023-X"},{"key":"e_1_3_5_31_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911430419"},{"key":"e_1_3_5_32_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"e_1_3_5_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"e_1_3_5_34_1","volume-title":"Rank Correlation Methods","author":"Kendall MG","year":"1948","unstructured":"Kendall MG (1948) Rank Correlation Methods. Tunbridge: Griffin."},{"key":"e_1_3_5_35_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918823086"},{"key":"e_1_3_5_36_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914547893"},{"key":"e_1_3_5_37_1","unstructured":"Kitanov A Indelman V (2019) Topological information-theoretic belief space planning with optimality guarantees. arXiv preprint arXiv:1903.00927."},{"key":"e_1_3_5_38_1","unstructured":"Koenig N Howard A (2004) Design and use paradigms for gazebo an open-source multi-robot simulator. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS). Sendai Japan September 2004."},{"key":"e_1_3_5_39_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364917721629"},{"key":"e_1_3_5_40_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912455072"},{"key":"e_1_3_5_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-0470-0_3"},{"key":"e_1_3_5_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00129169"},{"key":"e_1_3_5_43_1","first-page":"409","volume-title":"UAI","author":"McAllester DA","year":"1999","unstructured":"McAllester DA, Singh S (1999) Approximate planning for factored pomdps using belief state simplification. In: UAI. Morgan Kaufmann Publishers Inc., 409\u2013416."},{"key":"e_1_3_5_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2623344"},{"key":"e_1_3_5_45_1","doi-asserted-by":"crossref","unstructured":"Patil S Kahn G Laskey M et al. (2014) Scaling up gaussian belief space planning through covariance-free trajectory optimization and automatic differentiation. In: International Workshop on the Algorithmic Foundations of Robotics. Istanbul Turkey August 2014 WAFR pp. 515\u2013533.","DOI":"10.1007\/978-3-319-16595-0_30"},{"key":"e_1_3_5_46_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2078"},{"key":"e_1_3_5_47_1","doi-asserted-by":"crossref","unstructured":"Platt R Tedrake R Kaelbling L et al. (2010) Belief space planning assuming maximum likelihood observations. In: Robotics: Science and Systems. Zaragoza Spain: RSS pp. 587\u2013593.","DOI":"10.15607\/RSS.2010.VI.037"},{"key":"e_1_3_5_48_1","first-page":"2329","article-title":"Point-based value iteration for continuous pomdps","volume":"7","author":"Porta JM","year":"2006","unstructured":"Porta JM, Vlassis N, Spaan MT, et al. (2006) Point-based value iteration for continuous pomdps. J. of Machine Learning Research 7: 2329\u20132367.","journal-title":"J. of Machine Learning Research"},{"key":"e_1_3_5_49_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364909341659"},{"key":"e_1_3_5_50_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1496"},{"key":"e_1_3_5_51_1","first-page":"2164","volume-title":"Advances in Neural Information Processing Systems, NIPS","author":"Silver D","year":"2010","unstructured":"Silver D, Veness J (2010) Monte-carlo planning in large pomdps. In: Advances in Neural Information Processing Systems, NIPS. MIT Press, 2164\u20132172."},{"key":"e_1_3_5_52_1","unstructured":"Stachniss C Haehnel D Burgard W (2004) Exploration with active loop-closing for FastSLAM. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS). Sendai Japan September 2004."},{"key":"e_1_3_5_53_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045479"},{"key":"e_1_3_5_54_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912456319"},{"key":"e_1_3_5_55_1","doi-asserted-by":"crossref","unstructured":"Voss C Moll M Kavraki LE (2015) A heuristic approach to finding diverse short paths. In: IEEE Intl. Conf. on Robotics and Automation. ICRA pp. 4173\u20134179.","DOI":"10.1109\/ICRA.2015.7139774"},{"key":"e_1_3_5_56_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5328"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649221076381","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649221076381","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649221076381","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T02:31:01Z","timestamp":1767753061000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649221076381"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":55,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10.1177\/02783649221076381"],"URL":"https:\/\/doi.org\/10.1177\/02783649221076381","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"type":"print","value":"0278-3649"},{"type":"electronic","value":"1741-3176"}],"subject":[],"published":{"date-parts":[[2022,4]]}}}