Sriram Sankaranarayanan

selected publications

1. Counterexample-guided computation of polyhedral Lyapunov functions for piecewise linear systems

   Guillaume O. Berger, and Sriram Sankaranarayanan

   Automatica, 2023.

   Note: Accepted (in press).

   Abs Bib URL

   This paper presents a counterexample-guided iterative algorithm to compute convex, piecewise linear (polyhedral) Lyapunov functions for continuous-time piecewise linear systems. Polyhedral Lyapunov functions provide an alternative to commonly used polynomial Lyapunov functions. Our approach first characterizes intrinsic properties of a polyhedral Lyapunov function including its “eccentricity” and “robustness” to perturbations. We then derive an algorithm that either computes a polyhedral Lyapunov function proving that the system is asymptotically stable, or concludes that no polyhedral Lyapunov function exists whose eccentricity and robustness parameters satisfy some user-provided limits. Significantly, our approach places no a-priori bound on the number of linear pieces that make up the desired polyhedral Lyapunov function. The algorithm alternates between a learning step and a verification step, always maintaining a finite set of witness states. The learning step solves a linear program to compute a candidate Lyapunov function compatible with a finite set of witness states. In the verification step, our approach verifies whether the candidate Lyapunov function is a valid Lyapunov function for the system. If verification fails, we obtain a new witness. We prove a theoretical bound on the maximum number of iterations needed by our algorithm. We demonstrate the applicability of the algorithm on numerical examples.

           @article{ Berger+Sankaranarayanan/2023/Counterexample,
           title = { Counterexample-guided computation of polyhedral Lyapunov functions for piecewise linear systems },
           author = {   Berger, Guillaume O.  and    Sankaranarayanan, Sriram   },
           journal = { Automatica },  
           year = { 2023 },  
           
           
           
           
           
           
           
           }
           

2. Template-Based Piecewise Affine Regression

   Guillaume O. Berger, and Sriram Sankaranarayanan

   In Conference on Learning for Decision and Control (L4DC), 2023.

   Note: To Appear.

   Abs Bib URL

   We investigate the problem of fitting piecewise affine functions (PWA) to data. Our algorithm divides the input domain into finitely many polyhedral regions whose shapes are specified using a user-defined template such that the data points in each region are fit by an affine function within a desired error bound. We first prove that this problem is NP-hard. Next, we present a top-down algorithm that considers subsets of the overall data set in a systematic manner, trying to fit an affine function for each subset using linear regression. If regression fails on a subset, we extract a minimal set of points that led to a failure in order to split the original index set into smaller subsets. Using a combination of this top-down scheme and a set covering algorithm, we derive an overall approach that is optimal in terms of the number of pieces of the resulting PWA model. We demonstrate our approach on two numerical examples that include PWA approximations of a widely used nonlinear insulin–glucose regulation model and a double inverted pendulum with soft contacts.

           @inproceedings{ Berger+Sankaranarayanan/2023/Template,
           title = { Template-Based Piecewise Affine Regression },
           author = {   Berger, Guillaume O.  and    Sankaranarayanan, Sriram   },
           booktitle= {  Conference on Learning for Decision and Control (L4DC) },  
           year = { 2023 },  
           
           
           
           
           
           
           
           }
           

3. Timed Partial Order Inference Algorithm

   Kandai Watanabe, Georgios Fainekos, Bardh Hoxha, Morteza Lahijanian, Danil Prokhorov, Sriram Sankaranarayanan, and Tomoya Yamaguchi

   In Proc. Intl. Conference on Planning and Scheduling (ICAPS), 2023.

   Abs Bib URL

   In this work, we propose the model of timed partial orders (TPOs) for specifying workflow schedules, especially for modeling manufacturing processes. TPOs integrate partial orders over events in a workflow, specifying “happens-before” relations, with timing constraints specified using guards and resets on clocks – an idea borrowed from timed-automata specifications. TPOs naturally allow us to capture event ordering, along with a restricted but useful class of timing relationships. Next, we consider the problem of mining TPO schedules from workflow logs, which include events along with their time stamps. We demonstrate a relationship between formulating TPOs and the graph-coloring problem, and present an algorithm for learning TPOs with correctness guarantees. We demonstrate our approach on synthetic datasets, including two datasets inspired by real-life applications of aircraft turnaround and gameplay videos of the Overcooked computer game. Our TPO mining algorithm can infer TPOs involving hundreds of events from thousands of data-points within a few seconds. We show that the resulting TPOs provide useful insights into the dependencies and timing constraints for workflows.

           @inproceedings{ Watanabe+Others/2023/Timed,
           title = { Timed Partial Order Inference Algorithm },
           author = {   Watanabe, Kandai  and    Fainekos, Georgios  and    Hoxha, Bardh  and    Lahijanian, Morteza  and    Prokhorov, Danil  and    Sankaranarayanan, Sriram  and    Yamaguchi, Tomoya   },
           booktitle= { Proc. Intl. Conference on Planning and Scheduling (ICAPS) },  
           year = { 2023 },  
           
           
           
           
           
           
           
           }
           

4. An Algorithm for Learning Switched Linear Dynamics from Data

   Guillaume O. Berger, Monal Narasimhamurthy, Kandai Watanabe, Morteza Lahijanian, and Sriram Sankaranarayanan

   In Neural Information Processing Systems (NeurIPS’22), Vol. 35, pp. 30419-30431, 2022.

   Abs Bib URL Supp

   We present an algorithm for learning switched linear dynamical systems in discrete time from noisy observations of the system’s full state or output. Switched linear systems use multiple linear dynamical modes to fit the data within some desired tolerance. They arise quite naturally in applications to robotics and cyber-physical systems. Learning switched systems from data is a NP-hard problem that is nearly identical to the k-linear regression problem of fitting k > 1 linear models to the data. A direct mixed-integer linear programming (MILP) approach yields time complexity that is exponential in the number of data points. In this paper, we modify the problem formulation to yield an algorithm that is linear in the size of the data while remaining exponential in the number of state variables and the desired number of modes. To do so, we combine classic ideas from the ellipsoidal method for solving convex optimization problems, and well-known oracle separation results in non-smooth optimization. We demonstrate our approach on a set of microbenchmarks and a few interesting real-world problems. Our evaluation suggests that the benefits of this algorithm can be made practical even against highly optimized off-the-shelf MILP solvers.

           @inproceedings{ Berger+Others/2022/Algorithm,
           title = { An Algorithm for Learning Switched Linear Dynamics from Data },
           author = {   Berger, Guillaume O.  and    Narasimhamurthy, Monal  and    Watanabe, Kandai  and    Lahijanian, Morteza  and    Sankaranarayanan, Sriram   },
           booktitle= { Neural Information Processing Systems (NeurIPS’22) },  
           year = { 2022 },  
           
           pages = { 30419-30431 }, 
           
           
           volume = { 35 },  
           
           
           }
           

   Poster