Alessandro Abate

Alessandro Abate

Auto-generated profile, based on publicly available information

Alessandro Abate

University of Oxford

Research Focus & Metrics

Academic Career Length

18Years (2009-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
26 June 2020 in IEEE Control Systems Letters
Verified
Journal Article
Closed access
AAAlessandro Abate
Alessandro Abate
DADaniele Ahmed
Daniele Ahmed
MGMirco Giacobbe
Mirco Giacobbe
APAndrea Peruffo
Andrea Peruffo
We propose an automatic and formally sound method for synthesising Lyapunov functions for the asymptotic stability of autonomous non-linear systems. Traditional methods are either analytical and require manual effort or are numerical but lack of formal soundness. Symbolic computational methods for Lyapunov functions, which are in between, give formal guarantees but are typically semi-automatic because they rely on the user to provide appropriate function templates. We propose a method that finds Lyapunov functions fully automatically—using machine learning—while also providing formal guarantees—using satisfiability modulo theories (SMT). We employ a counterexample-guided approach where a numerical learner and a symbolic verifier interact to construct provably correct Lyapunov neural networks (LNNs). The learner trains a neural network that satisfies the Lyapunov criteria for asymptotic stability over a samples set; the verifier proves via SMT solving that the criteria are satisfied over the whole domain or augments the samples set with counterexamples. Our method supports neural networks with polynomial activation functions and multiple depth and width, which display wide learning capabilities. We demonstrate our method over several non-trivial benchmarks and compare it favourably against a numerical optimisation-based approach, a symbolic template-based approach, and a cognate LNN-based approach. Our method synthesises Lyapunov functions faster and over wider spatial domains than the alternatives, yet providing stronger or equal guarantees.

1 January 2010 in European Journal of Control
Verified
Journal Article
Closed access
AAAlessandro Abate
Alessandro Abate
JKJoost-Pieter Katoen
Joost-Pieter Katoen
JLJohn Lygeros
John Lygeros
MPMaria Prandini
Maria Prandini
A method for approximate model checking of stochastic hybrid systems with provable approximation guarantees is proposed. We focus on the probabilistic invariance problem for discrete time stochastic hybrid systems and propose a two-step scheme. The stochastic hybrid system is first approximated by a finite state Markov chain. The approximating chain is then model checked for probabilistic invariance. Under certain regularity conditions on the transition and reset kernels governing the dynamics of the stochastic hybrid system, the invariance probability computed using the approximating Markov chain is shown to converge to the invariance probability of the original stochastic hybrid system, as the grid used in the approximation gets finer. A bound on the convergence rate is also provided. The performance of the two-step approximate model checking procedure is assessed on a case study of a multi-room heating system.

4 August 2021 in IEEE Robotics and Automation Letters
Verified
Journal Article
Closed access
MCMingyu Cai
Mingyu Cai
MHMohammadhosein Hasanbeig
Mohammadhosein Hasanbeig
SXShaoping Xiao
Shaoping Xiao
AAAlessandro Abate
Alessandro Abate
ZKZhen Kan
Zhen Kan
This letter investigates the motion planning of autonomous dynamical systems modeled by Markov decision processes (MDP) with unknown transition probabilities over continuous state and action spaces. Linear temporal logic (LTL) is used to specify high-level tasks over infinite horizon, which can be converted into a limit deterministic generalized Büchi automaton (LDGBA) with several accepting sets. The novelty is to design an embedded product MDP (EP-MDP) between the LDGBA and the MDP by incorporating a synchronous tracking-frontier function to record unvisited accepting sets of the automaton, and to facilitate the satisfaction of the accepting conditions. The proposed LDGBA-based reward shaping and discounting schemes for the model-free reinforcement learning (RL) only depend on the EP-MDP states and can overcome the issues of sparse rewards. Rigorous analysis shows that any RL method that optimizes the expected discounted return is guaranteed to find an optimal policy whose traces maximize the satisfaction probability. A modular deep deterministic policy gradient (DDPG) is then developed to generate such policies over continuous state and action spaces. The performance of our framework is evaluated via an array of OpenAI gym environments.

18 July 2018
Verified
Book Chapter
Open access
PDF file
AAAlessandro Abate
Alessandro Abate
CDCristina David
Cristina David
PKPascal Kesseli
Pascal Kesseli
DKDaniel Kroening
Daniel Kroening
EPElizabeth Polgreen
Elizabeth Polgreen
Program synthesis is the mechanised construction of software. One of the main difficulties is the efficient exploration of the very large solution space, and tools often require a user-provided syntactic restriction of the search space. We propose a new approach to program synthesis that combines the strengths of a counterexample-guided inductive synthesizer with those of a theory solver, exploring the solution space more efficiently without relying on user guidance. We call this approach CEGIS(\(\mathcal {T}\)), where \(\mathcal {T}\) is a first-order theory. In this paper, we focus on one particular challenge for program synthesizers, namely the generation of programs that require non-trivial constants. This is a fundamentally difficult task for state-of-the-art synthesizers. We present two exemplars, one based on Fourier-Motzkin (FM) variable elimination and one based on first-order satisfiability. We demonstrate the practical value of CEGIS(\(\mathcal {T}\)) by automatically synthesizing programs for a set of intricate benchmarks.

21 January 2023 in Journal of Artificial Intelligence Research
Verified
Journal Article
Open access
PDF file
Thom BadingsThom Badings
Thom Badings
LRLicio Romao
Licio Romao
AAAlessandro Abate
Alessandro Abate
DPDavid Parker
David Parker
HPHasan A. Poonawala
Hasan A. Poonawala
NJNils Jansen
Nils Jansen
Controllers for dynamical systems that operate in safety-critical settings must account for stochastic disturbances. Such disturbances are often modeled as process noise in a dynamical system, and common assumptions are that the underlying distributions are known and/or Gaussian. In practice, however, these assumptions may be unrealistic and can lead to poor approximations of the true noise distribution. We present a novel controller synthesis method that does not rely on any explicit representation of the noise distributions. In particular, we address the problem of computing a controller that provides probabilistic guarantees on safely reaching a target, while also avoiding unsafe regions of the state space. First, we abstract the continuous control system into a finite-state model that captures noise by probabilistic transitions between discrete states. As a key contribution, we adapt tools from the scenario approach to compute probably approximately correct (PAC) bounds on these transition probabilities, based on a finite number of samples of the noise. We capture these bounds in the transition probability intervals of a so-called interval Markov decision process (iMDP). This iMDP is, with a user-specified confidence probability, robust against uncertainty in the transition probabilities, and the tightness of the probability intervals can be controlled through the number of samples. We use state-of-the-art verification techniques to provide guarantees on the iMDP and compute a controller for which these guarantees carry over to the original control system. In addition, we develop a tailored computational scheme that reduces the complexity of the synthesis of these guarantees on the iMDP. Benchmarks on realistic control systems show the practical applicability of our method, even when the iMDP has hundreds of millions of transitions.

19 February 2020 in IEEE Transactions on Automatic Control
Verified
Journal Article
Closed access
LLLuca Laurenti
Luca Laurenti
MLMorteza Lahijanian
Morteza Lahijanian
AAAlessandro Abate
Alessandro Abate
LCLuca Andrea Cardelli
Luca Andrea Cardelli
MKMarta Kwiatkowska
Marta Kwiatkowska
This work introduces a theoretical framework and a scalable computational method for formal analysis and control synthesis for switched diffusions, a class of stochastic models with linear dynamics that are continuous in both time and space domains; the focus is on safety with possible extensions to other properties. The proposed framework first constructs a finite abstraction in the form of an uncertain Markov process through discretization of both time and space domains. The errors caused by the discretization in each domain are formally characterized and cast into the abstraction model. Then, a strategy that maximizes the probability of the safety property and is robust against the errors is synthesized over the abstraction model. Finally, this robust strategy is mapped to a switching strategy for the stochastic processes that guarantees the safety property. The efficacy of the framework is demonstrated in three case studies, including one that illustrates the trade-off of the error contribution by the time and space discretization parameters.