Technische Samenvatting: Trust-Gated Predictive Reallocation (TGPR)

Probleemstelling

Gedecentraliseerde multi-robot taakallocatie (MRTA) vertrouwt doorgaans op marktgebaseerde veilingen (bijv. Contract Net Protocol, CBBA) die uitgaan van betrouwbare berichtlevering. In real-world implementaties is draadloze communicatie verliesgevoelig door padverlies, interferentie en, cruciaal, persistente hardwarematige degradatie (bijv. versleten antennes, vermogensbeperkte zenders) die per robot varieert.

Huidige robuuste methoden pakken dit aan door ofwel de berichtfrequentie te verlagen ofwel taken pas opnieuw toe te wijzen nadat een fout is gedetecteerd. Deze benaderingen behandelen communicatieonzekerheid als een planningshinder die moet worden geabsorbeerd door herpogingen of periodieke reconciliatie, in plaats van als een leerbare grootheid. Bovendien richten bestaande "vertrouwensmodellen" in MRTA zich op de capaciteit van een agent om een taak te voltooien, niet op de betrouwbaarheid van de communicatieverbinding zelf. Dit leidt tot twee primaire faalmodi in verliesgevoelige netwerken:

1. Uithongering (Starvation): Een taak wordt toegekend, maar de bevestiging gaat verloren; de coördinator wacht eindeloos terwijl geen enkele andere robot ingrijpt.
2. Duplicatie: De coördinator loopt in de tijd (timeout) omdat hij wacht op een vertraagde (maar niet verloren gegane) bevestiging en wijst de taak opnieuw toe, waardoor twee robots dezelfde taak uitvoeren.

Methodologie: Trust-Gated Predictive Reallocation (TGPR)

TGPR is een gedecentraliseerd veilingmechanisme dat een per-robot Bayesiaanse schatting van de round-trip communicatiebetrouwbaarheid integreert in de standaard announce-bid-award-acknowledge cyclus. Het wijzigt de beslissingslogica van de coördinator zonder het onderliggende berichtprotocol te veranderen.

1. Bayesiaanse Round-Trip Vertrouwensschatting

De coördinator houdt een Beta posterior distributie, $Beta(\alpha_i, \beta_i)$, bij voor elke robot $i$, die de waarschijnlijkheid van een succesvolle award-acknowledgment round trip vertegenwoordigt.

• Updates: De parameters worden bijgewerkt op basis van geobserveerde uitkomsten (succes bij vertraging $\delta$ of timeout).
• Verval (Decay): Een verv factor $\lambda < 1$ maakt het mogelijk dat de schatting niet-stationaire condities bijhoudt (bijv. hardwarefouten die halverwege de missie ontstaan).
• Vertrouwensscore: De geschatte betrouwbaarheid is $\hat{p}_i = \alpha_i / (\alpha_i + \beta_i)$.

2. Vertrouwings-gedisconteerde Biedevaluatie

In tegen tegenover standaardveilingen die bieders rangschikken op basis van ruwe nut ($u_{ij}$), rangschikt TGPR kandidaten op basis van een vertrouwings-gedisconteerd nut:
$$\hat{u}_{ij} = u_{ij} \cdot \hat{p}_i$$
Dit geeft prioriteit aan robots die zowel bekwaam als bereikbaar zijn, waarbij onderscheid wordt gemaakt tussen een zeer capabele robot met een historisch slechte verbinding en een iets minder capabele robot met een betrouwbare verbinding.

3. Adaptieve Predictieve Timeout

In plaats van een vaste globale timeout berekent TGPR een per-robot timeout $\tau_i$ op basis van de geleerde vertragingsdistributie:
$$\tau_i = \text{clip}(\mu_i + z\sigma_i, \tau_{min}, \tau_{max})$$
Dit biedt geduld aan historisch trage maar betrouwbare verbindingen, terwijl het snelle herstel mogelijk maakt voor verbindingen die nog nooit zijn gefaald.

4. Confidence-Gated Unilateral Bystander Claim

Om het hersteltraject te verkorten, kunnen stationaire robots die een award-broadcast onderscheppen een taak opeisen als de aangekondigde deadline verstrijkt zonder dat er een bevestigingsbroadcast volgt.

• Mechanisme: Als een bystander (omstander) de taak opeist, probeert de coördinator de oorspronkelijke houder te annuleren.
• Grace Window: Een korte gratieperiode voorkomt dat de claim van een bystander botst met de eigen fallback-logica van de coördinator, wat ervoor zorgt dat de herverdelingslogica van de coördinator niet voortijdig wordt gepreëmpt.

Belangrijkste Bijdragen

1. Testbed Ontwerp: Een discrete-event simulator met een kanaalmodel met afstandsafhankelijke verliezen, transient jamming en een persistente, leerbare per-robot hardware-betrouwbaarheidsfactor ($h_i$). De auteurs tonen aan dat zonder deze persistente differentiatie, vertrouwensgebaseerde mechanismen geen voordeel bieden ten opzichte van afstandgebaseerde heuristieken.
2. TGPR Algoritme: Een nieuw veilingmechanisme dat vertrouwings-gedisconteerd bieden, adaptieve per-robot timeouts en bystander-claims combineert.
3. Gecontroleerde Evaluatie: Een systematische vergelijking met drie baselines (Naive fixed-timeout, Exponential-backoff, en Periodic reconciliation) over vijf kanaalkwaliteit-regimes, twee teamgroottes en een hardware-heterogeniteit-ablatie.

Experimentele Resultaten

De studie evalueerde 4.800 main-sweep proeven en 2.000 ablatieproeven.

Efficiëntie en Verspillingsreductie

TGPR vertoont statistisch significante verbeteringen in communicatie-efficiëntie en reductie van verspilling:

• Duplicaat Uitvoering: Verminderd met 23,9% ten opzichte van de naive baseline (10,65% vs. 13,99%).
• Messaging Overhead: Verminderd met 13,6% (167,2 vs. 193,6 berichten per voltooide taak).
• Trend: Deze voordelen nemen toe naarmate de kanaalkwaliteit verslechtert en naarmate het deel gedegradeerde hardware groter wordt.

Taakvoltooiingspercentage

In tegenstelling tot de hypothese dat betrouwbaarheid-bewuste allocatie de algehele doorvoer zou verbeteren, verbetert TGPR de algehele taakvoltooiingsgraad niet.

• Prestaties: In slechte en zeer slechte kanaalcondities voltooit TGPR aanzienlijk minder taken dan de naive fixed-timeout baseline (bijv. 0,434 vs. 0,466 in extreme condities bij $N=25$).
• Ablatie Bevinding: Het gat in voltooiingspercentage vergroot zich (van 1,1% naar 1,9%) naarmate het deel gedegradeerde hardware toeneemt, wat de verwachting tegenspreekt dat het vertrouwensmechanisme zijn kosten zou "terugverdienen" door slecht werkende hardware te vermijden.

Grondoorzaak van de Kosten in Voltooiingspercentage

De auteurs herleiden het tekort in het voltooiingspercentage tot twee specifieke mechanismen:

1. Onbegrensde Variantie-inflatie: Onder aanhoudend hoge faalpercentages zorgt de adaptieve timeout-update regel voor een inflatie van de vertragingsvariantie ($\sigma_i$) zonder voldoende verval. Dit zorgt ervoor dat geleerde timeouts naar boven toe richting de maximale limiet ratelt, waardoor het onderscheidend vermogen tussen gezonde en gedegradeerde robots verloren gaat.
2. Vaste Latentiebelasting: De grace window van de bystander-claim introduceert een vaste vertraging bij elke herstelcyclus, wat onder frequente fouten cumulatieve kosten met zich meebrengt.

Parametersensitiviteitsanalyse bevestigt dat het verlagen van de timeout-multiplier ($z$) de voltooiingsgraad kan herstellen ten koste van een toename in duplicaten en messaging, wat duidt op een controleerbare afweging in plaats van een fundamenteel defect.

Betekenis en Claims

Het artikel positioneert TGPR niet als een universele verbetering van eenvoudige veilingen, maar als een gespecialiseerde oplossing voor specifieke operationele beperkingen.

• Operationele Grens: TGPR is een aanzienlijke winst voor implementaties waar communicatiebandbreedte schaars is of gedupliceerde fysieke inspanning (bijv. batterijverbruik, slijtage van actuatoren) de beperkende factor is. In dergelijke scenario's is de reductie in verspilling en messaging overhead de primaire succesmetriek.
• Beperking: Wanneer de enige metriek de ruwe taakvoltooiingsdoorvoer is in harde omgevingen, is TGPR geen strikte verbetering ten opzichte van simpelere fixed-timeout baselines en kan het zelfs onderpresteren.
• Wetenschappelijk Inzicht: De studie biedt een kritiek tegenvoorbeeld voor de aanname dat "vertrouwen" altijd helpt. Het toont aan dat vertrouwensgebaseerde mechanismen een persistente, leerbare signaal (hardwaredegradatie) vereisen om effectief te zijn; in vloten waar onbetrouwbaarheid puur positioneel en transient is, bieden vertrouwensmechanismen geen meetbaar voordeel.
• Eerlijke Rapportage: De auteurs rapporteren expliciet de afweging, waarbij zij opmerken dat de kosten van het mechanisme (verminderde voltooiingsgraad) groter worden met hardware-heterogeniteit, wat indruist tegen de initiële verwachtingen, en schrijven dit toe aan specifieke algoritmische gedragingen (variantie-inflatie) in plaats van externe factoren.

Het werk concludeert dat TGPR een waardevolle, kwantificeerbare afweging biedt: het opofferen van enige taakvoltooiingsdoorvoer om de communicatie-overhead en dubbele uitvoering aanzienlijk te verminderen, mits de implementatieomgeving een persistente, leerbare hardware-betrouwbaarheidsdifferentiatie vertoont.