🤖 AI

Scaling Multi-Agent Epistemic Planning through GNN-Derived Heuristics

Dit artikel stelt een schaalbaar multi-agent epistemisch planningsframework voor dat door Graph Neural Network-afgeleide heuristieken integreert om de zoektocht door complexe Kripke-structuren effectief te sturen, wat de prestaties van de solver aanzienlijk verbetert ten opzichte van bestaande baselines.

Oorspronkelijke auteurs: Giovanni Briglia, Francesco Fabiano, Stefano Mariani

Gepubliceerd 2026-02-09

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Giovanni Briglia, Francesco Fabiano, Stefano Mariani

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme, gelaagde puzzel probeert op te lossen. Maar hier komt de twist: je bent niet alleen maar stukjes aan het verplaatsen op een bord; je probeert ook te achterhalen wat andere mensen in de kamer denken over de stukjes, wat zij denken dat jij denkt, en wat zij denken dat jij denkt over hen.

Dit is de wereld van Multi-Agent Epistemic Planning (MEP). Dit is een vorm van computerplanning die wordt gebruikt wanneer groepen intelligente agenten (zoals robots of softwarebots) moeten coördineren, maar dit moeten doen terwijl ze hun eigen overtuigingen en wat ze weten over de geest van elkaar beheren.

Het probleem? Deze mentale jongleeract creëert een "zoekruimte" die zo groot en complex is dat computers overweldigd raken. Het is alsof je probeert een specifiek zandkorreltje te vinden op elk strand op aarde, één voor één, zonder dat je een kaart hebt.

De Oplossing: Een "Slimme GPS" voor Overtuigingen

De auteurs van dit artikel, Giovanni Briglia, Francesco Fabiano en Stefano Mariani, stellen een nieuwe manier voor om computers te helpen door deze complexe overtuigingspuzzels te navigeren. Ze hebben een systeem gebouwd dat gebruikmaakt van Graph Neural Networks (GNNs) om als een "Slimme GPS" voor deze complexe overtuigingspuzzels te fungeren.

Zo hebben ze het aangepakt, onderverdeeld in eenvoudige stappen:

1. De Kaart is een Web, Geen Lijst

In traditionele planning ziet de computer de wereld als een lijst met feiten. Maar in deze "epistemische" wereld laat de staat van het systeem zich beter beschrijven als een web van verbindingen (een Kripke-structuur). Stel je een spinnenweb voor waarbij elke knoop een mogelijke realiteit is, en de draden die de knopen verbinden, vertegenwoordigen wat verschillende agenten over elkaar geloven.

De Uitdaging: Standaard computertools zijn slecht in het lezen van deze webs. Ze proberen elke knoop te tellen, wat eeuwen duurt.
De Oplossing: De auteurs gebruikten GNN's. Zie een GNN als een speciaal soort camera die het hele web in één keer bekijkt. In plaats van knopen te tellen, "voelt" de GNN de vorm en structructuur van het web om te begrijpen hoe dicht het bij de oplossing is.

2. Leren van Ervaring (De Trainingsfase)

Voordat de computer nieuwe puzzels kan oplossen, moet hij leren wat een "goed" pad is.

De Methode: De onderzoekers creëerden een "trainingsgym". Ze lieten hun planningsoftware door duizenden oefenpuzzels gaan.
De Les: Terwijl de software de omgeving verkende, legde het elke stap die het nam en de afstand tot de finishlijn vast.
Het Resultaat: Ze voerden deze data in de GNN. De GNN leerde om naar een complex web van overtuigingen te kijken en direct te raden: "Dit ziet eruit alsof we nog 5 stappen van het doel af zijn," of "Dit ziet eruit als een doodlopende weg."

3. De "Heuristiek" (De Intuïtie)

In de informatica is een "heuristiek" een vuistregel of een intuïtief gevoel dat helpt om sneller beslissingen te nemen.

De Oude Manier: De computer zou blindelings elke mogbare route verkennen totdat hij geluk had (zoals een geblinddoekte persoon die elke muur in een doolhof aftast).
De Nieuwe Manier: De GNN fungeert als een gids. Voordat de computer een stap zet, vraat hij aan de GNN: "Is deze richting veelbelovend?" De GNN geeft een score. Als de score hoog is, duikt de computer erin. Als de score laag is, slaat hij dat pad over. Dit bespaart de computer tijd door doodlopende wegen te vermijden.

Wat Ze Ontdekten (De Resultaten)

Het team testte hun nieuwe "Slimme GPS" (die ze deep noemden) tegen de oude, blinde methoden op verschillende standaard puzzel-domeinen:

Assembly Line (Assemblagelijn): Robots die samen dingen bouwen.
Collaboration (Collaboratie): Agenten die dozen verplaatsen en met elkaar praten.
Grapevine (Geruchtenstroom): Agenten die geheimen delen in verschillende kamers.

De Uitkomst:

Minder Stappen: De GNN-gestuurde planner hoefde veel minder mogelijkheden te verkennen om de oplossing te vinden. In sommige gevallen verkende hij 10 tot 20 keer minder "kamers" in het doolhof dan de blinde methode.
Beter in de Moeilijke Zaken: Hoewel het niet perfect was bij elke enkele puzzel (sommige waren simpelweg te lastig), presteerde het consistent beter dan de oude methoden in het vinden van oplossingen, sneller en efficiënter.
Generalisatie: Zelfs toen ze de GNN trainden op het ene type puzzel en testten op een compleet ander type, werkte het nog steeds goed, wat bewees dat het de logica van het web heeft geleerd, en niet alleen de specifieke antwoorden.

De Keerzijde (Beperkingen)

De auteurs zijn eerlijk over de huidige beperkingen:

Snelheid: Hoewel de GNN de computer helpt slimmer te denken, kost de GNN zelf ook een beetje tijd om uit te voeren. Momenteel is het "denkgedeelte" langzamer dan het "zoekgedeelte". Het is alsof je een brilante navigator hebt die geweldige instructies geeft, maar die er lang over doet om te spreken.
Engineering: De auteurs merken op dat als ze de GNN sneller kunnen laten draaien (door gebruik te maken van betere computerhardware-trucs), het hele systeem nog krachtiger zou zijn.

De Kernboodschap

Dit artikel claimt niet alle AI-problemen te hebben opgelost. In plaats daarvan bewijst het dat het computers leren om de structuur van overtuigingen te "zien" met behulp van Graph Neural Networks een krachtige manier is om complexe multi-agent planning schaalbaar te maken. Het verandert een blinde, uitputtende zoektocht in een geleide, intelligente reis.

Technische Samenvatting: Schalen van Multi-Agent Epistemische Planning door GNN-afgeleide Heuristieken

Probleemstelling

Multi-Agent Epistemische Planning (MEP) is een raamwerk voor het redeneren over fysieke acties en de overtuigingen van meerdere agenten. In tegenstelling tot klassieke planning vereist MEP dat toestanden worden gerepresenteerd als Kripke-structuren (gepointerde, gerichte gelabelde grafen) om complexe overtuigingsrelaties en hogere-orde kennis te vangen. Deze representatie introduceert twee primaire uitdagingen die de schaalbaarheid belemmeren:

Intrinsieke Complexiteit: Het toepassen van transities en het evalueren van formules binnen epistemische toestanden (e-toestanden) is computationeel veeleisender dan in klassieke planning.
Gebrek aan Effectieve Heuristieken: Bestaande MEP-solvers vertrouwen vaak op onwetende zoekalgoritmen (bijv. Breadth-First Search) omdat effectieve heuristieken schaars zijn. Naarmate de planlengte toeneemt, groeit de zoekruimte exponentieel, wat leidt tot onhandelbaarheid. Hoewel recent werk (bijv. H-EFP) heeft geprobeerd heuristieken te integreren met behulp van traditionele planningsconstructen zoals planning-grafen, adresseren weinig benaderingen de schaalbaarheid van MEP via data-gestuurde methoden.

Methodologie

De auteurs stellen een data-gestuurde benadering voor om heuristieken voor MEP te genereren met behulp van Graph Neural Networks (GNNs). De kern van het idee is het trainen van een GNN-gebaseerde regressor om de "perfecte heuristiek" te benaderen—het schatten van de afstand van een gegeven epistemische toestand naar de dichtstbijzijnde doeltoestand.

1. Toerustingsrepresentatie en Embedding

Omdat e-toestanden van nature grafisch gestructureerd zijn (Kripke-modellen), zijn GNNs gekozen vanwege hun vermogen om relationele structuren te vangen. Het artikel onderzoekt drie strategieën om de "werelden" (knopen) binnen een Kripke-structuur te coderen naar numerieke vectoren die geschikt zijn voor GNN-input:

Symbolische ID-mapping: Wijst opeenvolgende integers toe aan werelden op basis van de generatievolgorde. Dit is computationeel goedkoop maar verliest de semantische gelijkenis tussen werelden en is niet-invariant over verschillende runs heen.
Hash-gebaseerde Codering: Past een hashfunctie toe op wereld-interpretaties en herhalingsindices. Dit zorgt voor consistente identificatoren over verschillende runs heen en biedt een balans tussen informatiebehoud en computationele efficiëntie.
Bitmask Codering: Representeert werelden als binaire vectoren die fluents en herhalingsindices coderen. Dit behoudt logische informatie maar brengt hogere computationele kosten met zich mee en vereist grotere modellen om te convergeren.

Om ervoor te zorgen dat de heuristieken generaliseren over verschillende doelcondities, breiden de auteurs de toestand-embedding uit met een compacte codering van het doel. Dit creëert een verenigde graaf waarin "toestandsknopen" en "doelknopen" met elkaar verbonden zijn, waardoor het model afhankelijkheden tussen de huidige toestand en specifieke doelcondities kan leren.

2. Data-generatie Pipeline

Trainingsdata wordt offline gegenereerd met behulp van een aangepaste Depth-First Search (DFS) binnen de deep planner (een herimplementatie van de state-of-the-art EFP planner).

De planner verkent de toestandsruimte tot een dieptelimiet.
Bij het bereiken van een doel keert het algoritme terug (backtracking), waarbij elke bezochte e-toestand een label krijgt dat overeenkomt met de afstand tot het dichtstbijzijnde doel.
Om de combinatorische explosie van de zoekruimte te beheersen, maakt het generatieproces gebruik van probabilistische vertakking-pruning, gerandomiseerde actievolgorde en dubbele toestand-controles.
Onbereikbare toestanden worden verwijderd om spooklabels te voorkomen, en de distributie van afstandsklassen wordt gebalanceerd om bias naar korte plannen te vermijden.

3. Modelarchitectuur

De neurale regressor is geïmplementeerd in PyTorch met behulp van PyTorch Geometric. De architectuur bestaat uit:

Bitwise Embedding: Knopen-identificatoren (bit-vectoren) en rand-attributen worden geprojecteerd in dichte embeddings via Multi-Layer Perceptrons (MLP's).
Relationele Message Passing: Twee lagen van GINEConv (Graph Isomorphism Network met Edge Convolution) aggregeren informatie van buren, waarbij rand-attributen expliciet worden opgenomen om heterogene modale afhankelijkheden te behandelen.
Graph-Level Summarization: Mean pooling aggregeert knoop-embeddings naar een vaste grootte graafrepresentatie.
Deep Residual Regression Head: Een sequentie van residuele blokken verwerkt de graaf-embedding en geeft een genormaliseerde afstandsschatting via een sigmoidfunctie.

4. Zoekintegratie

De getrainde GNN wordt geïntegreerd in de planningspipeline om een Heuristics-First Search (HFS) te sturen. De auteurs evalueren ook een variant, HFS*, die de voorspelde heuristiek $h(s)$ aanvult met de zoekdiepte $d(s)$ om een totale score $f(s) = h(s) + d(s)$ te vormen, geïnspireerd door het A*-algoritme.

Belangrijkste Bijdragen

Het artikel beschrijft vier primaire bijdragen:

Vergelijking van Embeddings: Een formele definitie en empirische vergelijking van drie Kripke-structuur embeddings (Symbolic ID, Hash, Bitmask) voor GNN-input, waarbij hash-gebaseerde codering wordt geïdentificeerd als de meest effectieve afweging.
Geautomatiseerde Pipeline: Een volledig geautomatiseerd systeem voor het genereren van trainingsdata (toestand-afstand paren) en het trainen van de GNN-regressor specifiek voor de MEP-setting.
Integratie: De integratie van de GNN-regressor in de deep planner om e-toestanden te evalueren en het zoekproces te sturen.
Uitgebreide Evaluatie: Een grondige benchmarking van de benadering tegenover onwetende zoekalgoritmen (BFS) en bestaande heuristiek-gebaseerde planners (H-EFP) over meerdere standaard domeinen.

Experimentele Resultaten

De evaluatie werd uitgevoerd op standaard MEP-benchmarks (bijv. Collaboration and Communication, Selective Communication, Grapevine) met een tijdslimiet van 600 seconden.

Schaalbaarheid vs. Onwetende Zoekalgoritmen: De GNN-gestuurde zoekopdracht verminderde het aantal uitgebreide knopen aanzienlijk vergeleken met Breadth-First Search (BFS) in de meeste domeinen. Bijvoorbeeld, in het Collaboration and Communication (CC) domein breidde de GNN-benadering gemiddeld ongeveer 65 knopen uit vergeleken met 610 voor BFS, terwijl hetzelfde aantal instanties werd opgelost.
Zoekstrategie: De HFS* variant (combinatie van heuristiek en diepte) presteerde beter dan standaard HFS, waarbij ongeveer 32% meer instanties werden opgelost en het aantal uitgebreide knopen werd verminderd.
Generalisatie: Modellen getraind op data verzameld uit meerdere domeinen (CC en GR) toonden het vermogen om te generaliseren naar onbekende domeinen, waarbij ze de BFS-baseline versloegen in termen van knoop-expansie.
Vergelijking met H-EFP: De GNN-benadering presteerde op gelijke voet met de beste individuele heuristieken in de H-EFP planner (specifiek de $S\_PG$ heuristiek), waarbij 85,33% van de testinstanties werd opgelost vergeleken met het bereik van 49–82% van H-EFP, afhankelijk van de gebruikte specifieke heuristiek.
Runtime Beperkingen: Het artikel merkt op dat hoewel de GNN de zoekruimte vermindert (uitgebreide knopen), de huidige implementatie geen optimalisaties voor batch-inferentie (zoals CUDA batching) mist. Hierdoor zijn de ruwe oplosttijden nog niet concurrerend met traditionele heuristieken, hoewel de auteurs aanvoeren dat de informatieve waarde van de heuristiek de primaire metriek is voor schaalbaarheid in deze context.

Betekenis en Claims

De auteurs positioneren dit werk als een fundamentele stap in de integratie van Machine Learning met Multi-Agent Epistemische Planning. Zij beweren dat:

Heuristiek-schaarsheid: MEP lijdt aan een gebrek aan effectieve heuristieken vergeleken met klassieke planning. Dit werk laat zien dat GNNs succesvol kunnen leren om de "perfecte heuristiek" te benaderen in deze complexe, graaf-gebaseerde setting.
Data-gestuurde Efficiëntie: Door elke e-toestand te behanden als een onafhankelijk trainingssignaal in plaats van te vertrouwen op volledige trajecten, genereert de benadering efficiënt grote datasets, wat het leren van betekenisvolle patronen uit de relationele structuur van Kripke-modellen mogelijk maakt.
Complementariteit: De auteurs beweren niet dat GNNs bestaande heuristieken onmiddellijk zullen vervangen. In plaats daarvan stellen zij dat GNN-gebaseerde heuristieken dienen als een krachtig complementair hulpmiddel om de dekking van solvers te verbeteren, vooral wanneer ze worden geïntegreerd in portfolio-gebaseerde benaderingen waar verschillende heuristieken elkaars zwaktes kunnen compenseren.

Het artikel concludeert dat hoewel engineering-optimalisaties (zoals batchverwerking) nodig zijn om de runtime-prestaties concurrerend te maken, de reductie in de complexiteit van de zoekruimte de levensvatbaarheid bewijst van het gebruik van leerbare heuristieken voor het schalen van MEP.