Thomas Lew

Contacts:

Thomas Lew


Thomas is a Ph.D. student in the Department of Aeronautics and Astronautics. He completed his M.Sc. in Robotics at ETH Zürich and his B.Sc. at EPFL, Switzerland. At ETH Zürich, he worked on motion generation for legged robotics with Prof. Hutter, designed control algorithms for the student rocketry team, and worked on terramechanics for ESA’s ExoMars rover at RUAG Space. He also interned at NASA JPL with Dr. Agha, where he developed resilient contact-based control algorithms for the DARPA SubT Challenge.

To enable autonomous systems to cope with uncertainty while guaranteeing safety, he is currently developing safe learning-based control and uncertainty-aware planning algorithms.


ASL Publications

  1. T. Lew, R. Bonalli, and M. Pavone, “Sample Average Approximation for Stochastic Programming with Equality Constraints,” SIAM Journal on Optimization, Jun. 2022. (Submitted)

    Abstract: We revisit the sample average approximation (SAA) approach for general non-convex stochastic programming. We show that applying the SAA approach to problems with expected value equality constraints does not necessarily result in asymptotic optimality guarantees as the number of samples increases. To address this issue, we relax the equality constraints. Then, we prove the asymptotic optimality of the modified SAA approach under mild smoothness and boundedness conditions on the equality constraint functions. Our analysis uses random set theory and concentration inequalities to characterize the approximation error from the sampling procedure. We apply our approach to the problem of stochastic optimal control for nonlinear dynamical systems subject to external disturbances modeled by a Wiener process. We verify our approach on a rocket-powered descent problem and show that our computed solutions allow for significant uncertainty reduction.

    @article{LewBonalliEtAl2022,
      author = {Lew, T. and Bonalli, R. and Pavone, M.},
      title = {Sample Average Approximation for Stochastic Programming with Equality Constraints},
      journal = {{SIAM Journal on Optimization}},
      month = jun,
      year = {2022},
      note = {Submitted},
      keywords = {sub},
      owner = {lew},
      timestamp = {2022-06-22},
      url = {https://arxiv.org/abs/2206.09963}
    }
    
  2. A. Wu, T. Lew, K. Solovey, E. Schmerling, and M. Pavone, “Robust-RRT: Probabilistically-Complete Motion Planning for Uncertain Nonlinear Systems,” in Int. Symp. on Robotics Research, 2022.

    Abstract: Robust motion planning entails computing a global motion plan that is safe under all possible uncertainty realizations, be it in the system dynamics, the robot’s initial position, or with respect to external disturbances. Current approaches for robust motion planning either lack theoretical guarantees, or make restrictive assumptions on the system dynamics and uncertainty distributions. In this paper, we address these limitations by proposing the robust rapidly-exploring random-tree (Robust-RRT) algorithm, which integrates forward reachability analysis directly into sampling-based control trajectory synthesis. We prove that Robust-RRT is probabilistically complete (PC) for nonlinear Lipschitz continuous dynamical systems with bounded uncertainty. In other words, Robust-RRT eventually finds a robust motion plan that is feasible under all possible uncertainty realizations assuming such a plan exists. Our analysis applies even to unstable systems that admit only short-horizon feasible plans; this is because we explicitly consider the time evolution of reachable sets along control trajectories. Thanks to the explicit consideration of time dependency in our analysis, PC applies to unstabilizable systems. To the best of our knowledge, this is the most general PC proof for robust sampling-based motion planning, in terms of the types of uncertainties and dynamical systems it can handle. Considering that an exact computation of reachable sets can be computationally expensive for some dynamical systems, we incorporate sampling-based reachability analysis into Robust-RRT and demonstrate our robust planner on nonlinear, underactuated, and hybrid systems.

    @inproceedings{WuLewEtAl2022,
      author = {Wu, A. and Lew, T. and Solovey, K. and Schmerling, E. and Pavone, M.},
      booktitle = {{Int. Symp. on Robotics Research}},
      title = {{Robust-RRT}: Probabilistically-Complete Motion Planning for Uncertain Nonlinear Systems},
      year = {2022},
      month = may,
      keywords = {pub},
      owner = {lew},
      timestamp = {2022-05-22},
      url = {https://arxiv.org/abs/2205.07728}
    }
    
  3. A. J. Thorpe, T. Lew, M. M. K. Oishi, and M. Pavone, “Data-Driven Chance Constrained Control using Kernel Distribution Embeddings,” in Learning for Dynamics & Control Conference, 2022.

    Abstract: We present a data-driven algorithm for efficiently computing stochastic control policies for general joint chance constrained optimal control problems. Our approach leverages the theory of kernel distribution embeddings, which allows representing expectation operators as inner products in a reproducing kernel Hilbert space. This framework enables approximately reformulating the original problem using a dataset of observed trajectories from the system without imposing prior assumptions on the parameterization of the system dynamics or the structure of the uncertainty. By optimizing over a finite subset of stochastic open-loop control trajectories, we relax the original problem to a linear program over the control parameters that can be efficiently solved using standard convex optimization techniques. We demonstrate our proposed approach in simulation on a system with nonlinear non-Markovian dynamics navigating in a cluttered environment.

    @inproceedings{ThorpeLewEtAl2022,
      author = {Thorpe, A.~J. and Lew, T. and Oishi, M.~M.~K. and Pavone, M.},
      title = {Data-Driven Chance Constrained Control using Kernel Distribution Embeddings},
      year = {2022},
      booktitle = {{Learning for Dynamics \& Control Conference}},
      month = mar,
      url = {https://arxiv.org/abs/2202.04193},
      keywords = {pub},
      owner = {lew},
      timestamp = {2022-03-01}
    }
    
  4. T. Lew, L. Janson, R. Bonalli, and M. Pavone, “A Simple and Efficient Sampling-based Algorithm for General Reachability Analysis,” in Learning for Dynamics & Control Conference, 2022.

    Abstract: In this work, we analyze an efficient sampling-based algorithm for general-purpose reachability analysis, which remains a notoriously challenging problem with applications ranging from neural network verification to safety analysis of dynamical systems. By sampling inputs, evaluating their images in the true reachable set, and taking their ε-padded convex hull as a set estimator, this algorithm applies to general problem settings and is simple to implement. Our main contribution is the derivation of asymptotic and finite-sample accuracy guarantees using random set theory. This analysis informs algorithmic design to obtain an ε-close reachable set approximation with high probability, provides insights into which reachability problems are most challenging, and motivates safety-critical applications of the technique. On a neural network verification task, we show that this approach is more accurate and significantly faster than prior work. Informed by our analysis, we also design a robust model predictive controller that we demonstrate in hardware experiments.

    @inproceedings{LewJansonEtAl2022,
      author = {Lew, T. and Janson, L. and Bonalli, R. and Pavone, M.},
      title = {A Simple and Efficient Sampling-based Algorithm for General Reachability Analysis},
      year = {2022},
      booktitle = {{Learning for Dynamics \& Control Conference}},
      month = mar,
      url = {https://arxiv.org/abs/2112.05745},
      keywords = {pub},
      owner = {lew},
      timestamp = {2022-03-01}
    }
    
  5. D. Malyuta, T. P. Reynolds, M. Szmuk, T. Lew, R. Bonalli, M. Pavone, and B. Acikmese, “Convex Optimization for Trajectory Generation,” IEEE Control Systems Magazine, vol. 42, no. 5, pp. 40–113, Jan. 2022.

    Abstract: Reliable and efficient trajectory generation methods are a fundamental need for autonomous dynamical systems of tomorrow. The goal of this article is to provide a comprehensive tutorial of three major convex optimization-based trajectory generation methods: lossless convexification (LCvx), and two sequential convex programming algorithms known as SCvx and GuSTO. In this article, trajectory generation is the computation of a dynamically feasible state and control signal that satisfies a set of constraints while optimizing key mission objectives. The trajectory generation problem is almost always nonconvex, which typically means that it is not readily amenable to efficient and reliable solution onboard an autonomous vehicle. The three algorithms that we discuss use problem reformulation and a systematic algorithmic strategy to nonetheless solve nonconvex trajectory generation tasks through the use of a convex optimizer. The theoretical guarantees and computational speed offered by convex optimization have made the algorithms popular in both research and industry circles. To date, the list of applications include rocket landing, spacecraft hypersonic reentry, spacecraft rendezvous and docking, aerial motion planning for fixed-wing and quadrotor vehicles, robot motion planning, and more. Among these applications are high-profile rocket flights conducted by organizations like NASA, Masten Space Systems, SpaceX, and Blue Origin. This article aims to give the reader the tools and understanding necessary to work with each algorithm, and to know what each method can and cannot do. A publicly available source code repository supports the numerical examples provided at the end of this article. By the end of the article, the reader should be ready to use each method, to extend them, and to contribute to their many exciting modern applications.

    @article{MalyutaEtAl2022,
      author = {Malyuta, D. and Reynolds, T.~P. and Szmuk, M. and Lew, T. and Bonalli, R. and Pavone, M. and Acikmese, B.},
      title = {Convex Optimization for Trajectory Generation},
      year = {2022},
      journal = {{IEEE Control Systems Magazine}},
      volume = {42},
      number = {5},
      pages = {40--113},
      month = jan,
      url = {https://arxiv.org/abs/2106.09125},
      keywords = {pub},
      owner = {lew},
      timestamp = {2022-01-30}
    }
    
  6. R. Sinha, A. Sharma, S. Banerjee, T. Lew, R. Luo, S. M. Richards, Y. Sun, E. Schmerling, and M. Pavone, “A System-Level View on Out-of-Distribution Data in Robotics,” in Proc. AAAI Conf. on Artificial Intelligence, 2022. (Submitted)

    Abstract: When testing conditions differ from those represented in training data, so-called out-of-distribution (OOD) inputs can mar the reliability of black-box learned components in the modern robot autonomy stack. Therefore, coping with OOD data is an important challenge on the path towards trustworthy learning-enabled open-world autonomy. In this paper, we aim to demystify the topic of OOD data and its associated challenges in the context of data-driven robotic systems, drawing connections to emerging paradigms in the ML community that study the effect of OOD data on learned models in isolation. We argue that as roboticists, we should reason about the overall system-level competence of a robot as it performs tasks in OOD conditions. We highlight key research questions around this system-level view of OOD problems to guide future research toward safe and reliable learning-enabled autonomy.

    @inproceedings{SinhaSharmaEtAl2022,
      author = {Sinha, Rohan and Sharma, Apoorva and Banerjee, Somrita and Lew, Thomas and Luo, Rachel and Richards, Spencer M. and Sun, Yixiao and Schmerling, Edward and Pavone, Marco},
      title = {A System-Level View on Out-of-Distribution Data in Robotics},
      booktitle = {{Proc. AAAI Conf. on Artificial Intelligence}},
      year = {2022},
      note = {Submitted},
      url = {/wp-content/papercite-data/pdf/Sinha.Sharma.ea.AAAI23.pdf},
      keywords = {sub},
      owner = {rhnsinha},
      timestamp = {2022-10-24}
    }
    
  7. T. Lew, A. Sharma, J. Harrison, A. Bylard, and M. Pavone, “Safe Active Dynamics Learning and Control: A Sequential Exploration-Exploitation Framework,” IEEE Transactions on Robotics, vol. 38, no. 5, pp. 2888–2907, 2022.

    Abstract: To safely deploy learning-based systems in highly uncertain environments, one must ensure that they always satisfy constraints. In this work, we propose a practical and theoretically justified approach to maintaining safety in the presence of dynamics uncertainty. Our approach leverages Bayesian meta-learning with last-layer adaptation: the expressiveness of neural-network features trained offline, paired with efficient last-layer online adaptation, enables the derivation of tight confidence sets which contract around the true dynamics as the model adapts online. We exploit these confidence sets to plan trajectories that guarantee the safety of the system. Our approach handles problems with high dynamics uncertainty where reaching the goal safely is initially infeasible by first exploring to gather data and reduce uncertainty, before autonomously exploiting the acquired information to safely perform the task. Under reasonable assumptions, we prove that our framework provides safety guarantees in the form of a single joint chance constraint. Furthermore, we use this theoretical analysis to motivate regularization of the model to improve performance. We extensively demonstrate our approach in simulation and on hardware.

    @article{LewEtAl2022,
      author = {Lew, T. and Sharma, A. and Harrison, J. and Bylard, A. and Pavone, M.},
      title = {Safe Active Dynamics Learning and Control: A Sequential Exploration-Exploitation Framework},
      journal = {{IEEE Transactions on Robotics}},
      volume = {38},
      number = {5},
      pages = {2888--2907},
      booktitle = {{Proc. Conf. on Uncertainty in Artificial Intelligence}},
      year = {2022},
      doi = {10.1109/TRO.2022.3154715},
      url = {https://arxiv.org/pdf/2008.11700.pdf},
      owner = {lew},
      timestamp = {2022-01-27}
    }
    
  8. R. Bonalli, T. Lew, and M. Pavone, “Sequential Convex Programming For Non-Linear Stochastic Optimal Control,” ESAIM: Control, Optimisation & Calculus of Variations, vol. 28, no. 64, 2022.

    Abstract:

    @article{BonalliLewESAIM2022,
      author = {Bonalli, R. and Lew, T. and Pavone, M.},
      title = {Sequential Convex Programming For Non-Linear Stochastic Optimal Control},
      journal = {{ESAIM: Control, Optimisation \& Calculus of Variations}},
      volume = {28},
      number = {64},
      year = {2022},
      owner = {lew},
      timestamp = {2022-01-29},
      url = {https://arxiv.org/abs/2009.05182}
    }
    
  9. R. Bonalli, T. Lew, and M. Pavone, “Analysis of Theoretical and Numerical Properties of Sequential Convex Programming for Continuous-Time Optimal Control,” IEEE Transactions on Automatic Control, 2022.

    Abstract: Sequential Convex Programming (SCP) has recently gained significant popularity as an effective method for solving optimal control problems and has been successfully applied in several different domains. However, the theoretical analysis of SCP has received comparatively limited attention, and it is often restricted to discrete-time formulations. In this paper, we present a unifying theoretical analysis of a fairly general class of SCP procedures for continuous-time optimal control problems. In addition to the derivation of convergence guarantees in a continuous-time setting, our analysis reveals two new numerical and practical insights. First, we show how one can more easily account for manifold-type constraints, which are a defining feature of optimal control of mechanical systems. Second, we show how our theoretical analysis can be leveraged to accelerate SCP-based optimal control methods by infusing techniques from indirect optimal control.

    @article{BonalliLewEtAl2022,
      author = {Bonalli, R. and Lew, T. and Pavone, M.},
      title = {Analysis of Theoretical and Numerical Properties of Sequential Convex Programming for Continuous-Time Optimal Control},
      journal = {{IEEE Transactions on Automatic Control}},
      year = {2022},
      keywords = {pub},
      owner = {lew},
      timestamp = {2020-12-07},
      url = {https://arxiv.org/abs/2009.05038}
    }
    
  10. J. Schilliger, T. Lew, S. M. Richards, S. Hanggi, M. Pavone, and C. Onder, “Control Barrier Functions for Cyber-Physical Systems and Applications to NMPC,” IEEE Robotics and Automation Letters, vol. 6, no. 4, pp. 8623–8630, Aug. 2021.

    Abstract: Tractable safety-ensuring algorithms for cyber-physical systems are important in critical applications. Approaches based on Control Barrier Functions assume continuous enforcement, which is not possible in an online fashion. This paper presents two tractable algorithms to ensure forward invariance of discrete-time controlled cyber-physical systems. Both approaches are based on Control Barrier Functions to provide strict mathematical safety guarantees. The first algorithm exploits Lipschitz continuity and formulates the safety condition as a robust program which is subsequently relaxed to a set of affine conditions. The second algorithm is inspired by tube-NMPC and uses an affine Control Barrier Function formulation in conjunction with an auxiliary controller to guarantee safety of the system. We combine an approximate NMPC controller with the second algorithm to guarantee strict safety despite approximated constraints and show its effectiveness experimentally on a mini-Segway.

    @article{SchilligerEtAl2021,
      author = {Schilliger, J. and Lew, T. and Richards, S.~M. and Hanggi, S. and Pavone, M. and Onder, C.},
      title = {Control Barrier Functions for Cyber-Physical Systems and Applications to NMPC},
      journal = {{IEEE Robotics and Automation Letters}},
      volume = {6},
      number = {4},
      pages = {8623--8630},
      year = {2021},
      month = aug,
      url = {https://arxiv.org/abs/2104.14250},
      owner = {lew},
      timestamp = {2021-08-23}
    }
    
  11. T. Lew and M. Pavone, “Sampling-based Reachability Analysis: A Random Set Theory Approach with Adversarial Sampling,” in Conf. on Robot Learning, 2020.

    Abstract: Reachability analysis is at the core of many applications, from neural network verification, to safe trajectory planning of uncertain systems. However, this problem is notoriously challenging, and current approaches tend to be either too restrictive, too slow, too conservative, or approximate and therefore lack guarantees. In this paper, we propose a simple yet effective sampling-based approach to perform reachability analysis for arbitrary dynamical systems. Our key novel idea consists of using random set theory to give a rigorous interpretation of our method, and prove that it returns sets which are guaranteed to converge to the convex hull of the true reachable sets. Additionally, we leverage recent work on robust deep learning and propose a new adversarial sampling approach to robustify our algorithm and accelerate its convergence. We demonstrate that our method is faster and less conservative than prior work, present results for approximate reachability analysis of neural networks and robust trajectory optimization of high-dimensional uncertain nonlinear systems, and discuss future applications.

    @inproceedings{LewPavone2020,
      title = {Sampling-based Reachability Analysis: A Random Set Theory Approach with Adversarial Sampling},
      author = {Lew, T. and Pavone, M.},
      booktitle = {{Conf. on Robot Learning}},
      year = {2020},
      month = aug,
      url = {https://arxiv.org/abs/2008.10180},
      owner = {lew},
      timestamp = {2020-11-07}
    }
    
  12. T. Lew, R. Bonalli, and M. Pavone, “Chance-Constrained Sequential Convex Programming for Robust Trajectory Optimization,” in European Control Conference, St. Petersburg, Russia, 2020.

    Abstract: Planning safe trajectories for nonlinear dynamical systems subject to model uncertainty and disturbances is challenging. In this work, we present a novel approach to tackle chance-constrained trajectory planning problems with nonconvex constraints, whereby obstacle avoidance chance constraints are reformulated using the signed distance function. We propose a novel sequential convex programming algorithm and prove that under a discrete time problem formulation, it is guaranteed to converge to a solution satisfying first-order optimality conditions. We demonstrate the approach on an uncertain 6 degrees of freedom spacecraft system and show that the solutions satisfy a given set of chance constraints.

    @inproceedings{LewBonalliEtAl2020,
      author = {Lew, T. and Bonalli, R. and Pavone, M.},
      title = {Chance-Constrained Sequential Convex Programming for Robust Trajectory Optimization},
      booktitle = {{European Control Conference}},
      year = {2020},
      address = {St. Petersburg, Russia},
      month = may,
      url = {/wp-content/papercite-data/pdf/Lew.Bonalli.Pavone.ECC20.pdf},
      owner = {lew},
      timestamp = {2020-03-16}
    }
    
  13. S. Banerjee, T. Lew, R. Bonalli, A. Alfaadhel, I. A. Alomar, H. M. Shageer, and M. Pavone, “Learning-based Warm-Starting for Fast Sequential Convex Programming and Trajectory Optimization,” in IEEE Aerospace Conference, Big Sky, Montana, 2020.

    Abstract: Sequential convex programming (SCP) has recently emerged as an effective tool to quickly compute locally optimal trajectories for robotic and aerospace systems alike, even when initialized with an unfeasible trajectory. In this paper, by focusing on the Guaranteed Sequential Trajectory Optimization (GuSTO) algorithm, we propose a methodology to accelerate SCP-based algorithms through warm-starting. Specifically, leveraging a dataset of expert trajectories from GuSTO, we devise a neural-network-based approach to predict a locally optimal state and control trajectory, which is used to warm-start the SCP algorithm. This approach allows one to retain all the theoretical guarantees of GuSTO while simultaneously taking advantage of the fast execution of the neural network and reducing the time and number of iterations required for GuSTO to converge. The result is a faster and theoretically guaranteed trajectory optimization algorithm.

    @inproceedings{BanerjeeEtAl2020,
      author = {Banerjee, S. and Lew, T. and Bonalli, R. and Alfaadhel, A. and Alomar, I. A. and Shageer, H. M. and Pavone, M.},
      title = {Learning-based Warm-Starting for Fast Sequential Convex Programming and Trajectory Optimization},
      booktitle = {{IEEE Aerospace Conference}},
      year = {2020},
      address = {Big Sky, Montana},
      month = mar,
      url = {/wp-content/papercite-data/pdf/Banerjee.Lew.Bonalli.ea.AeroConf20.pdf},
      owner = {lew},
      timestamp = {2020-01-09}
    }
    
  14. R. Bonalli, A. Bylard, A. Cauligi, T. Lew, and M. Pavone, “Trajectory Optimization on Manifolds: A Theoretically-Guaranteed Embedded Sequential Convex Programming Approach,” in Robotics: Science and Systems, Freiburg im Breisgau, Germany, 2019.

    Abstract: Sequential Convex Programming (SCP) has recently gain popularity as a tool for trajectory optimization, due to its sound theoretical properties and practical performance. Yet, most SCP-based methods for trajectory optimization are restricted to Euclidean settings, which precludes their application to problem instances where one needs to reason about manifold-type constraints (that is, constraints, such as loop closure, which restrict the motion of a system to a subset of the ambient space). The aim of this paper is to fill this gap by extending SCP-based trajectory optimization methods to a manifold setting. The key insight is to leverage geometric embeddings to lift a manifold-constrained trajectory optimization problem into an equivalent problem defined over a space enjoying Euclidean structure. This insight allows one to extend existing SCP methods to a manifold setting in a fairly natural way. In particular, we present an SCP algorithm for manifold problems with theoretical guarantees that resemble those derived for the Euclidean setting, and demonstrate its practical performance via numerical experiments.

    @inproceedings{BonalliBylardEtAl2019,
      author = {Bonalli, R. and Bylard, A. and Cauligi, A. and Lew, T. and Pavone, M.},
      title = {Trajectory Optimization on Manifolds: {A} Theoretically-Guaranteed Embedded Sequential Convex Programming Approach},
      booktitle = {{Robotics: Science and Systems}},
      year = {2019},
      address = {Freiburg im Breisgau, Germany},
      month = jun,
      url = {https://arxiv.org/pdf/1905.07654.pdf},
      owner = {bylard},
      timestamp = {2019-05-01}
    }