18/03/2024
Door Ad Spijkers
Een nieuw algoritme verkort de reistijd door sluiproutes te identificeren die een robot kan nemen op weg naar zijn bestemming.
Als een robot die naar een bestemming reist slechts twee mogelijke paden heeft, hoeft hij alleen maar de reistijd en de kans op succes van de routes te vergelijken. Maar als hij een complexe omgeving met veel mogelijke paden doorkruist, kan het kiezen van de beste route te midden van zoveel onzekerheid snel een hardnekkig probleem worden.
Sluiproutes
Onderzoekers aan het Massachusetts Institute of Technology ontwikkelden een methode waarmee deze robot efficiënt kan redeneren over de beste routes naar zijn bestemming. Ze creëerden een algoritme voor het construeren van routekaarten van een onzekere omgeving. Het algoritme begint met paden die veilig zijn en vindt sluiproutes die de robot kan nemen om de reistijd te verkorten. In gesimuleerde experimenten ontdekten de onderzoekers dat hun algoritme een beter evenwicht kan bereiken tussen planningsprestaties en efficiëntie in vergelijking met andere basislijnen, die prioriteit geven aan het een of het ander.
Dit algoritme zou toepassingen kunnen vinden op gebieden als verkenning. Het zou een robot kunnen helpen bij het plannen van de beste manier om naar de rand van een verre krater over het oneffen oppervlak van Mars te reizen. Het zou ook een zoek- en reddingsdrone kunnen helpen bij het vinden van de snelste route naar iemand die op een afgelegen berghelling is gestrand.
In grote buitenomgevingen is niet altijd precies bekend waar je wel en niet doorheen mag. Maar een klein beetje informatie over deze omgeving kan helpen om een hoogwaardige routekaart op te stellen.
Grafieken genereren
Om bewegingsplanning te bestuderen, denken onderzoekers vaak aan de omgeving van een robot als een grafiek. Een reeks 'randen' of lijnsegmenten vertegenwoordigt mogelijke paden tussen een start- en een eindpunt. De onderzoekers aan het MIT gebruikten een grafische weergave genaamd het Canadian Traveler’s Problem (CTP). Deze ontleent zijn naam aan gefrustreerde Canadese automobilisten die moeten omkeren en een nieuwe route moeten vinden wanneer de weg voor hen geblokkeerd is door sneeuw.
In een CTP is aan elke rand van de grafiek een gewicht gekoppeld, dat aangeeft hoe lang het duurt om dat pad te doorlopen. Ook geeft het een indicatie hoe waarschijnlijk het is dat het pad ook kan worden afgelegd. Het doel van een CTP is om de reistijd naar de bestemming te minimaliseren.
De onderzoekers concentreerden zich op het automatisch genereren van een CTP-grafiek die effectief een onzekere omgeving weergeeft. Wie in een omgeving wil navigeren, gaat niet zomaar blind naar binnen. Hoewel het geen gedetailleerd navigatieplan is, geeft de grafiek een idee waar mee is te werken. De kern van dit werk is proberen dat vast te leggen in de CTP-grafiek.
Opbouw
Het algoritme gaat ervan uit dat deze gedeeltelijke informatie – misschien een satellietbeeld – kan worden onderverdeeld in specifieke gebieden (een meer kan het ene gebied zijn, een open veld een ander gebied, enzovoorts). Elk gebied heeft een waarschijnlijkheid dat de robot er doorheen kan reizen. Het algoritme gebruikt deze informatie om een eerste grafiek te bouwen, waarbij een conservatief pad wordt uitgestippeld dat langzaam maar zeker begaanbaar is. Vervolgens gebruikt het een metriek om te bepalen welke randen, of kortere paden door onzekere gebieden, aan de grafiek moeten worden toegevoegd om de totale reistijd te verkorten.
Door alleen sluiproutes te selecteren die waarschijnlijk begaanbaar zijn, zorgt het algoritme ervoor dat het planningsproces niet nodeloos ingewikkeld wordt. De kwaliteit van het bewegingsplan is afhankelijk van de kwaliteit van de grafiek. Als die grafiek geen goede paden bevat, kan het algoritme geen goed plan geven.
Testen
De onderzoekers testten het algoritme in meer dan honderd gesimuleerde experimenten met steeds complexere omgevingen. Ze ontdekten dat hun algoritme consequent beter presteerde dan basismethoden die geen rekening houden met waarschijnlijkheden. Ze testten het ook met behulp van een luchtfoto van de campuskaart van MIT om aan te tonen dat het effectief zou kunnen zijn in echte, stedelijke omgevingen.
In de toekomst willen ze het algoritme verbeteren, zodat het in meer dan twee dimensies kan werken. Dat zou het gebruik voor ingewikkelde robotmanipulatieproblemen mogelijk kunnen maken. Ze zijn ook geïnteresseerd in het bestuderen van de discrepantie tussen CTP-grafieken en de echte omgeving die deze grafieken vertegenwoordigen.
Foto: PxHere