Om zelfrijdende voertuigen een dagelijkse realiteit te laten worden, ze moeten veilig en foutloos door elkaar navigeren zonder te crashen of onnodige files te veroorzaken.

Om dit mogelijk te maken, Onderzoekers van de Northwestern University hebben het eerste gedecentraliseerde algoritme ontwikkeld met een botsingsvrije, garantie zonder blokkades.

De onderzoekers testten het algoritme in een simulatie van 1, 024 robots en op een zwerm van 100 echte robots in het laboratorium. De robots betrouwbaar, veilig en efficiënt geconvergeerd tot een vooraf bepaalde vorm in minder dan een minuut.

"Als je veel autonome voertuigen op de weg hebt, je wilt niet dat ze met elkaar in botsing komen of vast komen te zitten in een impasse, " zei Michael Rubenstein van Northwestern, die de studie leidde. "Door te begrijpen hoe we onze zwermrobots kunnen besturen om vormen te vormen, we kunnen begrijpen hoe we vloten van autonome voertuigen kunnen besturen terwijl ze met elkaar communiceren."

De paper wordt later deze maand gepubliceerd in het tijdschrift IEEE-transacties op robotica . Rubenstein is de Lisa Wissner-Slivka en Benjamin Slivka Professor in Computer Science aan de McCormick School of Engineering van Northwestern.

Het voordeel van een zwerm kleine robots - versus één grote robot of een zwerm met één leidende robot - is het ontbreken van een gecentraliseerde besturing, die snel een centraal punt van mislukking kan worden. Het gedecentraliseerde algoritme van Rubenstein werkt als een fail-safe.

"Als het systeem gecentraliseerd is en een robot stopt met werken, dan faalt het hele systeem, Rubenstein zei. "In een gedecentraliseerd systeem, er is geen leider die alle andere robots vertelt wat ze moeten doen. Elke robot maakt zijn eigen beslissingen. Als een robot faalt in een zwerm, de zwerm kan de taak nog steeds volbrengen."

Nog altijd, de robots moeten coördineren om botsingen en impasse te voorkomen. Om dit te doen, het algoritme ziet de grond onder de robots als een raster. Door gebruik te maken van technologie die vergelijkbaar is met GPS, elke robot weet waar hij op het rooster zit.

Alvorens een beslissing te nemen over waar te verhuizen, elke robot gebruikt sensoren om met zijn buren te communiceren, bepalen of nabijgelegen ruimtes binnen het raster al dan niet leeg of bezet zijn.

"De robots weigeren naar een plek te gaan totdat die plek vrij is en totdat ze weten dat er geen andere robots naar die plek gaan, Rubenstein zei. "Ze zijn voorzichtig en reserveren een plaats van tevoren."

Zelfs met al deze zorgvuldige coördinatie, de robots kunnen nog steeds communiceren en snel bewegen om een ​​vorm te vormen. Rubenstein bereikt dit door de robots bijziend te houden.

"Elke robot kan slechts drie of vier van zijn naaste buren waarnemen, " legde Rubenstein uit. "Ze kunnen niet over de hele zwerm kijken, wat het eenvoudiger maakt om het systeem te schalen. De robots werken lokaal samen om beslissingen te nemen zonder wereldwijde informatie."

In de zwerm van Rubenstein, bijvoorbeeld, 100 robots kunnen binnen een minuut coördineren om een ​​vorm te vormen. In sommige eerdere benaderingen, het kan een vol uur duren. Rubenstein stelt zich voor dat zijn algoritme kan worden gebruikt in vloten van zelfrijdende auto's en in geautomatiseerde magazijnen.

"Grote bedrijven hebben magazijnen met honderden robots die taken uitvoeren die vergelijkbaar zijn met wat onze robots in het laboratorium doen, " zei hij. "Ze moeten ervoor zorgen dat hun robots niet botsen, maar zo snel mogelijk bewegen om de plek te bereiken waar ze uiteindelijk een object aan een mens geven."