Least Restrictive Hyperplane Control Barrier Functions

Deze paper introduceert een methode om minder restrictieve Veiligheidsbarrière-Functionen (CBF's) te vinden door de oriëntatie van een scheidend hypervlak te optimaliseren, waardoor dynamische systemen veilig en efficiënter kunnen navigeren in de buurt van complexe obstakels dan met traditionele op afstand gebaseerde CBF's.

De kern

Stel je voor dat je met een zelfrijdende auto door een drukke stad rijdt. Je hebt een GPS die je een perfect, recht pad naar je bestemming laat zien. Maar plotseling zie je een grote vrachtwagen die je pad blokkeert, of een kind dat op het trottoir rent.

Je auto moet nu iets doen: ofwel remmen en wachten (veilig, maar traag en vervelend), of slim om de obstakels heen sturen (snel en efficiënt).

Dit is precies het probleem dat de auteurs van dit paper, Mattias Trende en Petter Ögren, oplossen. Ze hebben een nieuwe manier bedacht om robots en auto's veilig te laten rijden, zonder ze onnodig te remmen.

Hier is de uitleg in gewone taal, met een paar handige vergelijkingen.

1. Het oude probleem: De "Stijve Muur"

In de robotwereld gebruiken ze iets dat een CBF (Control Barrier Function) heet. Je kunt dit zien als een onzichtbare, onbreekbare muur die de robot omgeeft. Als de robot te dicht bij een obstakel komt, wordt deze muur dikker en dwingt hij de robot om te remmen of af te buigen.

Het probleem met de oude methode (die ze OH-CBF noemen) is dat deze muur altijd loodrecht staat op de lijn tussen de robot en het obstakel.

• De analogie: Stel je voor dat je door een smalle gang loopt en er staat een grote kist in de weg. De oude methode denkt: "Ik moet precies recht voor die kist stoppen alsof er een muur staat." Zelfs als je gewoon langs de zijkant van de kist kunt lopen zonder erin te knallen, zegt de robot: "Stop! Er is een muur!"
• Het gevolg: De robot remt veel te vroeg en te hard. Hij is veilig, maar hij is ook erg traag en onhandig.

2. De nieuwe oplossing: De "Draaibare Scherm"

De auteurs zeggen: "Waarom moeten we die muur altijd loodrecht houden? Waarom draaien we hem niet een beetje?"

Ze introduceren de LRH-CBF (Least Restrictive Hyperplane Control Barrier Function).

• De analogie: In plaats van één stijve muur, heeft de robot nu een draaibare scherm (een hyperplane). De robot kijkt naar zijn gewenste richting (waar hij naartoe wil) en draait zijn scherm zo, dat het hem de meeste vrijheid geeft om die kant op te gaan, terwijl hij nog steeds veilig blijft.
• Hoe het werkt: De robot vraagt zich af: "Als ik hierheen wil gaan, welke hoek moet ik voor mijn veiligheidsmuur kiezen zodat ik niet onnodig hoef te remmen?"
  • Als hij recht op een obstakel afrijdt, staat het scherm loodrecht (remmen).
  • Als hij langs een obstakel wil glijden, draait hij het scherm mee met zijn beweging. Dan hoeft hij niet te remmen, want de "muur" staat nu schuin en laat hem langs glippen.

3. Waarom is dit zo slim?

Stel je voor dat je met een fiets door een bos rijdt en je ziet een boomstam op je pad.

• Oude methode: Je ziet de boomstam, je stopt direct omdat je denkt dat je erin gaat knallen, ook al kun je er makkelijk omheen fietsen.
• Nieuwe methode: Je kijkt naar je fietspad, ziet dat je de boomstam netjes kunt omfietsen, en past je veiligheidszone (je "scherm") zo aan dat je gewoon doorfietsen kunt zonder te vallen.

De nieuwe methode is minder restrictief. Dat betekent dat de robot minder vaak hoeft te stoppen of te vertragen, maar hij is net zo veilig.

4. Is dit niet te moeilijk om te berekenen?

Je zou denken: "Oh, elke seconde een nieuwe hoek voor de muur berekenen? Dat kost veel rekenkracht!"
De auteurs tonen aan dat dit niet zo is.

• De analogie: Het is alsof je in plaats van één muur te bouwen, een kleine doos hebt met 5 of 10 verschillende muur-hoeken. De robot kiest in een fractie van een seconde de beste hoek uit die doos.
• Het kost bijna evenveel rekenkracht als de oude methode, maar het resultaat is veel soepeler en sneller.

Samenvatting in één zin

Deze paper introduceert een slimme truc waarbij robots hun veiligheidsmuur niet stijf houden, maar draaien naar de richting waar ze naartoe willen, zodat ze veilig maar veel sneller en soepeler langs obstakels kunnen rijden.

Het is het verschil tussen een robot die paniekremt bij elk obstakel, en een robot die soepel en slim om de obstakels heen glijdt.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Least Restrictive Hyperplane Control Barrier Functions" van Trende en Ögren, geschreven in het Nederlands.

Titel: Minimaal Restrictieve Hyperplane Control Barrier Functions (LRH-CBF)

Auteurs: Mattias Trende en Petter Ögren (KTH Royal Institute of Technology, Stockholm)

---

1. Probleemstelling

Control Barrier Functions (CBF's) zijn een krachtig wiskundig instrument om proefbare veiligheidsgaranties te bieden voor dynamische systemen (zoals robots). Ze fungeren als een "veiligheidsfilter" dat een gewenste besturing (control action) aanpast naar de dichtstbijzijnde veilige besturing.

Het hoofdprobleem bij het gebruik van CBF's is het vinden van een geldig CBF voor complexe systemen:

• Voor systemen met hoge dimensies of complexe obstakelgeometrieën is het vaak moeilijk om een analytische oplossing te vinden.
• Numerieke oplossingen schalen slecht met complexiteit.
• Een veelgebruikte oplossing is de afstandsbased CBF (of Orthogonal Hyperplane-CBF, OH-CBF). Deze plaatst een steunend vlak (hyperplane) loodrecht op de lijn tussen het voertuig en het dichtstbijzijnde punt van het obstakel.
• Nadeel: De OH-CBF is vaak te conservatief. Het kan een agent dwingen te remmen of een onnodig omweg te maken, zelfs als de agent veilig langs het obstakel zou kunnen passeren zonder te remmen. Dit gebeurt omdat de oriëntatie van het vlak vaststaat en niet rekening houdt met de gewenste bewegingsrichting.

2. Methodologie

De auteurs stellen een nieuwe aanpak voor: Least Restrictive Hyperplane CBF (LRH-CBF). In plaats van één vast CBF te kiezen, wordt een familie van CBF's geoptimaliseerd die afhankelijk is van de gewenste besturing.

Kernconcepten:

• Hyperplane CBF (H-CBF): Een CBF die gebaseerd is op een hyperplane die het agent-gebied scheidt van het obstakel. De standaard OH-CBF is een speciaal geval hiervan waarbij de normaalvector loodrecht staat op de verbindingslijn tussen agent en obstakel.
• Geoptimaliseerde Oriëntatie: De auteurs introduceren een parameter $\theta$ die de oriëntatie van de steunende hyperplane bepaalt.
• Gecombineerde Optimalisatie: In plaats van eerst een CBF te kiezen en dan de veilige besturing $u$ te vinden, worden $\theta$ (de CBF-oriëntatie) en $u$ (de besturing) gelijktijdig geoptimaliseerd.
  • Het doel is om de afwijking $||u - u_{des}||$ te minimaliseren, waarbij $u_{des}$ de gewenste (mogelijk onveilige) besturing is.
  • Dit leidt tot het probleem LR-CBF-OP (Least-Restrictive-CBF-Optimisation-Problem).

Wiskundige Formulering:
Voor een dubbele integrator (model met positie en snelheid, beperkt door versnelling) wordt de veiligheidsfunctie $h(x, \theta)$ gedefinieerd als:
$$h(x, \theta) = \hat{n}(\theta)^T (p_A - p_O) - \delta(\theta) - b$$
Waarbij:

• $\hat{n}(\theta)$ de eenheidsnormaalvector van het vlak is.
• $\delta(\theta)$ de veiligheidsmarge is (afhankelijk van de vorm van het obstakel).
• $b$ de remafstand is die nodig is om de relatieve snelheid tot nul te brengen.

Het algoritme zoekt binnen een verzameling $\Theta$ van mogelijke hoeken $\theta$ naar de combinatie $(\theta, u)$ die veilig is ($h \geq 0$) en de kostenfunctie minimaliseert.

Implementatie voor Discrete Systemen:
Voor systemen met embedded hardware (discrete tijd) wordt een Discrete CBF (D-CBF) gebruikt. Dit transformeert het probleem van een Kwantitatief Programmeren (QP) naar een Kwantitatief Geconstrueerd QP (QCQP), maar de auteurs tonen aan dat dit nog steeds efficiënt oplosbaar is, vooral als de verzameling $\Theta$ een eindige, kleine set is.

3. Belangrijkste Bijdragen

1. Generalisatie van OH-CBF: De LRH-CBF is een generalisatie van de bestaande afstandsbased CBF. De OH-CBF is slechts een speciaal geval waarbij $\Theta$ slechts één element bevat.
2. Minder Conservatief: Door de oriëntatie van het hyperplane te optimaliseren op basis van de gewenste besturing, kunnen agenten sneller en dichter langs obstakels passeren zonder onnodig te remmen.
3. Bewijs van Bestaan en Veiligheid: De auteurs bewijzen met behulp van convexe analyse dat er voor elke veilige trajectorie een geschikte hyperplane bestaat die de veiligheid garandeert (Lemma 2).
4. Rekenkracht: De methode behoudt een lage rekencomplexiteit. Door $\Theta$ als een eindige set te behandelen, kan het probleem worden opgelost als een reeks QP's, wat vergelijkbaar is met de snelheid van de standaard OH-CBF, maar met aanzienlijk betere prestaties.

4. Resultaten (Simulaties)

De auteurs testen de methode op een 2D dubbele integrator met verschillende scenario's:

• Invloed van Resolutie ($N_\theta$): Simulaties tonen aan dat zelfs met een kleine set van hoeken (bijv. 3 tot 9 opties), de afwijking van de gewenste besturing ($||u - u_{des}||$) drastisch daalt ten opzichte van de OH-CBF ($N_\theta=1$). De rekentijd neemt lineair toe met het aantal hoeken, maar blijft zeer laag (microseconden per stap).
• Voorbijrijden van een Obstakel: In een scenario waarbij een agent recht op een obstakel afrijdt maar er veilig langs moet (zonder te remmen), faalt de OH-CBF (de veiligheidsfunctie $h$ wordt negatief, wat onveilig impliceert). De LRH-CBF kiest een andere hoek $\theta$ zodat $h$ positief blijft, waardoor de agent de gewenste snelheid kan behouden.
• Navigatie naar een Doel: In een scenario met een obstakel dat de directe weg blokkeert, remt de OH-CBF de agent vroeg en sterk af, waardoor deze later bij het doel arriveert. De LRH-CBF laat de agent eerder van de rechte lijn afwijken (een kleine bocht) maar behoudt een hogere snelheid, wat leidt tot een aanzienlijk kortere reistijd.
• Complexe Obstakels: De methode werkt succesvol met statische veelhoeken, ellipsen en bewegende obstakels.

5. Betekenis en Conclusie

De paper introduceert een paradigmaverschuiving in het gebruik van CBF's:

• Traditioneel: Kies eerst een CBF (gebaseerd op de huidige staat), zoek dan een veilige besturing.
• Nieuw (LRH-CBF): Kies de CBF en de besturing gezamenlijk om de gewenste actie zo goed mogelijk te benaderen.

Dit resulteert in een minder restrictieve veiligheidsfilter die robuust blijft, maar de robot toestaat om sneller en efficiënter te navigeren in complexe omgevingen. De methode is rekenkundig haalbaar voor real-time toepassingen en biedt een theoretisch onderbouwde manier om de conservatisme van bestaande afstandsbased CBF's te overwinnen zonder in te leveren op veiligheidsgaranties.