The Metastable Consensus Cliff Under Communication Delay in a Swarm of Robots

Stel je een menigte eenvoudige robots voor die zich door een rommelig, obstakelrijk landschap bewegen, met de taak om een enkele, verenigde beslissing te nemen. Ze kunnen niet praten met een centrale commandant; ze kunnen alleen fluisteren naar buren die ze kunnen zien en horen. Dit is de wereld van de zwermrobotica, waar het doel is dat een grote groep onafhankelijke machines het eens wordt over een koers van actie met behulp van alleen lokale informatie. Een veelvoorkomende regel voor deze overeenstemming is dat elke robot af en toe de mening van een buur kopieert, gewogen door hoeveel hij die buur vertrouwt. In een perfecte wereld met instant communicatie zou de groep uiteindelijk op één antwoord uitkomen. In de echte wereld doen berichten er echter tijd over om te reizen. Wanneer robots door complex terrein bewegen, zijn signalen vertraagd. Jarenlang hebben onderzoekers een verontrustend patroon waargenomen: naarmate deze vertraging toeneemt, lijkt het vermogen van de zwerm om tot een overeenstemming te komen abrupt in te storten, als een klifrand, waardoor de groep in een staat van verwarring achterblijft.

Dit gedrag heeft velen doen geloven dat er een harde limiet is aan hoeveel vertraging een robotzwerm kan tolereren. De heersende theorie suggereerde dat zodra de vertraging een bepaalde drempel overschreed, de zwerm uiteenviel in geïsoleerde clusters die niet langer met elkaar konden communiceren, wat een totale instorting van de consensus veroorzaakte. Maar een nieuwe studie door onderzoekers aan de University of Sunderland daagt dit lang gehouden standpunt uit. Door duizenden gecontroleerde simulaties uit te voeren met een honderd robots die door een veld vol obstakels navigeren, ontdekten het team dat de dramatische "klif" geen plotseling falen is van de structuur van de zwerm, maar eerder een misverstand over hoe de robots zich in de loop van de tijd gedragen. De onderzoekers ontdekten dat de zwerm niet uit elkaar valt; in plaats daarvan maakt de vertraging de overeenstemming instabiel, waardoor de groep een beslissing bereikt en deze vervolgens onmiddellijk weer verliest, keer op keer.

Om te begrijpen wat er aan de hand was, bouwden de onderzoekers een digitaal model van een zwerm van honderd robots die zich door een veld van tweehonderd bij vierhonderd meter vol obstakels bewegen. Elke robot droeg een eenvoudige binaire mening, ofwel nul of één, en bewoog onafhankelijk van wat hij dacht. De robots communiceerden binnen een beperkt bereik, maar hun berichten waren onderhevig aan een vertraging die toenam met de afstand en een basisvertragingstijd. Het team voerde deze simulaties uit met variërende hoeveelheden vertraging en keek of de robots een staat konden bereiken waarin bijna al hen dezelfde mening hadden. Wanneer zij de resultaten bekeken met behulp van een standaard, vaste tijdslimiet voor het experiment, zagen zij de bekende scherpe daling: naarmate de vertraging toenam voorbij een bepaald punt, stortte het succespercentage in van hoog naar nul, wat de beruchte klif creëerde.

Echter, de onderzoekers vermoedden dat deze scherpe daling een illusie was, veroorzaakt door de manier waarop zij succes maten. Ze besloten de observatietijd te verlengen, waardoor de robots veel langer de tijd kregen om tot een overeenstemming te komen. Wanneer zij dit deden, verschoof de klif. De robots die voorheen niet binnen de korte tijdslimiet waren geslaagd in het bereiken van een overeenstemming, bereikten uiteindelijk wel een consensus als ze meer tijd kregen. Dit onthulde dat voor matige vertragingen het probleem niet was dat de robots nooit tot overeenstemming konden komen, maar dat het simpelweg langer duurde dan het experiment toeliet. De onderzoekers identificeerden twee verschillende regimes. In het eerste, het "slow-approach" regime (langzame benadering), kon de zwerm nog steeds tot overeenstemming komen als het observatievenster lang genoeg was. In het tweede, het "genuine-failure" regime (werkelijk falen), dat optrad bij zeer hoge vertragingen, kon de zwerm zelfs met tien keer het oorspronkelijke tijdsbudget niet tot overeenstemming komen.

Cruciaal was dat het team bewees dat de ineenstorting niet werd veroorzaakt door de robots die gescheiden raakten in niet-communicerende groepen. Omdat de robots bewogen op basis van hun fysieke omgeving en niet op basis van hun meningen, bleef het netwerk van verbindingen tussen hen exact hetzelfde, ongeacht hoe lang de berichten erover deden om aan te komen. De onderzoekers verifieerden dat zelfs wanneer de robots volledig verbonden bleven, de scherpe daling in succes nog steeds optrad. Dit weerlegde het idee dat de vertraging het communicatienetwerk van de zwerm verbrak. In plaats daarvan werkte de vertraging in op het besluitvormingsproces zelf. De robots ontvingen oude, verouderde informatie van buren die al van mening waren veranderd, of van "ghost" agenten die vastzaten en bevroren meningen uitzonden. Deze verouderde data bracht de zwerm constant uit balans met elke overeenstemming die zij wist te bereiken.

Het resultaat is een staat van metastabiliteit, waarbij de zwerm nabij een beslissing zweeft maar deze niet kan vastleggen. In deze simulaties was ongeveer een kwart van de runs die aanvankelijk een consensus bereikten, uiteindelijk weer teruggedreven naar onenigheid naarmate de vertraging toenam. De zwerm slaagde niet in convergentie; zij convergeerde en werd vervolgens weggestoten. De scherpe "klif" die in eerdere studies werd waargenomen, was simpelweg het punt waarop de tijd die nodig was voor de zwerm om tot een beslissing te komen, overeenkwam met de tijdslimiet van het experiment. Onder dit punt waren de robots slechts traag; boven dit punt was de vertraging zo ernstig dat de verouderde informatie de groep er nooit voor kon zorgen dat zij tot rust kwam. De onderzoekers vonden dat op goed verbonden netwerken, dit kantelpunt voorspeld kon worden door hoe lang het er gewoonlijk duurde voordat de groep haar meningen mengde, maar op minder verbonden netwerken was de instabiliteit meer chaotisch.

De studie benadrukte ook een praktische les voor het ontwerpen van robotzwermen. Aangezien het probleem niet een gebrek aan verbinding is, maar de instabiliteit veroorzaakt door vertraagde informatie, zal het simpelweg groter maken van het bereik waarmee de robots met elkaar praten het probleem niet oplossen zodra het netwerk al verbonden is. In plaats daarvan ligt de oplossing in het beheren van de ouderdom van de informatie. De onderzoekers suggereren dat toekomstige systemen mogelijk meningen moeten verdisconteren of negeren die te oud of te vertraagd zijn, zodat de zwerm de ruis kan filteren die haar verhindert tot rust te komen. Dit werk herformuleert een fundamenteel probleem in de zwermrobotica, door aan te tonen dat wat lijkt op een catastrofaal falen vaak slechts een transiënte staat van instabiliteit is, en dat de manier waarop we succes meten de schijn van een harde limiet kan wekken waar die er eigenlijk niet is.