Simplified Decision Making in the Belief Space

2022

1. Journal

   Simplified decision making in the belief space using belief sparsification

   Khen Elimelech and Vadim Indelman

   International Journal of Robotics Research (IJRR), Sep 2022

   Abs DOI Bib

   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.

   @article{Elimelech22ijrr,
     bibtex_show = true,
     author = {Elimelech, Khen and Indelman, Vadim},
     author+an = {1=KE},
     title = {Simplified decision making in the belief space using belief sparsification},
     journal = {International Journal of Robotics Research ({IJRR})},
     volume = {41},
     number = {5},
     pages = {470-496},
     doi = {10.1177/02783649221076381},
     year = {2022}
   }

2021

1. Preprint

   Efficient Belief Space Planning in High-Dimensional State Spaces using PIVOT: Predictive Incremental Variable Ordering Tactic

   Khen Elimelech and Vadim Indelman

   arXiv:2112.14428, Dec 2021

   Abs arXiv Bib

   In this work, we examine the problem of online decision making under uncertainty, which we formulate as planning in the belief space. Maintaining beliefs (i.e., distributions) over high-dimensional states (e.g., entire trajectories) was not only shown to significantly improve accuracy, but also allows planning with information-theoretic objectives, as required for the tasks of active SLAM and information gathering. Nonetheless, planning under this "smoothing" paradigm holds a high computational complexity, which makes it challenging for online solution. Thus, we suggest the following idea: before planning, perform a standalone state variable reordering procedure on the initial belief, and "push forwards" all the predicted loop closing variables. Since the initial variable order determines which subset of them would be affected by incoming updates, such reordering allows us to minimize the total number of affected variables, and reduce the computational complexity of candidate evaluation during planning. We call this approach PIVOT: Predictive Incremental Variable Ordering Tactic. Applying this tactic can also improve the state inference efficiency; if we maintain the PIVOT order after the planning session, then we should similarly reduce the cost of loop closures, when they actually occur. To demonstrate its effectiveness, we applied PIVOT in a realistic active SLAM simulation, where we managed to significantly reduce the computation time of both the planning and inference sessions. The approach is applicable to general distributions, and induces no loss in accuracy.

   @article{Elimelech21pivot_preprint,
     bibtex_show = true,
     author = {Elimelech, Khen and Indelman, Vadim},
     author+an = {1=KE},
     title = {Efficient Belief Space Planning in High-Dimensional State Spaces using {PIVOT}: {P}redictive {I}ncremental {V}ariable {O}rdering {T}actic},
     journal = {arXiv:2112.14428},
     year = {2021},
     month = dec,
     keywords = {preprint}
   }

2. Journal

   Efficient Modification of the Upper Triangular Square Root Matrix on Variable Reordering

   Khen Elimelech and Vadim Indelman

   IEEE Robotics and Automation Letters (RA-L), Apr 2021

   also selected for presentation at ICRA 2021

   Abs DOI Bib

   In probabilistic state inference, we seek to estimate the state of an (autonomous) agent from noisy observations. It can be shown that, under certain assumptions, finding the estimate is equivalent to solving a linear least squares problem. Solving such a problem is done by calculating the upper triangular matrix R from the coefficient matrix A, using the QR or Cholesky factorizations; this matrix is commonly referred to as the "square root matrix". In sequential estimation problems, we are often interested in periodic optimization of the state variable order, e.g., to reduce fill-in, or to apply a predictive variable ordering tactic; however, changing the variable order implies expensive re-factorization of the system. Thus, we address the problem of modifying an existing square root matrix R, to convey reordering of the variables. To this end, we identify several conclusions regarding the effect of column permutation on the factorization, to allow efficient modification of R, without accessing A at all, or with minimal re-factorization. The proposed parallelizable algorithm achieves a significant improvement in performance over the state-of-the-art incremental Smoothing And Mapping (iSAM2) algorithm, which utilizes incremental factorization to update R.

   @article{Elimelech21ral,
     bibtex_show = true,
     author = {Elimelech, Khen and Indelman, Vadim},
     author+an = {1=KE},
     title = {Efficient Modification of the Upper Triangular Square Root Matrix on Variable Reordering},
     journal = {{IEEE} Robotics and Automation Letters ({RA-L})},
     volume = {6},
     number = {2},
     pages = {675-682},
     doi = {10.1109/LRA.2020.3048663},
     issn = {2377-3766},
     year = {2021},
     month = apr,
     note = {also selected for presentation at ICRA 2021}
   }

3. Thesis

   Efficient Decision Making under Uncertainty in High-Dimensional State Spaces

   Khen Elimelech

   Technion – Israel Institute of Technology, Jun 2021

   Awarded Bib

   Outstanding Ph.D. Research Award, ISTRC

   @phdthesis{Elimelech21thesis,
     bibtex_show = true,
     author = {Elimelech, Khen},
     author+an = {1=KE},
     title = {Efficient Decision Making under Uncertainty in High-Dimensional State Spaces},
     school = {Technion -- Israel Institute of Technology},
     month = jun,
     year = {2021},
   }

2019

1. Conference

   Introducing PIVOT: Predictive Incremental Variable Ordering Tactic for Efficient Belief Space Planning

   Khen Elimelech and Vadim Indelman

   In International Symposium on Robotics Research (ISRR), Hanoi, Vietnam, Oct 2019

   Abs Bib Supp

   Belief Space Planning (BSP) is a fundamental technique in artificial intelligence and robotics, which is widely used in the solution of problems such as online autonomous navigation and manipulation. Unfortunately, BSP is computationally demanding, especially when dealing with high-dimensional state spaces. We thus introduce PIVOT: Predictive Incremental Variable Ordering Tactic, a novel approach to improve planning efficiency. Although variable ordering has been extensively used for the state inference problem, variable ordering specifically for planning has hardly been considered. Interestingly, this tactic can also lead to improved loop-closing efficiency during state inference. We use the approach in an active-SLAM scenario, and demonstrate a significant improvement in efficiency. This approach follows our previous work regarding efficient BSP via belief sparsification.

   @inproceedings{Elimelech19isrr,
     bibtex_show = true,
     author = {Elimelech, Khen and Indelman, Vadim},
     author+an = {1=KE},
     title = {Introducing {PIVOT}: {P}redictive {I}ncremental {V}ariable {O}rdering {T}actic for Efficient Belief Space Planning},
     booktitle = {International Symposium on Robotics Research ({ISRR})},
     year = {2019},
     month = oct,
     location = {Hanoi, Vietnam},
   }

2017

1. Conference

   Consistent Sparsification for Efficient Decision Making Under Uncertainty in High Dimensional State Spaces

   Khen Elimelech and Vadim Indelman

   In IEEE International Conference on Robotics and Automation (ICRA), Singapore, May 2017

   Abs DOI Bib

   In this paper we introduce a novel approach for efficient decision making under uncertainty and belief space planning, in high dimensional state spaces. While recently developed methods focus on sparsifying the inference process, the sparsification here is done in the context of efficient decision making, with no impact on the state inference. By identifying state variables which are uninvolved in the decision, we generate a sparse version of the state’s information matrix, to be used in the examination of candidate actions. This sparse approximation is action-consistent, i.e. has no influence on the action selection. Overall we manage to maintain the same quality of solution, while reducing the computational complexity of the problem. The approach is put to the test in a SLAM simulation, where a significant improvement in runtime is achieved. Nevertheless, the method is generic, and not tied to a specific type of problem.

   @inproceedings{Elimelech17icra,
     bibtex_show = true,
     author = {Elimelech, Khen and Indelman, Vadim},
     author+an = {1=KE},
     title = {Consistent Sparsification for Efficient Decision Making Under Uncertainty in High Dimensional State Spaces},
     booktitle = {{IEEE} International Conference on Robotics and Automation ({ICRA})},
     pages = {3786-3791},
     doi = {10.1109/ICRA.2017.7989437},
     year = {2017},
     month = may,
     location = {Singapore}
   }

2. Conference

   Scalable Sparsification for Efficient Decision Making Under Uncertainty in High Dimensional State Spaces

   Khen Elimelech and Vadim Indelman

   In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, Canada, Sep 2017

   Abs DOI Bib

   In this paper we introduce a novel sparsification method for efficient decision making under uncertainty and belief space planning in high dimensional state spaces. By using a sparse version of the state’s information matrix, we are able to improve the high computational cost of examination of all candidate actions. We also present an in-depth analysis for the general case of approximated decision making, and use it in order to set bounds over the induced error in potential revenue. The scalability of the method allows balancing between the degree of sparsification and the tolerance for this error, in order to maximize its benefits. The approach differs from recent methods by focusing on improving the decision making process directly, and not as a byproduct of a sparsification of the state inference. Eventually, we demonstrate the superiority of the approach in a SLAM simulation, where we manage to maintain the accuracy of the solution, while demonstrating a significant improvement in run time.

   @inproceedings{Elimelech17iros,
     bibtex_show = true,
     author = {Elimelech, Khen and Indelman, Vadim},
     author+an = {1=KE},
     title = {Scalable Sparsification for Efficient Decision Making Under Uncertainty in High Dimensional State Spaces},
     booktitle = {{IEEE/RSJ} International Conference on Intelligent Robots and Systems ({IROS})},
     pages = {5668-5673},
     doi = {10.1109/IROS.2017.8206456},
     year = {2017},
     month = sep,
     location = {Vancouver, Canada}
   }

3. Conference

   Fast Action Elimination for Efficient Decision Making and Belief Space Planning Using Bounded Approximations

   Khen Elimelech and Vadim Indelman

   In International Symposium on Robotics Research (ISRR), Puerto Varas, Chile, Dec 2017

   Abs Bib

   In this paper we develop a novel paradigm to efficiently solve decision making and planning problems, and demonstrate it for the challenging case of planning under uncertainty. While conventional methods tend to optimize properties of specific problems, and sacrifice performance in order to reduce their complexity, our approach has no coupling to a specific problem, and relies solely on the structure of the general decision making problem, in order to directly reduce its computational cost, with no influence over the quality of solution, nor the maintained state. Using bounded approximations of the state, we can easily eliminate unfit actions, while sparing the need to evaluate the exact revenues (or rewards) of all the candidate actions. The original problem can then be solved considering a minimal subset of candidates. Since the approach is especially relevant when the action domain is large, and revenues are expensive to evaluate, we later extend the discussion specifically for decision making under uncertainty and belief space planning, and present dedicated and practical tools, in order to apply the method to a sensor deployment problem. This paper continues our previous work towards efficient decision making.

   @inproceedings{Elimelech17isrr,
     bibtex_show = true,
     author = {Elimelech, Khen and Indelman, Vadim},
     author+an = {1=KE},
     title = {Fast Action Elimination for Efficient Decision Making and Belief Space Planning Using Bounded Approximations},
     booktitle = {International Symposium on Robotics Research ({ISRR})},
     year = {2017},
     month = dec,
     location = {Puerto Varas, Chile},
     keywords = {duplicate}
   }