More Web Proxy on the site http://driver.im/

research-article

Testing Cyber-Physical Systems through Bayesian Optimization

Authors:

Jyotirmoy Deshmukh,

Rupak Majumdar,

Vinayak S. PrabhuAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 16, Issue 5s

Article No.: 170, Pages 1 - 18

https://doi.org/10.1145/3126521

Published: 27 September 2017 Publication History

Abstract

Many problems in the design and analysis of cyber-physical systems (CPS) reduce to the following optimization problem: given a CPS which transforms continuous-time input traces in R_m to continuous-time output traces in R_n and a cost function over output traces, find an input trace which minimizes the cost. Cyber-physical systems are typically so complex that solving the optimization problem analytically by examining the system dynamics is not feasible. We consider a black-box approach, where the optimization is performed by testing the input-output behaviour of the CPS.

We provide a unified, tool-supported methodology for CPS testing and optimization. Our tool is the first CPS testing tool that supports Bayesian optimization. It is also the first to employ fully automated dimensionality reduction techniques. We demonstrate the potential of our tool by running experiments on multiple industrial case studies. We compare the effectiveness of Bayesian optimization to state-of-the-art testing techniques based on CMA-ES and Simulated Annealing.

References

[1]

H. Abbas and G. Fainekos. 2012. Convergence proofs for Simulated Annealing falsification of safety properties. In Communication, Control, and Computing (Allerton), 2012 50th Annual Allerton Conference on. IEEE, 1594--1601.

[2]

T. Akazaki. 2016. Falsification of Conditional Safety Properties for Cyber-Physical Systems with Gaussian Process Regression. 439--446.

[3]

R. Alur. 2015. Principles of Cyber-Physical Systems. The MIT Press.

[4]

R. Alur, T. Feder, and T. A. Henzinger. 1996. The benefits of relaxing punctuality. J. ACM 43, 1 (1996), 116--146.

Digital Library

[5]

Y. Annpureddy, C. Liu, G. E. Fainekos, and S. Sankaranarayanan. 2011. S-TaLiRo: A tool for temporal logic falsification for hybrid systems. In TACAS 11 (Lecture Notes in Computer Science), Vol. 6605. Springer, 254--257.

Digital Library

[6]

S. Bansal, R. Calandra, T. Xiao, S. Levine, and C. Tomlin. 2017. Goal-driven dynamics learning via Bayesian optimization. CoRR abs/1703.09260 (2017).

[7]

M. Branicky. 1995. Studies in hybrid systems: modeling, analysis, and control. Ph.D. thesis, Massachusetts Institute of Technology.

Digital Library

[8]

E. Brochu, V. M. Cora, and N. de Freitas. 2010. A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. CoRR abs/1012.2599 (2010).

[9]

A. D. Bull. 2011. Convergence rates of efficient global optimization algorithms. J. Mach. Learn. Res. 12 (Nov. 2011), 2879--2904.

Digital Library

[10]

J. Deshmukh, X. Jin, J. Kapinski, and O. Maler. 2015. Stochastic local search for falsification of hybrid systems. In ATVA. Springer, 500--517.

[11]

A. Donzé. 2010. Breach, A Toolbox for Verification and Parameter Synthesis of Hybrid Systems. Springer, 167--170.

Digital Library

[12]

A. Donzé and O. Maler. 2010. Robust Satisfaction of Temporal Logic over Real-Valued Signals. Springer, 92--106.

Digital Library

[13]

T. Dreossi, T. Dang, A. Donzé, J. Kapinski, X. Jin, and J. V. Deshmukh. 2015. Efficient Guiding Strategies for Testing of Temporal Properties of Hybrid Systems. Springer International Publishing, 127--142.

[14]

B. Fabien. 1998. Some tools for the direct solution of optimal control problems. Advances in Engineering Software 29, 1 (1998), 45--61.

Digital Library

[15]

G. Fainekos. 2015. Automotive control design bug-finding with the S-TaLiRo tool. In ACC 2015. 4096.

[16]

S. Grünewälder, J.-Y. Audibert, M. Opper, and J. Shawe-Taylor. 2010. Regret Bounds for Gaussian Process Bandit Problems. In AISTATS 2010. 273--280.

[17]

N. Hansen. 2016. The CMA Evolution Strategy: A tutorial. CoRR abs/1604.00772 (2016).

[18]

M. Huang, K. Zaseck, K. Butts, and I. Kolmanovsky. 2016. Rate-based model predictive controller for diesel engine air path: Design and experimental evaluation. IEEE Trans. on Control Systems Technology 99 (2016), 1--14.

[19]

X. Jin, J. V. Deshmukh, J. Kapinski, K. Ueda, and K. Butts. 2014. Powertrain control verification benchmark. In HSCC’14. ACM, 253--262.

Digital Library

[20]

W. B. Johnson and J. Lindenstrauss. 1984. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics 26 (1984), 189--206.

[21]

D. R. Jones, C. D. Perttunen, and B. E. Stuckman. 1993. Lipschitzian optimization without the Lipschitz constant. Journal of Optimization Theory and Applications 79, 1 (1993), 157--181.

Digital Library

[22]

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. 1983. Optimization by simulated annealing. Science 220, 4598 (1983), 671--680.

[23]

D. Lizotte, T. Wang, M. Bowling, and D. Schuurmans. 2007. Automatic gait optimization with Gaussian process regression. In IJCAI 07. 944--949.

Digital Library

[24]

N. Mahendran, Z. Wang, F. Hamze, and N. D. Freitas. 2012. Adaptive MCMC with Bayesian optimization. In AISTATS-12), N. D. Lawrence and M. A. Girolami (Eds.), Vol. 22. 751--760.

[25]

O. Maler and D. Nickovic. 2013. Monitoring properties of analog and mixed-signal circuits. STTT 15, 3 (2013), 247--268.

Digital Library

[26]

A. Marco, P. Hennig, J. Bohg, S. Schaal, and S. Trimpe. 2016. Automatic LQR tuning based on Gaussian process global optimization. In ICRA 16. 270--277.

[27]

Mathworks. 2017. Simulink—Simulation and model-based design. https://www.mathworks.com/products/simulink.html.

[28]

W. Messner and D. Tilbury. 2017. Control tutorials for MATLAB and Simulink. http://ctms.engin.umich.edu/CTMS/index.php?aux=Basics_Simulink% #27.

[29]

M. J. D. Powell. 2009. The BOBYQA algorithm for bound constrained optimization without derivatives. Technical Report DAMTP2009/NA06. University of Cambridge.

[30]

C. E. Rasmussen and C. K. I. Williams. 2006. Gaussian processes for machine learning. MIT Press.

Digital Library

[31]

S. Sankaranarayanan and G. Fainekos. 2012. Falsification of temporal properties of hybrid systems using the cross-entropy method. In HSCC 12. ACM, 125--134.

Digital Library

[32]

P. Tabuada. 2009. Verification and Control of Hybrid Systems - A Symbolic Approach. Springer.

Digital Library

[33]

Z. Wang, F. Hutter, M. Zoghi, D. Matheson, and N. De Freitas. 2016. Bayesian optimization in a billion dimensions via random embeddings. Journal of Artificial Intelligence Research 55, 1 (2016), 361--387.

[34]

Y. Xue and P. Bogdan. 2017. Constructing compact causal mathematical models for complex dynamics. In ICCPS’17. ACM, 97--107.

Digital Library

Cited By

Birchler CMohammed TRani PNechita TKehrer TPanichella S(2024)How Does Simulation-Based Testing for Self-Driving Cars Match Human Perception?Proceedings of the ACM on Software Engineering10.1145/36437681:FSE(929-950)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3643768
Bak SBogomolov SHekal AKochdumper NLew EMata ARahmati A(2024)Falsification using Reachability of Surrogate Koopman ModelsProceedings of the 27th ACM International Conference on Hybrid Systems: Computation and Control10.1145/3641513.3650141(1-13)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3641513.3650141
Abou-Mrad CAbbas H(2024)Approximating the Geometry of Temporal Logic FormulasProceedings of the 27th ACM International Conference on Hybrid Systems: Computation and Control10.1145/3641513.3650139(1-10)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3641513.3650139
Show More Cited By

Index Terms

Testing Cyber-Physical Systems through Bayesian Optimization

Recommendations

Black-box optimization benchmarking of IPOP-saACM-ES and BIPOP-saACM-ES on the BBOB-2012 noiseless testbed
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

In this paper, we study the performance of IPOP-saACM-ES and BIPOP-saACM-ES, recently proposed self-adaptive surrogate-assisted Covariance Matrix Adaptation Evolution Strategies. Both algorithms were tested using restarts till a total number of function ...
A Survey on Testing for Cyber Physical System
ICTSS 2015: Proceedings of the 27th IFIP WG 6.1 International Conference on Testing Software and Systems - Volume 9447

Cyber Physical Systems CPS bridge the cyber-world of computing and communications with the physical world and require development of secure and reliable software. It asserts a big challenge not only on testing and verifying the correctness of all ...
Digital-twin-based testing for cyber–physical systems: A systematic literature review
Abstract Context:
Cyber–physical systems present a challenge to testers, bringing complexity and scale to safety-critical and collaborative environments. Digital twins enhance these systems through data-driven and simulation based ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 16, Issue 5s

Special Issue ESWEEK 2017, CASES 2017, CODES + ISSS 2017 and EMSOFT 2017

October 2017

1448 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/3145508

Editor:
Sandeep K. Shukla
Indian Institute of Technology, India

Issue’s Table of Contents

Copyright © 2017 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 the author(s) 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].

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 27 September 2017

Accepted: 01 July 2017

Revised: 01 June 2017

Received: 01 April 2017

Published in TECS Volume 16, Issue 5s

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

ERC Synergy Award “IMPACT”
Toyota

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
729
Total Downloads

Downloads (Last 12 months)63
Downloads (Last 6 weeks)4

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Birchler CMohammed TRani PNechita TKehrer TPanichella S(2024)How Does Simulation-Based Testing for Self-Driving Cars Match Human Perception?Proceedings of the ACM on Software Engineering10.1145/36437681:FSE(929-950)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3643768
Bak SBogomolov SHekal AKochdumper NLew EMata ARahmati A(2024)Falsification using Reachability of Surrogate Koopman ModelsProceedings of the 27th ACM International Conference on Hybrid Systems: Computation and Control10.1145/3641513.3650141(1-13)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3641513.3650141
Abou-Mrad CAbbas H(2024)Approximating the Geometry of Temporal Logic FormulasProceedings of the 27th ACM International Conference on Hybrid Systems: Computation and Control10.1145/3641513.3650139(1-10)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3641513.3650139
Zhou ZSong JXie XShu ZMa LLiu DYin JSee SRoychoudhury APaiva AAbreu RStorey MAniche MNagappan N(2024)Towards Building AI-CPS with NVIDIA Isaac Sim: An Industrial Benchmark and Case Study for Robotics ManipulationProceedings of the 46th International Conference on Software Engineering: Software Engineering in Practice10.1145/3639477.3639740(263-274)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3639477.3639740
Pedrielli GKhandait TCao YThibeault QHuang HCastillo-Effen MFainekos G(2024)Part-X: A Family of Stochastic Algorithms for Search-Based Test Generation With Probabilistic GuaranteesIEEE Transactions on Automation Science and Engineering10.1109/TASE.2023.329798421:3(4504-4525)Online publication date: Jul-2024
https://doi.org/10.1109/TASE.2023.3297984
Ghorbel BPrabhu V(2024) Fast Robust Monitoring for Signal Temporal Logic with Value Freezing Operators (STL * ) 2024 22nd ACM-IEEE International Symposium on Formal Methods and Models for System Design (MEMOCODE)10.1109/MEMOCODE63347.2024.00006(1-11)Online publication date: 3-Oct-2024
https://doi.org/10.1109/MEMOCODE63347.2024.00006
Yancosek JBaheri A(2024)BEACON: A Bayesian Evolutionary Approach for Counterexample Generation of Control SystemsIEEE Access10.1109/ACCESS.2024.343651512(106455-106465)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3436515
Akella PDixit AAhmadi MBurdick JAmes A(2024)Sample-Based Bounds for Coherent Risk Measures: Applications to Policy Synthesis and VerificationArtificial Intelligence10.1016/j.artint.2024.104195(104195)Online publication date: Aug-2024
https://doi.org/10.1016/j.artint.2024.104195
Wang JLiu WZhang MWei JShi YBu LLi X(2024)Scenario-Based Flexible Modeling and Scalable Falsification for Reconfigurable CPSsComputer Aided Verification10.1007/978-3-031-65633-0_15(329-355)Online publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-65633-0_15
Gangopadhyay BDasgupta PDey SAgmon NAn BRicci AYeoh W(2023)Counterexample-Guided Policy Refinement in Multi-Agent Reinforcement LearningProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598816(1606-1614)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598816
Show More Cited By

View Options

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents