Lifted Relational Kalman Filtering

Choi, Jaesik; Guzmán-Rivera, Abner; Amir, Eyal

doi:10.5591/978-1-57735-516-8/IJCAI11-350

Lifted Relational Kalman Filtering

Jaesik Choi, Abner Guzmán-Rivera, Eyal Amir

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2092-2098.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-350

Abstract

Kalman Filtering is a computational tool with widespread applications in robotics, financial and weather forecasting, environmental engineering and defense. Given observation and state transition models, the Kalman Filter (KF) recursively estimates the state variables of a dynamic system. However, the KF requires a cubic time matrix inversion operation at every timestep which prevents its application in domains with large numbers of state variables. We propose Relational Gaussian Models to represent and model dynamic systems with large numbers of variables efficiently. Furthermore, we devise an exact lifted Kalman Filtering algorithm which takes only linear time in the number of random variables at every timestep. We prove that our algorithm takes linear time in the number of state variables even when individual observations apply to each variable. To our knowledge, this is the first lifted (linear time) algorithm for filtering with continuous dynamic relational models.

Jaesik Choi, Abner Guzmán-Rivera, and Eyal Amir. 2011. Lifted Relational Kalman Filtering. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2092–2098. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-350

@inproceedings{ijcai2011p350,
  title     = {Lifted Relational Kalman Filtering},
  author    = {Choi, Jaesik and Guzmán-Rivera, Abner and Amir, Eyal},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {2092--2098},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-350},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-350},
}

TY  - CPAPER
TI  - Lifted Relational Kalman Filtering
AU  - Choi, Jaesik
AU  - Guzmán-Rivera, Abner
AU  - Amir, Eyal
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 2092
EP  - 2098
DO  - 10.5591/978-1-57735-516-8/IJCAI11-350
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-350
ER  -