Belief Space Planning

Single- and Multi-Robot

Reliable planning under uncertainty is crucial in many application endeavors in which the platform operates in full or partial autonomy, such as autonomous navigation and exploration, monitoring, surveillance and robotic surgery. Autonomous operation in complex unknown scenarios involves a deep intertwining of estimation and planning capabilities. The agent has to fuse sensor measurements in order to infer its state and to build a model of the surrounding environment. Moreover, accomplishing given goals with high accuracy and robustness requires accounting for different sources of uncertainty within motion planning. Consequently, planning should be done in the belief space, a problem also known as partially observable Markov decision process (POMDP). In this research we develop approaches for planning under uncertainty when the environment model in which the platform operates is unknown or uncertain, and in lack of sources of absolute information (e.g. no GPS). We represent the agent state and the state of the surrounding environment within the belief space, and investigate approaches for planning in the continuous domain.

Related Publications:

Journal Articles

  1. A. Kitanov and V. Indelman, “Topological Belief Space Planning for Active SLAM with Pairwise Gaussian Potentials and Performance Guarantees,” International Journal of Robotics Research (IJRR), no. 1, 2024.
    Kitanov24ijrr.pdf DOI: 10.1177/02783649231204898
  2. A. Zhitnikov and V. Indelman, “Simplified Continuous High Dimensional Belief Space Planning with Adaptive Probabilistic Belief-dependent Constraints,” IEEE Transactions on Robotics (T-RO), 2024.
    Zhitnikov24tro.pdf DOI: 10.1109/TRO.2023.3341625
  3. M. Barenboim, M. Shienman, and V. Indelman, “Monte Carlo Planning in Hybrid Belief POMDPs,” IEEE Robotics and Automation Letters (RA-L), no. 8, Aug. 2023.
    Barenboim23ral.pdf DOI: 10.1109/LRA.2023.3282773 Barenboim23ral.supplementary
  4. J. Placed et al., “A Survey on Active Simultaneous Localization and Mapping: State of the Art and New Frontiers,” IEEE Transactions on Robotics (T-RO), no. 3, Jun. 2023.
    Placed23tro.pdf DOI: 10.1109/TRO.2023.3248510
  5. V. Tchuiev and V. Indelman, “Epistemic Uncertainty Aware Semantic Localization and Mapping for Inference and Belief Space Planning,” Artificial Intelligence, Special Issue on Risk-Aware Autonomous Systems, 2023.
    Tchuiev23ai.pdf DOI: 10.1016/j.artint.2023.103903
  6. M. Barenboim, I. Lev-Yehudi, and V. Indelman, “Data Association Aware POMDP Planning with Hypothesis Pruning Performance Guarantees,” IEEE Robotics and Automation Letters (RA-L), no. 10, Oct. 2023.
    Barenboim23ral2.pdf DOI: 10.1109/LRA.2023.3311205 Barenboim23ral2.supplementary
  7. E. Farhi and V. Indelman, “Bayesian Incremental Inference Update by Re-using Calculations from Belief Space Planning: A New Paradigm,” Autonomous Robots, Aug. 2022.
    Farhi22arj.pdf DOI: 10.1007/s10514-022-10045-w
  8. K. Elimelech and V. Indelman, “Simplified decision making in the belief space using belief sparsification,” International Journal of Robotics Research (IJRR), no. 5, Jun. 2022.
    Elimelech22ijrr.pdf DOI: 10.1177/02783649221076381
  9. D. Kopitkov and V. Indelman, “General Purpose Incremental Covariance Update and Efficient Belief Space Planning via Factor-Graph Propagation Action Tree,” International Journal of Robotics Research (IJRR), no. 14, Sep. 2019.
    Kopitkov19ijrr.pdf URL: https://journals.sagepub.com/doi/10.1177/0278364919875199
  10. T. Regev and V. Indelman, “Decentralized Multi-Robot Belief Space Planning in Unknown Environments via Identification and Efficient Re-Evaluation of Impacted Paths,” Autonomous Robots, Special Issue on Online Decision Making in Multi-Robot Coordination, no. 4, 2018.
    Regev17arj.pdf DOI: 10.1007/s10514-017-9659-4
  11. S. Pathak, A. Thomas, and V. Indelman, “A Unified Framework for Data Association Aware Belief Space Planning and Perception,” International Journal of Robotics Research (IJRR), no. 2-3, 2018.
    Pathak18ijrr.pdf DOI: 10.1177/0278364918759606
  12. V. Indelman, “Cooperative Multi-Robot Belief Space Planning for Autonomous Navigation in Unknown Environments,” Autonomous Robots, Special Issue on Active Perception, 2017.
    Indelman17arj.pdf DOI: 10.1007/s10514-017-9620-6
  13. D. Kopitkov and V. Indelman, “No Belief Propagation Required: Belief Space Planning in High-Dimensional State Spaces via Factor Graphs, Matrix Determinant Lemma and Re-use of Calculation,” International Journal of Robotics Research (IJRR), no. 10, 2017.
    Kopitkov17ijrr.pdf DOI: 10.1177/0278364917721629
  14. V. Indelman, L. Carlone, and F. Dellaert, “Planning in the Continuous Domain: a Generalized Belief Space Approach for Autonomous Navigation in Unknown Environments,” International Journal of Robotics Research (IJRR), no. 7, 2015.
    Indelman15ijrr.pdf URL: http://ijr.sagepub.com/content/34/7/849.full.pdf+html

Conference Articles

  1. I. Lev-Yehudi, M. Barenboim, and V. Indelman, “Simplifying Complex Observation Models in Continuous POMDP Planning with Probabilistic Guarantees and Practice,” in 38th AAAI Conference on Artificial Intelligence (AAAI-24), Feb. 2024.
    LevYehudi24aaai.pdf LevYehudi24aaai.slides LevYehudi24aaai.poster
  2. M. Barenboim and V. Indelman, “Online POMDP Planning with Anytime Deterministic Guarantees,” in Conference on Neural Information Processing Systems (NeurIPS), Dec. 2023.
    Barenboim23nips.pdf Barenboim23nips.supplementary Barenboim23nips.poster
  3. M. Shienman and V. Indelman, “D2A-BSP: Distilled Data Association Belief Space Planning with Performance Guarantees Under Budget Constraints,” in IEEE International Conference on Robotics and Automation (ICRA), *Outstanding Paper Award Finalist*, May 2022.
    Shienman22icra.pdf Shienman22icra.supplementary Shienman22icra.poster
  4. M. Barenboim and V. Indelman, “Adaptive Information Belief Space Planning,” in the 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence (IJCAI-ECAI), Jul. 2022.
    Barenboim22ijcai.pdf arXiv: https://arxiv.org/pdf/2201.05673.pdf Barenboim22ijcai.supplementary
  5. I. Zilberman and V. Indelman, “Qualitative Belief Space Planning via Compositions,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Oct. 2022.
    Zilberman22iros.pdf Zilberman22iros.supplementary Zilberman22iros.video
  6. O. Sztyglic and V. Indelman, “Speeding up POMDP Planning via Simplification,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Oct. 2022.
    Sztyglic22iros.pdf Sztyglic22iros.supplementary Sztyglic22iros.video
  7. M. Shienman and V. Indelman, “Nonmyopic Distilled Data Association Belief Space Planning Under Budget Constraints,” in International Symposium on Robotics Research (ISRR), Sep. 2022.
    Shienman22isrr.pdf Shienman22isrr.supplementary
  8. O. Asraf and V. Indelman, “Experience-Based Prediction of Unknown Environments for Enhanced Belief Space Planning,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Oct. 2020.
    Asraf20iros.pdf Asraf20iros.supplementary
  9. E. Farhi and V. Indelman, “iX-BSP: Belief Space Planning through Incremental Expectation,” in IEEE International Conference on Robotics and Automation (ICRA), May 2019.
    Farhi19icra.pdf Farhi19icra.supplementary Farhi19icra.poster
  10. K. Elimelech and V. Indelman, “PIVOT: Predictive Incremental Variable Ordering Tactic for Efficient Belief Space Planning,” in Workshop on Toward Online Optimal Control of Dynamic Robots, in conjunction with the IEEE International Conference on Robotics and Automation (ICRA), May 2019.
    Elimelech19icra_ws.poster
  11. E. Farhi and V. Indelman, “Tear Down that Wall: Calculation Reuse Across Inference and Belief Space Planning,” in Workshop on Toward Online Optimal Control of Dynamic Robots, in conjunction with the IEEE International Conference on Robotics and Automation (ICRA), May 2019.
    Farhi19icra_ws.pdf Farhi19icra_ws.poster
  12. K. Elimelech and V. Indelman, “Introducing PIVOT: Predictive Incremental Variable Ordering Tactic for Efficient Belief Space Planning,” in International Symposium on Robotics Research (ISRR), Oct. 2019.
    Elimelech19isrr.pdf Elimelech19isrr.slides
  13. K. Elimelech and V. Indelman, “Efficient Belief Space Planning using Sparse Approximations,” in RSS Pioneers Workshop, 2019.
    Elimelech19rss_ws.pdf
  14. A. Kitanov and V. Indelman, “Topological Multi-Robot Belief Space Planning in Unknown Environments,” in IEEE International Conference on Robotics and Automation (ICRA), May 2018.
    Kitanov18icra.pdf Kitanov18icra.video Kitanov18icra.poster
  15. Y. Ben-Elisha and V. Indelman, “Active Online Visual-Inertial Navigation and Sensor Calibration via Belief Space Planning and Factor Graph Based Incremental Smoothing,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Sep. 2017.
    BenElisha17iros.pdf BenElisha17iros.slides BenElisha17iros.supplementary
  16. K. Elimelech and V. Indelman, “Fast Action Elimination for Efficient Decision Making and Belief Space Planning Using Bounded Approximations,” in International Symposium on Robotics Research (ISRR), Dec. 2017.
    Elimelech17isrr.pdf Elimelech17isrr.slides
  17. T. Regev and V. Indelman, “Multi-Robot Decentralized Belief Space Planning in Unknown Environments via Efficient Re-Evaluation of Impacted Paths,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Oct. 2016.
    Regev16iros.pdf Regev16iros.slides
  18. V. Indelman, “Towards Multi-Robot Active Collaborative State Estimation via Belief Space Planning,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Sep. 2015.
    Indelman15iros.pdf Indelman15iros.slides Indelman15iros.video
  19. V. Indelman, “Towards Cooperative Multi-Robot Belief Space Planning in Unknown Environments,” in International Symposium on Robotics Research (ISRR), Sep. 2015.
    Indelman15isrr.pdf Indelman15isrr.slides
  20. V. Indelman, “On Multi-Robot Active Collaborative Inference in Unknown Environments via Belief Space Planning,” in Principles of Multi-Robot Systems, workshop in conjunction with Robotics Science and Systems (RSS) Conference, Jul. 2015.
    Indelman15rss_ws_b.pdf Indelman15rss_ws_b.poster
  21. V. Indelman, L. Carlone, and F. Dellaert, “Planning Under Uncertainty in the Continuous Domain: a Generalized Belief Space Approach,” in IEEE International Conference on Robotics and Automation (ICRA), Jun. 2014.
    Indelman14icra_a.pdf Indelman14icra_a.slides
  22. V. Indelman, L. Carlone, and F. Dellaert, “Towards Planning in Generalized Belief Space,” in International Symposium on Robotics Research (ISRR), Dec. 2013.
    Indelman13isrr.pdf Indelman13isrr.slides

Book Chapters

  1. M. Shienman and V. Indelman, “Nonmyopic Distilled Data Association Belief Space Planning Under Budget Constraints,” in Robotics Research, Springer, 2023.
    Shienman23chapter.pdf DOI: 10.1007/978-3-031-25555-7_8
  2. K. Elimelech and V. Indelman, “Introducing PIVOT: Predictive Incremental Variable Ordering Tactic for Efficient Belief Space Planning,” in Robotics Research, Springer, 2022.
    Elimelech19isrr_chapter.pdf DOI: 10.1007/978-3-030-95459-8_6
  3. K. Elimelech and V. Indelman, “Fast Action Elimination for Efficient Decision Making and Belief Space Planning Using Bounded Approximations,” in Robotics Research, Springer, 2020.
    Elimelech20chapter.pdf URL: https://link.springer.com/chapter/10.1007/978-3-030-28619-4_58
  4. V. Indelman, “Towards Cooperative Multi-Robot Belief Space Planning in Unknown Environments,” in Robotics Research, Springer, 2018.
    URL: http://www.springer.com/gp/book/9783319515311
  5. V. Indelman, L. Carlone, and F. Dellaert, “Towards Planning in Generalized Belief Space,” in Robotics Research, The 16th International Symposium ISRR, Springer, 2016, pp. 593–609.
    Indelman16chapter.pdf URL: http://link.springer.com/chapter/10.1007%2F978-3-319-28872-7_34

Theses

  1. T. Yotam, “Measurement Simplification in ρ-POMDP with Performance Guarantees,” Master's thesis, Technion - Israel Institute of Technology, 2023.
    Yotam23thesis.pdf Yotam23thesis.slides Yotam23thesis.video
  2. I. Zilberman, “Belief Space Planning using Qualitative Spatial Relationships,” Master's thesis, Technion - Israel Institute of Technology, 2022.
    Zilberman22thesis.pdf Zilberman22thesis.slides Zilberman22thesis.video
  3. G. Rotman, “Efficient Informative Planning with High-dimensional Non-Gaussian Beliefs by Exploiting Structure,” Master's thesis, Technion - Israel Institute of Technology, 2022.
    Rotman22thesis.pdf Rotman22thesis.slides Rotman22thesis.video
  4. E. Farhi, “Joint Incremental Inference and Belief Space Planning for Online Operations of Autonomous systems,” PhD thesis, Technion - Israel Institute of Technology, 2021.
    Farhi21thesis.pdf Farhi21thesis.slides Farhi21thesis.video
  5. V. Tchuiev, “Autonomous Classification Under Uncertainty,” PhD thesis, Technion - Israel Institute of Technology, 2021.
    Tchuiev21thesis.pdf Tchuiev21thesis.slides Tchuiev21thesis.video
  6. K. Elimelech, “Efficient Decision Making under Uncertainty in High-Dimensional State Spaces,” PhD thesis, Technion - Israel Institute of Technology, 2021.
    Elimelech21thesis.pdf Elimelech21thesis.slides Elimelech21thesis.video
  7. O. Sztyglic, “Online Partially Observable Markov Decision Process Planning via Simplification,” Master's thesis, Technion - Israel Institute of Technology, 2021.
    Sztyglic21thesis.pdf Sztyglic21thesis.slides Sztyglic21thesis.video
  8. O. Asraf, “Experience-Based Prediction of Unknown Environments for Enhanced Belief Space Planning,” Master's thesis, Technion - Israel Institute of Technology, 2020.
    Asraf20thesis.pdf Asraf20thesis.slides
  9. S. Har-Nes, “Belief Space Planning for Autonomous Navigation while Modeling Landmark Identification,” Master's thesis, Technion - Israel Institute of Technology, 2017.
    HarNes17thesis.pdf HarNes17thesis.slides
  10. A. Thomas, “Incorporating Data Association Within Belief Space Planning For Robust Autonomous Navigation,” Master's thesis, Technion - Israel Institute of Technology, 2017.
    Thomas17thesis.pdf Thomas17thesis.slides
  11. D. Kopitkov, “Efficient Belief Space Planning in High-dimensional State Spaces by Exploiting Sparsity and Calculation Re-use,” Master's thesis, Technion - Israel Institute of Technology, 2017.
    Kopitkov17thesis.pdf Kopitkov17thesis.slides
  12. Y. Ben-Elisha, “Cooperative Multi-Robot Belief Space Planning for Visual-Inertial Navigation and Online Sensor Calibration,” Master's thesis, Technion - Israel Institute of Technology, 2017.
    BenElisha17thesis.pdf BenElisha17thesis.slides
  13. T. Regev, “Multi-Robot Decentralized Belief Space Planning in Unknown Environments,” Master's thesis, Technion - Israel Institute of Technology, 2016.
    Regev16thesis.pdf Regev16thesis.slides

Technical Reports

  1. T. Yotam and V. Indelman, “Measurement Simplification in ρ-POMDP with Performance Guarantees,” Sep. 2023.
    arXiv: https://arxiv.org/abs/2309.10701
  2. A. Zhitnikov, O. Sztyglic, and V. Indelman, “No Compromise in Solution Quality: Speeding Up Belief-dependent Continuous POMDPs via Adaptive Multilevel Simplification,” 2023.
    arXiv: https://arxiv.org/abs/2310.10274
  3. G. Rotman and V. Indelman, “involve-MI: Informative Planning with High-Dimensional Non-Parametric Beliefs,” Sep. 2022.
    arXiv: https://arxiv.org/pdf/2209.11591.pdf
  4. E. Farhi and V. Indelman, “iX-BSP: Incremental Belief Space Planning,” 2021.
    arXiv: https://arxiv.org/pdf/2102.09539
  5. A. Zhitnikov and V. Indelman, “Probabilistic Loss and its Online Characterization for Simplified Decision Making Under Uncertainty,” 2021.
    arXiv: https://arxiv.org/pdf/2105.05789.pdf
  6. K. Elimelech and V. Indelman, “Efficient Belief Space Planning in High-Dimensional State Spaces using PIVOT: Predictive Incremental Variable Ordering Tactic,” 2021.
    arXiv: https://arxiv.org/pdf/2112.14428.pdf
  7. O. Sztyglic, A. Zhitnikov, and V. Indelman, “Simplified Belief-Dependent Reward MCTS Planning with Guaranteed Tree Consistency,” May 2021.
    arXiv: https://arxiv.org/pdf/2105.14239.pdf
  8. D. Kopitkov and V. Indelman, “General Purpose Incremental Covariance Update and Efficient Belief Space Planning via Factor-Graph Propagation Action Tree,” 2019.
    arXiv: https://arxiv.org/abs/1906.02249
  9. K. Elimelech and V. Indelman, “Efficient Decision Making and Belief Space Planning using Sparse Approximations,” 2019.
    arXiv: https://arxiv.org/abs/1909.00885