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

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.

This dissertation explores the development of sophisticated distributed layered control algorithms focused on the navigation, planning, and control of multi-agent quadrupedal robots collaborating in uncertain environments. Quadrupedal robots are high-dimensional, complex systems that are inherently unstable, posing significant challenges in designing predictive control laws. Template models offer a solution by providing a bridging layer of reduced-order models with fewer state variables and linearized dynamics. However, this approach compromises the agility and full potential of these sophisticated machines, as template models may fail to capture the intricate nonlinear dynamics of quadrupedal robots. Furthermore, in multi-robot systems (MRS) where numerous robots operate concurrently, it becomes crucial to develop strategies embedding collision safety mechanisms. One approach involves embedding Euclidean distance constraints in the predictive control formulation. While effective, this method significantly complicates the optimal control (OC) problem and increases computational overhead. To mitigate these challenges, this dissertation explores hierarchical and distributed control frameworks, focusing on developing real-time feasible controllers that guarantee collision avoidance while preserving the agility of these hardware platforms by utilizing fully nonlinear template models. In particular, this research investigates a multi-layered framework consisting of potential fields at the high-level layer, a distributed nonlinear model predictive control (DNMPC) based middle-level layer responsible for uncertainty mitigation, and full-order nonlinear controllers at the low-level layer. Additionally, the latter part of this dissertation examines the integration of safety-ensuring control barrier functions (CBFs) into the nonlinear model predictive control (NMPC) layer, thereby providing rigorous mathematical guarantees for collision avoidance. The crux of this research lies in addressing the following questions: How do we design layered control frameworks to guarantee optimal gait planning and collision avoidance while maintaining computational tractability? How do we mitigate uncertainty in the environment in real-time using safety-critical control algorithms? / Doctor of Philosophy / This dissertation investigates advanced control strategies for coordinating teams of quadrupedal robots in dynamic and uncertain environments. Quadrupedal robots present significant challenges in control and stability due to their complex, high-dimensional nature and inherent instability. Current approaches often employ simplified models for control, which, while computationally efficient, fail to fully capture the intricate dynamics of these sophisticated machines, thus limiting their agility and potential. Furthermore, in multi-robot systems, ensuring collision avoidance is a practically integral part of control. Conventional methods, including Euclidean distance constraints for collision avoidance, prove effective but substantially increase computational demands and complicate the optimal control problem. To address these challenges, this research explores a hierarchical, distributed control framework designed to guarantee collision-free navigation while maximizing the agility of quadrupedal platforms through the use of comprehensive nonlinear models. The proposed framework consists of three primary layers: a high-level layer utilizing potential fields for global path planning, a middle layer employing distributed nonlinear model predictive control for local navigation and uncertainty mitigation, and a low-level layer implementing full-order nonlinear controllers for precise motion execution. Additionally, this work examines the integration of control barrier functions into the predictive control layer, providing mathematical guarantees for collision avoidance. The core objectives of this research are twofold: first, to develop layered control frameworks that ensure optimal gait planning and collision avoidance while maintaining computational feasibility; and second, to create real-time algorithms capable of mitigating environmental uncertainties using safety-critical control methods. By addressing these fundamental questions, this dissertation aims to advance the field of multi-agent quadrupedal robotics, enhancing the capability of robotic teams to operate effectively in complex, unpredictable environments. The potential applications of this research extend to critical areas such as search and rescue operations, environmental monitoring, and exploration of hazardous terrains.

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.