Algoritme voorkomt botsende drones

Thu Oct 10 2024

10 10

Algoritme voorkomt botsende drones

30/03/2023

Door Ad Spijkers

Dankzij een trajectplanningssysteem kunnen drones in hetzelfde luchtruim een veilig pad naar voren kiezen.


     

Wanneer meerdere drones samenwerken in hetzelfde luchtruim, bijvoorbeeld door besproeien van een maïsveld, bestaat het risico dat ze tegen elkaar botsen. Onderzoekers aan het Masachusetts Institute of Technology in Cambridge hebben een trajectplanningssysteem ontwikkeld waarmee drones in hetzelfde luchtruim altijd een veilig pad naar voren kunnen kiezen.

Mader

Om kostbare crashes te helpen voorkomen, presenteerden MIT-onderzoekers in 2020 een systeem genaamd Mader. Met deze multi-agent trajectplanner kan een groep drones optimale, botsingsvrije trajecten formuleren. Elke agent zendt zijn traject uit, zodat collega-drones weten waar hij naartoe wil. Agenten houden vervolgens rekening met elkaars trajecten bij het optimaliseren van hun eigen trajecten om ervoor te zorgen dat ze niet botsen.

Mader is een asynchrone, gedecentraliseerde, multi-agent trajectplanner: elke drone formuleert zijn eigen traject. Hoewel alle agenten het eens moeten zijn over elk nieuw traject, hoeven ze het niet tegelijkertijd eens te zijn. Dit maakt Mader schaalbaarder dan andere benaderingen; het voor duizenden drones moeilijk zijn om het tegelijkertijd eens te worden over een traject. Vanwege het gedecentraliseerde karakter zou het systeem ook beter werken in real-world omgevingen waar drones ver van een centrale computer kunnen vliegen.

Mader werkte goed in simulaties, maar het was niet getest in hardware. Toen het ontwikkelteam het systeem testte op echte drones, ontdekten ze dat een drone geen actuele informatie heeft over de trajecten van zijn partners. Er zijn altijd communicatievertragingen die tot enkele storingen leiden. Een drone kan dus onbedoeld een pad kiezen dat resulteert in een botsing.

Robust Mader

De onderzoekers hebben hun systeem vernieuwd en rollen nu Robust Mader uit. Dit is een trajectplanner voor meerdere agenten die botsingsvrije trajecten genereert, zelfs wanneer de communicatie tussen agenten vertraging oploopt. Het algoritme bevat een vertragingscontrolestap waarbij een drone een bepaalde tijd wacht voordat hij zich vastlegt op een nieuw, geoptimaliseerd traject. Als hij tijdens de vertragingsperiode aanvullende trajectinformatie ontvangt van mede-drones, kan het zijn nieuwe traject verlaten en het optimalisatieproces opnieuw starten.

Zowel in simulaties als in vluchtexperimenten met echte drones behaalden de onderzoekers een slagingspercentage van 100% bij het genereren van botsingsvrije trajecten. De reistijd van de drones iets langer dan bij sommige andere benaderingen, maar die konden de veiligheid niet garanderen. Om niet tegen een obstakel te botsen, is wel meer tijd nodig om op de bestemming te komen.

Plannen van trajecten

Met Mader optimaliseert elke drone een nieuw traject met behulp van een algoritme dat rekening houdt met de trajecten die het van andere agenten heeft ontvangen. Door voortdurend hun nieuwe trajecten te optimaliseren en uit te zenden, vermijden de drones botsingen. In echte omgevingen worden signalen vaak vertraagd door interferentie van andere apparaten of omgevingsfactoren zoals stormachtig weer. Door onvermijdelijke vertragingen kan een drone onbedoeld een nieuw traject volgen waardoor hij op ramkoers komt te liggen.

Robuuste Mader voorkomt dergelijke botsingen omdat elke agent twee trajecten beschikbaar heeft. Het houdt één traject aan waarvan het weet dat het veilig is en dat het al heeft gecontroleerd op mogelijke botsingen. Terwijl hij dat oorspronkelijke traject volgt, optimaliseert de drone een nieuw traject, maar legt zich hier niet op vast totdat het een vertragingscontrolestap heeft voltooid.

Tijdens de vertragingscontroleperiode besteedt de drone een vaste hoeveelheid tijd aan het herhaaldelijk controleren op communicatie van andere agenten om te zien of zijn nieuwe traject veilig is. Als hij een mogelijke botsing detecteert, verlaat hij het nieuwe traject en begint het optimalisatieproces opnieuw. De lengte van de vertragingscontroleperiode hangt af van de afstand tussen agenten en omgevingsfactoren die de communicatie kunnen belemmeren. Als de agenten bijvoorbeeld vele kilometers van elkaar verwijderd zijn, zou de vertragingscontroleperiode langer moeten zijn.

Botsingsvrij

De onderzoekers testten hun nieuwe aanpak door honderden simulaties uit te voeren waarin ze op kunstmatige wijze communicatievertragingen introduceerden. In elke simulatie was Robust Mader 100% succesvol in het genereren van botsingsvrije trajecten, terwijl alle basislijnen crashes veroorzaakten.

Ze bouwden ook zes drones en twee luchtobstakels en testten Robust Mader in een multiagent-vluchtomgeving. Het gebruik van de originele versie van Mader in deze omgeving zou tot zeven botsingen hebben geleid. Robust Mader veroorzaakte in een van de hardware-experimenten geen enkele crash. De drones konden met Robust Mader 3,4 m/s vliegen, hoewel ze een iets langere gemiddelde reistijd hadden dan sommige basislijnen. Maar geen enkele andere methode was in elk experiment perfect botsingsvrij.

In de toekomst willen de onderzoekers Robust Mader buiten testen, waar veel obstakels en soorten ruis de communicatie kunnen beïnvloeden. Ze willen de drones ook uitrusten met visuele sensoren, zodat ze andere agenten of obstakels kunnen detecteren, hun bewegingen kunnen voorspellen en die informatie kunnen opnemen in baanoptimalisaties.

Foto: MIT