# Belief Space Planning via Factor Graphs, Matrix Determinant Lemma 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.

### Articles

• 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, 36(10):1088-1130, 2017. doi:https://doi.org/10.1177/0278364917721629
[BibTeX] [PDF]
@Article{Kopitkov17ijrr,
author = {D. Kopitkov and V. Indelman},
title = {No Belief Propagation Required: Belief Space Planning in High-Dimensional State Spaces via Factor Graphs, Matrix Determinant Lemma and Re-use of Calculation},
journal = "International Journal of Robotics Research",
year = 2017,
year = 2017,
volume = 36,
number = 10,
pages = {1088-1130},
pdf = "http://indelman.github.io/ANPL-Website/Publications/Kopitkov17ijrr.pdf",
doi = "https://doi.org/10.1177/0278364917721629",
researchtopic = {RAMDL, BeliefSpacePlanning},
}

• 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), 2(2):506-513, 2017.
[BibTeX] [URL] [PDF] [Supplementary Material]
@Article{Kopitkov17ral,
author = {D. Kopitkov and V. Indelman},
title = {Computationally Efficient Belief Space Planning via Augmented Matrix Determinant Lemma and Re-Use of Calculations},
journal = {IEEE Robotics and Automation Letters (RA-L)},
year = 2017,
pages = "506-513",
volume = 2,
number = 2,
pdf = "http://indelman.github.io/ANPL-Website/Publications/Kopitkov17ral.pdf",
supplementary = "http://indelman.github.io/ANPL-Website/Publications/Kopitkov17ral_Supplementary.pdf",
url = "http://ieeexplore.ieee.org/document/7801141/",
researchtopic = {RAMDL},
}

### In Proceedings

• D. Kopitkov and V. Indelman. Computationally Efficient Belief Space Planning via Augmented Matrix Determinant Lemma and Re-Use of Calculations. In IEEE International Conference on Robotics and Automation (ICRA), submission via IEEE Robotics and Automation Letters (RA-L), May 2017.
[BibTeX] [PDF] [Slides] [Supplementary Material]
@InProceedings{Kopitkov17icra,
author = {D. Kopitkov and V. Indelman},
title = {Computationally Efficient Belief Space Planning via Augmented Matrix Determinant Lemma and Re-Use of Calculations},
booktitle = "IEEE International Conference on Robotics and Automation (ICRA), submission via IEEE Robotics and Automation Letters (RA-L)",
year = 2017,
pdf = "http://indelman.github.io/ANPL-Website/Publications/Kopitkov17ral.pdf",
supplementary = "http://indelman.github.io/ANPL-Website/Publications/Kopitkov17ral_Supplementary.pdf",
slides = "http://indelman.github.io/ANPL-Website/Publications/Kopitkov17icra_ppt.pdf",
month = "May",
location = {Singapore},
researchtopic = {RAMDL},
}

• 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), October 2016.
[BibTeX] [PDF] [Slides]
@inproceedings{Kopitkov16iros,
author = {D. Kopitkov and V. Indelman},
title = {Computationally Efficient Decision Making Under Uncertainty in High-Dimensional State Spaces},
booktitle = "IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)",
year = 2016,
month = "October",
location = {Daejeon, Korea},
pdf = "http://indelman.github.io/ANPL-Website/Publications/Kopitkov16iros.pdf",
slides = "http://indelman.github.io/ANPL-Website/Publications/Kopitkov16iros_ppt.pdf",
researchtopic = {RAMDL},
}

• 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.
[BibTeX] [PDF] [Poster]
@inproceedings{Kopitkov16icra_ws,
author = {D. Kopitkov and V. Indelman},
title = {Computationally Efficient Active Inference in High-Dimensional State Spaces},
booktitle = {AI for Long-term Autonomy, workshop in conjunction with IEEE International Conference on Robotics and Automation (ICRA)},
year = 2016,
month = "May",
location = {Sweden},
pdf = "http://indelman.github.io/ANPL-Website/Publications/Kopitkov16icra_ws.pdf",
poster = "http://indelman.github.io/ANPL-Website/Publications/Kopitkov16icra_ws_poster.pdf",
researchtopic = {RAMDL},
}

### Technical Reports

• D. Kopitkov and V. Indelman. Computationally Efficient Belief Space Planning via Augmented Matrix Determinant Lemma and Re-Use of Calculations – Supplementary Material. Technical Report ANPL-2017-01, Technion – Israel Institute of Technology, 2017.
[BibTeX] [PDF]
@TechReport{Kopitkov17ral_Supplementary,
author = {D. Kopitkov and V. Indelman},
title = {Computationally Efficient Belief Space Planning via Augmented Matrix Determinant Lemma and Re-Use of Calculations - Supplementary Material},
pdf = "http://indelman.github.io/ANPL-Website/Publications/Kopitkov17ral_Supplementary.pdf",
institution = "Technion - Israel Institute of Technology",
year = 2017,
number = "ANPL-2017-01",
researchtopic = {RAMDL},
}