Jun Liu

Jun Liu

We define robust abstractions for synthesizing provably correct and robust controllers for (possibly infinite) uncertain transition systems. It is shown that robust abstractions are sound in the sense that they preserve robust satisfaction of linear-time properties. We then focus on discrete-time control systems modelled by nonlinear difference equations with inputs and define concrete robust abstractions for them. While most abstraction techniques in the literature for nonlinear systems focus on constructing sound abstractions, we present computational procedures for constructing both sound and approximately complete robust abstractions for general nonlinear control systems without stability assumptions. Such procedures are approximately complete in the sense that, given a concrete discrete-time control system and an arbitrarily small perturbation of this system, there exists a finite transition system that robustly abstracts the concrete system and is abstracted by the slightly perturbed system simultaneously. A direct consequence of this result is that robust control synthesis for discrete-time nonlinear systems and linear-time specifications is robustly decidable. More specifically, if there exists a robust control strategy that realizes a given linear-time specification, we can algorithmically construct a (potentially less) robust control strategy that realizes the same specification. The theoretical results are illustrated with a simple motion planning example.

Jun Liu, Andrew R. Teel

Hybrid systems with memory refer to dynamical systems exhibiting both hybrid and delay phenomena. While systems of this type are frequently encountered in many physical and engineering systems, particularly in control applications, various issues centered around the robustness of hybrid delay systems have not been adequately dealt with. In this paper, we establish some basic results on a framework that allows to study hybrid systems with memory through generalized concepts of solutions. In particular, we develop the basic existence of generalized solutions using regularity conditions on the hybrid data, which are formulated in a phase space of hybrid trajectories equipped with the graphical convergence topology. In contrast with the uniform convergence topology that has been often used, adopting the graphical convergence topology allows us to establish well-posedness of hybrid systems with memory. We then show that, as a consequence of well-posedness, pre-asymptotic stability of well-posed hybrid systems with memory is robust.

Jun Liu, Yiming Meng, Maxwell Fitzsimmons et al.

The search for Lyapunov functions is a crucial task in the analysis of nonlinear systems. In this paper, we present a physics-informed neural network (PINN) approach to learning a Lyapunov function that is nearly maximal for a given stable set. A Lyapunov function is considered nearly maximal if its sub-level sets can be made arbitrarily close to the boundary of the domain of attraction. We use Zubov's equation to train a maximal Lyapunov function defined on the domain of attraction. Additionally, we propose conditions that can be readily verified by satisfiability modulo theories (SMT) solvers for both local and global stability. We provide theoretical guarantees on the existence of maximal Lyapunov functions and demonstrate the effectiveness of our computational approach through numerical examples.

Jun Liu

This paper explores the theoretical limits of using discrete abstractions for nonlinear control synthesis. More specifically, we consider the problem of deciding continuous-time control with temporal logic specifications. We prove that sampled-data control of nonlinear systems with temporal logic specifications is robustly decidable in the sense that, given a continuous-time nonlinear control system and a temporal logic formula, one can algorithmically decide whether there exists a robust sampled-data control strategy to realize this specification when the right-hand side of the system is slightly perturbed by a small disturbance. If the answer is positive, one can then construct a (potentially less) robust sampled-data control strategy that realizes the same specification. The result is proved by constructing a robustly complete abstraction of the original continuous-time control system using sufficiently small discretization parameters. We illustrate the result with a nonlinear control example.

Thanin Quartz, Maxwell Fitzsimmons, Jun Liu

We show that the existence of a strictly compatible pair of control Lyapunov and control barrier functions is equivalent to the existence of a single smooth Lyapunov function that certifies both asymptotic stability and safety. This characterization complements existing literature on converse Lyapunov functions by establishing a partial differential equation (PDE) characterization with prescribed boundary conditions on the safe set, ensuring that the safe set is exactly certified by this Lyapunov function. The result also implies that if a safety and stability specification cannot be certified by a single Lyapunov function, then any pair of control Lyapunov and control barrier functions necessarily leads to a conflict and cannot be satisfied simultaneously in a robust sense.

Jun Liu, Maxwell Fitzsimmons, Ruikun Zhou et al.

Control Lyapunov functions are a central tool in the design and analysis of stabilizing controllers for nonlinear systems. Constructing such functions, however, remains a significant challenge. In this paper, we investigate physics-informed learning and formal verification of neural network control Lyapunov functions. These neural networks solve a transformed Hamilton-Jacobi-Bellman equation, augmented by data generated using Pontryagin's maximum principle. Similar to how Zubov's equation characterizes the domain of attraction for autonomous systems, this equation characterizes the null-controllability set of a controlled system. This principled learning of neural network control Lyapunov functions outperforms alternative approaches, such as sum-of-squares and rational control Lyapunov functions, as demonstrated by numerical examples. As an intermediate step, we also present results on the formal verification of quadratic control Lyapunov functions, which, aided by satisfiability modulo theories solvers, can perform surprisingly well compared to more sophisticated approaches and efficiently produce global certificates of null-controllability.

Jun Liu, Yiming Meng, Maxwell Fitzsimmons et al.

We provide a systematic investigation of using physics-informed neural networks to compute Lyapunov functions. We encode Lyapunov conditions as a partial differential equation (PDE) and use this for training neural network Lyapunov functions. We analyze the analytical properties of the solutions to the Lyapunov and Zubov PDEs. In particular, we show that employing the Zubov equation in training neural Lyapunov functions can lead to approximate regions of attraction close to the true domain of attraction. We also examine approximation errors and the convergence of neural approximations to the unique solution of Zubov's equation. We then provide sufficient conditions for the learned neural Lyapunov functions that can be readily verified by satisfiability modulo theories (SMT) solvers, enabling formal verification of both local stability analysis and region-of-attraction estimates in the large. Through a number of nonlinear examples, ranging from low to high dimensions, we demonstrate that the proposed framework can outperform traditional sums-of-squares (SOS) Lyapunov functions obtained using semidefinite programming (SDP).

Mohamed Serry, Haoyu Li, Ruikun Zhou et al.

Analysis of nonlinear autonomous systems typically involves estimating domains of attraction, which have been a topic of extensive research interest for decades. Despite that, accurately estimating domains of attraction for nonlinear systems remains a challenging task, where existing methods are conservative or limited to low-dimensional systems. The estimation becomes even more challenging when accounting for state constraints. In this work, we propose a framework to accurately estimate safe (state-constrained) domains of attraction for discrete-time autonomous nonlinear systems. In establishing this framework, we first derive a new Zubov equation, whose solution corresponds to the exact safe domain of attraction. The solution to the aforementioned Zubov equation is shown to be unique and continuous over the whole state space. We then present a physics-informed approach to approximating the solution of the Zubov equation using neural networks. To obtain certifiable estimates of the domain of attraction from the neural network approximate solutions, we propose a verification framework that can be implemented using standard verification tools (e.g., $α,\!β$-CROWN and dReal). To illustrate its effectiveness, we demonstrate our approach through numerical examples concerning nonlinear systems with state constraints.

Jun Liu

Convergence analysis of Nesterov's accelerated gradient method has attracted significant attention over the past decades. While extensive work has explored its theoretical properties and elucidated the intuition behind its acceleration, a simple and direct proof of its convergence rates is still lacking. We provide a concise Lyapunov analysis of the convergence rates of Nesterov's accelerated gradient method for both general convex and strongly convex functions.

Amartya Mukherjee, Thanin Quartz, Jun Liu

This paper presents a novel approach to generating stabilizing controllers for a large class of dynamical systems using diffusion models. The core objective is to develop stabilizing control functions by identifying the closest asymptotically stable vector field relative to a predetermined manifold and adjusting the control function based on this finding. To achieve this, we employ a diffusion model trained on pairs consisting of asymptotically stable vector fields and their corresponding Lyapunov functions. Our numerical results demonstrate that this pre-trained model can achieve stabilization over previously unseen systems efficiently and rapidly, showcasing the potential of our approach in fast zero-shot control and generalizability.

Jun Liu, Ryan K. Williams

In this paper, we formulate and solve the intermittent deployment problem, which yields strategies that couple \emph{when} heterogeneous robots should sense an environmental process, with where a deployed team should sense in the environment. As a motivation, suppose that a spatiotemporal process is slowly evolving and must be monitored by a multi-robot team, e.g., unmanned aerial vehicles monitoring pasturelands in a precision agriculture context. In such a case, an intermittent deployment strategy is necessary as persistent deployment or monitoring is not cost-efficient for a slowly evolving process. At the same time, the problem of where to sense once deployed must be solved as process observations yield useful feedback for determining effective future deployment and monitoring decisions. In this context, we model the environmental process to be monitored as a spatiotemporal Gaussian process with mutual information as a criterion to measure our understanding of the environment. To make the sensing resource-efficient, we demonstrate how to use matroid constraints to impose a diverse set of homogeneous and heterogeneous constraints. In addition, to reflect the cost-sensitive nature of real-world applications, we apply budgets on the cost of deployed heterogeneous robot teams. To solve the resulting problem, we exploit the theories of submodular optimization and matroids and present a greedy algorithm with bounds on sub-optimality. Finally, Monte Carlo simulations demonstrate the correctness of the proposed method.

Ye Zhao, Yinan Li, Luis Sentis et al.

Contact-based decision and planning methods are becoming increasingly important to endow higher levels of autonomy for legged robots. Formal synthesis methods derived from symbolic systems have great potential for reasoning about high-level locomotion decisions and achieving complex maneuvering behaviors with correctness guarantees. This study takes a first step toward formally devising an architecture composed of task planning and control of whole-body dynamic locomotion behaviors in constrained and dynamically changing environments. At the high level, we formulate a two-player temporal logic game between the multi-limb locomotion planner and its dynamic environment to synthesize a winning strategy that delivers symbolic locomotion actions. These locomotion actions satisfy the desired high-level task specifications expressed in a fragment of temporal logic. Those actions are sent to a robust finite transition system that synthesizes a locomotion controller that fulfills state reachability constraints. This controller is further executed via a low-level motion planner that generates feasible locomotion trajectories. We construct a set of dynamic locomotion models for legged robots to serve as a template library for handling diverse environmental events. We devise a replanning strategy that takes into consideration sudden environmental changes or large state disturbances to increase the robustness of the resulting locomotion behaviors. We formally prove the correctness of the layered locomotion framework guaranteeing a robust implementation by the motion planning layer. Simulations of reactive locomotion behaviors in diverse environments indicate that our framework has the potential to serve as a theoretical foundation for intelligent locomotion behaviors.

Yinan Li, Jun Liu

This paper focuses on the invariance control problem for discrete-time switched nonlinear systems. The proposed approach computes controlled invariant sets in a finite number of iterations and directly yields a partition-based invariance controller using the information recorded during the computation. In contrast with Lyapunov-based control methods, this method does not require the subsystems to have common equilibrium points. Algorithms are developed for computing both outer and inner approximations of the maximal controlled invariant sets, which are represented as finite unions of intervals. The general convergence results of interval methods allow us to obtain arbitrarily precise approximations without any stability assumptions. In addition, invariant inner approximations can be computed provided that the switched system satisfies a robustly controlled invariance condition. Under the same condition, we also prove the existence of an invariance controller based on partitions of the state space. Our method is illustrated with three examples drawn from different applications and compared with existing work in the literature.

Yinan Li, Jun Liu, Necmiye Ozay

This paper proposes a method to compute finite abstractions that can be used for synthesizing robust hybrid control strategies for nonlinear systems. Most existing methods for computing finite abstractions utilize some global, analytical function to provide bounds on the reachable sets of nonlinear systems, which can be conservative and lead to spurious transitions in the abstract systems. This problem is even more pronounced in the presence of imperfect measurements and modelling uncertainties, where control synthesis can easily become infeasible due to added spurious transitions. To mitigate this problem, we propose to compute finite abstractions with robustness margins by over-approximating the local reachable sets of nonlinear systems. We do so by linearizing the nonlinear dynamics into linear affine systems and keeping track of the linearization error. It is shown that this approach provides tighter approximations and several numerical examples are used to illustrate of effectiveness of the proposed methods.

Jun Liu, Andrew R. Teel

Hybrid systems with memory are dynamical systems exhibiting both hybrid and delay phenomena. In this note, we study the asymptotic stability of hybrid systems with memory using generalized concepts of solutions. These generalized solutions, motivated by studying robustness and well-posedness of such systems, are defined on hybrid time domains and parameterized by both continuous and discrete time. We establish Lyapunov-based sufficient conditions for asymptotic stability using both Lyapunov-Razumikhin functions and Lyapunov-Krasovskii functionals. Examples are provided to illustrate these conditions.