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.

In this thesis, we develop methods leading towards the distributed control of spatio-temporally constrained systems. Overall, we focus on two different approaches: a model predictive control approach and an approach based on ensuring set-invariance via control barrier functions. Developing a distributed control framework for spatio-temporally constrained systems is challenging since multiple subsystems are interconnected via time-varying state constraints. Often, such constraints are only implicitly given as logic formulas, for example in Signal Temporal Logic (STL). Our approach to dealing with spatio-temporal constraints is as follows. We aim at combining the computational efficiency of low-level feedback controllers with planning algorithms. Low-level feedback controllers shall ensure the satisfaction of parts of spatio-temporal constraints such as coupling state constraints or short term time-constraints. In contrast, planning algorithms account for those parts that require computationally intense planning operations. Powerful low-level controllers can simplify the planning task significantly. For this reason, the focus of this thesis is on the development of low level feedback controllers.  In the first part, we focus on handling coupling state constraints using a model predictive control (MPC) approach. Commonly, the distributed handling of coupling state constraints requires a sequential or iterative MPC scheme which however is computationally time-intense. We address this issue by employing consistency constraints to develop a parallelized distributed model predictive controller (DMPC). By using consistency constraints, each subsystem guarantees to its neighbors that its states stay within a particular neighborhood around a reference trajectory. Furthermore, we propose extensions to robust and iterative schemes. Building up on this, also systems with bounded dynamic couplings can be controlled. In the second part, we focus on methods for ensuring set-invariance. In particular, we focus on control barrier functions (CBF). We show how spatio-temporal constraints that comprise disjunctions (logic OR) can be encoded in non-smooth time-varying control barrier functions and how subgradients can be used to synthesize an efficient gradient-based controller. For these results, controllability assumptions must be invoked. To extend the results to systems with weaker controllability properties, we investigate the connection between controllability properties and the construction of CBFs. As a result, we propose a construction method for CBFs based on finite horizon predictions. The constructed CBF exhibits favorable properties for the extension of the previous results on encoding spatio-temporal constraints in CBFs to systems with weaker controllability properties. At last, we investigate with a case study how set-invariance methods can be used to implicitly coordinate systems subject to coupled state constraints. Our proposed method is fully decentralized and subsystems coordinate themselves purely via their actions and the adjustment of their individual constraints. In the end, we draw a conclusion and outline how the presented results contribute to the development of a distributed control framework for spatio-temporally constrained systems. / I den här avhandlingen utvecklar vi metoder som leder till distribuerad styrning av tillstånds-temporalt begränsade system. Vi följer två olika tillvägagångssätt: å ena sidan en modellprediktiv styrning och å andra sidan ett tillvägagångssätt som bygger på att säkerställa invarians i mängden via kontrollbarriärfunktioner. Det är en utmaning att utveckla ett ramverk för distribuerad styrning för tillstånds-temporalt begränsade system, eftersom flera delsystem är sammankopplade via sina tillståndsbegränsningar som varierar över tiden. Ofta ges sådana begränsningar endast implicit som logiska formler, till exempel i Signal Temporal Logic (STL).  Vår metod för att hantera tillstånds- och tidsmässiga begränsningar är följande. Vi strävar efter att kombinera beräkningseffektiviteten hos återkopplingsregulatorer på låg nivå med planeringsalgoritmer. Återkopplingsregulatorer på låg nivå skall säkerställa att delar av de tillstånds- och tidsmässiga begränsningarna uppfylls, t.ex. sammankopplande tillståndsbegränsningar eller kortsiktiga tidsbegränsningar, medan planeringsalgoritmerna tar hänsyn till de delar som kräver beräkningsintensiva planeringsoperationer. Kraftfulla styrsystem på låg nivå kan förenkla planeringsuppgiften avsevärt. Därför fokuserar vi i denna avhandlingen på utvecklingen av återkopplingsregulatorer på låg nivå.  I den första delen fokuserar vi på att hantera sammankopplande tillståndsbegränsningar för distribuerade system med hjälp av en modell prediktiv styrning (MPC). Vanligtvis kräver den distribuerade hanteringen av kopplingsbegränsningar ett sekventiellt eller iterativt MPC-system som dock är tidskrävande. Därför utvecklar vi en parallelliserad distribuerad modell prediktiv styrning (DMPC) baserad på konsistensbegränsningar. Därigenom garanterar ett delsystem till sina grannar att det håller sig inom ett visst område runt en referensbana. Den generiska formuleringen av vårt DMPC-system möjliggör flera realiseringar. En särskild realisering föreslås. Dessutom utvecklas utvidgningar till ett robust och iterativt system samt ett DMPC-system för system med begränsade dynamiska kopplingar. I den andra delen fokuserar vi på metoder för att säkerställa invariansen av mängder. Vi fokuserar särskilt på kontrollbarriärfunktioner (CBF). Vi visar hur tillstånds- och tidsmässiga begränsningar kan inkodas i icke-glatta tidsvarierande kontrollbarriärfunktioner och hur subgradienter kan användas för att konstruera en effektiv gradientbaserad styrning. För dessa resultat måste antaganden om kontrollerbarhet åberopas. För att utvidga detta resultat till system med svagare kontrollerbarhetsegenskaper undersöker vi kopplingen mellan dynamiska systems kontrollerbarhetsegenskaper och konstruktionen av en CBF. Som ett resultat av detta föreslår vi en konstruktionsmetod för CBF:er som bygger på förutsägelser för ändliga horisonter. Den konstruerade CBF:n uppvisar gynnsamma egenskaper för att utvidga det tidigare resultatet om kodning av rums-temporala begränsningar i CBF:er till system med svagare kontrollerbarhetsegenskaper. Slutligen undersöker vi med hjälp av en fallstudie hur metoder för att säkerställa invariansen av mängder kan användas för att implicit samordna system som är kopplade via tillståndsbegränsningar. Vår föreslagna metod är helt decentraliserad och delsystemen samordnar sig själva endast via sina handlingar och justeringen av sina individuella begränsningar. Slutligen drar vi en slutsats och beskriver hur de presenterade resultaten bidrar till utvecklingen av ett ramverk för distribuerad styrning av tillstånds- och tidsmässigt begränsade system. / <p>QC 20230520</p>

Autonomous Driving Systems (ADS), a subcategory of Cyber-Physical Systems (CPS) are becoming increasingly popular with ubiquitous deployment. They provide advanced operational functions for perception and control, but this also raises the question of their safety capability. Such questions include if the vehicle can stay within its lane, keep a safe distance from the leading vehicle, or avoid obstacles, especially under the presence of uncertainties. In this master thesis, the operational safety of ADS will be addressed, more specifically on the Adaptive Cruise Control (ACC) system by modeling an optimal control problem based on Control Barrier Function (CBF) unified with Model Predictive Control (MPC). The corresponding optimal control problem is robust against measurement uncertainties for an Autonomous Vehicle (AV) driving on a highway, where the measurement uncertainties will represent the common faults in the perception system of the AV. A Kalman Filter (KF) is also added to the system to investigate the performance difference. The resulting framework is implemented and evaluated on a simulation scenario created in the open-source autonomous driving simulator CARLA. Simulations show that MPC-CBF is indeed robust against measurement uncertainties for well-selected horizon and slack variable values. The simulations also show that adding a KF improves the overall performance. The higher the horizon, the more confident the system becomes as the distance to the leading vehicle decreases. However, this may cause infeasibility where there are no solutions to the optimal control problem during sudden braking as the AV cannot brake fast enough before it crashes. Meanwhile, the smaller the slack variable, the more restrictive becomes CBF where it impacts more on the control input than desired which could also cause infeasibility. The results of this thesis will help to facilitate safety-critical CPS development to be deployed in real-world applications. / Autonoma körsystem (ADS), som är en del av cyberfysiska system (CPS), har blivit alltmer populär med allestädes närvarande användning. Det bidra med avancerade operativa funktioner för perception och styrning, men samtidig väcker detta också frågan om dess säkerhetsförmåga. Sådana frågor inkluderar om fordonet kan hålla sig inom sitt körfält, om det kan hålla ett säkert avstånd till det ledande fordonet eller om det kan undvika hinder, speciellt under osäkerheter hos systemet. I detta examensarbete kommer driftsäkerheten hos ADS att behandlas, mer specifik på adaptiv farthållare (ACC) genom att modellera ett optimalt kontrollproblem baserat på kontrollbarriärfunktion (CBF) förenat med modellförutsägande styrning (MPC). Motsvarande optimalt kontrollproblem är robust mot mätosäkerheter för ett autonomt fordon som kör på en motorväg, där mätosäkerheterna representerar vanliga fel i AV:s perceptionssystem. Ett Kalmanfilter (KF) läggs också till i systemet för att undersöka skillnaden i prestanda. Det resulterande ramverket implementeras och utvärderas på ett simuleringsscenario som skapats i den öppna källkodssimulatorn för autonom körning CARLA. Simulationer visar att MPC-CBF är robust mot mätosäkerheter för väl valda värden för horisont och slackvariabler. Det visar också att systemets prestanda förbättrats ännu mer om ett KF läggs till. Ju större horisont, desto mer självsäkert blir systemet när avståndet till det ledande fordonet minskar. Detta kan dock leda till att det inte finns några lösningar på det optimala kontrollproblemet vid plötslig inbromsning, eftersom fordonet inte hinner bromsa tillräckligt snabbt innan det kraschar. Ju mindre slackvariabeln är, desto mer restriktiv blir CBF som påverkar styrningen mer än vad som är önskvärt vilket också kan leda till olösbart optimalt kontrollproblem. Resultatet från detta examensarbete bär syftet att gynna utvecklingen av säkerhetkritisk CPS som ska användas i praktiska tillämpningar.