In this thesis we modified a sampling-based motion planning algorithm to improve sampling efficiency. First, we modify the RRT* motion planning algorithm with a local motion planner that guarantees collision-free state trajectories without explicitly checking for collision with obstacles. The control trajectories are generated by solving a sequence of quadratic programs with Control Barrier Functions (CBF) constraints. If the control trajectories satisfy the CBF constraints, the state trajectories are guaranteed to stay in the free subset of the state space. Second, we use a stochastic optimization algorithm to adapt the sampling density function of RRT* to increase the probability of sampling in promising regions in the configuration space. In our approach, we use the nonparametric generalized cross-entropy (GCE) method is used for importance sampling, where a subset of the sampled RRT* trajectories is incrementally exploited to adapt the density function. The modified algorithms, the Adaptive CBF-RRT* and the CBF-RRT*, are demonstrated with numerical examples using the unicycle dynamics. The Adaptive CBF-RRT* has been shown to yield paths with lower cost with fewer tree vertexes than the CBF-RRT*. / 2022-03-27T00:00:00Z

The rising levels of autonomy exhibited by complex cyber-physical systems have brought questions related to safety and adaptation to the forefront of the minds of controls and robotics engineers. Often, such autonomous systems are deemed to be safety-critical in the sense that failures during operation could significantly harm the system itself, other autonomous systems, or, in the worst-case, humans interacting with such a system. Complicating the design of control and decision-making algorithms for safety-critical systems is that they must cope with various degrees of uncertainty as they are deployed autonomously in increasingly real-world environments. These challenges motivate the use of learning-based techniques that can adapt to such uncertainties while adhering to safety-critical constraints. The main objective of this dissertation is to present a unified framework for the design of controllers that learn from data online with formal guarantees of safety. Rather than using a controller trained on an a priori dataset collected offline that is then statically deployed on a system, we are interested in using real-time data to continuously update the control policy online and cope with uncertainties that are challenging to characterize until deployment. We approach the problem of designing such learning-based control algorithms for safety-critical systems through the use of certificate functions, such as Control Lyapunov Functions (CLFs) and Control Barrier Functions (CBFs), from nonlinear control theory. To this end, we first discuss how modern data-driven techniques can be integrated into traditional adaptive control frameworks to develop classes of CLFs and CBFs that facilitate the design of both controllers and learning algorithms that guarantee, respectively, stability and safety by construction. Next, we shift from the problem of safe adaptive control to safe reinforcement learning where we demonstrate how similar ideas from adaptive control can be extended to safely learn the value functions of optimal control problems online using data from a single trajectory. Finally, we discuss an extension of the aforementioned approaches to richer control specifications given in the form of temporal logic formulas, which provide a formal way to express complex control objectives beyond that of stability and safety. / 2025-05-30T00:00:00Z

With the development and integration of cyber-physical and safety-critical systems, control systems are expected to achieve tasks that include logic rules, receptive decision-making, safety constraints, and so forth. For example, in a persistent surveillance application, an unmanned aerial vehicle might be required to "take photos of areas A and B infinitely often, always avoid unsafe region C, and return to the charging point when the battery level goes low." One possible design approach to achieve such complex specifications is automata-based planning using formal verification algorithms. Central to the existing formal verification of continuous-time systems is the notion of abstraction, which consists of partitioning the state space into cells, and then formulating a certain control problem on each cell. The control problem is characterized as finding a state feedback to make all the closed-loop trajectories starting from one cell reach and enter a consecutive cell in finite time without intruding any other cells. This essentially abstracts the continuous system into a finite-state transition graph. The complex specifications can thus be checked against the simple transition model using formal verification tools, which yields a sequence of cells to visit consecutively. While control algorithms have been developed in the literature for linear systems associated with a polytopic partitioning of the state space, the partitioning and control problem for systems on a curved space is a relatively unexplored research area. In this thesis, we consider $ SO (3) $ and $ \ mathbb {S} ^ 2 $, the two most commonly encountered manifolds in mechanical systems, and propose several approaches to address the partitioning and control problem that in principle could be generalized to other manifolds. Chapter 2 proposes a discretization scheme that consists of sampling point generation and cell construction. Each cell is constructed as a ball region around a sampling point with an identical radius. Uniformity measures for the sampling points are proposed. As a result, the $SO(3)$ manifold is discretized into interconnected cells whose union covers the whole space. A graph model is naturally built up based on the cell adjacency relations. This discretization method, in general, can be extended to any Riemannian manifold. To enable the cell transitions, two reference trajectories are constructed corresponding to the cell-level plan. We demonstrate the results by solving a constrained attitude maneuvering problem with arbitrary obstacle shapes. It is shown that the algorithm finds a feasible trajectory as long as it exists at that discretization level. In Chapter 3, the 2-sphere manifold is considered and discretized into spherical polytopes, an analog of convex polytopes in the Euclidean space. Moreover, with the gnomonic projection, we show that the spherical polytopes can be naturally mapped into Euclidean polytopes and the dynamics on the manifold locally transform to a simple linear system via feedback linearization. Based on this transformation, the control problems then can be solved in the Euclidean space, where many control schemes exist with safe cell transition guarantee. This method serves as a special case that solves the partition-and-control problem by transforming the states and dynamics on manifold to Euclidean space in local charts. In Chapter 4, we propose a notion of high-order barrier functions for general control affine systems to guarantee set forward invariance by checking their higher order derivatives. This notion provides a unified framework to constrain the transient behavior of the closed-loop trajectories, which is essential in the cell-transition control design. The asymptotic stability of the forward invariant set is also proved, which is highly favorable for robustness with respect to model perturbations. We revisit the cell transition problem in Chapter 2 and show that even with a simple stabilizing nominal controller, the proposed high-order barrier function framework provides satisfactory transient performance. / <p>QC 20201012</p>

Over the last decades, autonomous robots have been considered in a variety of applications such  as persistent monitoring, package delivery and cooperative transportation. These applications often require the satisfaction of a set of complex tasks that need to be possibly performed in a timely manner. For example, in search and rescue missions, UAVs are expected to cover a set of regions within predetermined time intervals in order to increase the probability of identifying the victims of an accident. Spatio-temporal tasks of this form can be easily expressed in Signal Temporal Logic (STL), a predicate language that allow us to formally introduce time-constrained tasks such as visit area A between 0 and 5 min or robot 1 should move in a formation with robot 2 until robot 1 reaches region B between 5 and 20 sec. Existing approaches in control under spatio-temporal tasks encode the STL constraints using mixed-integer expressions. In the majority of these works, receding horizon schemes are designed and long planning horizons are considered that depend on the temporal constraints of the STL tasks. As a result, the complexity of these problems may increase with the number of the tasks or the length of the time interval within which a STL task needs to be satisfied. Other approaches, consider a limited STL fragment and propose computationally efficient feedback controllers that ensure the satisfaction of the STL task with a minimum, desired robustness. Nevertheless, these approaches do not consider actuation limitations that are always present in real-world systems and thus, yield controllers of arbitrarily large magnitude.  In this thesis, we consider the control problem under spatio-temporal constraints for systems that are subject to actuation limitations. In the first part, receding horizon control schemes (RHS) are proposed that ensure the satisfaction or minimal violation of a given set of STL tasks. Contrary to existing approaches, the planning horizon of the RHS scheme can be chosen independent of the STL task and hence, arbitrarily small, given the initial feasibility of the problem. Combining the advantages of the RHS and feedback strategies, we encode the STL tasks using control barrier functions that are designed either online or offline and design controllers that aim at maximizing the robustness of the STL task. The recursive feasibility property of the framework is established and a lower bound on the violation of the STL formula is derived. In the next part, we consider a multi-agent system that is subject to a STL task whose satisfaction may involve a large number of agents in the team. Then, the goal is to decompose the global task into local ones the satisfaction of each one of which  depends only on a given sub-team of agents. The proposed decomposition method enables the design of decentralized controllers under local STL tasks avoiding unnecessary communication among agents.  In the last part of the thesis, the coordination problem of multiple platoons is considered and related tasks such as splitting, merging and distance maintenance are expressed as Signal Temporal Logic tasks. Then, feedback control techniques are employed ensuring the satisfaction the STL formula, or alternatively minimal violation in presence of actuation limitations. / De senaste ̊artiondena har autonoma robotar sett en rad nya användningsområden, såsom ̈overvakning, paketleverans och kooperativ transport. Dessa innebär ofta att en samling komplexa uppgifter måste lösas på kort tid. Inom Search and Rescue (SAR), till exempel, krävs att drönare hinner genomsöka vissa geografiska regioner inom givna tidsintervall. Detta för att ̈oka chansen att identifierade drabbade vid en olycka. Den här typen av uppgift i tid och rum (spatio-temporal) kan enkelt uttryckas med hjälp av Signal Temporal Logic (STL). STL ̈är ett språk som tillåter oss att på ett formellt sätt formulera tidsbegränsade uppgifter, såsom besök område A mellan o och 5 minuter, eller robot 1 ska röra sig i formationtillsammans med robot 2 till dess att robot 1 når område B mellan 5 och 20 sekunder. Nuvarande lösningar till styrproblem av spatio-temporal-typen kodar STL-begränsningar med hjälp av mixed-integer-uttryck. Majoriteten av lösningarna involverar receding-horizon-metoder med långa tidshorisonter som beror av tidsbegränsningarna i STL-uppgifterna. Detta leder till att problemens komplexitet ̈ökar med antalet deluppgifter inom och tiden för STL-uppgifterna. Andra lösningar bygger på restriktiva STL-fragment och beräkningsmässigt effektiva ̊aterkopplingsregulatorer som garanterar STL-begränsningarna med minimal önskad robusthet. Dessvärre tar dessa sällan hänsyn till fysiska begräsningar hos regulatorn och ger ofta godtyckligt stora styrsignaler. I den här licentiatuppsatsen behandlar vi styrproblem med begräsningar i rum och tid, samt den ovan nämnda typen av fysiska regulatorbegränsningar. I den första delen presenterar vi receding-horizon-metoder (RHS) som uppfyller kraven i STL-uppgifter, eller minimalt bryter mot dessa. Till skillnad från tidigare lösningar så kan tidshorisonten i våra RHS-metoder väljas oberoende av STL-uppgifterna och därmed göras godtyckligt kort, så länge ursprungsproblemet ̈ar lösbart. Genom att formulera STL-uppgifterna som control barrier funktioner kan vi kombinera fördelarna hos RHS och ̊återkoppling. Vi härleder en rekursiv lösbarhetsegenskap och en undre gräns på ̈overträdelsen av STL-kraven. I den andra delen behandlar vi multi-agent-system med uppgifter i tid och rum som berör många agenter. Målet är att bryta ner den globala uppgiften i fler men enklare lokala uppgifter som var och en bara involverar en given delmängd av agenterna. Vår nedbrytning till ̊åter oss att konstruera decentraliserade regulatorer som löser lokala STL-uppgifter, och kan i och med det markant minska kommunikationskostnaderna i j̈ämförelse med centraliserad styrning. I den sista delen av uppsatsen behandlar vi samordning av flera grupper. Vi uttrycker uppgifter såsom delning, sammanslagning och avståndshållning med hjälp av STL, och utnyttjar sedan ̊aterkoppling för att uppfylla eller minimalt bryta mot kraven. / <p>QC 20220311</p>

No description available.

Traffic congestion is a central problem in transportation systems, especially in urban areas. The rapid development of Connected and Automated Vehicles (CAVs) and new traffic infrastructure technologies provides a promising solution to solve this problem. This work focuses on the safety-critical optimal control of CAVs in autonomous traffic systems. The dissertation starts with the roundabout problem of controlling CAVs travelling through a roundabout so as to jointly minimize their travel time, energy consumption, and centrifugal discomfort while providing speed-dependent safety guarantees. A systematic approach is developed to determine the safety constraints for each CAV dynamically. The joint optimal control and control barrier function (OCBF) controller is applied, where the unconstrained optimal control solution is derived which is subsequently optimally tracked by a real-time controller while guaranteeing the satisfaction of all safety constraints. Secondly, the dissertation deals with the feasibility problem of OCBF. The feasibility problem arises when the control bounds conflict with the Control Barrier Function (CBF) constraints and is solved by adding a single feasibility constraint to the Quadratic Problem (QP) in the OCBF controller to derive the feasibility guaranteed OCBF. The feasibility guaranteed OCBF is applied in the merging control problem which provably guarantees the feasibility of all QPs derived from the OCBF controller. Thirdly, the dissertation deals with the performance loss of OCBF due to the improperly selected reference trajectory which deviates largely from the complete optimal solution especially when the vehicle limitations are tight. A neural network is used to learn the control policy from data retrieved by offline calculation from the complete optimal solutions. Tracking the learnt reference trajectory with CBF outperforms OCBF in simulation experiments. Finally, a hierarchical framework of modular control zones (CZ) is proposed to extend the safety-critical optimal control of CAV from a single CZ to a traffic network. The hierarchical modular CZ framework is developed consisting of a lower-level OCBF controller and a higher-level feedback flow controller to coordinate adjacent CZs which outperforms a direct extension of the OCBF framework to multiple CZs without any flow control in simulation.

The thesis focuses on the design of a control strategy for safety-critical remote teleoperation. The main goal is to make the controlled system track the desired velocity specified by a human operator while avoiding obstacles despite communication delays. Different methods adopting Control Barrier Functions (CBFs) and Model Predictive Control (MPC) have been explored and tested. In this combination, CBFs are used to define the safety constraints the system has to respect to avoid obstacles, while MPC provides the framework for filtering the desired input by solving an optimization problem. The resulting input is sent to the remote system, where appropriate low-level velocity controllers translate it into system-specific commands. The main novelty of the thesis is a method to make the CBFs robust against the uncertainties affecting the system’s state due to network delays. Other techniques are investigated to improve the quality of the system information starting from the delayed one and to formulate the optimization problem without knowing the specific dynamic of the controlled system. The results show how the proposed method successfully solves the safetycritical teleoperation problem, making the controlled systems avoid obstacles with different types of network delay. The controller has also been tested in simulation and on a real manipulator, demonstrating its general applicability when reliable low-level velocity controllers are available. / Avhandlingen fokuserar på utformningen av en kontrollstrategi för säkerhetskritisk fjärrstyrd teleoperation. Huvudmålet är att få det kontrollerade systemet att följa den önskade hastigheten som specificeras av en mänsklig operatör samtidigt som hinder undviks trots kommunikationsfördröjningar. Olika metoder som använder Control Barrier Functions (CBFs) och Model Predictive Control har undersökts och testats. I denna kombination används CBFs för att definiera de säkerhetsbegränsningar som systemet måste respektera för att undvika hinder, medan MPC utgör ramverket för filtrering av den önskade indata genom att lösa ett optimeringsproblem. Den resulterande indata skickas till fjärrsystemet, där lämpliga hastighetsregulatorer på låg nivå översätter den till systemspecifika kommandon. Den viktigaste nyheten i avhandlingen är en metod för att göra CBFs robust mot de osäkerheter som påverkar systemets tillstånd på grund av nätverksfördröjningar. Andra tekniker undersöks för att förbättra kvaliteten på systeminformationen med utgångspunkt från den fördröjda informationen och för att formulera optimeringsproblemet utan att känna till det kontrollerade systemets specifika dynamik. Resultaten visar hur den föreslagna metoden framgångsrikt löser det säkerhetskritiska teleoperationsproblemet, vilket gör att de kontrollerade systemen undviker hinder med olika typer av nätverksfördröjningar. Styrningen har också testats i simulering och på en verklig manipulator, vilket visar dess allmänna tillämpbarhet när tillförlitliga lågnivåhastighetsregulatorer finns tillgängliga.

In the past few years, the application of Control Barrier Functions (CBF) and High Order Control Barrier Functions (HOCBF) as a suitable framework to ensure safety for autonomous systems has attracted increasing interest. In particular, autonomous space systems are frequently subject to safety-critical constraints due to the high costs involved in manufacturing and launching. In the present work, the application of a sample data MPC controller subject to CBF and HOCBF constraints is explored as a suitable solution for spacecraft formation flight operations. Specifically, a prototype inspection mission of the International Space Station through a multi-agent formation of CubeSats is explored. Each CubeSat is assumed to be injected in a passive relative orbit around the ISS and controlled such that the state of each agent is maintained within a prescribed safe corridor from its reference relative orbit. Moreover, appropriate conditions on the minimum control authority required to guarantee the constraints satisfaction within the MPC scheme formulation are derived and a numerical procedure to assess the recursive feasibility of the designed controller is presented. Moreover, suitable analytical modifications of the classical CBF and HOCBF constraints definitions are introduced such that the presented sample data MPC control scheme is guaranteed to ensure safety for the state of each agent in between sampling intervals. Lastly, the final control strategy is validated numerically by means of computer simulation. / Under de senaste åren har tillämpningen av Kontrollbarriärfunktioner (CBF) och Högre ordningens kontrollbarriärfunktioner (HOCBF) som ett lämpligt ramverk för att säkerställa säkerhet för autonoma system väckt ett ökande intresse. Autonoma rymdsystem är ett område med särskilt fokus på säkerhetsbegränsningar på grund av de höga tillverknings och uppskjutningskostnaderna. I detta arbete undersöks tillämpningen av en MPC-kontroller med CBF och HOCBF bivillkor för applikation inom formationsflygningsoperationer för rymdfarkoster. Detta görs genom att ett prototypinspektionsuppdrag på Internationella Rymdstationen (ISS) genom en multi-agent formation av CubeSats tas fram. Varje CubeSat är ämnad att injiceras i en passiv relativ omloppsbana runt ISS och styras sådant att varje agents tillstånd bevaras inom en föreskriven säker korridor från dess passiva relativa referensomloppsbana. Lämpliga villkor för den minsta styrbarheten som krävs för att garantera att MPC-schemaformuleringens begränsningar är tillfredsställda härleds, och en numerisk procedur för att bedöma den rekursiva genomförbarheten för den designade kontrollern presenteras. Vidare introduceras lämpliga analytiska modifieringar av de klassiska CBF- och HOCBF-begränsningsdefinitionerna så att det presenterade MPC-kontrollschemat med provdata garanterar säkerheten för varje agents tillstånd mellan dess samplingsintervall. Till sist valideras den slutliga kontrollstrategin numeriskt via datorsimuleringar.

Autonomous Unmanned Aerial Vehicles (UAV) havegreat potential in executing various complex tasks due to theirflexibility and relatively small size. The aim of this paper is todevelop a motion planner capable of generating a trajectory withaggressive maneuvers through narrow spaces without collision.The approach utilizes a framework using an optimized variantof the Rapidly-exploring Random Tree (RRT) algorithm, calledRRT*, with a Control Barrier Functions (CBF) based obstacleavoidance algorithm as well as a motion primitive generator. If amotion primitive collides with an obstacle, the obstacle avoidancealgorithm will attempt to reach the end state of a motion primitivein a collision free manner while complying with the actuationconstraints. From the collision free trajectories an optimal path iscontinuously searched for by RRT* by minimizing a cost in jerk.The performance of RRT* and the obstacle avoidance are testedin simulations independently and jointly, in several differentscenarios. The resulting motion planner successfully finds ahigh-level trajectory for the different scenarios. Limitations ofthe method as well as possible areas of improvements are alsodiscussed at the end of this paper. / Autonoma UAV har goda möjligheter för att utföra flera olika komplexa uppgifter tack vare deras flexibilitet och storlek. Denna rapport redogör för en rörelseplaneringsalgoritm som kombinerar manövrerbarheten hos en UAV för att skapa en kollisionsfri bana som innehåller aggressiva manövreringar genom trånga utrymmen. Tillvägagångssättet innefattar att kombinera Rapidly-exploring Random Tree (RRT*) med en algoritm för att undvika hinder baserad på Control Barrier Functions (CBF), samt att låta banan delas upp i segment, så kallade motion primitives, som genereras var för sig. Om en motion primitive kolliderar kommer den hinderundvikande algoritmen göra ett försök att nå dess målposition medan kollision undviks och manövreringsbegränsningarna uppfylls. Med en samling genomförbara motion primitives söker RRT* efter en kontinuerlig bana optimerad med hänsyn till en kostnad i ryck. Prestandan för RRT* och den hinderundvikande algoritmen simuleras både separat och tillsammans. Den resulterande rörelseplaneraren lyckas hitta en genomförbar bana för vardera scenario. Begränsningar av metoden samt potentiella förbättringsområden diskuteras i slutet av denna rapport. / Kandidatexjobb i elektroteknik 2021, KTH, Stockholm

In this thesis, we consider the motion planning problem for an autonomous vehicle in an obstacle-cluttered environment approximated by zonotopes, and we propose an input sampling algorithm leveraging discrete-time control barrier function conditions (DCBF). Specifically, an optimization-based control barrier function that takes into account the geometric shapes of the vehicle and obstacles is constructed and verified. We then propose a discrete-time CBF that guarantees the safety during the inter-sampling intervals. It is worth noting that we do not need an explicit expression of the barrier function, but instead, an numerically efficient algorithm is proposed to evaluate and implement the CBF/DCBF conditions. Finally, an RRT algorithm is incorporated that draws the input sampling from the input space restricted to DCBF condition. Thanks to our proposed DCBF and input sampling method approach, our proposed method is less conservative, computationally efficient and guarantees the safety during the sampling intervals. Numerical simulation with unicycle model has been done to demonstrate the favorable properties of the algorithm. / I det här dokumentet tar vi upp problemet med rörelseplanering för ett autonomt fordon i en hinderfylld miljö som approximeras av zonotoper och föreslår en algoritm för insatsprovtagning som utnyttjar diskreta villkor för kontrollbarriärfunktioner (DCBF). Vi konstruerar och verifierar en optimeringsbaserad kontrollbarriärfunktion som tar hänsyn till fordonets och hindrens geometriska former. Vi föreslår sedan en diskret CBF i diskret tid som garanterar säkerheten under intervallerna mellan provtagningarna. Det är värt att notera att vi inte behöver ett explicit uttryck för barriärfunktionen, utan istället föreslås en numeriskt effektiv algoritm för att utvärdera och genomföra CBF/DCBF-villkoren. Slutligen införlivas en RRT-algoritm som drar inmatningsprovtagningen från inmatningsutrymmet som är begränsat till DCBF-villkoret. Tack vare vår föreslagna metod för DCBF och insatsprovtagning är vår föreslagna metod mindre konservativ, beräkningsmässigt effektiv och garanterar säkerheten under provtagningsintervallerna. Numerisk simulering med encykelmodell har gjorts för att verifiera algoritmen.