EncloSOS

Certificates are mathematical functions whose existence offers a formal guarantee for dynamical system properties. These certificates do not necessitate the explicit computation of system trajectories and, as such, provide a convenient way to ensure the reliability and trustworthiness of control systems. Among these certificates, the Lyapunov function is one of the most renowned examples: many works in the literature were devoted to the computational search of Lyapunov functions.

On the other hand, barrier certificates were introduced to ensure that the system will not enter undesirable or unsafe states.¹ Finding barrier certificates is typically a challenging task, similar to the search for Lyapunov functions. Nevertheless, when dealing with polynomial dynamical systems and initial and unsafe sets defined as basic semialgebraic sets (defined by an intersection of polynomial inequalities), a feasible computational approach using sum-of-squares (SOS) is available.

In the context of obstacle avoidance problems, an unsafe set contains the obstacle. In many real-world scenarios, however, these obstacles do not have a direct semialgebraic description but are typically represented as point clouds obtained by sampling. Thus, to formulate a SOS feasibility problem with these obstacles, one must find an adequate semialgebraic set over-approximating them. A common approach in the literature is to compute a minimal-volume ellipsoid containing the sampled points from the obstacle. However, this approach can be overly conservative and may limit its applicability for scenarios with more complex object shapes. For instance, in a pick-and-place task, a robot might need to pick up an object located at the bottom of a box without colliding with the edges of the box:²

To address these challenges, we propose EncloSOS, a MATLAB toolbox implementing various algorithms for computing semialgebraic enclosures in obstacle-rich environments.

Implemented algorithms

• SVM: Support Vector Machine with polynomial kernel.
• PSS: Polynomial Super-level Set proposed in ³. The MATLAB functions in the folder .\pss are adapted (or directly) from the code by AmirHosein Sadeghimanesh.⁴
• EM: Empirical-Moment based approach proposed in ⁵.

Demo

enclosos.mp4

Setup

Install MATLAB (tested with R2023a).

Install the MathWorks toolboxes Image Processing Toolbox, Optimization Toolbox, Statistics and Machine Learning Toolbox, and Symbolic Math Toolbox.

Install the third party tool YALMIP.

Usage

Run enclosos.mlapp.

Configure the parameters via the GUI as desired, hit the "compute" button, and check the result in the figure window.

Optionally, make adjustments and recompute as needed.

Optionally, save the computed polynomial to an m-file.

(Optionally, recreate the shown U-shaped semi-algebraic set by using the settings from ushape_settings.txt.)

Citation

@Article{enclosos2024,
  title = {{EncloSOS}: A {MATLAB} Toolbox for Computing Semi-Algebraic Enclosures},
  author = {Schonger, Martin and Kussaba, Hugo Tadashi M. and Swikir, Abdalla and Billard, Aude and Haddadin, Sami},
  journal = {Manuscript in preparation},
  year = {2024},
}

Contact

[email protected]

This software was created as part of Martin Schonger's master's thesis in Computer Science at the Technical University of Munich's (TUM) School of Computation, Information and Technology (CIT).

Copyright © 2024 Martin Schonger.

This software is licensed under the GPLv3.

References

Footnotes

1. Prajna, S., and Jadbabaie, A. "Safety verification of hybrid systems using barrier certificates." International Workshop on Hybrid Systems: Computation and Control. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. ↩

2. Schonger, M., Kussaba, H., Chen, L., Figueredo, L., Swikir, A., Billard, A., and Haddadin, S. "Learning Barrier-Certified Polynomial Dynamical Systems for Obstacle Avoidance with Robots." Proceedings of the 41st IEEE International Conference on Robotics and Automation (ICRA), 2024. ↩

3. Dabbene, F., Henrion, D., and Lagoa, C. M. (2017). Simple approximations of semialgebraic sets and their applications to control. Automatica, 78, 110-118. ↩

4. Sadeghimanesh, A., & England, M. (2022). Polynomial superlevel set representation of the multistationarity region of chemical reaction networks. BMC bioinformatics, 23(1), 391. ↩

5. Pauwels, E., and Lasserre, J. B. (2016). Sorting out typicality with the inverse moment matrix SOS polynomial. Advances in Neural Information Processing Systems, 29. ↩