Document Open Access Logo

Control-System Stability Under Consecutive Deadline Misses Constraints

Authors Martina Maggio , Arne Hamann, Eckart Mayer-John, Dirk Ziegenbein

PDF

File

Thumbnail PDF
PDF
LIPIcs.ECRTS.2020.21.pdf
  • Filesize: 0.52 MB
  • 24 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
  • Computer systems organization → Embedded and cyber-physical systems
  • Mathematics of computing → Mathematical analysis
  • Computer systems organization → Dependable and fault-tolerant systems and networks
Keywords
  • Real-Time Control
  • Deadline Misses
  • Weakly Hard Models

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

This paper deals with the real-time implementation of feedback controllers. In particular, it provides an analysis of the stability property of closed-loop systems that include a controller that can sporadically miss deadlines. In this context, the weakly hard m-K computational model has been widely adopted and researchers used it to design and verify controllers that are robust to deadline misses. Rather than using the m-K model, we focus on another weakly-hard model, the number of consecutive deadline misses, showing a neat mathematical connection between real-time systems and control theory. We formalise this connection using the joint spectral radius and we discuss how to prove stability guarantees on the combination of a controller (that is unaware of deadline misses) and its system-level implementation. We apply the proposed verification procedure to a synthetic example and to an industrial case study.

Cite As Get BibTex

Martina Maggio, Arne Hamann, Eckart Mayer-John, and Dirk Ziegenbein. Control-System Stability Under Consecutive Deadline Misses Constraints. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ECRTS.2020.21

Author Details

Martina Maggio
  • Saarland University, Department of Computer Science, Saarbrücken, Germany
  • Lund University, Department of Automatic Control, Sweden
  • Robert Bosch GmbH, Renningen, Germany
Arne Hamann
  • Robert Bosch GmbH, Renningen, Germany
Eckart Mayer-John
  • Robert Bosch GmbH, Renningen, Germany
Dirk Ziegenbein
  • Robert Bosch GmbH, Renningen, Germany

Funding

This work was supported by: the ELLIIT Strategic Research Area, the project ARAMiS II of the German Federal Ministry for Education and Research with the funding ID 01IS16025. The project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 871259 (ADMORPH). The responsibility for the content remains with the authors.

Acknowledgements

This research was developed while Martina Maggio was on sabbatical at Robert Bosch GmbH.

References

  1. Leonie Ahrendts, Sophie Quinton, Thomas Boroske, and Rolf Ernst. Verifying Weakly-Hard Real-Time Properties of Traffic Streams in Switched Networks. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018), volume 106 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1-15:22. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ECRTS.2018.15.
  2. Philip Axer, Maurice Sebastian, and Rolf Ernst. Probabilistic response time bound for CAN messages with arbitrary deadlines. In Design, Automation & Test in Europe Conference & Exhibition (DATE), 2012, pages 1114-1117. IEEE, 2012. Google Scholar
  3. G. Bernat, A. Burns, and A. Liamosí. Weakly hard real-time systems. IEEE Transactions on Computers, 50(4):308-321, April 2001. URL: https://doi.org/10.1109/12.919277.
  4. Alessandro Biondi, Marco Di Natale, Giorgio C. Buttazzo, and Paolo Pazzaglia. Selecting the transition speeds of engine control tasks to optimize the performance. ACM Transaction on Cyber-Physical Systems, 2(1):1:1-1:26, January 2018. URL: https://doi.org/10.1145/3127022.
  5. R. Blind and F. Allgöwer. Towards networked control systems with guaranteed stability: Using weakly hard real-time constraints to model the loss process. In 54th IEEE Conference on Decision and Control (CDC), pages 7510-7515, December 2015. URL: https://doi.org/10.1109/CDC.2015.7403405.
  6. V. Blondel and Y. Nesterov. Computationally efficient approximations of the joint spectral radius. SIAM Journal on Matrix Analysis and Applications, 27(1):256-272, 2005. URL: https://doi.org/10.1137/040607009.
  7. Vincent Blondel, Yurii Nesterov, and Jacques Theys. On the accuracy of the ellipsoid norm approximation of the joint spectral radius. Linear Algebra and its Applications, 394:91-107, 2005. URL: https://doi.org/10.1016/j.laa.2004.06.024.
  8. Vincent Blondel and John N. Tsitsiklis. The boundedness of all products of a pair of matrices is undecidable. Systems & Control Letters, 41(2):135-140, 2000. URL: https://doi.org/10.1016/S0167-6911(00)00049-9.
  9. Tobias Bund and Frank Slomka. Controller/platform co-design of networked control systems based on density functions. In Proceedings of the 4th ACM SIGBED International Workshop on Design, Modeling, and Evaluation of Cyber-Physical Systems, CyPhy '14, pages 11-14. ACM, 2014. URL: https://doi.org/10.1145/2593458.2593467.
  10. Tobias Bund and Frank Slomka. Worst-case performance validation of safety-critical control systems with dropped samples. In Proceedings of the 23rd International Conference on Real Time and Networks Systems, RTNS '15, pages 319-326. ACM, 2015. URL: https://doi.org/10.1145/2834848.2834860.
  11. Lane Desborough. Increasing customer value of industrial control performance monitoring-honeywell’s experience. Preprints of CPC, pages 153-186, 2001. Google Scholar
  12. G. Frehse, A. Hamann, S. Quinton, and M. Woehrle. Formal analysis of timing effects on closed-loop properties of control software. In 2014 IEEE Real-Time Systems Symposium, pages 53-62, December 2014. URL: https://doi.org/10.1109/RTSS.2014.28.
  13. Maximilian Gaukler, Andreas Michalka, Peter Ulbrich, and Tobias Klaus. A new perspective on quality evaluation for control systems with stochastic timing. In Proceedings of the 21st International Conference on Hybrid Systems: Computation and Control (Part of CPS Week), HSCC, pages 91-100. ACM, 2018. URL: https://doi.org/10.1145/3178126.3178134.
  14. Maximilian Gaukler, Tim Rheinfels, Peter Ulbrich, and Günter Roppenecker. Convergence rate abstractions for weakly-hard real-time control. arXiv preprint arXiv:1912.09871, 2019. Google Scholar
  15. Maximilian Gaukler and Peter Ulbrich. Worst-case analysis of digital control loops with uncertain input/output timing. In Goran Frehse and Matthias Althoff, editors, ARCH19. 6th International Workshop on Applied Verification of Continuous and Hybrid Systems, volume 61 of EPiC Series in Computing, pages 183-200. EasyChair, 2019. URL: https://doi.org/10.29007/c4zl.
  16. Saurav Kumar Ghosh, Soumyajit Dey, Dip Goswami, Daniel Mueller-Gritschneder, and Samarjit Chakraborty. Design and validation of fault-tolerant embedded controllers. In Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1283-1288, 2018. URL: https://doi.org/10.23919/DATE.2018.8342212.
  17. N. Guglielmi, F. Wirth, and M. Zennaro. Complex polytope extremality results for families of matrices. SIAM Journal on Matrix Analysis and Applications, 27(3):721-743, 2005. URL: https://doi.org/10.1137/040606818.
  18. M. Hamdaoui and P. Ramanathan. A dynamic priority assignment technique for streams with (m, k)-firm deadlines. IEEE Transactions on Computers, 44(12):1443-1451, December 1995. URL: https://doi.org/10.1109/12.477249.
  19. Z. A. H. Hammadeh, R. Ernst, S. Quinton, R. Henia, and L. Rioux. Bounding deadline misses in weakly-hard real-time systems with task dependencies. In Design, Automation Test in Europe Conference Exhibition (DATE), 2017, pages 584-589, March 2017. URL: https://doi.org/10.23919/DATE.2017.7927054.
  20. Zain A. H. Hammadeh, Sophie Quinton, Marco Panunzio, Rafik Henia, Laurent Rioux, and Rolf Ernst. Budgeting Under-Specified Tasks for Weakly-Hard Real-Time Systems. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017), volume 76 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1-17:22. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ECRTS.2017.17.
  21. R. Jungers. The Joint Spectral Radius: Theory and Applications. Lecture Notes in Control and Information Sciences. Springer Berlin Heidelberg, 2009. Google Scholar
  22. Raphael Jungers. JSR Toolbox. https://www.mathworks.com/matlabcentral/ fileexchange/33202-the-jsr-toolbox, accessed October 23, 2019. Google Scholar
  23. E. C. Kerrigan, G. A. Constantinides, A. Suardi, A. Picciau, and B. Khusainov. Computer architectures to close the loop in real-time optimization. In 2015 54th IEEE Conference on Decision and Control (CDC), pages 4597-4611, December 2015. URL: https://doi.org/10.1109/CDC.2015.7402937.
  24. Antzela Kosta, Nikolaos Pappas, Anthony Ephremides, and Vangelis Angelakis. Age and value of information: Non-linear age case. In Information Theory (ISIT), 2017 IEEE International Symposium on, pages 326-330. IEEE, 2017. Google Scholar
  25. Huibert Kwakernaak. Linear Optimal Control Systems. John Wiley & Sons, Inc., New York, NY, USA, 1972. Google Scholar
  26. W.S. Levine. The Control Handbook. Electrical Engineering Handbook. Taylor & Francis, 1996. Google Scholar
  27. D. Liberzon. Switching in Systems and Control. Systems & Control: Foundations & Applications. Birkhäuser Boston, 2003. Google Scholar
  28. B. Lincoln and A. Cervin. JITTERBUG: a tool for analysis of real-time control performance. In 41st IEEE Conference on Decision and Control, volume 2, pages 1319-1324, December 2002. URL: https://doi.org/10.1109/CDC.2002.1184698.
  29. S. Linsenmayer and F. Allgower. Stabilization of networked control systems with weakly hard real-time dropout description. In IEEE 56th Annual Conference on Decision and Control (CDC), pages 4765-4770, December 2017. URL: https://doi.org/10.1109/CDC.2017.8264364.
  30. L. Palopoli, L. Abeni, G. Buttazzo, F. Conticelli, and M. Di Natale. Real-time control system analysis: an integrated approach. In Real-Time Systems Symposium, 2000. Proceedings. The 21st IEEE, pages 131-140, 2000. URL: https://doi.org/10.1109/REAL.2000.896003.
  31. P. Park, S. Coleri Ergen, C. Fischione, C. Lu, and K. H. Johansson. Wireless network design for control systems: A survey. IEEE Communications Surveys Tutorials, 20(2):978-1013, 2018. URL: https://doi.org/10.1109/COMST.2017.2780114.
  32. Pablo A. Parrilo and Ali Jadbabaie. Approximation of the joint spectral radius using sum of squares. Linear Algebra and its Applications, 428(10):2385-2402, 2008. URL: https://doi.org/10.1016/j.laa.2007.12.027.
  33. Paolo Pazzaglia, Claudio Mandrioli, Martina Maggio, and Anton Cervin. DMAC: Deadline-Miss-Aware Control. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019), volume 133 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1-1:24, 2019. URL: https://doi.org/10.4230/LIPIcs.ECRTS.2019.1.
  34. Paolo Pazzaglia, Luigi Pannocchi, Alessandro Biondi, and Marco Di Natale. Beyond the Weakly Hard Model: Measuring the Performance Cost of Deadline Misses. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018), volume 106 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1-10:22, 2018. URL: https://doi.org/10.4230/LIPIcs.ECRTS.2018.10.
  35. Gang Quan and Xiaobo Hu. Enhanced fixed-priority scheduling with (m,k)-firm guarantee. In Proceedings of the 21st IEEE Conference on Real-time Systems Symposium, RTSS, pages 79-88. IEEE Computer Society, 2000. Google Scholar
  36. Gian–Carlo Rota and W. Gilbert Strang. A note on the joint spectral radius. Indagationes Mathematicae, 63:379-381, 1960. URL: https://doi.org/10.1016/S1385-7258(60)50046-1.
  37. Abusayeed Saifullah, Chengjie Wu, Paras Babu Tiwari, You Xu, Yong Fu, Chenyang Lu, and Yixin Chen. Near optimal rate selection for wireless control systems. ACM Transactions on Embedded Computing Systems, 13(4s):128:1-128:25, April 2014. URL: https://doi.org/10.1145/2584652.
  38. Luca Schenato, Bruno Sinopoli, Massimo Franceschetti, Kameshwar Poolla, and S Shankar Sastry. Foundations of control and estimation over lossy networks. Proceedings of the IEEE, 95(1):163-187, 2007. Google Scholar
  39. Amir Shahzad, Eric C. Kerrigan, and George A. Constantinides. A stable and efficient method for solving a convex quadratic program with application to optimal control. SIAM Journal on Optimization, 22(4):1369-1393, 2012. URL: https://doi.org/10.1137/11082960X.
  40. Bruno Sinopoli, Luca Schenato, Massimo Franceschetti, Kameshwar Poolla, and Shankar Sastry. An lqg optimal linear controller for control systems with packet losses. In Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC'05. 44th IEEE Conference on, pages 458-463. IEEE, 2005. Google Scholar
  41. D. Soudbakhsh, L. T. X. Phan, A. M. Annaswamy, and O. Sokolsky. Co-design of arbitrated network control systems with overrun strategies. IEEE Transactions on Control of Network Systems, 5(1):128-141, March 2018. URL: https://doi.org/10.1109/TCNS.2016.2583064.
  42. Damoon Soudbakhsh, Linh T. X. Phan, Oleg Sokolsky, Insup Lee, and Anuradha Annaswamy. Co-design of control and platform with dropped signals. In Proceedings of the ACM/IEEE 4th International Conference on Cyber-Physical Systems, ICCPS '13, pages 129-140. ACM, 2013. URL: https://doi.org/10.1145/2502524.2502542.
  43. Youcheng Sun and Marco Di Natale. Weakly hard schedulability analysis for fixed priority scheduling of periodic real-time tasks. ACM Transactions on Embedded Computing Systems, 16(5s):171:1-171:19, September 2017. URL: https://doi.org/10.1145/3126497.
  44. E. P. van Horssen, A. R. B. Behrouzian, D. Goswami, D. Antunes, T. Basten, and W. P. M. H. Heemels. Performance analysis and controller improvement for linear systems with (m, k)-firm data losses. In 2016 European Control Conference (ECC), pages 2571-2577, June 2016. URL: https://doi.org/10.1109/ECC.2016.7810677.
  45. Guillaume Vankeerberghen, Julien Hendrickx, and Raphaël M. Jungers. JSR: a toolbox to compute the joint spectral radius. In Proceedings of the 17th International Conference on Hybrid Systems: Computation and Control, HSCC, pages 151-156. ACM, 2014. URL: https://doi.org/10.1145/2562059.2562124.
  46. Dirk Ziegenbein and Arne Hamann. Timing-aware control software design for automotive systems. In Proceedings of the 52Nd Annual Design Automation Conference, DAC '15, pages 56:1-56:6, 2015. URL: https://doi.org/10.1145/2744769.2747947.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact