Sparsification for Decision Making in High-Dimensional State Spaces

In this research we introduce and investigate simplification of decision making problems in partially observable domains, while providing performance guarantees. Specifically, we propose the conceptual idea of resorting to sparsification and conservative information fusion techniques for information-theoretic decision making, aiming to address challenges involved with decision making over a potentially high-dimensional and highly-correlated, information space. ur key observation is that in certain cases, the impact of any two actions (or policies) on an appropriate utility measure, such as entropy, has the same trend regardless if using the original probability distribution function (pdf) or an appropriately sparsified approximation of thereof. This observation suggests that in these cases, decision making can be performed over a sparsified (possibly conservative) pdf, instead of the original pdf, without sacrificing performance. We call such a simplification as action-consistent simplification. Finding an action-consistent simplification, in our case, belief sparsification, is not trivial in general. However, a computationally-easy simplification that is not necessarily action-consistent can still be very useful if the potential loss in performance (regret) can be quantified or bounded. In this research we investigate these and additional aspects considering decision making in high dimensional state spaces.

Related Publications:

Journal Articles

  1. 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
  2. K. Elimelech and V. Indelman, “Efficient Modification of the Upper Triangular Square Root Matrix on Variable Reordering,” IEEE Robotics and Automation Letters (RA-L), no. 2, Apr. 2021.
    Elimelech21ral.pdf Elimelech21ral.slides DOI: 10.1109/LRA.2020.3048663 Elimelech21ral.video
  3. V. Indelman, “No Correlations Involved: Decision Making Under Uncertainty in a Conservative Sparse Information Space,” IEEE Robotics and Automation Letters (RA-L), no. 1, 2016.
    Indelman16ral.pdf URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7383252 Indelman16ral.supplementary

Book Chapters

  1. 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
  2. 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

Theses

  1. 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

Technical Reports

  1. 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
  2. K. Elimelech and V. Indelman, “Efficient Decision Making and Belief Space Planning using Sparse Approximations,” 2019.
    arXiv: https://arxiv.org/abs/1909.00885

Conference Articles

  1. 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
  2. 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
  3. K. Elimelech and V. Indelman, “Efficient Belief Space Planning using Sparse Approximations,” in RSS Pioneers Workshop, 2019.
    Elimelech19rss_ws.pdf
  4. K. Elimelech and V. Indelman, “Consistent Sparsification for Efficient Decision Making Under Uncertainty in High Dimensional State Spaces,” in IEEE International Conference on Robotics and Automation (ICRA), May 2017.
    Elimelech17icra.pdf Elimelech17icra.slides
  5. K. Elimelech and V. Indelman, “Scalable Sparsification for Efficient Decision Making Under Uncertainty in High Dimensional State Spaces,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Sep. 2017.
    Elimelech17iros.pdf Elimelech17iros.slides
  6. 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
  7. V. Indelman, “No Correlations Involved: Decision Making Under Uncertainty in a Conservative Sparse Information Space,” in IEEE International Conference on Robotics and Automation (ICRA), submission via IEEE Robotics and Automation Letters (RA-L), May 2016.
    Indelman16icra.pdf Indelman16icra.slides
  8. V. Indelman, “Towards Information-Theoretic Decision Making in a Conservative Information Space,” in American Control Conference (ACC), Jul. 2015.
    Indelman15acc.pdf Indelman15acc.slides
  9. V. Indelman, “On Decision Making and Planning in the Conservative Information Space - Is the Concept Applicable to Active SLAM?,” in The Problem of Mobile Sensors: Setting future goals and indicators of progress for SLAM, workshop in conjunction with Robotics Science and Systems (RSS) Conference, Jul. 2015.
    Indelman15rss_ws_a.pdf Indelman15rss_ws_a.poster