Sværmende robotter undgår kollisioner, trafikpropper

For at selvkørende køretøjer bliver en hverdagsrealitet, de skal sikkert og fejlfrit navigere hinanden uden at styrte ned eller forårsage unødvendige trafikpropper.

For at hjælpe med at gøre dette muligt, Northwestern University forskere har udviklet den første decentraliserede algoritme med en kollisionsfri, deadlock-fri garanti.

Forskerne testede algoritmen i en simulering af 1, 024 robotter og på en sværm af 100 rigtige robotter i laboratoriet. Robotterne pålideligt, sikkert og effektivt konvergeret for at danne en forudbestemt form på mindre end et minut.

"Hvis du har mange selvkørende køretøjer på vejen, du vil ikke have, at de kolliderer med hinanden eller sidder fast i et dødvande, " sagde Northwesterns Michael Rubenstein, der ledede undersøgelsen. "Ved at forstå, hvordan man styrer vores sværmrobotter til at danne former, vi kan forstå, hvordan man kontrollerer flåder af autonome køretøjer, når de interagerer med hinanden."

Artiklen vil blive offentliggjort senere på måneden i tidsskriftet IEEE-transaktioner på robotteknologi . Rubenstein er Lisa Wissner-Slivka og Benjamin Slivka professor i datalogi ved Northwesterns McCormick School of Engineering.

Fordelen ved en sværm af små robotter – versus én stor robot eller en sværm med én hovedrobot – er manglen på en centraliseret kontrol, som hurtigt kan blive et centralt fejlpunkt. Rubensteins decentraliserede algoritme fungerer som en fejlsikker.

"Hvis systemet er centraliseret, og en robot holder op med at arbejde, så fejler hele systemet, " sagde Rubenstein. "I et decentraliseret system, der er ingen leder, der fortæller alle de andre robotter, hvad de skal gøre. Hver robot træffer sine egne beslutninger. Hvis en robot fejler i en sværm, sværmen kan stadig klare opgaven."

Stadig, robotterne skal koordinere for at undgå kollisioner og dødvande. At gøre dette, Algoritmen ser jorden under robotterne som et gitter. Ved at bruge teknologi, der ligner GPS, hver robot er opmærksom på, hvor den sidder på nettet.

Inden du beslutter dig for, hvor du skal flytte, hver robot bruger sensorer til at kommunikere med sine naboer, afgøre, om nærliggende rum inden for nettet er ledige eller besatte.

"Robotterne nægter at flytte til et sted, indtil det sted er frit, og indtil de ved, at ingen andre robotter bevæger sig til det samme sted, " sagde Rubenstein. "De er forsigtige og reserverer en plads i forvejen."

Selv med al denne omhyggelige koordinering, robotterne er stadig i stand til at kommunikere og bevæge sig hurtigt for at danne en form. Rubenstein opnår dette ved at holde robotterne nærsynede.

"Hver robot kan kun mærke tre eller fire af sine nærmeste naboer, Rubenstein forklarede. "De kan ikke se hele sværmen, hvilket gør det nemmere at skalere systemet. Robotterne interagerer lokalt for at træffe beslutninger uden global information."

I Rubensteins sværm, for eksempel, 100 robotter kan koordinere for at danne en form inden for et minut. I nogle tidligere tilgange, det kunne tage en hel time. Rubenstein forestiller sig, at hans algoritme kunne bruges i flåder af førerløse biler og i automatiserede lagre.

"Store virksomheder har varehuse med hundredvis af robotter, der udfører opgaver svarende til, hvad vores robotter gør i laboratoriet, " sagde han. "De skal sørge for, at deres robotter ikke kolliderer, men bevæger sig så hurtigt som muligt for at nå det sted, hvor de til sidst giver en genstand til et menneske."