Uncertainty quantification of set-membership estimation in control and perception: Revisiting the minimum enclosing ellipsoid

Yukai Tang, Jean-Bernard Lasserre, Heng Yang
Proceedings of the 6th Annual Learning for Dynamics & Control Conference, PMLR 242:286-298, 2024.

Abstract

Set-membership estimation (SME) outputs a set estimator that guarantees to cover the groundtruth. Such sets are, however, defined by (many) abstract (and potentially nonconvex) constraints and therefore difficult to manipulate. We present tractable algorithms to compute simple and tight overapproximations of SME in the form of minimum enclosing ellipsoids (MEE). We first introduce the hierarchy of enclosing ellipsoids proposed by Nie and Demmel (2005), based on sums-of-squares relaxations, that asymptotically converge to the MEE of a basic semialgebraic set. This framework, however, struggles in modern control and perception problems due to computational challenges. We contribute three computational enhancements to make this framework practical, namely constraints pruning, generalized relaxed Chebyshev center, and handling non-Euclidean geometry. We showcase numerical examples on system identification and object pose estimation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v242-tang24a, title = {Uncertainty quantification of set-membership estimation in control and perception: Revisiting the minimum enclosing ellipsoid}, author = {Tang, Yukai and Lasserre, Jean-Bernard and Yang, Heng}, booktitle = {Proceedings of the 6th Annual Learning for Dynamics & Control Conference}, pages = {286--298}, year = {2024}, editor = {Abate, Alessandro and Cannon, Mark and Margellos, Kostas and Papachristodoulou, Antonis}, volume = {242}, series = {Proceedings of Machine Learning Research}, month = {15--17 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v242/tang24a/tang24a.pdf}, url = {https://proceedings.mlr.press/v242/tang24a.html}, abstract = {Set-membership estimation (SME) outputs a set estimator that guarantees to cover the groundtruth. Such sets are, however, defined by (many) abstract (and potentially nonconvex) constraints and therefore difficult to manipulate. We present tractable algorithms to compute simple and tight overapproximations of SME in the form of minimum enclosing ellipsoids (MEE). We first introduce the hierarchy of enclosing ellipsoids proposed by Nie and Demmel (2005), based on sums-of-squares relaxations, that asymptotically converge to the MEE of a basic semialgebraic set. This framework, however, struggles in modern control and perception problems due to computational challenges. We contribute three computational enhancements to make this framework practical, namely constraints pruning, generalized relaxed Chebyshev center, and handling non-Euclidean geometry. We showcase numerical examples on system identification and object pose estimation.} }
Endnote
%0 Conference Paper %T Uncertainty quantification of set-membership estimation in control and perception: Revisiting the minimum enclosing ellipsoid %A Yukai Tang %A Jean-Bernard Lasserre %A Heng Yang %B Proceedings of the 6th Annual Learning for Dynamics & Control Conference %C Proceedings of Machine Learning Research %D 2024 %E Alessandro Abate %E Mark Cannon %E Kostas Margellos %E Antonis Papachristodoulou %F pmlr-v242-tang24a %I PMLR %P 286--298 %U https://proceedings.mlr.press/v242/tang24a.html %V 242 %X Set-membership estimation (SME) outputs a set estimator that guarantees to cover the groundtruth. Such sets are, however, defined by (many) abstract (and potentially nonconvex) constraints and therefore difficult to manipulate. We present tractable algorithms to compute simple and tight overapproximations of SME in the form of minimum enclosing ellipsoids (MEE). We first introduce the hierarchy of enclosing ellipsoids proposed by Nie and Demmel (2005), based on sums-of-squares relaxations, that asymptotically converge to the MEE of a basic semialgebraic set. This framework, however, struggles in modern control and perception problems due to computational challenges. We contribute three computational enhancements to make this framework practical, namely constraints pruning, generalized relaxed Chebyshev center, and handling non-Euclidean geometry. We showcase numerical examples on system identification and object pose estimation.
APA
Tang, Y., Lasserre, J. & Yang, H.. (2024). Uncertainty quantification of set-membership estimation in control and perception: Revisiting the minimum enclosing ellipsoid. Proceedings of the 6th Annual Learning for Dynamics & Control Conference, in Proceedings of Machine Learning Research 242:286-298 Available from https://proceedings.mlr.press/v242/tang24a.html.

Related Material