Karma Mechanisms for Decentralised, Cooperative Multi Agent Path Finding

Titel: Karma-mechanismen voor Decentralisatie en Cooperatieve Multi-Agent Path Finding (MAPF)

Auteurs: Kevin Riehl, Julius Schlapbach, Anastasios Kouvelas, Michail A. Makridis (ETH Zürich)

---

1. Probleemstelling

Multi-Agent Path Finding (MAPF) is een fundamenteel coördinatieprobleem waarbij meerdere agenten (bijv. robots in een magazijn) paden moeten berekenen van start- naar doellocaties zonder botsingen.

• Uitdagingen:
  • Centralisatie: Bestaande optimale oplossers (zoals Conflict-Based Search - CBS) garanderen een optimale oplossing, maar hebben een exponentiële computationele complexiteit. Dit maakt ze ongeschikt voor grote schaal en real-time toepassing.
  • Decentralisatie: Bestaande decentrale heuristieken zijn sneller, maar leiden vaak tot suboptimale resultaten en grote ongelijkheden in kosten (bijv. sommige agenten moeten veel langer wachten of omwegen maken dan anderen).
  • Beperkte Communicatie: In grote systemen is globale observatie of directe coördinatie vaak niet haalbaar.

Het paper richt zich op het vinden van een balans tussen efficiëntie (totale doorvoer) en eerlijkheid (verdeling van de last van replanning over de agenten) in een decentrale omgeving zonder globale prioriteitsstructuur.

2. Methodologie

De auteurs stellen een decentraal coördinatiekader voor dat gebaseerd is op Karma-mechanismen. Dit is een vorm van kunstmatige, niet-handelbare valuta die het verleden van coöperatief gedrag van agenten vastlegt.

A. Het Karma-concept

• Elke agent $i$ heeft een Karma-balans $k_i$ (een geheel getal).
• Deze balans fungeert als een intern krediet dat de geschiedenis van coöperatie encodeert.
• Het mechanisme werkt als een distributieve integrale feedbackregelaar: agenten die in het verleden vaak hebben moeten replannen (en dus "opofferingen" hebben gedaan), krijgen een hogere Karma-balans, wat hen in de toekomst prioriteit geeft bij conflictoplossing.

B. Bilaterale Onderhandeling met Karma

Conflicten worden opgelost via een bilateraal onderhandelingsproces tussen twee agenten ($i$ en $j$) die een botsing dreigen te hebben.

1. Kostenberekening: Beide agenten berekenen de kostenstijging ($\Delta_i$ en $\Delta_j$) die gepaard gaat met het replannen van hun traject om de botsing te vermijden.
2. Onderhandelingsregel: In plaats van alleen te kijken naar de directe kostenstijging (zoals bij egoïstische of altruïstische regels), wordt de Karma-balans meegewogen met een parameter $\tau$.
   De agent die moet replannen ($r$) wordt bepaald door:
   $$\text{Kies } j \text{ als } \Delta_j + \tau k_j < \Delta_i + \tau k_i$$
   (Waarbij $\tau$ de invloed van de Karma-balans bepaalt.)
3. Update van Karma: Na de onderhandeling worden de balanssen bijgewerkt:
   • De agent die replant ($r$) krijgt Karma toegevoegd: $k_r \leftarrow k_r + \Delta_r$.
   • De andere agent ($\bar{r}$) verliest evenveel Karma: $k_{\bar{r}} \leftarrow k_{\bar{r}} - \Delta_r$.
   • Dit zorgt ervoor dat agenten die vaak "opofferingen" doen, in de toekomst minder snel hoeven te replannen.

C. Casestudy

Het mechanisme wordt getest in een lifelong Multi-Agent Pickup-and-Delivery (MAPD) scenario in een robotmagazijn:

• Omgeving: Rastergrafiek met kinematische beperkingen (richtinggevoeligheid).
• Taken: Random gegenereerde ophaal- en bezorgtaken.
• Vergelijking: Het Karma-mechanisme wordt vergeleken met:
  • Token-passing (sequentiële planning).
  • Egoïstische onderhandeling (replan alleen als kostenstijging $\leq 0$).
  • Altruïstische onderhandeling (replan als kostenstijging lager is dan die van de tegenpartij).

3. Belangrijkste Bijdragen

1. Integratie van Incentives: Het introduceren van een decentraal mechanisme dat directe economische prikkels (Karma) gebruikt om langdurige wederkerigheid en eerlijkheid te bevorderen zonder centrale controle.
2. Dynamische Prioriteit: Het creëren van een endogene prioriteitsstructuur die zich aanpast op basis van de geschiedenis van coöperatie, in plaats van een statische volgorde.
3. Balans tussen Efficiëntie en Eerlijkheid: Het tonen aan dat men de dispariteit in service-tijden (wie moet het langst wachten) significant kan verkleinen zonder de algehele systeem-efficiëntie (totale doorvoer) te offeren.

4. Resultaten

De evaluatie op verschillende rastergroottes (5x5 tot 15x15) met wisselend aantal agenten toont het volgende:

• Token-passing: Voltooit het minst aantal taken en heeft de langste doorlooptijden vanwege de starre, sequentiële planning.
• Egoïstisch vs. Altruïstisch:
  • Egoïstische regels zijn minder efficiënt in het verminderen van het totale aantal A*-zoeken (herplanningen) dan altruïstische regels.
  • Altruïstische regels presteren beter in totale kosten, maar leiden nog steeds tot ongelijke lastverdeling.
• Karma-mechanisme:
  • Efficiëntie: Bereikt een algehele doorvoer en gemiddelde kosten die vergelijkbaar zijn met de beste decentrale heuristieken (altruïstisch).
  • Eerlijkheid: Vermindert de dispersie (variantie) in service-tijden en taakduur aanzienlijk. Dit betekent dat de wachttijden en omwegen veel eerlijker over de agenten worden verdeeld.
  • Parameter $\tau$: Een waarde van $\tau = 0.5$ bleek ideaal om een balans te vinden tussen kostenminimalisatie en het egaliseren van de last. Bij te hoge $\tau$ wordt de efficiëntie iets lager ten gunste van extreme eerlijkheid.

5. Betekenis en Conclusie

Dit onderzoek toont aan dat incentive-based feedback mechanisms (zoals Karma) een krachtige, principieel onderbouwde aanpak zijn voor schaalbare en eerlijke coördinatie in decentrale multi-agent systemen.

• Praktische Impact: Het biedt een oplossing voor systemen waar centrale optimalisatie te duur is, maar waar "wie het eerst komt, het eerst maalt" (egoïstisch) of starre prioriteiten (token-passing) leiden tot onacceptabele ongelijkheid in service.
• Toekomstperspectief: De auteurs wijzen op de noodzaak van verder onderzoek naar stabiliteit, convergentiegaranties, en de invloed van verschillende Karma-verdelingsregels (bijv. "pay-to-peer" vs. "pay-to-society") en limieten op de balans.

Samenvattend: Het Karma-mechanisme transformeert decentrale conflictoplossing van een lokaal kosten-minimalisatieprobleem naar een systeem dat langdurige indirecte wederkerigheid bevordert, waardoor robuustere en eerlijkere robotzwermen mogelijk worden.