research-article

Public Access

SOCKS: A Stochastic Optimal Control and Reachability Toolbox Using Kernel Methods

Authors:

Meeko OishiAuthors Info & Claims

HSCC '22: Proceedings of the 25th ACM International Conference on Hybrid Systems: Computation and Control

Article No.: 21, Pages 1 - 12

https://doi.org/10.1145/3501710.3519525

Published: 04 May 2022 Publication History

All formats PDF

Abstract

We present SOCKS, a data-driven stochastic optimal control toolbox based in kernel methods. SOCKS is a collection of data-driven algorithms that compute approximate solutions to stochastic optimal control problems with arbitrary cost and constraint functions, including stochastic reachability, which seeks to determine the likelihood that a system will reach a desired target set while respecting a set of pre-defined safety constraints. Our approach relies upon a class of machine learning algorithms based in kernel methods, a nonparametric technique which can be used to represent probability distributions in a high-dimensional space of functions known as a reproducing kernel Hilbert space. As a nonparametric technique, kernel methods are inherently data-driven, meaning that they do not place prior assumptions on the system dynamics or the structure of the uncertainty. This makes the toolbox amenable to a wide variety of systems, including those with nonlinear dynamics, black-box elements, and poorly characterized stochastic disturbances. We present the main features of SOCKS and demonstrate its capabilities on several benchmarks.

References

[1]

Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. 2015. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems. https://www.tensorflow.org/ Software available from tensorflow.org.

[2]

Alessandro Abate, Henk Blom, Nathalie Cauchi, Kurt Degiorgio, Martin Fränzle, Ernst Moritz Hahn, Sofie Haesaert, Hao Ma, Meeko Oishi, Carina Pilch, 2019. ARCH-COMP19 category report: Stochastic modelling. EPiC Series in Computing 61 (2019), 62–102.

[3]

Alessandro Abate, Henk Blom, Nathalie Cauchi, Joanna Delicaris, Arnd Hartmanns, Mahmoud Khaled, Abolfazl Lavaei, Carina Pilch, Anne Remke, Stefan Schupp, 2020. ARCH-COMP20 Category Report: Stochastic Models. EPiC Series in Computing 74 (2020), 76–106.

[4]

Alessandro Abate, HAP Blom, Nathalie Cauchi, Sofie Haesaert, Arnd Hartmanns, Kendra Lesser, Meeko Oishi, Vignesh Sivaramakrishnan, and Sadegh Soudjani. 2018. ARCH-COMP18 Category Report: Stochastic Modelling. EPiC Series in Computing 54 (2018).

[5]

Alessandro Abate, Maria Prandini, John Lygeros, and Shankar Sastry. 2008. Probabilistic reachability and safety for controlled discrete time stochastic hybrid systems. Automatica 44, 11 (2008), 2724–2734.

Digital Library

[6]

Nachman Aronszajn. 1950. Theory of reproducing kernels. Transactions of the American mathematical society 68, 3 (1950), 337–404.

[7]

Dimitri P Bertsekas and Steven E Shreve. 1978. Stochastic optimal control: the discrete time case. Elsevier.

[8]

Olivier Bousquet and André Elisseeff. 2002. Stability and generalization. The Journal of Machine Learning Research 2 (2002), 499–526.

Digital Library

[9]

Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press.

Digital Library

[10]

Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. 2016. Openai gym. arXiv preprint arXiv:1606.01540(2016).

[11]

Nathalie Cauchi and Alessandro Abate. 2019. StocHy - Automated Verification and Synthesis of Stochastic Processes: Poster Abstract. In Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control(HSCC ’19). Association for Computing Machinery, New York, NY, USA, 258–259.

Digital Library

[12]

François Chollet 2015. Keras. https://keras.io.

[13]

Erhan Çınlar. 2011. Probability and Stochastics. Vol. 261. Springer Science & Business Media.

[14]

Ernesto De Vito, Lorenzo Rosasco, and Alessandro Toigo. 2014. Learning sets with separating kernels. Applied and Computational Harmonic Analysis 37, 2 (2014), 185–217.

[15]

Christian Dehnert, Sebastian Junges, Joost-Pieter Katoen, and Matthias Volk. 2017. A Storm is Coming: A Modern Probabilistic Model Checker. In Computer Aided Verification, Rupak Majumdar and Viktor Kunčak (Eds.). Springer International Publishing, Cham, 592–600.

[16]

Marc Peter Deisenroth, Carl Edward Rasmussen, and Jan Peters. 2009. Gaussian process dynamic programming. Neurocomputing 72, 7-9 (2009), 1508–1524.

Digital Library

[17]

Franck Djeumou and Ufuk Topcu. 2021. Learning to Reach, Swim, Walk and Fly in One Trial: Data-Driven Control with Scarce Data and Side Information. arXiv preprint arXiv:2106.10533(2021).

[18]

Franck Djeumou, Aditya Zutshi, and Ufuk Topcu. 2021. On-the-fly, data-driven reachability analysis and control of unknown systems: an F-16 aircraft case study. In Proceedings of the 24th International Conference on Hybrid Systems: Computation and Control. 1–2.

Digital Library

[19]

Souradeep Dutta, Xin Chen, Susmit Jha, Sriram Sankaranarayanan, and Ashish Tiwari. 2019. Sherlock-A tool for verification of neural network feedback systems. In International Conference on Hybrid Systems: Computation and Control. 262–263.

Digital Library

[20]

Javier Garcıa and Fernando Fernández. 2015. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research 16, 1 (2015), 1437–1480.

Digital Library

[21]

Luca Geretti, Julien Alexandre Dit Sandretto, Matthias Althoff, Luis Benet, Alexandre Chapoutot, Xin Chen, Pieter Collins, Marcelo Forets, Daniel Freire, Fabian Immler, 2020. Arch-comp20 category report: Continuous and hybrid systems with nonlinear dynamics. EPiC Series in Computing 74 (2020), 49–75.

[22]

Steffen Grünewälder, Guy Lever, Luca Baldassarre, Sam Patterson, Arthur Gretton, and Massimilano Pontil. 2012. Conditional mean embeddings as regressors. In Proceedings of the 29th International Coference on International Conference on Machine Learning. 1803–1810.

[23]

Steffen Grünewälder, Guy Lever, Luca Baldassarre, Massimilano Pontil, and Arthur Gretton. 2012. Modelling Transition Dynamics in MDPs with RKHS Embeddings. In Proceedings of the 29th International Coference on International Conference on Machine Learning(ICML’12). Omnipress, Madison, WI, USA, 1603–1610.

Digital Library

[24]

Guy Katz, Derek Huang, Duligur Ibeling, Kyle Julian, Christopher Lazarus, Rachel Lim, Parth Shah, Shantanu Thakoor, Haoze Wu, Aleksandar Zeljić, David L. Dill, Mykel Kochenderfer, and Clark Barrett. 2019. The Marabou Framework for Verification and Analysis of Deep Neural Networks. In Computer Aided Verification, Isil Dillig and Serdar Tasiran (Eds.). Springer International Publishing, Cham, 443–452.

[25]

Zachary Kingston, Mark Moll, and Lydia E Kavraki. 2018. Sampling-based methods for motion planning with constraints. Annual review of control, robotics, and autonomous systems 1 (2018), 159–185.

[26]

Marta Kwiatkowska, Gethin Norman, and David Parker. 2011. PRISM 4.0: Verification of probabilistic real-time systems. In International conference on computer aided verification. Springer, 585–591.

[27]

Abolfazl Lavaei, Mahmoud Khaled, Sadegh Soudjani, and Majid Zamani. 2020. AMYTISS: A Parallelized Tool on Automated Controller Synthesis for Large-Scale Stochastic Systems. In Proceedings of the 23rd International Conference on Hybrid Systems: Computation and Control(HSCC ’20). Association for Computing Machinery, New York, NY, USA, Article 31, 2 pages.

Digital Library

[28]

Kendra Lesser, Meeko Oishi, and R Scott Erwin. 2013. Stochastic reachability for control of spacecraft relative motion. In 52nd IEEE Conference on Decision and Control. IEEE, 4705–4712.

[29]

Guy Lever and Ronnie Stafford. 2015. Modelling Policies in MDPs in Reproducing Kernel Hilbert Space. In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics(Proceedings of Machine Learning Research), Guy Lebanon and S. V. N. Vishwanathan (Eds.). Vol. 38. PMLR, San Diego, California, USA, 590–598.

[30]

Zita Marinho, Byron Boots, Anca Dragan, Arunkumar Byravan, Geoffrey J. Gordon, and Siddhartha Srinivasa. 2016. Functional Gradient Motion Planning in Reproducing Kernel Hilbert Spaces. In Proceedings of Robotics: Science and Systems. AnnArbor, Michigan. https://doi.org/10.15607/RSS.2016.XII.046

[31]

Charles A Micchelli and Massimiliano Pontil. 2005. On learning vector-valued functions. Neural computation 17, 1 (2005), 177–204.

[32]

Junhyung Park and Krikamol Muandet. 2020. A measure-theoretic approach to kernel conditional mean embeddings. Advances in Neural Information Processing Systems 33 (2020).

[33]

Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems 32, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (Eds.). Curran Associates, Inc., 8024–8035.

Digital Library

[34]

F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research 12 (2011), 2825–2830.

Digital Library

[35]

Ali Rahimi and Benjamin Recht. 2007. Random Features for Large-Scale Kernel Machines. In Advances in Neural Information Processing Systems, J. Platt, D. Koller, Y. Singer, and S. Roweis (Eds.). Vol. 20. Curran Associates, Inc.https://proceedings.neurips.cc/paper/2007/file/013a006f03dbc5392effeb8f18fda755-Paper.pdf

[36]

Carl Edward Rasmussen and Chris Williams. 2006. Gaussian Processes for Machine Learning. MIT Press.

Digital Library

[37]

Alex Ray, Joshua Achiam, and Dario Amodei. 2019. Benchmarking safe exploration in deep reinforcement learning. (2019).

[38]

Siddharth Reddy, Anca Dragan, Sergey Levine, Shane Legg, and Jan Leike. 2020. Learning human objectives by evaluating hypothetical behavior. In International Conference on Machine Learning. PMLR, 8020–8029.

[39]

Ugo Rosolia and Francesco Borrelli. 2017. Learning model predictive control for iterative tasks. a data-driven control framework. IEEE Trans. Automat. Control 63, 7 (2017), 1883–1896.

[40]

Ugo Rosolia and Francesco Borrelli. 2019. Sample-based learning model predictive control for linear uncertain systems. In 2019 IEEE 58th Conference on Decision and Control (CDC). IEEE, 2702–2707.

Digital Library

[41]

Bernhard Schölkopf, Alexander J Smola, Francis Bach, 2002. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press.

[42]

Fedor Shmarov and Paolo Zuliani. 2015. ProbReach: Verified Probabilistic Delta-Reachability for Stochastic Hybrid Systems. In Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control(HSCC ’15). Association for Computing Machinery, New York, NY, USA, 134–139. https://doi.org/10.1145/2728606.2728625

Digital Library

[43]

Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf. 2007. A Hilbert space embedding for distributions. In International Conference on Algorithmic Learning Theory. Springer, 13–31.

Digital Library

[44]

Le Song, Byron Boots, Sajid M. Siddiqi, Geoffrey Gordon, and Alex Smola. 2010. Hilbert Space Embeddings of Hidden Markov Models. In Proceedings of the 27th International Conference on International Conference on Machine Learning(ICML’10). Omnipress, Madison, WI, USA, 991–998.

Digital Library

[45]

Le Song, Arthur Gretton, and Carlos Guestrin. 2010. Nonparametric Tree Graphical Models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics(Proceedings of Machine Learning Research), Yee Whye Teh and Mike Titterington (Eds.). Vol. 9. PMLR, Chia Laguna Resort, Sardinia, Italy, 765–772.

[46]

Le Song, Jonathan Huang, Alex Smola, and Kenji Fukumizu. 2009. Hilbert space embeddings of conditional distributions with applications to dynamical systems. In Proceedings of the 26th Annual International Conference on Machine Learning. 961–968.

Digital Library

[47]

Sadegh Esmaeil Zadeh Soudjani, Caspar Gevaerts, and Alessandro Abate. 2015. FAUST 2 : Formal Abstractions of Uncountable-STate STochastic Processes. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Vol. 9035. Springer International Publishing, 272–286.

[48]

Ingo Steinwart and Andreas Christmann. 2008. Support Vector Machines. Springer Publishing Company, Incorporated.

[49]

Sean Summers and John Lygeros. 2010. Verification of discrete time stochastic hybrid systems: A stochastic reach-avoid decision problem. Automatica 46, 12 (2010), 1951–1961.

Digital Library

[50]

Adam J. Thorpe and Meeko M. K. Oishi. 2020. Model-Free Stochastic Reachability Using Kernel Distribution Embeddings. IEEE Control Systems Letters 4, 2 (2020), 512–517.

[51]

Adam J. Thorpe and Meeko M. K. Oishi. 2021. Stochastic Optimal Control via Hilbert Space Embeddings of Distributions. In 2021 60th IEEE Conference on Decision and Control (CDC). 904–911. https://doi.org/10.1109/CDC45484.2021.9682801

Digital Library

[52]

Adam J. Thorpe, Kendric R. Ortiz, and Meeko M. K. Oishi. 2021. Learning Approximate Forward Reachable Sets Using Separating Kernels. In Proceedings of the 3rd Conference on Learning for Dynamics and Control(Proceedings of Machine Learning Research), Ali Jadbabaie, John Lygeros, George J. Pappas, Pablo A. Parrilo, Benjamin Recht, Claire J. Tomlin, and Melanie N. Zeilinger (Eds.). Vol. 144. PMLR, 201–212.

[53]

Adam J. Thorpe, Kendric R. Ortiz, and Meeko M. K. Oishi. 2021. SReachTools Kernel Module: Data-Driven Stochastic Reachability Using Hilbert Space Embeddings of Distributions. In 2021 60th IEEE Conference on Decision and Control (CDC). 5073–5079. https://doi.org/10.1109/CDC45484.2021.9683169

Digital Library

[54]

Adam J. Thorpe, Vignesh Sivaramakrishnan, and Meeko M. K. Oishi. 2021. Approximate Stochastic Reachability for High Dimensional Systems. In 2021 American Control Conference (ACC). 1287–1293.

[55]

Hoang-Dung Tran, Patrick Musau, Diego Manzanas Lopez, Xiaodong Yang, Luan Viet Nguyen, Weiming Xiang, and Taylor Johnson. 2020. NNV: A Tool for Verification of Deep Neural Networks and Learning-Enabled Autonomous Cyber-Physical Systems. In International Conference on Computer-Aided Verification.

[56]

Abraham Vinod, Joseph Gleason, and Meeko Oishi. 2019. SReachTools: a MATLAB stochastic reachability toolbox. In International Conference on Hybrid Systems: Computation and Control. ACM, 33–38.

Digital Library

[57]

Jia-Jie Zhu, Wittawat Jitkrittum, Moritz Diehl, and Bernhard Schölkopf. 2021. Kernel Distributionally Robust Optimization: Generalized Duality Theorem and Stochastic Approximation. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics(Proceedings of Machine Learning Research), Arindam Banerjee and Kenji Fukumizu (Eds.). Vol. 130. PMLR, 280–288.

Cited By

Sridhar HHuang GThorpe AOishi MPitts B(2024)Characterizing the Effect of Mind Wandering on Braking Dynamics in Partially Autonomous VehiclesACM Transactions on Cyber-Physical Systems10.1145/36536788:3(1-21)Online publication date: 22-Mar-2024
https://dl.acm.org/doi/10.1145/3653678
Zhang LBurbano LChen XCardenas ADrager SAnderson MKong F(2024)Fast Attack Recovery for Stochastic Cyber-Physical Systems2024 IEEE 30th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS61025.2024.00030(280-293)Online publication date: 13-May-2024
https://doi.org/10.1109/RTAS61025.2024.00030
Yuh MOrtiz KSommer-Kohrt KOishi MJain N(2024)Classification of Human Learning Stages via Kernel Distribution EmbeddingsIEEE Open Journal of Control Systems10.1109/OJCSYS.2023.33487043(102-117)Online publication date: 2024
https://doi.org/10.1109/OJCSYS.2023.3348704
Show More Cited By

Recommendations

SReachTools: A MATLAB stochastic reachability toolbox: demo abstract
HSCC '19: Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control

In this demo, we present SReachTools, an open-source MATLAB toolbox for performing stochastic reachability of linear, potentially time-varying, discrete-time systems that are perturbed by a stochastic disturbance [8]. The toolbox addresses the problem ...
Pathwise Optimality in Stochastic Control

We introduce a notion of pathwise optimality for stochastic control problems over an infinite time horizon, and give sufficient conditions for the existence of pathwise optimal controls. We analyze both diffusion processes and processes with discrete ...
Infinite Horizon Forward-Backward SDEs and Open-Loop Optimal Controls for Stochastic Linear-Quadratic Problems with Random Coefficients

In this paper, we introduce a new infinite horizon domination-monotonicity framework. In this framework, by the method of continuation and some subtle techniques, we obtain an existence and uniqueness result and a pair of estimates for the solutions to a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

HSCC '22: Proceedings of the 25th ACM International Conference on Hybrid Systems: Computation and Control

May 2022

265 pages

ISBN:9781450391962

DOI:10.1145/3501710

Co-chairs:
Ezio Bartocci
Technische Universität Wien, Vienna, Austria
,
Sylvie Putot
Ecole Polytechnique, Palaiseau, France

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 May 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Results Reproduced / v1.1

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

NSF
National Science Foundation
NASA University Leadership initiative

Conference

HSCC '22

Sponsor:

SIGBED

HSCC '22: 25th ACM International Conference on Hybrid Systems: Computation and Control

May 4 - 6, 2022

Milan, Italy

Acceptance Rates

Overall Acceptance Rate 153 of 373 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
266
Total Downloads

Downloads (Last 12 months)144
Downloads (Last 6 weeks)30

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sridhar HHuang GThorpe AOishi MPitts B(2024)Characterizing the Effect of Mind Wandering on Braking Dynamics in Partially Autonomous VehiclesACM Transactions on Cyber-Physical Systems10.1145/36536788:3(1-21)Online publication date: 22-Mar-2024
https://dl.acm.org/doi/10.1145/3653678
Zhang LBurbano LChen XCardenas ADrager SAnderson MKong F(2024)Fast Attack Recovery for Stochastic Cyber-Physical Systems2024 IEEE 30th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS61025.2024.00030(280-293)Online publication date: 13-May-2024
https://doi.org/10.1109/RTAS61025.2024.00030
Yuh MOrtiz KSommer-Kohrt KOishi MJain N(2024)Classification of Human Learning Stages via Kernel Distribution EmbeddingsIEEE Open Journal of Control Systems10.1109/OJCSYS.2023.33487043(102-117)Online publication date: 2024
https://doi.org/10.1109/OJCSYS.2023.3348704
Beikmohammadi AMagnússon S(2024)Accelerating actor-critic-based algorithms via pseudo-labels derived from prior knowledgeInformation Sciences: an International Journal10.1016/j.ins.2024.120182661:COnline publication date: 17-Apr-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.120182
Thorpe AGonzales JOishi M(2023)Data-Driven Stochastic Optimal Control Using Kernel Gradients2023 American Control Conference (ACC)10.23919/ACC55779.2023.10155897(2548-2553)Online publication date: 31-May-2023
https://doi.org/10.23919/ACC55779.2023.10155897
Romao LHota AAbate A(2023)Distributionally Robust Optimal and Safe Control of Stochastic Systems via Kernel Conditional Mean Embedding2023 62nd IEEE Conference on Decision and Control (CDC)10.1109/CDC49753.2023.10383997(2016-2021)Online publication date: 13-Dec-2023
https://doi.org/10.1109/CDC49753.2023.10383997
Rouzegar HGhanbarisabagh M(2023)A novel on–off linear quadratic regulator control approach for satellite rendezvousAerospace Systems10.1007/s42401-023-00230-96:4(613-620)Online publication date: 23-Jun-2023
https://doi.org/10.1007/s42401-023-00230-9

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents