# Decision Making and Planning in High Dimensional State Spaces

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 high-dimensional, possibly highly-correlated, information space. Our key observation is that in certain cases, the impact of any two actions (or controls) 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.

In particular, we consider a specific conservative pdf that decouples the random variables in the joint pdf, admitting extremely efficient entropy computation. The left figure below illustrates this process for a two-dimensional state. The two images on the right show a posteriori covariances for two different actions calculated using the original and conservative a priori covariance matrices.

The concept is particularly applicable to decision making in high-dimensional state spaces, e.g. in context of SLAM.

## Related Publications:

### Articles

• 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 = {CBS},
}

• V. Indelman. No Correlations Involved: Decision Making Under Uncertainty in a Conservative Sparse Information Space. IEEE Robotics and Automation Letters (RA-L), 1(1):407-414, 2016.
[BibTeX] [URL] [PDF] [Supplementary Material]
@Article{Indelman16ral,
author = {V. Indelman},
title = {No Correlations Involved: Decision Making Under Uncertainty in a Conservative Sparse Information Space},
journal = {IEEE Robotics and Automation Letters (RA-L)},
volume = {1},
number = {1},
pages = {407-414},
year={2016},
url = "http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7383252",
pdf = "http://indelman.github.io/ANPL-Website/Publications/Indelman16ral.pdf",
supplementary = "http://indelman.github.io/ANPL-Website/Publications/Indelman16ral_Supplementary.pdf",
researchtopic = {CBS},
}

### 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] [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",
month = "May",
location = {Singapore},
researchtopic = {CBS},
}

• E. Farhi and V. Indelman. Towards Efficient Inference Update through Planning via JIP – Joint Inference and Belief Space Planning. In IEEE International Conference on Robotics and Automation (ICRA), May 2017.
[BibTeX] [PDF]
@InProceedings{Farhi17icra,
author = {E. Farhi and V. Indelman},
title = {Towards Efficient Inference Update through Planning via JIP - Joint Inference and Belief Space Planning},
booktitle = "IEEE International Conference on Robotics and Automation (ICRA)",
year = 2017,
month = "May",
pdf = "http://indelman.github.io/ANPL-Website/Publications/Farhi17icra.pdf",
location = {Singapore},
researchtopic = {BeliefSpacePlanning, CBS},
}

• 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.
[BibTeX] [PDF]
@InProceedings{Elimelech17icra,
author = {K. Elimelech and V. Indelman},
title = {Consistent Sparsification for Efficient Decision Making Under Uncertainty in High Dimensional State Spaces},
booktitle = "IEEE International Conference on Robotics and Automation (ICRA)",
year = 2017,
month = "May",
pdf = "http://indelman.github.io/ANPL-Website/Publications/Elimelech17icra.pdf",
location = {Singapore},
researchtopic = {CBS},
}

• 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), October 2016.
[BibTeX] [PDF] [Slides]
@inproceedings{Regev16iros,
author = {T. Regev and V. Indelman},
title = {Multi-Robot Decentralized Belief Space Planning in Unknown Environments via Efficient Re-Evaluation of Impacted Paths},
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/Regev16iros.pdf",
slides = "http://indelman.github.io/ANPL-Website/Publications/Regev16iros_ppt.pdf",
researchtopic = {BeliefSpacePlanning, CBS},
}

• 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 = {CBS},
}

• 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.
[BibTeX] [PDF] [Slides]
@InProceedings{Indelman16icra,
author = {V. Indelman},
title = {No Correlations Involved: Decision Making Under Uncertainty in a Conservative Sparse Information Space},
booktitle = "IEEE International Conference on Robotics and Automation (ICRA), submission via IEEE Robotics and Automation Letters (RA-L)",
year = 2016,
month = "May",
location = {Sweden},
pdf = "http://indelman.github.io/ANPL-Website/Publications/Indelman16ral.pdf",
slides = "http://indelman.github.io/ANPL-Website/Publications/Indelman16icra_spotlight.pdf",
researchtopic = {CBS},
}

• 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 = {CBS},
}

• 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, July 2015.
[BibTeX] [PDF] [Poster]
@InProceedings{Indelman15rss_ws_a,
author = {V. Indelman},
title = {On Decision Making and Planning in the Conservative Information Space - Is the Concept Applicable to Active SLAM?},
booktitle = {The Problem of Mobile Sensors: Setting future goals and indicators of progress for SLAM, workshop in conjunction with Robotics Science and Systems (RSS) Conference},
year = 2015,
month = "July",
location = {Italy},
researchtopic = {CBS},
}

• V. Indelman. Towards Information-Theoretic Decision Making in a Conservative Information Space. In American Control Conference (ACC), July 2015.
[BibTeX] [PDF] [Slides]
@InProceedings{Indelman15acc,
author = {V. Indelman},
title = {Towards Information-Theoretic Decision Making in a Conservative Information Space},
booktitle = "American Control Conference (ACC)",
year = 2015,
month = "July",
location = {Chicago, USA},
pdf = "http://indelman.github.io/ANPL-Website/Publications/Indelman15acc.pdf",
slides = "http://indelman.github.io/ANPL-Website/Publications/Indelman15acc_ppt.pdf",
researchtopic = {CBS},
}

### 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 = {CBS},
}

• V. Indelman. No Correlations Involved: Decision Making Under Uncertainty in the Conservative Information Space – Supplementary Material. Technical Report ANPL-2016-01, Technion – Israel Institute of Technology, 2016.
[BibTeX] [PDF]
@TechReport{Indelman16ral_Supplementary,
author = {V. Indelman},
title = {No Correlations Involved: Decision Making Under Uncertainty in the Conservative Information Space - Supplementary Material},
institution = "Technion - Israel Institute of Technology",
year = 2016,
number = "ANPL-2016-01",
pdf = "http://indelman.github.io/ANPL-Website/Publications/Indelman16ral_Supplementary.pdf",
researchtopic = {CBS},
}