Abstract
The deterministic temporal behavior of a time-triggered computer platform provides an ideal base for the implementation of a real-time control system. The temporal predictability requires that the durations of the time-slots for the execution of the control algorithms can be specified a priori at design time. Since the indeterminism of state of the art hardware makes it difficult to arrive at a tight worst-case-execution-time (WCET) bound for the execution of a conventional control algorithm we propose to use anytime algorithms in a time-triggered control systems. An anytime algorithm trades precision for execution time. In a real-time control system we would like to have both, good algorithmic precision and a low response time—but these are conflicting goals. In this paper we propose a novel method for the design of the slot length for the execution of an anytime algorithm in a time-triggered control that on the one side is sufficient to achieve the required precision and on the other side will not introduce an extensive latency that has a detrimental effect on the quality and stability of a closed-loop control system.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Kopetz, H.: Real-Time Systems—Design Principles for Distributed Embedded Applications. Springer, Heidelberg (2011). https://doi.org/10.1007/978-1-4419-8237-7
Wilhelm, R., et al.: The worst-case execution time problem—on overview of methods and a survey of tools. ACM Trans. Embed. Comput. Syst. (TECS) 7(3), 36 (2008)
Zilberstein, S.: Using anytime algorithms in intelligent systems. AI Mag. 7(3), 73–83 (1996)
Simon, H.A.: The architecture of complexity. Proc. Am. Philos. Soc. 106(6), 467–482 (1962)
Puschner, P., Burns, A.: Writing temporally predictable code. In: Proceedings of the Workshop on Object Oriented Dependable Real-Time Systems (WORDS 2002), pp. 85–91. IEEE Press (2002)
Liu, B., He, X.: Learning dynamic hierarchical models for anytime scene labeling. In: Leibe, B., Matas, J., Sebe, N., Welling, M. (eds.) ECCV 2016. LNCS, vol. 9910, pp. 650–666. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46466-4_39
Rosen, R.: Anticipatory Systems, pp. 313–370. Springer, Heidelberg (2012). https://doi.org/10.1007/978-1-4614-1269-4
Lee, E.: Fundamental limits of cyber-physical systems modeling. ACM Trans. Cyber-Phys. Syst. 1(1), 3 (2016)
Liu, J., et al.: Algorithms for scheduling imprecise computations. In: van Tilborg, A.M., Koob, G.M. (eds.) Foundations of Real-Time Computing. Scheduling and Resource Managemen, pp. 203–249. Springer, Heidelberg (1991). https://doi.org/10.1007/978-1-4615-3956-8_8
Dean, T., Boddy, M.: An analysis of time-dependent planning. Proc. AAAI 88, 49–54 (1988)
Bhattacharaya, R., et al.: Anytime control algorithm: model reduction approach. J. Guidance Control Dyn. 27(5), 767–776 (2005)
Mangraham, R., et al.: Anytime algorithms for GPU architectures. In: Proceedings of RTSS 2011, pp. 47–56. IEEE Press (2011)
Pant, Y.V., et al.: Co-design of anytime computation and robust control. In: Proceedings of RTSS 2015, pp. 43–52. IEEE Press (2015)
Jha, D.K., et al.: Data-driven anytime algorithms for motion planning with safety guarantees. In: Proceedings of the 2016 American Control Conference (ACC), pp. 5716–5721. IEEE Press (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this chapter
Cite this chapter
Kopetz, H. (2018). Anytime Algorithms in Time-Triggered Control Systems. In: Lohstroh, M., Derler, P., Sirjani, M. (eds) Principles of Modeling. Lecture Notes in Computer Science(), vol 10760. Springer, Cham. https://doi.org/10.1007/978-3-319-95246-8_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-95246-8_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-95245-1
Online ISBN: 978-3-319-95246-8
eBook Packages: Computer ScienceComputer Science (R0)