För att självkörande fordon ska bli en vardaglig verklighet, de måste säkert och felfritt navigera varandra utan att krascha eller orsaka onödiga trafikstockningar.

För att hjälpa till att göra detta möjligt, Northwestern University forskare har utvecklat den första decentraliserade algoritmen med en kollisionsfri, låsningsfri garanti.

Forskarna testade algoritmen i en simulering av 1, 024 robotar och på en svärm av 100 riktiga robotar i laboratoriet. Robotarna tillförlitligt, säkert och effektivt konvergerat för att bilda en förutbestämd form på mindre än en minut.

"Om du har många autonoma fordon på vägen, du vill inte att de ska kollidera med varandra eller fastna i ett dödläge, " sa Northwesterns Michael Rubenstein, som ledde studien. "Genom att förstå hur vi styr våra svärmrobotar för att bilda former, vi kan förstå hur man kontrollerar flottor av autonoma fordon när de interagerar med varandra."

Tidningen kommer att publiceras senare denna månad i tidskriften IEEE -transaktioner om robotik . Rubenstein är Lisa Wissner-Slivka och Benjamin Slivka professor i datavetenskap vid Northwesterns McCormick School of Engineering.

Fördelen med en svärm av små robotar - kontra en stor robot eller en svärm med en ledande robot - är avsaknaden av en centraliserad kontroll, som snabbt kan bli en central punkt för misslyckande. Rubensteins decentraliserade algoritm fungerar som en felsäker.

"Om systemet är centraliserat och en robot slutar fungera, då misslyckas hela systemet, " sa Rubenstein. "I ett decentraliserat system, det finns ingen ledare som talar om för alla andra robotar vad de ska göra. Varje robot fattar sina egna beslut. Om en robot misslyckas i en svärm, svärmen kan fortfarande utföra uppgiften."

Fortfarande, robotarna måste samordna sig för att undvika kollisioner och dödläge. Att göra detta, algoritmen ser marken under robotarna som ett rutnät. Genom att använda teknik som liknar GPS, varje robot är medveten om var den sitter på nätet.

Innan du fattar ett beslut om var du ska flytta, varje robot använder sensorer för att kommunicera med sina grannar, avgöra om närliggande utrymmen inom nätet är lediga eller upptagna.

"Robotarna vägrar att flytta till en plats tills den platsen är ledig och tills de vet att inga andra robotar rör sig till samma plats, " sa Rubenstein. "De är försiktiga och reserverar ett utrymme i förväg."

Även med all denna noggranna samordning, robotarna kan fortfarande kommunicera och röra sig snabbt för att bilda en form. Rubenstein åstadkommer detta genom att hålla robotarna närsynta.

"Varje robot kan bara känna av tre eller fyra av sina närmaste grannar, "Rubenstein förklarade." De kan inte se över hela svärmen, vilket gör det lättare att skala systemet. Robotarna interagerar lokalt för att fatta beslut utan global information."

I Rubensteins svärm, till exempel, 100 robotar kan samordna sig för att bilda en form inom en minut. I vissa tidigare tillvägagångssätt, det kan ta en hel timme. Rubenstein föreställer sig att hans algoritm skulle kunna användas i flottor av förarlösa bilar och i automatiserade lager.

"Stora företag har lager med hundratals robotar som gör uppgifter som liknar vad våra robotar gör i labbet, "sa han." De måste se till att deras robotar inte krockar men rör sig så snabbt som möjligt för att nå platsen där de så småningom ger ett objekt till en människa. "