05/12/2024
Door Ad Spijkers
Een nieuw algoritme van Caltech helpt autonome robotsystemen om onderweg in real-time optimale keuzes te maken.
Onderzoekers van Caltech in Pasadena (Californië) hebben een plannings- en besluitvormingssysteem ontwikkeld dat vrij bewegende robots helpt om de beste bewegingen te bepalen terwijl ze door de echte wereld navigeren. Het algoritme, SETS (voor Spectral Expansion Tree Search) genaamd, is succesvol ingezet in drie compleet verschillende experimentele settings met verschillende robotsystemen. Het werd toegepast op een drone, een rupsvoertuig en robots die ruimtevaartuigen nabootsen.
Nieuw algoritme
In 2018 leerde het AlphaZero-programma van Google DeepMind zichzelf schaken, shogi en Go spelen. Dat gebeurde met behulp van machine learning en een speciaal algoritme om de beste zetten te bepalen om een spel binnen een gedefinieerd raster te winnen. Een team van Caltech-onderzoekers heeft een analoog algoritme ontwikkeld voor autonome robots. Een plannings- en besluitvormingssysteem helpt vrij bewegende robots de beste bewegingen te bepalen terwijl ze door de echte wereld navigeren.
Het algoritme maakt strategieën en onderzoekt vervolgens alle mogelijke en belangrijke bewegingen. Vervolgens kiest het de beste door middel van dynamische simulatie, zoals het spelen van veel gesimuleerde spellen met bewegende robots. De innovatie hier is dat de onderzoekers een efficiënte manier hebben ontwikkeld om die optimale veilige beweging te vinden die typische op optimalisatie gebaseerde methoden nooit zouden vinden.
Eén algoritme?
Veel robots kunnen vrij en in elke richting bewegen. Denk bijvoorbeeld aan een humanoïde robot die is ontworpen om een oudere persoon in een huis te helpen. Zo'n robot zou op veel verschillende manieren moeten kunnen bewegen. Dat moet, in principe, in elke richting binnen de ruimte, terwijl hij obstakels of onverwachte gebeurtenissen tegenkomt tijdens het uitvoeren van zijn taken. De bewegingen, obstakels en uitdagingen van die robot zijn heel anders dan die van bijvoorbeeld een zelfrijdende auto.
Hoe kan een enkel algoritme dan verschillende robotsystemen begeleiden om de beste beslissingen te nemen om door hun omgeving te bewegen? Het is niet gewenst dat een ontwerper deze bewegingen handmatig moet maken en moet zeggen: 'Dit is de discrete set bewegingen die de robot zou moeten kunnen doen'. Om dit te overwinnen, bedachten de onderzoekers SETS.
SETS
SETS gebruikt regeltheorie en lineaire algebra om natuurlijke bewegingen te vinden die de mogelijkheden van een robotplatform ten volle benutten in een fysieke omgeving. Het onderliggende basisconcept is gebaseerd op een Monte Carlo Tree Search, een besluitvormingsalgoritme dat ook wordt gebruikt door AlphaZero van Google. Monte Carlo betekent hier in wezen iets willekeurigs. Tree search verwijst naar het navigeren door een vertakkende structuur die de relaties van data in een systeem vertegenwoordigt.
In zo'n boom vertakt een wortel zich naar zogenaamde kindknooppunten die verbonden zijn door randen. Met Monte Carlo Tree Search voor een spel als Go worden mogelijke zetten weergegeven als nieuwe knooppunten. De boom wordt groter naarmate er meer willekeurige voorbeelden van mogelijke trajecten worden geprobeerd. Het algoritme speelt de mogelijke zetten uit om de uiteindelijke uitkomsten van de verschillende knooppunten te zien en selecteert vervolgens degene die de beste uitkomst biedt op basis van een puntwaardering.
Exploratie en exploitatie
Het probleem is dat, bij gebruik van deze vertakkende boomstructuur voor continue dynamische systemen zoals robots die in de fysieke wereld werken, het totale aantal trajecten in de boom exponentieel groeit. Voor sommige problemen zou het jaren duren, misschien wel honderden jaren, om elke mogelijkheid te simuleren en er vervolgens achter te komen welke het beste is.
Om dit te verhelpen, maakt SETS gebruik van een afweging tussen exploratie en exploitatie. De onderzoekers willen trajecten simuleren die ze nog niet eerder hebben onderzocht: exploratie. Ze willen doorgaan met het zoeken naar paden die eerder een hoge beloning hebben opgeleverd: exploitatie. Door de exploratie en de exploitatie in evenwicht te brengen, kan het algoritme snel convergeren naar de optimale oplossing tussen alle mogelijke trajecten.
Als een robot bijvoorbeeld begint met het berekenen van een aantal mogelijke acties waarvan hij vaststelt dat ze hem tegen een muur laten botsen, hoeft hij geen van de andere knooppunten op die tak van de boom te onderzoeken.
Deze afweging van exploratie en exploitatie en het doorzoeken van de natuurlijke bewegingen van de robot stelt robots in staat om in real-time te denken, te bewegen en zich aan te passen aan nieuwe informatie. SETS kan een hele boomzoektocht uitvoeren in ongeveer een tiende van een seconde. Gedurende die tijd kan het duizenden tot tienduizenden mogelijke trajecten simuleren, de beste selecteren en vervolgens handelen. De lus gaat steeds opnieuw door, waardoor het robotsysteem de mogelijkheid heeft om elke seconde veel beslissingen te nemen.
De praktijk
Een belangrijk kenmerk van het SETS-algoritme is, dat het in principe op elk robotplatform kan worden toegepast. De functies en mogelijkheden hoeven niet afzonderlijk te worden geprogrammeerd. De onderzoekers hebben het succes van het algoritme in drie compleet verschillende experimentele settings aan.
In het eerste geval kon een quadrotor-drone vier zwevende witte ballen observeren terwijl hij vier oranje ballen ontweek. Intussen navigeerde hij over een vliegveld met willekeurig voorkomende, gevaarlijke luchtstromen of thermiek. Het drone-experiment werd uitgevoerd in het Center for Autonomous Systems and Technologies (CAST) van Caltech. In het tweede geval versterkte het algoritme een menselijke bestuurder van een rupsvoertuig om over een smal en kronkelig spoor te navigeren zonder de zijrails te raken. In de laatste opstelling hielp SETS een paar vastgebonden ruimtevaartuigen om een derde object te vangen en om te leiden, dat een ander ruimtevaartuig, een asteroïde of een ander object zou kunnen vertegenwoordigen.
Een team van Caltech-studenten en -onderzoekers past momenteel een versie van het SETS-algoritme toe op een Indy-auto die op 9 januari deelneemt aan de Indy Autonomous Challenge op de Consumer Electronics Show (CES) in Las Vegas.
De wetenschappelijke publicatie vindt u hier.
Foto: Caltech