Belief Space Planning via Factor Graphs and Re-use of Calculation

We propose 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 run-time 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 to 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.

Related Publications:

Journal Articles

  1. 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
  2. D. Kopitkov and V. Indelman, “Computationally Efficient Belief Space Planning via Augmented Matrix Determinant Lemma and Re-Use of Calculations,” IEEE Robotics and Automation Letters (RA-L), no. 2, 2017.
    Kopitkov17ral.pdf Kopitkov17ral.slides URL: http://ieeexplore.ieee.org/document/7801141/ Kopitkov17ral.supplementary
  3. 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

Technical Reports

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

Theses

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

Conference Articles

  1. D. Kopitkov and V. Indelman, “Computationally Efficient Active Inference in High-Dimensional State Spaces,” in AI for Long-term Autonomy, workshop in conjunction with IEEE International Conference on Robotics and Automation (ICRA), May 2016.
    Kopitkov16icra_ws.pdf Kopitkov16icra_ws.poster
  2. D. Kopitkov and V. Indelman, “Computationally Efficient Decision Making Under Uncertainty in High-Dimensional State Spaces,” in IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Oct. 2016.
    Kopitkov16iros.pdf Kopitkov16iros.slides