When deploying autonomous agents in unstructured environments over sustained periods of time, adaptability and robustness oftentimes outweigh optimality as a primary consideration. In other words, safety and survivability constraints play a key role and in this paper, we present a novel, constraint-learning framework for control tasks built on the idea of constraints-driven control. However, since control policies that keep a dynamical agent within state constraints over infinite horizons are not always available, this work instead considers constraints that can be satisfied over a sufficiently long time horizon T > 0, which we refer to as limited-duration safety. Consequently, value function learning can be used as a tool to help us find limited-duration safe policies. We show that, in some applications, the existence of limited-duration safe policies is actually sufficient for long-duration autonomy. This idea is illustrated on a swarm of simulated robots that are tasked with covering a given area, but that sporadically need to abandon this task to charge batteries. We show how the battery-charging behavior naturally emerges as a result of the constraints. Additionally, using a cart-pole simulation environment, we show how a control policy can be efficiently transferred from the source task, balancing the pole, to the target task, moving the cart to one direction without letting the pole fall down.
On the other hand, control barrier functions (CBFs) @cite_45 @cite_17 @cite_1 @cite_8 @cite_46 @cite_43 @cite_12 @cite_15 @cite_32 @cite_7 were proposed to guarantee that an agent remains in a certain region of the state space (i.e., forward invariance @cite_42 ) by using a locally accurate model of the agent dynamics (i.e., a model that accurately predicts a time derivative of the state at the current state and control input). When the system is linearizable and has a high relative degree, an exponential control barrier function @cite_41 was proposed and was applied to control of quadrotors @cite_49 . When a Lyapunov function is available, the work @cite_14 proposed a sum-of-squares approach to compute a valid barrier function. The idea of constraints-driven controls is in stark contrast to solving the task-specific problem that basically aims at singling out one optimal trajectory. However, although there exist converse theorems for safety and barrier functions which claim that a forward invariant set has a barrier function under certain conditions @cite_29 @cite_21 @cite_46 , finding such a set without assuming stability of the system is difficult in general (see @cite_45 for the conditions that a candidate barrier function can be a valid one).
@cite_14 @cite_7 @cite_8 @cite_15 @cite_41 @cite_29 @cite_42 @cite_1 @cite_32 @cite_21 @cite_43 @cite_45 @cite_49 @cite_46 @cite_12 @cite_17
2560504659 2468433498 2889711700 2489231587 1937654348 2963995490 2031397756 2620840602 1970832114 2114578185 1972149633 2139386764 2296356821 2057133391 2042204128 1964927113
Safety critical systems involve the tight coupling between potentially conflicting control objectives and safety constraints. As a means of creating a formal framework for controlling systems of this form, and with a view toward automotive applications, this paper develops a methodology that allows safety conditions—expressed as control barrier functions —to be unified with performance objectives—expressed as control Lyapunov functions—in the context of real-time optimization-based controllers. Safety conditions are specified in terms of forward invariance of a set, and are verified via two novel generalizations of barrier functions; in each case, the existence of a barrier function satisfying Lyapunov-like conditions implies forward invariance of the set, and the relationship between these two classes of barrier functions is characterized. In addition, each of these formulations yields a notion of control barrier function (CBF), providing inequality constraints in the control input that, when satisfied, again imply forward invariance of the set. Through these constructions, CBFs can naturally be unified with control Lyapunov functions (CLFs) in the context of a quadratic program (QP); this allows for the achievement of control objectives (represented by CLFs) subject to conditions on the admissible states of the system (represented by CBFs). The mediation of safety and performance through a QP is demonstrated on adaptive cruise control and lane keeping, two automotive control problems that present both safety and performance considerations coupled with actuator bounds. Abstract Barrier functions (also called certificates) have been an important tool for the verification of hybrid systems, and have also played important roles in optimization and multi-objective control. The extension of a barrier function to a controlled system results in a control barrier function. This can be thought of as being analogous to how Sontag extended Lyapunov functions to control Lypaunov functions in order to enable controller synthesis for stabilization tasks. A control barrier function enables controller synthesis for safety requirements specified by forward invariance of a set using a Lyapunov-like condition. This paper develops several important extensions to the notion of a control barrier function. The first involves robustness under perturbations to the vector field defining the system. Input-to-State stability conditions are given that provide for forward invariance, when disturbances are present, of a “relaxation” of set rendered invariant without disturbances. A control barrier function can be combined with a control Lyapunov function in a quadratic program to achieve a control objective subject to safety guarantees. The second result of the paper gives conditions for the control law obtained by solving the quadratic program to be Lipschitz continuous and therefore to gives rise to well-defined solutions of the resulting closed-loop system. This paper presents a safe learning framework that employs an adaptive model learning method together with barrier certificates for systems with possibly nonstationary agent dynamics. To extract the dynamic structure of the model, we use a sparse optimization technique, and the resulting model will be used in combination with control barrier certificates which constrain policies (feedback controllers) in order to maintain safety, which refers to avoiding certain regions of the state space. Under certain conditions, recovery of safety in the sense of Lyapunov stability after violations of safety due to the nonstationarity is guaranteed. In addition, we reformulate action-value function approximation to make any kernel-based nonlinear function estimation method applicable to our adaptive learning framework. Lastly, solutions to the barrier-certified policy optimization are guaranteed to be globally optimal, ensuring greedy policy updates under mild conditions. The resulting framework is validated via simulations of a quadrotor, which has been used in the safe learnings literature under stationarity assumption, and then tested on a real robot called brushbot , whose dynamics is unknown, highly complex, and most probably nonstationary. We introduce Exponential Control Barrier Functions as means to enforce strict state-dependent high relative degree safety constraints for nonlinear systems. We also develop a systematic design method that enables creating the Exponential CBFs for nonlinear systems making use of tools from linear control theory. The proposed control design is numerically validated on a relative degree 6 linear system (the serial cart-spring system) and on a relative degree 4 nonlinear system (the two-link pendulum with elastic actuators.) The thesis describes a new method for obtaining minimizers for optimal control problems whose minima serve as control policies for guiding nonlinear dynamical systems to achieve prescribed goals under imposed trajectory and actuator constraints. One of the major contributions of the present work resides in the approximation of such minimizers by piecewise polynomial functions expressed in terms of a linear combination of non-uniform rational B-spline (NURBS) basis functions and the judicious exploitation of the properties of the resulting NURBS curves to improve the computational effort often associated with solving optimal control problems for constrained dynamical systems. In particular, by exploiting the two structures combined in a NURBS curve, NURBS basis functions and an associated union of overlapping polytopes constructed from the coefficients of the linear combination, we are able to separate an optimal control problem into two subproblems | guidance and obstacle avoidance, making the original problem tractable. This is accomplished by laying out the union of overlapping polytopes in such a way that they delineate a section of space that avoids all obstacles and then manipulating the NURBS basis functions to obtain trajectories that are guaranteed to remain bounded by this section of space without explicitly including the conjunction of disjunctions naturally induced from obstacles into the guidance problem. In addition, we show how one can construct systematically a feasible region that corresponds to a NURBS parameterization starting from an ordered union of pairwise adjacently overlapping nonempty compact convex sets. Specifically, we show how to setup a nonlinear programming problem to solve for the feasible region in terms of an ordered union of pairwise adjacently overlapping polytopes with nonempty interiors by maximizing the sum of their volumes and starting from a feasible region described by an ordered union of pairwise adjacently overlapping nonempty convex compact simi-algebraic sets. Finally, we show how this strategy can be implemented practically for an autonomous system traversing an urban environment. Finally, this work culminated in the filing of patent US20070179685 on behalf of Northrop Grumman for the Space Technology sector and in the development of the NURBS-based OTG software package. This C++ package contains the theoretical results of this thesis in the form of an object-oriented implementation optimized for real-time trajectory generation. Motivated by the need to simultaneously guarantee safety and stability of safety-critical dynamical systems, we construct permissive barrier certificates in this paper that explicitly maximize the region where the system can be stabilized without violating safety constraints. An iterative search algorithm is developed to search for the maximum volume barrier certified region of safe stabilization. The barrier certified region, which is allowed to take any arbitrary shape, is proved to be strictly larger than safe regions generated with Lyapunov sublevel set based methods. The proposed approach effectively unites a Lyapunov function with multiple barrier functions that might not be compatible with each other. Simulation results of the iterative search algorithm demonstrate the effectiveness of the proposed method. This paper examines techniques for finding falsifying trajectories of hybrid systems using an approach that we call trajectory splicing. Many formal verification techniques for hybrid systems, including flowpipe construction, can identify plausible abstract counterexamples for property violations. However, there is often a gap between the reported abstract counterexamples and the concrete system trajectories. Our approach starts with a candidate sequence of disconnected trajectory segments, each segment lying inside a discrete mode. However, such disconnected segments do not form concrete violations due to the gaps that exist between the ending state of one segment and the starting state of the subsequent segment. Therefore, trajectory splicing uses local optimization to minimize the gap between these segments, effectively splicing them together to form a concrete trajectory. We demonstrate the use of our approach for falsifying safety properties of hybrid systems using standard optimization techniques. As such, our approach is not restricted to linear systems. We compare our approach with other falsification approaches including uniform random sampling and a robustness guided falsification approach used in the tool S-Taliro. Our preliminary evaluation clearly shows the potential of our approach to search for candidate trajectory segments and use them to find concrete property violations. As multi-agent systems become more wide-spread and versatile, the ability to satisfy multiple system-level constraints grows increasingly important. In applications ranging from automated cruise control to safety in robot swarms, barrier functions have emerged as a tool to provably meet such constraints by guaranteeing forward invariance of desirable sets. However, satisfying multiple constraints typically implies formulating multiple barrier functions, which would be ameliorated if the barrier functions could be composed together as Boolean logic formulas. The use of max and min operators, which yields nonsmooth functions, represents one path to accomplish Boolean compositions of barrier functions, and this letter extends previously established concepts for barrier functions to a class of nonsmooth barrier functions that operate on systems described by differential inclusions. We validate our results by deploying Boolean compositions of nonsmooth barrier functions onto a team of mobile robots. The concept of a robust control Lyapunov function ( rclf ) is introduced, and it is shown that the existence of an rclf for a control-affine system is equivalent to robust stabilizability via continuous state feedback. This extends Artstein's theorem on nonlinear stabilizability to systems with disturbances. It is then shown that every rclf satisfies the steady-state Hamilton--Jacobi--Isaacs (HJI) equation associated with a meaningful game and that every member of a class of pointwise min-norm control laws is optimal for such a game. These control laws have desirable properties of optimality and can be computed directly from the rclf without solving the HJI equation for the upper value function. In this paper, we focus on a particular class of nonlinear affine control systems of the form xdot=f(x)+Bu, where the drift f is a multi-affine vector field (i.e., affine in each state component), the control distribution B is constant, and the control u is constrained to a convex set. For such a system, we first derive necessary and sufficient conditions for the existence of a multiaffine feedback control law keeping the system in a rectangular invariant. We then derive sufficient conditions for driving all initial states in a rectangle through a desired facet in finite time. If the control constraints are polyhedral, we show that all these conditions translate to checking the feasibility of systems of linear inequalities to be satisfied by the control at the vertices of the state rectangle. This work is motivated by the need to construct discrete abstractions for continuous and hybrid systems, in which analysis and control tasks specified in terms of reachability of sets of states can be reduced to searches on finite graphs. We show the application of our results to the problem of controlling the angular velocity of an aircraft with gas jet actuators Abstract This paper presents a new safety feedback design for nonlinear systems based on barrier certificates and the idea of control Lyapunov functions. In contrast to existing methods, this approach ensures safety independently of abstract high-level tasks that might be unknown or change over time. Leaving as much freedom as possible to the safe system, the authors believe that the flexibility of this approach is very promising. The design is validated using an illustrative example. This paper builds upon the scalable admission control schemes for CDMA networks developed in F. (2003, December 2004). These schemes are based on an exact representation of the geometry of both the downlink and the uplink channels and ensure that the associated power allocation problems have solutions under constraints on the maximal power of each station user. These schemes are decentralized in that they can be implemented in such a way that each base station only has to consider the load brought by its own users to decide on admission. By load we mean here some function of the configuration of the users and of their bit rates that is described in the paper. When implemented in each base station, such schemes ensure the global feasibility of the power allocation even in a very large (infinite number of cells) network. The estimation of the capacity of large CDMA networks controlled by such schemes was made in these references. In certain cases, for example for a Poisson pattern of mobiles in an hexagonal network of base stations, this approach gives explicit formulas for the infeasibility probability, defined as the fraction of cells where the population of users cannot be entirely admitted by the base station. In the present paper we show that the notion of infeasibility probability is closely related to the notion of blocking probability, defined as the fraction of users that are rejected by the admission control policy in the long run, a notion of central practical importance within this setting. The relation between these two notions is not bound to our particular admission control schemes, but is of more general nature, and in a simplified scenario it can be identified with the well-known Erlang loss formula. We prove this relation using a general spatial birth-and-death process, where customer locations are represented by a spatial point process that evolves over time as users arrive or depart. This allows our model to include the exact representation of the geometry of inter-cell and intra-cell interferences, which play an essential role in the load indicators used in these cellular network admission control schemes. Recent advances in the direct computation of Lyapunov functions using convex optimization make it possible to efficiently evaluate regions of stability for smooth nonlinear systems. Here we present a feedback motion planning algorithm which uses these results to efficiently combine locally-valid linear quadratic regulator (LQR) controllers into a nonlinear feedback policy which probabilistically covers the reachable area of a (bounded) state space with a region of stability, certifying that all initial conditions that are capable of reaching the goal will stabilize to the goal. We carefully investigate the algorithm on a two-dimensional model system and discuss the potential for the control of more complicated underactuated control problems like bipedal walking. In this paper we consider some aspects of the problem of feedback control of a time-invariant uncertain system subject to state constraints over an infinite-time interval. The central question that we investigate is under what conditions can the state of the uncertain system be forced to stay in a specified region of the state space for all times by using feedback control. At the same time we study the behavior of the region of n -step reachability as n tends to infinity. It is shown that in general this region may exhibit instability as we pass to the limit, and that under a compactness assumption this region converges to a steady state. A special case involving a linear finite-dimensional system is examined in more detail. It is shown that there exist ellipsoidal regions in state space where the state can be confined by making use of a linear time-invariant control law, provided that the system is stabilizable. Such control laws can be calculated efficiently through the solution of a recursive matrix equation of the Riccati type. We present an algorithm that probabilistically covers a bounded region of the state space of a nonlinear system with a sparse tree of feedback stabilized trajectories leading to a goal state. The generated tree serves as a lookup table control policy to get any reachable initial condition within that region to the goal. The approach combines motion planning with reasoning about the set of states around a trajectory for which the feedback policy of the trajectory is able to stabilize the system. The key idea is to use a random sample from the bounded region for both motion planning and approximation of the stabilizable sets by falsification; this keeps the number of samples and simulations needed to generate covering policies reasonably low. We simulate the nonlinear system to falsify the stabilizable sets, which allows enforcing input and state constraints. Compared to the algebraic verification using sums of squares optimization in our previous work, the simulation-based approximation of the stabilizable set is less exact, but considerably easier to implement and can be applied to a broader range of nonlinear systems. We show simulation results obtained with model systems and study the performance and robustness of the generated policies. This paper develops the application of the alternating direction method of multipliers (ADMM) to optimize a dynamic objective function in a decentralized multi-agent system. At each time slot, agents in the network observe local functions and cooperate to track the optimal time-varying argument of the sum objective. This cooperation is based on maintaining local primal variables that estimate the value of the optimal argument and auxiliary dual variables that encourage proximity with neighboring estimates. Primal and dual variables are updated by an ADMM iteration that can be implemented in a distributed manner whereby local updates require access to local variables and the most recent primal variables from adjacent agents. For objective functions that are strongly convex and have Lipschitz continuous gradients, the distances between the primal and dual iterates to their corresponding time-varying optimal values are shown to converge to a steady state gap. This gap is explicitly characterized in terms of the condition number of the objective function, the condition number of the network that is defined as the ratio between the largest and smallest nonzero Laplacian eigenvalues, and a bound on the drifts of the optimal primal variables and the optimal gradients. Numerical experiments corroborate theoretical findings and show that the results also hold for non-differentiable and non-strongly convex primal objectives.