Wat is een multi-agentsysteem

Een andere vorm van kunstmatige intelligentie is die van een multi-agentsysteem (MAS). In de naam multi-agentsysteem zit het woord ‘multi’, dat staat voor meervoudig. Een multi-agentsysteem is dus letterlijk een systeem met meerdere agents. Multi-agentsystemen zijn gecomputeriseerde systemen die taken verrichten die niet of moeilijk door een individuele agent of een allesomvattende applicatie kan worden gedaan.

Multi-agentsystemen overlappen met het concept agent-based modelleren (ABM). Het doel van een agent-based model is het verkrijgen van inzicht in het gedrag dat agents door interactie met elkaar vertonen. De agents in een agent-based model hoeven niet noodzakelijk intelligent te zijn en er wordt meestal gekeken naar verklaringen op basis van simpele regels in natuurlijke systemen (zwerm gedrag van vogels, groepsgedrag van mensen, mierensnelwegen). Multi-agentsystemen worden juist ontwikkeld om technische problemen op te lossen. Dus niet om gedrag te verklaren maar om gedrag te verkrijgen, Toepassingsgebieden voor MAS zijn onder andere online handel, handelen bij rampen, serious gaming en surveillance. Ben je meer of ook geïnteresseerd in het zoeken naar de oorzaak van gezamenlijk gedrag van organismen (ABM) dan is de verdiepingsmodule modelleren bij het keuze thema computational science iets voor jou. Later in deze sectie bekijken we aan aantal agent-based modellen die in multi-agentsytemen worden gebruikt.

Gedrag

In de introductie in AI technieken hebben we het begrip agent geïntroduceerd als een zelfstandig functionerend deel van een AI applicatie. Functioneren betekent hier het tonen van gedrag. Een zelfrijdende auto is een agent van een AI applicatie die getraind is om zelfstandig te handelen in het verkeer. Het hele verkeer bestaat uit agents (let wel een menselijk persoon is ook een agent). De auto heeft als doel om personen in de auto veilig van plek A naar plek B te brengen. De auto neemt de huidige verkeersituatie (is omgeving) waar. De auto zal handelen ten opzichte van de verkeerssituatie in het belang van de inzittenden van de auto. Stel dat er twee zelfrijdende auto’s op elkaar afrijden. Beide zelfrijdende auto’s zullen dan waarschijnlijk uitwijken om een botsing te voorkomen. In dit geval overlappen de doelen van deze agents en vertonen ze coöperatief gedrag.

Figuur 1: De agent in zijn omgeving

Het is zeker niet zo dat de doelen van agents tot samenwerking leiden. Bij online handel is het doel van jouw agent om de winst voor de eigenaar van de agent te vergroten. Als er een vaste hoeveelheid aandelen in omloop is dan is er concurrentie om die aandelen en dus concurrentie tussen jouw agents en de andere agents in het handelsproces. De agents vertonen nu competitief gedrag. Ander voorbeeld: stel je voor dat er kunstmatige intelligentie in je koelkast zit. Zodra bij jou thuis de boter op is, probeert de koelkast-agent een zo goed mogelijke deal te sluiten. Hij probeert dan dus de beste boter te kopen voor de laagste prijs. De verkoop-agents van de winkels die boter verkopen, hebben een tegengesteld belang. Zij proberen een zo hoog mogelijke prijs te krijgen voor een pak boter. De verkoop-agents zijn in dit geval dus competitief. Toch moet er tot een overeenkomst gekomen worden. De agents gaan hierover met elkaar in onderhandeling.
Een mix van concurrentie en samenwerking is ook mogelijk. Onderzoek in die richting in robotica vindt onder andere plaats bij robotvoetbal.

Omgeving

Een agent bevindt zich in een omgeving. In het Engels spreken we van een environment. In deze omgeving kan een agent acties uitvoeren. Het hangt af van de aard van de agent in welke omgeving deze kan handelen. Je hebt bijvoorbeeld omgevingen die puur softwarematig zijn. Een game zoals World of Warcraft is hier een voorbeeld van. De agents kunnen hierbinnen van alles doen, zoals een gevecht starten. De zelfrijdende auto is een agent in de echte wereld die uit andere agents bestaat. In figuur 1 zie je een schematische weergave van een agent en de omgeving. Binnen multi-agent systemen kunnen we de volgende omgevingen onderscheiden:

• Virtuele omgevingen. In bijvoorbeeld games, simulaties en online handel kom je die tegen.
• Discrete omgevingen. De agents kunnen zich in een eindig aantal posities bevinden en ook slecht een eindig aantal handelingen verrichten. Een schaakspel is een dergelijke omgeving.
• Continue omgevingen. De verkeerssituatie is een dergelijke omgeving. Een agent kan overal in de ruimte plaatsnemen en zijn eigen positie verandert ook geleidelijk.

Agents

Het is nog wel even nuttig om stil te staan bij de verschillende typen agents. In een omgeving is eigenlijk alles waarop een agent moet reageren zelf weer een agent. Dus in de verkeerssituatie is niet alleen de zelfrijdende auto een agent, maar ook de wandelaar, de fietser, de bestuurder van een auto. Zelfs de verkeersheuvels en verkeersborden worden als agents beschouwd. Dit leidt tot de volgende grove indeling voor agents:

• Passieve agents of "agent zonder doel" (verkeersborden, een aandeel of in een spel een wapen of schat );
• Actieve agents met een simpel doel (robot in een distributie magazijn);
• Intelligente agents (zelfrijdende auto, mens, dier).

Agent in de omgeving

Actieve en intelligente agents nemen hun omgeving in meer of minder detail waar. Afhankelijk van de taak en training reageert een agent. Iedere actie van een agent verandert de toestand van die agent, maar tegelijkertijd ook de omgeving van zichzelf en andere agents. Bijvoorbeeld één van de doelen van een bestuurder van een auto is ‘bots nergens tegenaan’. Als er een obstakel in beeld komt waar de auto niet omheen kan zal de auto tot stilstand moeten worden gebracht. De bestuurder remt. De toestand van de agent wordt anders. Positie en snelheid veranderen. Een agent in het achterop komend verkeer neemt hopelijk die verandering waar, want de omgeving voor deze agent is ook veranderd. Kortom een multi-agentsysteem is een samenspel van waarnemingen, acties en reacties.

Kenmerken van multi-agentsysteem

Er zijn veel verschillende kenmerken van multi-agentsystemen. We hebben tot dusver al een aantal kenmerken genoemd. We zetten de belangrijkste kenmerken van een multi-agentsysteem hier op een rijtje:

De organisatie binnen een multi-agentsysteem is decentraal

Een belangrijk kenmerk van een multi-agentsysteem is dat het decentraal is. Dat houdt in dat er niet zoiets bestaat als een coördinator of centraal bestuur. De agents hebben tot op zekere hoogte autonomie, wat betekent dat ze zelf bepalen wat en wanneer ze iets doen om hun doelen te behalen. Denk weer even terug aan de zelfrijdende auto. Elke auto gaat zijn eigen weg. Er is geen centraal beheer dat alle zelfrijdende auto’s bestuurt.

Agents functioneren binnen een omgeving

Een agent moet zich in een omgeving bevinden. Binnen zo’n omgeving moet een agent het volgende kunnen doen:

• Observaties van de omgeving. De agent moet een deel van de omgeving kunnen waarnemen. In het geval van een zelfrijdende auto of andersoortige robot gebeurt dat door middel van sensoren en camera’s.
• Acties binnen de omgeving. De agent moet invloed kunnen uitoefenen op een omgeving door middel van acties. Bij een zelfrijdende auto of andersoortige robot zou je spreken van actuatoren. Een actuator is het tegengestelde van een sensor: er komt geen informatie binnen, maar er wordt iets naar buiten gebracht. Remmen, sturen of toeteren zouden acties kunnen zijn van een zelfrijdende auto.

Agents doen aannames

Agents nemen altijd maar een deel van hun omgeving waar. Dit is niet omdat deze agents niet alles mógen zien, maar eerder omdat de omgeving voor een agent te complex is om volledig te kunnen overzien. Agents zijn dus niet alwetend over hun omgeving, maar hebben kennis over die omgeving die ook wel aannames over de omgeving worden genoemd. Een aanname is dus iets wat een agent eerder heeft waargenomen en geleerd, maar wat niet per se hoeft te kloppen. Bijvoorbeeld, een ‘stofzuiger-agent’ heeft met zijn sensor een plantenbak waargenomen en legt vast dat er op die locatie een plantenbak staat. Als iemand vervolgens de plantenbak weghaalt en de agent heeft deze actie niet waargenomen, dan heeft de agent nog de, inmiddels onjuiste, kennis dat de plantenbak er nog staat. Pas als de agent weer opnieuw op de oude plek van de plantenbak komt, neemt deze waar dat de aanname niet meer klopt en wordt deze aangepast.

Agent-based modellen in multi-agentsystemen

Hoewel agent-based modellering niet het zelfde is als een multi-agentsysteem worden er wel elementen uit het onderzoek in agent-based modellering ingezet in multi-agentsystemen om doelen van de applicaties te kunnen bereiken. We bekijken een competitief en een samenwerkend model.

Competitief: Speltheorie

Agents zijn onafhankelijk en moeten dus zelf beslissingen nemen zonder dat er mensen bij betrokken zijn. In een multi-agentsysteem moet elke agent ook rekening houden met de acties van anderen en de consequenties daarvan. Soms, maar niet altijd, zijn de doelen van agents onderling tegenstrijdig of wel competitief. Als dat het geval is, dan moet een agent slimme keuzes maken. Daarbij kan speltheorie toegepast worden.

Figuur 2: Toepassingsgebieden speltheorie

Bij speltheorie worden situaties vertaald naar punten die deelnemers kunnen verdienen. Net zoals bij een spelletje is het doel van een agent om zo veel mogelijk punten te scoren. Een agent kan een bepaalde actie doen, waardoor een bepaalde situatie ontstaat. Voor elke situatie die kan ontstaan, verdienen de agents die meedoen meer of minder punten.

Speltheorie wordt vaak geïllustreerd door middel van een matrix. In de matrix staan de acties van alle spelers tegenover elkaar. Hieronder zie je een voorbeeld van hoe je het spelletje steen-papier-schaar in een matrix zet:

Figuur 3: Pay-off matrix steen papier schaar

Zoals je ziet, verdienen de spelers punten als ze in een bepaalde situatie terechtkomen. In dit geval heeft elke speler drie opties om te spelen: steen, papier of schaar. De score wordt bepaald nadat beide spelers hun keuze hebben gemaakt. In dit voorbeeld heeft elke speler maar een paar opties. Er zijn echter ook situaties waarin je per speler tientallen opties hebt of nog wel meer. In het steen papier schaar spel is de puntenverdeling in balans. Er is eigenlijk geen beste keus te maken om te winnen. Dit is ook niet altijd het geval.

Neem bijvoorbeeld een schaakcomputer. Elke mogelijke zet van beide spelers is een optie en zou je in zo’n matrix kunnen zetten. Daarnaast hebben de stukken niet een gelijk waarde, een pion die een koningin slaat verdient meer punten dan andersom. Een schaakcomputer gebruikt soortgelijke matrices, maar rekent zelfs de zetten nog door: er worden dan heel veel van zulke matrices berekend. De zet met de meest gunstige uitkomst wordt dan gekozen. Speltheorie leent zich goed voor zulk soort games.

Prisoners Dilemma

De volgende opdracht is klassikaal. Voer deze uit voordat je doorgaat met de theorie.

Groepsopdracht

Benodigdheden

Per persoon een pen en een aantal papiertjes.

Voorbereiding

Verdeel de klas in groepjes van minimaal 2 personen. Het beste is als er groepjes zijn met verschillende groottes, variërend van 2 tot 6 personen.

Werking

Elk groepje speelt afzonderlijk 10 beurten. Aan het begin van elke beurt schrijft iedereen een ‘1’ of een ‘0’ op een briefje, zonder dat de anderen het zien. Als iedereen een getal heeft opgeschreven, dan laat iedereen tegelijk zijn/haar getal binnen de groep zien. Afhankelijk van de getallen die zijn opgeschreven, krijgen alle deelnemers van de groep punten. Iedereen heeft als doel om als individu de meeste punten van de klas te halen.

De regels voor het tellen van de punten zijn als volgt:

1. Wie heeft er gewonnen? Zat deze persoon in een klein groepje of een grotere?
   antwoord
   Hoe groter de groep, hoe groter de kans dat er iemand ‘0’ opschrijft. Dan is een klein groepje dus succesvoller. Maar de grootste kans om te winnen heb je tussen mensen die je goed kunt vertrouwen. Je vrienden bijvoorbeeld.
2. Heeft de winnaar vaker 1 of 0 opgeschreven?
   antwoord
   Waarschijnlijk heeft de winnaar meestal ‘1’ opgeschreven om vertrouwen te winnen. Misschien in de laatste beurten schreef hij/zij ‘0’.
3. Werd er in veel groepjes overlegd?
   antwoord
   Het is aantrekkelijk om hierbij te overleggen en een strategie af te spreken. Het probleem is alleen dat je niet weet of je de anderen kunt vertrouwen.
4. Denk je dat de uitslag anders was geweest met of zonder overleg in de groepjes?
   antwoord
   Het zal misschien niet eens veel uitmaken. Iedereen heeft een individueel doel en de medespelers zijn tegenstanders. Je hebt dan dus een motief om te liegen over de strategie die je afspreekt.
5. Zou je jouw eigen strategie aanpassen nu je ervaring hebt met dit spel?
   antwoord
   Als je met dezelfde mensen speelt, is dat misschien wel handig. Ze hebben immers de strategie die je eerder speelde al gezien.

John Nash

John Forbes Nash jr. (Bluefield, 13 juni 1928 – Monroe Township, 23 mei 2015) was een Amerikaans wiskundige, die in zijn beste tijd geniaal genoemd werd. Hij kreeg vooral bekendheid door zijn werk op het gebied van de speltheorie, die voornamelijk haar toepassing kent in de economie. Nash ontving hiervoor samen met twee andere speltheoretici, Reinhard Selten en John Harsanyi, de Prijs van de Zweedse Rijksbank voor economie (de Nobelprijs voor de Economie) in 1994. De nobelprijs kreeg hij pas na het overwinnen van psychische problemen. Over zijn leven is de film A beautiful mind verschenen.

Je hebt zojuist kennisgemaakt met het prisoners dilemma. Dit is een probleemstelling waar een agent mee te maken kan krijgen. Het probleem bij het prisoners dilemma is de keuze tussen de winst van de groep en de winst van het individu. Als alle partijen in een prisoners dilemma voor de groep kiezen (in de opdracht was dat ‘1’ opschrijven) dan wordt iedereen daar beter van. Helaas weet je niet of je iedereen kunt vertrouwen.

Het prisoners dilemma wordt vaak uitgelegd met het voorbeeld van twee verdachten bij de politie. Alice en Bob zijn opgepakt voor een overval en worden allebei afzonderlijk verhoord. De verhoorder vertelt beide verdachten hetzelfde: “Als jij meewerkt en getuigt, dan ga je vrij en zit je partner een straf van 10 jaar uit. Maar als jullie allebei tegen elkaar getuigen, dan zitten jullie allebei vast voor 5 jaar.” Alice en Bob weten dat als ze beiden weigeren te getuigen, ze beiden slechts een straf van 1 jaar krijgen. Wat is nu de meest logische optie: getuigen of weigeren? Je kunt een prisoners dilemma in een matrix vatten om het overzichtelijk te maken:

Dominante strategie

De matrix hierboven helpt om het probleem inzichtelijker te maken en te bepalen wat de meest logische keus is. Stel dat je in de schoenen van Alice staat. Als Bob kiest om te getuigen, dan krijgt Alice 5 jaar als ze zelf ook getuigt en 10 jaar als ze weigert; getuigen is dan de betere keus. Als Bob er voor kiest om te weigeren, dan krijgt Alice 0 jaar als ze getuigt en 1 jaar als ze weigert; ook hier is getuigen de betere keus. In dit voorbeeld is getuigen een zogenaamde dominante strategie. In dit geval geldt voor Alice dat de strategie om te getuigen de strategie om te weigeren sterk domineert. Dat is zo omdat alle uitkomsten voor Alice bij getuigen beter zijn dan weigeren, ongeacht welke strategie Bob kiest.

Voor Bob geldt trouwens hetzelfde: ook zijn dominante strategie is om te getuigen. Waarschijnlijk zullen Bob en Alice beiden voor hun dominante strategie kiezen en getuigen. Het is namelijk voor geen van beiden aantrekkelijk om van deze strategie af te wijken: ze krijgen dan meer straf. We spreken hier van een dominante strategie evenwicht, omdat alle partijen in hun dominante strategie blijven hangen. Een andere naam hiervoor die vaak gebruikt wordt is Nash evenwicht (naar John Nash, de bedenker hiervan).

Je kunt speltheorie niet alleen bij games gebruiken, maar ook in het echte leven. Als een zelfrijdende auto is voorbereid voor deelname in het verkeer moet deze voorbereid zijn op acties van andere agents, waaronder andere zelfrijdende auto's. Laten we ons voorstellen dat we proberen de verkeersstroom in een stad te verbeteren met behulp van een groep AI-aangedreven zelfrijdende auto's. Op zichzelf kan elk van de auto's perfect communiceren met de externe omgeving, maar het kan ingewikkelder worden als we de auto's als een groep willen laten denken. Een auto kan bijvoorbeeld in conflict komen met een andere omdat het voor beiden het handigst is om een bepaalde route te volgen. Speltheorie kan dan deel uitmaken van het leerproces om de AI verstandige keuzes uit te laten voeren.

Samenwerkend: Zwermintelligentie

Als een systeem bestaat uit een groot aantal eenvoudige eenheden die gezamenlijk een complexe taak kunnen uitvoeren, dan is er sprake van zwermintelligentie. Zoals de meeste uitvindingen van de mens, is ook de zwermintelligentie gebaseerd op een verschijnsel uit de natuur. Denk aan een zwerm spreeuwen die samen een golf aan bewegingen maken, een kolonne mieren op weg naar voedsel, trekkende gnoes in Afrika en keizerpinguïns op Antarctica.

Zwermintelligentie in AI is een bijzondere vorm van een multi-agentsysteem: het voldoet aan alle drie de genoemde kenmerken van de vorige paragraaf. Je moet zwermintelligentie zien als een subgroep van de bredere groep van multi-agentsystemen. Kenmerkend voor een taak voor zwermintelligentie is dat de agents individueel niet complex hoeven te zijn en de taak vrij eenvoudig is. Het resulterende samenwerkende gedrag lijkt dan intelligent.

Kenmerken van een zwermintelligentie:

• Er zijn veel agents.
• De agents van de zwerm reageren sterk op elkaar of werken samen.
• Het gedrag van de individuele agents voor de zwermtaak is eenvoudig.
• Het gedrag van de zwerm is complex.

Het conflict dat zelfrijdende auto's in de speltheorie sectie hebben opgeworpen zou wel eens door het inzetten van zwermintelligentie kunnen worden opgelost. Hoewel de agents een conflicterend doel hebben namelijk dezelfde koers, kan er bijvoorbeeld voor worden gekozen om dicht achter elkaar aan te rijden om zo energie uit te sparen. Voorwaarde is dan natuurlijk wel dat de auto's met elkaar kunnen communiceren. Het 5G netwerk is deels ontworpen met zulke doelen in het vooruitzicht.