CS637: Embedded and Cyber-Physical Systems

Monsoon 2021 (August 2, 2021 - November 18, 2021)

Online Modes:
Lectures: https://hello.iitk.ac.in
Discussion: https://zoom.us/
Assignment submission and Grading: https://www.gradescope.com/

Discussion Hour: Monday 12:00 pm to 1:30 pm

Instructor: Indranil Saha (Email: isaha[at]cse[dot]iitk[dot]ac[dot]in)

Teaching Assistants:
Aakash (Email: aakashp[at]cse[dot]iitk[dot]ac[dot]in)
Shatroopa Saxena (Email: ssaxena[at]cse[dot]iitk[dot]ac[dot]in)
Aman Aryan (Email: ryn20[at]iitk[dot]ac[dot]in)
Kushagra Pandey (Email: kushagrap20[at]iitk[dot]ac[dot]in)


Overview

A cyber-physical system is a collection of interconnected computing devices interacting with the physical world. The computing devices together constitute a cyber system that regulates the behavior of the physical world. The cyber system closely monitors the physical world through sensors, computes required control laws based on the current state of the physical world, and applies the computed control law to the physical world through actuators. The sensors, the controllers, and the actuators are developed on top of an embedded platform. Thus, the cyber component of a cyber-physical system is often termed as an embedded control system.

Developing an embedded control system requires the understanding of the physical world with which the system has to interact. The understanding of the physical world is captured in a faithful model that is used for synthesizing feedback control laws using control theoretic methods. Implementing the feedback control law on the embedded computing platform requires addressing the challenges of embedded computing, for example, the availability of limited resources in terms of computing power and memory, stringent timing requirements, and so on. Moreover, most cyber-physical systems are safety-critical. Thus, it is essential that the correctness of such systems is established through the use of formal verification techniques.

The course will cover the modeling, implementation and verification issues related to developing a cyber-physical system. Through the discussion of the implementation of an embedded control system, the course will cover the basic design principles of an embedded system.


Prerequisites

The course does not have any formal prerequisites. The students are expected to have mathematical maturity of the level of an undergraduate degree in engineering. However, some familiarity with finite state machines and ordinary differential equations, and programming experience will be helpful.


Topics

  • Modeling Dynamic Behaviors and Control: Continuous Dynamics, Feedback Control, Discrete Systems, Hybrid Systems, Composition of State Machines, Concurrent Models of Computation
  • Design and Implementation: Sensors and Actuators, Embedded Processors, Memory Architectures, Input and Output Interface, Multitasking, Scheduling
  • Analysis and Verification: Invariants and Temporal Logic, Equivalence and Refinement, Rechability Analysis, Model Checking, Timing Analysis

  • Grading Policy

    Homework Assignments - 20%
    Project - 30%
    Mid-Semester Examination - 25%
    End-Semester Examination - 25%

    Our department follows this anti-cheating policy strictly.


    Exam Schedule and Deadlines

    Homework
    Homework 1 (Deadline: August 29, 2021)
    Homework 2 (Deadline: September 12, 2021)
    Homework 3 (Deadline: October 3, 2021)
    Homework 4 (Deadline: October 17, 2021)
    Homework 5 (Deadline: October 31, 2021)

    Project
    Project Proposal Submission (Deadline: August 29, 2021)
    Final Project Presentation (Will be scheduled between October 28, 2021 and November 18, 2021)
    Final Report Submission (Deadline: November 18, 2021)
    Detailed Project Evaluation (November 19-20, 2021)

    Mid-Semester Examination
    September 17, 2021 (Friday) 1:00 pm to 3:00 pm Online

    Final Examination
    November 29, 2021 (Monday) 4:00 pm to 7:00 pm Online


    Lecture Schedule

    Lecture Date Topic References
    -- Aug 2 - Aug 8 (Week 1) Discussion 1
    1Introduction to the course[LS15 - Ch 1]
    2Modeling Dynamic Behaviors - Continuous Dynamics[LS15 - Ch 2]
    -- Aug 9 - Aug 15 (Week 2) Discussion 2
    3Basics of Feedback Control Theory[AM09]
    4Modeling Dynamic Behaviors - Discrete Dynamics[LS15 - Ch 3]
    -- Aug 16 - Aug 22 (Week 3) Discussion 3
    5Hybrid Systems[LS15 - Ch 4]
    6Composition of State Machines[LS15 - Ch 5]
    -- Aug 23 - Aug 29 (Week 4) Discussion 4
    7Concurrent Models of Computation[LS15 - Ch 6]
    8Sensors and ActuatorsLS15 - Ch 7]
    -- Aug 30 - Sep 5 (Week 5) Discussion 5
    9Embedded Processors [LS15 - Ch 8]
    10Memory Architectures [LS15 - Ch 9]
    -- Sep 6 - Sep 12 (Week 6) Discussion 6
    11Input and Output [LS15 - Ch 10]
    12Multitasking[LS15 - Ch 11]
    -- Sep 13 - Sep 19 Mid-Semester Examination
    -- Sep 20 - Sep 26 (Week 7) Discussion 7
    13Scheduling[LS15 - Ch 12]
    14Scheduling[LS15 - Ch 12]
    -- Sep 27 - Oct 3 (Week 8) Discussion 8
    15Invariants and Temporal Logic[LS15 - Ch 13]
    16Equivalence and Refinement[[LS15 - Ch 14]
    -- Oct 4 - Oct 10 (Week 9) Discussion 9
    17Reachability Analysis and Model Checking[LS15 - Ch 15]
    18Quantitative Analysis[LS15 - Ch 16]
    -- Oct 11 - Oct 17 Mid-Semester Recess
    -- Oct 18 - Oct 24 (Week 10) Discussion 10
    19 Runtime Monitoring TBD
    -- Oct 25 - Oct 31 (Week 11) Student Presentation 1 (Oct 25, 12:00 - 1:30 pm)
    -- Student Presentation 2 (Oct 28, 12:00 - 1:30 pm)
    -- Nov 1 - Nov 7 (Week 12) Student Presentation 3 (Nov 1, 12:00 - 1:30 pm)
    -- Holiday: Diwali (Nov 4)
    -- Nov 8 - Nov 14 (Week 13) Student Presentation 4 (Nov 8, 12:00 - 1:30 pm)
    -- Student Presentation 5 (Nov 11, 2:00 - 3:30 pm)
    -- Nov 15 - Nov 18 (Week 14) Student Presentation 6 (Nov 15, 12:00 - 1:30 pm)
    -- Student Presentation 7 (Nov 18, 12:00 - 1:30 pm)
    -- Nov 21 - Nov 30 End-Semester Examination

    References

    [Alur15] Rajeev Alur. Principles of Cyber-Physical Systems. The MIT Press, 2015.
    [AD94] Rajeev Alur, David L. Dill: A Theory of Timed Automata. Theor. Comput. Sci. 126(2): 183-235 (1994).
    [AM09] K. J. Astrom and R. M. Murray. Feedback Systems: An Introduction for Scientists and Engineers. Prince- ton University Press, 2009. http://www.cds.caltech.edu/~murray/amwiki/index.php/Main_Page.
    [BK08] C. Baier and J.-P. Katoen. Principles of Model Checking. The MIT Press, 2008.
    [Harel87] D. Harel. Statecharts: A Visual Formalism for Complex Systems. Science of Computer Programming 8 (1987) 231-274.
    [Lee08] Edward A. Lee. Cyber-Physical Systems: Design Challenges. IRORC 2008.
    [LS15] Edward A. Lee and Sanjit A. Seshia, Introduction to Embedded Systems, A Cyber-Physical Systems Approach, Second Edition, http://LeeSeshia.org, ISBN 978-1-312-42740-2, 2015.
    [Ras05] Jean-Francois Raskin. An Introduction to Hybrid Automata. Handbook of Networked and Embedded Control Systems, pages 491-517, 2005.