Search

In this paper, we propose a quadratic programming-based filter for safe and stable controller design, via a Control Barrier Function (CBF) and a Control Lyapunov Function (CLF). Our method guarantees safety and local asymptotic stability without the need for an asymptotically stabilizing control law. Feasibility of the proposed program is ensured under a mild regularity condition, termed relaxed compatibility between the CLF and CBF. The resulting optimal control law is guaranteed to be locally Lipschitz continuous. We also analyze the closed-loop behaviour by characterizing the equilibrium points, and verifying that there are no equilibrium points in the interior of the control invariant set except at the origin. For a polynomial system and a semi-algebraic safe set, we provide a sum-of-squares program to design a relaxed compatible pair of CLF and CBF. The proposed approach is compared with other methods in the literature using numerical examples, exhibits superior filter performance and guarantees safety and local stability.

This paper proposes a data-driven approach to design a feedforward Neural Network (NN) controller with a stability guarantee for systems with unknown dynamics. We first introduce data-driven representations of stability conditions for Neural Feedback Loops (NFLs) with linear plants. These conditions are then formulated into a semidefinite program (SDP). Subsequently, this SDP constraint is integrated into the NN training process resulting in a stable NN controller. We propose an iterative algorithm to solve this problem efficiently. Finally, we illustrate the effectiveness of the proposed method and its superiority compared to model-based methods via numerical examples.

We study the problem of co-designing control barrier functions (CBF) and linear state feedback controllers for continuous-time linear systems. We achieve this by means of a single semi-definite optimization program. Our formulation can handle mixed-relative degree problems without requiring an explicit safe controller. Different L-norm based input limitations can be introduced as convex constraints in the proposed program. We demonstrate our results on an omni-directional car numerical example., Comment: manuscript submitted to TAC

Reinforcement learning (RL) excels in applications such as video games, but ensuring safety as well as the ability to achieve the specified goals remains challenging when using RL for real-world problems, such as human-aligned tasks where human safety is paramount. This paper provides safety and stability definitions for such human-aligned tasks, and then proposes an algorithm that leverages neural ordinary differential equations (NODEs) to predict human and robot movements and integrates the control barrier function (CBF) and control Lyapunov function (CLF) with the actor-critic method to help to maintain the safety and stability for human-aligned tasks. Simulation results show that the algorithm helps the controlled robot to reach the desired goal state with fewer safety violations and better sample efficiency compared to other methods in a human-aligned task., Comment: Accepted at the Workshop on Human-aligned Reinforcement Learning for Autonomous Agents and Robots at ICRA 2024

The Forward-Forward (FF) Algorithm has been recently proposed to alleviate the issues of backpropagation (BP) commonly used to train deep neural networks. However, its current formulation exhibits limitations such as the generation of negative data, slower convergence, and inadequate performance on complex tasks. In this paper, we take the main ideas of FF and improve them by leveraging channel-wise competitive learning in the context of convolutional neural networks for image classification tasks. A layer-wise loss function is introduced that promotes competitive learning and eliminates the need for negative data construction. To enhance both the learning of compositional features and feature space partitioning, a channel-wise feature separator and extractor block is proposed that complements the competitive learning process. Our method outperforms recent FF-based models on image classification tasks, achieving testing errors of 0.58%, 7.69%, 21.89%, and 48.77% on MNIST, Fashion-MNIST, CIFAR-10 and CIFAR-100 respectively. Our approach bridges the performance gap between FF learning and BP methods, indicating the potential of our proposed approach to learn useful representations in a layer-wise modular fashion, enabling more efficient and flexible learning., Comment: To be published in AAAI 2024, 11 pages, 7 figures

Neural network controllers have shown potential in achieving superior performance in feedback control systems. Although a neural network can be trained efficiently using deep and reinforcement learning methods, providing formal guarantees for the closed-loop properties is challenging. The main difficulty comes from the nonlinear activation functions. One popular method is to use sector bounds on the activation functions resulting in a robust analysis. These methods work well under the assumption that the system dynamics are perfectly known, which is, however, impossible in practice. In this paper, we propose data-driven semi-definite programs to formally verify stability and safety for a neural network controlled linear system with unknown dynamics. The proposed method performs verification directly from end-to-end without identifying the dynamics. Through a numerical example, we validate the efficacy of our method on linear systems with controller trained by imitation learning., Comment: submitted to L4DC 2024

This paper proposes a (control) barrier function synthesis and safety verification scheme for interconnected nonlinear systems based on assume-guarantee contracts (AGC) and sum-of-squares (SOS) techniques. It is well-known that the SOS approach does not scale well for barrier function synthesis for high-dimensional systems. In this paper, we show that compositional methods like AGC can mitigate this problem. We formulate the synthesis problem into a set of small-size problems, which constructs local contracts for subsystems, and propose a negotiation scheme among the subsystems at the contract level. The proposed scheme is then implemented numerically on two examples: vehicle platooning and room temperature regulation.

Neural networks have shown great success in many machine learning related tasks, due to their ability to act as general function approximators. Recent work has demonstrated the effectiveness of neural networks in control systems (known as neural feedback loops), most notably by using a neural network as a controller. However, one of the big challenges of this approach is that neural networks have been shown to be sensitive to adversarial attacks. This means that, unless they are designed properly, they are not an ideal candidate for controllers due to issues with robustness and uncertainty, which are pivotal aspects of control systems. There has been initial work on robustness to both analyse and design dynamical systems with neural network controllers. However, one prominent issue with these methods is that they use existing neural network architectures tailored for traditional machine learning tasks. These structures may not be appropriate for neural network controllers and it is important to consider alternative architectures. This paper considers rational neural networks and presents novel rational activation functions, which can be used effectively in robustness problems for neural feedback loops. Rational activation functions are replaced by a general rational neural network structure, which is convex in the neural network's parameters. A method is proposed to recover a stabilising controller from a Sum of Squares feasibility test. This approach is then applied to a refined rational neural network which is more compatible with Sum of Squares programming. Numerical examples show that this method can successfully recover stabilising rational neural network controllers for neural feedback loops with non-linear plants with noise and parametric uncertainty., Comment: 20 Pages, 12 Figures

Reinforcement learning (RL) has demonstrated impressive performance in various areas such as video games and robotics. However, ensuring safety and stability, which are two critical properties from a control perspective, remains a significant challenge when using RL to control real-world systems. In this paper, we first provide definitions of safety and stability for the RL system, and then combine the control barrier function (CBF) and control Lyapunov function (CLF) methods with the actor-critic method in RL to propose a Barrier-Lyapunov Actor-Critic (BLAC) framework which helps maintain the aforementioned safety and stability for the system. In this framework, CBF constraints for safety and CLF constraint for stability are constructed based on the data sampled from the replay buffer, and the augmented Lagrangian method is used to update the parameters of the RL-based controller. Furthermore, an additional backup controller is introduced in case the RL-based controller cannot provide valid control signals when safety and stability constraints cannot be satisfied simultaneously. Simulation results show that this framework yields a controller that can help the system approach the desired state and cause fewer violations of safety constraints compared to baseline algorithms., Comment: Accepted by IEEE CDC 2023

We propose distributed iterative algorithms for safe control design and safety verification for networked multi-agent systems. These algorithms rely on distributing a control barrier function (CBF) related quadratic programming (QP) problem. The proposed distributed algorithm addresses infeasibility issues of existing schemes by dynamically allocating auxiliary variables across iterations. The resulting control input is guaranteed to be optimal, and renders the system safe. Furthermore, a truncated algorithm is proposed to facilitate computational implementation. The performance of the truncated algorithm is evaluated using a distributed safety verification algorithm. The algorithm quantifies safety for a multi-agent system probabilistically, using a certain locally Lipschitz continuous feedback controller by means of CBFs. Both upper and lower bounds on the probability of safety are obtained using the so called scenario approach. Both the scenario sampling and safety verification procedures are fully distributed. The efficacy of our algorithms is demonstrated by an example on multi-robot collision avoidance., Comment: manuscript submitted to Automatica

A numerical framework for the 'real-time' estimation of the infection risk from airborne diseases (e.g., SARS-CoV-2) in indoor spaces such as hospitals, restaurants, cinemas or teaching rooms is proposed. The developed model is based on the use of computational fluid dynamics as a pre-processor to obtain the time-averaged ventilation pattern inside a room, and a post-processing tool for the computation of the dispersion of sprays and aerosols emitted by its occupants in 'real time'. The model can predict the dispersion and concentration of droplets carrying viable viral copies in the air, the contamination of surfaces, and the related spatially-resolved infection risk. It may therefore provide useful information for the management of indoor environments in terms of, e.g., maximum occupancy, air changes per hour and cleaning of surfaces. This work describes the fundamentals of the model and its main characteristics. The model was developed using open-source software and is conceived to be simple, user-friendly and highly automated to enable any potential user to perform estimations of the local infection risk., Comment: for associated video, see https://www.linkedin.com/posts/danielfredrich_we-have-developed-sprei-an-easy-to-use-computational-activity-6865360164510404608-ORyU?utm_source=share&utm_medium=member_desktop

Safety is closely related to set invariance for dynamical systems. However, synthesizing a safe invariant set and at the same time synthesizing the associated safe controller still remains challenging. In this note we introduce a simple invariance-based method for linear systems with safety guarantee. The proposed method uses sum-of-squares programming., Comment: submitted to POEMA as an extended abstract

The existence of multiple irregular obstacles in the environment introduces nonconvex constraints into the optimization for motion planning, which makes the optimal control problem hard to handle. One efficient approach to address this issue is Successive Convex Approximation (SCA), where the nonconvex problem is convexified and solved successively. However, this approach still faces two main challenges: I) infeasibility, caused by linearisation about infeasible reference points; ii) high computational complexity incurred by multiple constraints, when solving the optimal control problem with a long planning horizon and multiple obstacles. To overcome these challanges, this paper proposes an energy efficient safetyaware control method for motion planning with low computing complexity and address these challenges. Specifically, a control barrier function-based linear quadratic regulator is formulated for the motion planning to guarantee safety and energy efficiency. Then, to avoid infeasibility, Backward Receding SCA (BRSCA) approach with a dynamic constraints-selection rule is proposed. Dynamic programming with primal-dual iteration is designed to decrease computational complexity. It is found that BRSCA is applicable to time-varying control limits. Numerical simulations and hardware experiments vevify the efficiency of BRSCA. Simulations demonstrates that BRSCA has a higher probability of finding feasible solutions, reduces the computation time by about 17.4% and the energy cost by about four times compared to other methods in the literature.

The task assignment problem is fundamental in combinatorial optimisation, aiming at allocating one or more tasks to a number of agents while minimizing the total cost or maximizing the overall assignment benefit. This problem is known to be computationally hard since it is usually formulated as a mixed-integer programming problem. In this paper, we consider a novel time-triggered dimension reduction algorithm (TTDRA). We propose convexification approaches to convexify both the constraints and the cost function for the general non-convex assignment problem. The computational speed is accelerated via our time-triggered dimension reduction scheme, where the triggering condition is designed based on the optimality tolerance and the convexity of the cost function. Optimality and computational efficiency are verified via numerical simulations on benchmark examples.

In this paper we consider the safety verification and safe controller synthesis problems for nonlinear control systems. The Control Barrier Certificates (CBC) approach is proposed as an extension to the Barrier certificates approach. Our approach can be used to characterize the control invariance of a given set in terms of safety of a general nonlinear control system subject to input constraints. From the point of view of controller design, the proposed method provides an approach to synthesize a safe control law that guarantees that the trajectories of the system starting from a given initial set do not enter an unsafe set. Unlike the related control Barrier functions approach, our formulation only considers the vector field within the tangent cone of the zero level set defined by the certificates, and is shown to be less conservative by means of numerical evidence. For polynomial systems with semi-algebraic initial and safe sets, CBCs and safe control laws can be synthesized using sum-of-squares decomposition and semi-definite programming. Examples demonstrate our method.

The control Barrier function approach has been widely used for safe controller synthesis. By solving an online convex quadratic programming problem, an optimal safe controller can be synthesized implicitly in state-space. Since the solution is unique, the mapping from state-space to control inputs is injective, thus enabling us to evaluate the underlying relationship. In this paper we aim at explicitly synthesizing a safe control law as a function of the state for nonlinear control-affine systems with limited control ability. We propose to transform the online quadratic programming problem into an offline parameterized optimisation problem which considers states as parameters. The obtained explicit safe controller is shown to be a piece-wise Lipschitz continuous function over the partitioned state space if the program is feasible. We address the infeasible cases by solving a parameterized adaptive control Barrier function-based quadratic programming problem. Extensive simulation results show the state-space partition and the controller properties.

Neural network controllers have the potential to improve the performance of feedback systems compared to traditional controllers, due to their ability to act as general function approximators. However, quantifying their safety and robustness properties has proven challenging due to the non-linearities of the activation functions inside the neural network. A key robustness indicator is certifying the stability properties of the feedback system and providing a region of attraction, which has been addressed in previous literature. However, these works only address linear systems or require one to abstract the plant non-linearities and bound them using slope and sector constraints. In this paper we use a Sum of Squares programming framework to compute the stability of non-linear systems with neural network controllers directly. Within this framework, we can propose higher order candidate Lyapunov functions with richer structures that are able to better capture the dynamics of the non-linear system and the nonlinearities in the neural network. We are also able to analyse these systems in continuous time, whereas other methods rely on discretising the system. These higher order Lyapunov functions are used in conjunction with higher order multipliers on the inequality and equality constraints that bound the neural network input-output properties. The volume of the region of attraction computed is increased compared to other methods, allowing for better safety guarantees on the stability of the system. We are also able to easily analyse non-linear polynomial systems, which is not possible to do with other methods. We are also able to conduct robustness analysis on the parameter uncertainty. We show the benefits of our method using numerical examples., Comment: 8 pages, 4 figures, submitted to CDC 2022

The prevalence of neural networks in society is expanding at an increasing rate. It is becoming clear that providing robust guarantees on systems that use neural networks is very important, especially in safety-critical applications. A trained neural network's sensitivity to adversarial attacks is one of its greatest shortcomings. To provide robust guarantees, one popular method that has seen success is to bound the activation functions using equality and inequality constraints. However, there are numerous ways to form these bounds, providing a trade-off between conservativeness and complexity. Depending on the complexity of these bounds, the computational time of the optimisation problem varies, with longer solve times often leading to tighter bounds. We approach the problem from a different perspective, using sparse polynomial optimisation theory and the Positivstellensatz, which derives from the field of real algebraic geometry. The former exploits the natural cascading structure of the neural network using ideas from chordal sparsity while the later asserts the emptiness of a semi-algebraic set with a nested family of tests of non-decreasing accuracy to provide tight bounds. We show that bounds can be tightened significantly, whilst the computational time remains reasonable. We compare the solve times of different solvers and show how the accuracy can be improved at the expense of increased computation time. We show that by using this sparse polynomial framework the solve time and accuracy can be improved over other methods for neural network verification with ReLU, sigmoid and tanh activation functions., Comment: 25 pages, 20 figures

Autonomous vehicles increasingly rely on cameras to provide the input for perception and scene understanding and the ability of these models to classify their environment and objects, under adverse conditions and image noise is crucial. When the input is, either unintentionally or through targeted attacks, deteriorated, the reliability of autonomous vehicle is compromised. In order to mitigate such phenomena, we propose DriveGuard, a lightweight spatio-temporal autoencoder, as a solution to robustify the image segmentation process for autonomous vehicles. By first processing camera images with DriveGuard, we offer a more universal solution than having to re-train each perception model with noisy input. We explore the space of different autoencoder architectures and evaluate them on a diverse dataset created with real and synthetic images demonstrating that by exploiting spatio-temporal information combined with multi-component loss we significantly increase robustness against adverse image effects reaching within 5-6% of that of the original model on clean images., Comment: 2021 IEEE Winter Conference on Applications of Computer Vision Workshops (WACVW)

Chordal and factor-width decomposition methods for semidefinite programming and polynomial optimization have recently enabled the analysis and control of large-scale linear systems and medium-scale nonlinear systems. Chordal decomposition exploits the sparsity of semidefinite matrices in a semidefinite program (SDP), in order to formulate an equivalent SDP with smaller semidefinite constraints that can be solved more efficiently. Factor-width decompositions, instead, relax or strengthen SDPs with dense semidefinite matrices into more tractable problems, trading feasibility or optimality for lower computational complexity. This article reviews recent advances in large-scale semidefinite and polynomial optimization enabled by these two types of decomposition, highlighting connections and differences between them. We also demonstrate that chordal and factor-width decompositions allow for significant computational savings on a range of classical problems from control theory, and on more recent problems from machine learning. Finally, we outline possible directions for future research that have the potential to facilitate the efficient optimization-based study of increasingly complex large-scale dynamical systems., Comment: 49 pages, 21 figures, 4 tables

We revisit the so-called sampling and discarding approach used to quantify the probability of constraint violation of a solution to convex scenario programs when some of the original samples are allowed to be discarded. Motivated by two scenario programs that possess analytic solutions and the fact that the existing bound for scenario programs with discarded constraints is not tight, we analyze a removal scheme that consists of a cascade of optimization problems, where at each step we remove a superset of the active constraints. By relying on results from compression learning theory, we show that such a removal scheme leads to less conservative bounds for the probability of constraint violation than the existing ones. We also show that the proposed bound is tight by characterizing a class of optimization problems that achieves the given upper bound. The performance improvement of the proposed methodology is illustrated by an example that involves a resource sharing linear program.

This paper presents a control reconfiguration approach to improve the performance of two classes of dynamical systems. Motivated by recent research on re-engineering cyber-physical systems, we propose a three-step control retrofit procedure. First, we reverse-engineer a dynamical system to dig out an optimization problem it actually solves. Second, we forward-engineer the system by applying a corresponding faster algorithm to solve this optimization problem. Finally, by comparing the original and accelerated dynamics, we obtain the implementation of the redesigned part (the extra dynamics). As a result, the convergence rate/speed or transient behavior of the given system can be improved while the system control structure is maintained. Internet congestion control and distributed proportional-integral (PI) control, as applications in the two different classes of target systems, are used to show the effectiveness of the proposed approach., Comment: 20 pages, 3 figures

Semidefinite programs (SDPs) are standard convex problems that are frequently found in control and optimization applications. Interior-point methods can solve SDPs in polynomial time up to arbitrary accuracy, but scale poorly as the size of matrix variables and the number of constraints increases. To improve scalability, SDPs can be approximated with lower and upper bounds through the use of structured subsets (e.g., diagonally-dominant and scaled-diagonally dominant matrices). Meanwhile, any underlying sparsity or symmetry structure may be leveraged to form an equivalent SDP with smaller positive semidefinite constraints. In this paper, we present a notion of decomposed structured subsets}to approximate an SDP with structured subsets after an equivalent conversion. The lower/upper bounds found by approximation after conversion become tighter than the bounds obtained by approximating the original SDP directly. We apply decomposed structured subsets to semidefinite and sum-of-squares optimization problems with examples of H-infinity norm estimation and constrained polynomial optimization. An existing basis pursuit method is adapted into this framework to iteratively refine bounds., Comment: 23 pages, 10 figures, 9 tables

In this paper, we describe sufficient conditions when block-diagonal solutions to Lyapunov and $\mathcal{H}_{\infty}$ Riccati inequalities exist. In order to derive our results, we define a new type of comparison systems, which are positive and are computed using the state-space matrices of the original (possibly nonpositive) systems. Computing the comparison system involves only the calculation of $\mathcal{H}_{\infty}$ norms of its subsystems. We show that the stability of this comparison system implies the existence of block-diagonal solutions to Lyapunov and Riccati inequalities. Furthermore, our proof is constructive and the overall framework allows the computation of block-diagonal solutions to these matrix inequalities with linear algebra and linear programming. Numerical examples illustrate our theoretical results., Comment: This is an extended technical report. The main results have been accepted for publication as a technical note in the IEEE Transactions on Automatic Control