CS637: Embedded and Cyber-Physical Systems

Fall 2023 (July 31, 2023 - November 13, 2023)

Lecture Hours: Monday and Thursday 12 noon to 1:30 pm
Office Hour: By Appointment

Lecture Venue: L7

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]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

    Quiz - 5%
    Homework Assignments - 15%
    Mid-Semester Examination - 20%
    End-Semester Examination - 30%
    Project - 30%

    Our department follows this anti-cheating policy strictly.


    Exam Schedule and Deadlines

    Homework
    Homework 1 (Deadline: September 15, 2023)
    Homework 2 (Deadline: October 13, 2023)
    Homework 3 (Deadline: November 3, 2023)

    Project
    Project Team Formation (Deadline: August 11, 2023)
    Project Proposal Submission (Deadline: August 18, 2023)
    Final Project Presentation (Scheduled on October 30, 2023 - November 13, 2023)
    Final Report Submission (Deadline: November 14, 2023)

    Mid-Semester Examination
    September 22, 2023 (Friday) 1:00 pm to 3:00 pm at L20 ERES

    Final Examination
    November 21, 2023 (Tuesday) 5:30 pm to 8:30 pm at L20 ERES

    Lecture Schedule


    Lecture Date Topic References
    1July 31, 2023Introduction to the course[LS15 - Ch 1]
    2August 3, 2023Modeling Dynamic Behaviors - Continuous Dynamics[LS15 - Ch 2]
    3August 7, 2023Basics of Feedback Control Theory[AM09]
    4August 10, 2023Modeling Dynamic Behaviors - Discrete Dynamics[LS15 - Ch 3]
    5August 14, 2023Hybrid Systems[LS15 - Ch 4]
    6August 17, 2023Timed Systems[BK08 - Ch 8]
    7August 21, 2023Composition of State Machines[LS15 - Ch 5]
    8August 24, 2023Concurrent Models of Computation[LS15 - Ch 6]
    9August 28, 2023Sensors and Actuators[LS15 - Ch 7]
    10August 31, 2023Embedded Processors[LS15 - Ch 8]
    11Swptember 4, 2023Memory Architectures[LS15 - Ch 9]
    --September 7, 2023 Holiday: Janmasthami
    12September 11, 2023Scheduling[LS15 - Ch 12]
    13September 14, 2023Scheduling[LS15 - Ch 12]
    --September 18, 2023 Mid-Semester Examination
    --September 21, 2023Mid-Semester Examination
    14September 25, 2023Invariants and Temporal Logic[LS15 - Ch 13]
    --September 28, 2023 Holiday: Milad-un-Nabi or Id-e-Milad
    --October 2, 2023 Holiday: Mahatma Gandhi's Birthday
    15October 5, 2023Invariants and Temporal Logic [LS15 - Ch 13]
    16October 9, 2023Equivalence and Refinement [LS15 - Ch 14]
    17October 12, 2023Reachability Analysis and Model Checking [LS15 - Ch 15]
    18October 16, 2023Quantitative Analysis[LS15 - Ch 16]
    19October 19, 2023Specification Guided Controller Synthesis Using RL[SS23]
    --October 23, 2023 Mid-Semester Recess
    --October 26, 2023 Mid-Semester Recess
    20October 30, 2023Project Presentation
    21November 2, 2023Project Presentation
    22November 6, 2023Project Presentation
    23November 9, 2023Project Presentation
    24November 11, 2023Project Presentation
    24November 13, 2023Project Presentation

    References

    [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.
    [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.
    [SS23] Nikhil.K. Singh and Indranil Saha. STL-Based Synthesis of Feedback Controllers Using Reinforcement Learning. AAAI 2023.
    [KGS20] Danish Khalidi, Dhaval Gujarathi, Indranil Saha: T* : A Heuristic Search Based Path Planning Algorithm for Temporal Logic Specifications. ICRA 2020: 8476-8482