cursus Inleiding Adaptieve Systemen Opleiding Kunstmatige Intelligentie 2020-21

Opdracht 3: slime mould

Inleiding

De Physarum polycephalum (“veelkoppig slijm”) is een gele slijmzam. De Physarum staat er om bekend dat deze via vertakkingen goed zijn weg kan vinden naar relatief verafgelegen voedsel. Er zijn bijzonder veel beschrijvingen, plaatjes en videos te vinden over deze slijmzwam.

Tot aan, zeg, 2005 werd Physarum voornamelijk gemodelleerd met behulp van differentiaalvergelijkingen. Deze modellen waren vrij complex. In 2012-2014 hebben de Britse onderzoekers Jeff Jones en Andrew Adamatzky een alternatief model voorgesteld om Physarum te modelleren. Dit model werkt met deeltjes (“particles” , “mieren”) die geurstoffen afscheiden en bewegen aan de hand van die geurstoffen. Videos van Jones' werk zijn te vinden op zijn YouTube kanaal.

Globale omschrijving

Implementeer het Jones' Physarum model in Netlogo. Baseer je model in het bijzonder op Fig. 1 (p. 1349) en Fig. 2 (p. 1351) uit “Influences on the formation and evolution of Physarum Polycephalum inspired emergent transport networks” (Jones & Adamatzky, 2011), zie materiaal.

Randvoorwaarden

Hier staat wat moet. Bij afwijking van randvoorwaarden worden punten in mindering gebracht.

  1. Afmetingen en kleuren. Tijdens het werken aan je app bezit het canvas waarschijnlijk minder patches en is de turtle- en patch size groter, maar bij inleveren is het veld [-120, 120] × [-120, 120] patches groot, patch size 2. Deeltjes zijn lime, size 2.5. Voedselplekken (dit is een breed) zijn rond, rood, size 8. Het moet mogelijk zijn de vorm van de deeltjes via een widget (GUI-element) in te stellen, met tenminste twee keuzes: "circle" en "default" ("circle" animeert namelijk het snelst). Feromoon varieert van wit tot geel (zie hieronder).
  2. Voorafgaand aan de animatie kunnen instellen van: turtle-shape, of deeltjes centraal (op patch 0 0) danwel verspreid danwel op voedselplekken starten. Aantal voedselplekken.
  3. Dekkingsgraad. Met dekkingsgraad x% wordt bedoeld x/100 kans op een mier op elke patch bij initialisatie. Dus met dekkingsgraad 50% is bij initialisatie bij elke patch kans 0.5 dat er een mier op die patch verschijnt. Bij deze methode kan nooit meer dan één mier op een patch verschijnen.
  4. Voorafgaand en tijdens animatie kunnen instellen van: stapgrootte (step size, S), lengte van antennes (sensor offset, SO), hoek tussen middelste en buitenste antennes (sensor angle, SA), draaihoek (rotation angle, RO), of co-locatie is toegestaan (of het is toegestaan dat mieren mogen wandelen naar reeds bezette patches), kans op sterven per mier per tik (let op: deze kans is in de regel erg klein).
  5. Tijdens animatie: mieren opnieuw kunnen verspreiden, alle feromoon wegnemen, de combinatie van de eerste twee acties (verspreiden en wegnemen) tegelijkertijd, N mieren tegelijkertijd (steeds op een willekeurige plek) toevoegen, N willekeurige mieren tegelijkertijd wegnemen, mieren zichtbaar maken, mieren onzichtbaar maken, feromoon zichtbaar maken, feromoon onzichtbaar maken, voedselplekken zichbaar maken (met een apart breed), etensplekken onzichtbaar maken (zodat etensplekken alleen nog te herkennen zijn aan de hoge feromoonintensiteit). Feromoon deposito ratio (hoeveel feromoon per tik per mier wordt neergelegd), feromoon verdampings-snelheid, feromoon diffusie-snelheid (= feromoon verspreidings-snelheid), feromoon-intensiteit op voedselplekken.
  6. Feromoon-helderheid. Een kritisch onderdeel van de animatie is een goede weergave van de hoeveelheid feromoon per patch. Weinig feromoon is donkergeel, en veel fermoon is felgeel, bijna wit. Je app moet in staat zijn de helderheid van het fermoon handmatig te regelen. Bijvoorbeeld, als alle feromoon-sporen wit zijn, dan moet de helderheid kunnen worden bijgeregeld zodat er ook weer gele feromoonsporen onstaan, die dan aangeven dat daar verhoudingsgewijs minder fermoon ligt.
  7. Uitleg. Leg in de documentatie uit hoe je app werkt. Leg vooral uit wat afwijkt van de standaard.
Met de standaard-implementatie kunnen maximaal negen punten worden verdiend.

Extra features

Het tiende punt kan worden verdiend door het aanbrengen van een extra feature. Als meerdere features zijn geïmplementeerd telt het best uitgevoerde feature, dit ter beoordeling van de TA. Sterren geven de moeilijkheidsgraad danwel arbeidsintensiviteit aan. Geef in de info-tab onder een kopje EXTRA FEATURES aan wat de extra features zijn. Als er geen extra features zijn, dan komt onder het kopje “Geen.” te staan. Het ontbreken van een onderdeel uit de basis-implementatie kan niet worden gecompenseerd met een extra feature.

  1. Zegen mieren. Sta op enig moment (door een druk op de knop) toe dat alle mieren vanaf dat moment feromoon mogen dumpen. (Normaliter mogen mieren pas feromoon dumpen als zij tenminste één keer een etensplek zijn gepasseerd.)
  2. Help mieren. Een knop die bij indrukken N mieren (of alle mieren) naar een willekeurige voedselplek teleporteert.
  3. Feromoon.* Fermoon kunnen sprayen met verschillende intensiteit en spray-straal (dikte). Feromoon kunnen opzuigen met verschillende intensiteit en straal. Een willekeurig plek bombarderen met feromoon. Op een willekeurige plek alle feromoon weghalen.
  4. Scenarios (I).* Knoppen waarmee je bepaalde scenarios kunt instellen. Bijvoorbeeld:
    to set-scenario-5
      ; start
      set start-formation "start bij voedsel"
      ...
      ; food
      set nr-of-food-pellets 7
      set radius-of-food-pellets 4
      set minimal-distance-between-food 6
      ...
      ; pheromone
      set pheromone-visible? true
      set pheromone-deposit-rate 50
      set pheromone-factor-at-food 500
      ...
      ; mieren
      set density (dekkingsgraad) 20%
      set ants-visible? true
      set ant-step-size 3.0
      set pre-blessed? false
      set co-location-allowed false
      ...
    end
    
  5. Scenarios (II).* Jones en Adamatzky's benadering kent drie scenarios: filamenteuze condensatie (filamentous condensation), filamenteus voederen (filamentous foraging), en plasmodiale krimp (plasmodial shrinkage). Bij filamenteuze condensatie worden mieren met een lage dekkingsgraad (typisch 2%) over het canvas verspreidt. Bij filamenteus voederen worden mieren met een lage dekkingsgraad (typisch 2%) bij aanvang van de simulatie gedropt op voedselplekken. Bij plasmodiale krimp worden mieren met een hoge dekkingsgraad (typisch 50%) over het convexe omhulsel van de voederplekken verspreidt, waarna de mierenpopulatie langzaam afneemt (typisch sterfte met een kans 0.00025 per mier per tik). Voor meer informatie, zie Jones' artikel. Het convexe onhulsel van een set punten berekenen is niet heel makkelijk. Hier is code.
  6. Randen.** Laat mieren niet op een torus, maar op een rechthoek lopen. Vind een elegante manier om mieren te ontmoedigen hoeken in te lopen. Of vind een manier om mieren te stimuleren uit hoeken te lopen.
  7. Voedselplek-manipulatie.** Implementeer (en selectie van) de volgende (observer) acties: haal voedselplek weg, voeg voedselplek toe, versleep voedselplek, verwijder alle voedselplekken, creëer voedselplekken volgens een wiskundige formule (bijvoorbeeld op afstand R en om de 300), creëer voedselplekken volgens een van tevoren opgegeven patroon. (De laatste actie is bewerkelijk om te implementeren, want: hoe ga je dat patroon uitlezen?)
  8. Water.** Sta toe dat sommige patches water bevatten, van 0% tot 100% water. Het idee is dat bij water patches fermoon veel sneller verdampt. Faciliteer de creatie en wegneming van dergelijke patches door het aanbrengen van paint en suck widgets. Denk na over een goede visalisatie van dergelijke patches
  9. Blokkades.** Sta toe dat sommige patches niet beloopbaar zijn. Faciliteer de creatie en wegneming van dergelijke patches en denk na over visualisatie.
  10. Steiner bomen.*** Een Steiner boom voor N voedselplekken is de kortste constructie die al deze voedselplekken verbindt. Vind parameters die er voor zorgen dat het feromoon convergeert naar een Steiner boom. (Let op: je kunt convergentie naar Steiner bomen alleen maar stimuleren maar nooit afwingen en zeker niet wiskundig bewijzen.) Zie hier een voorbeeld hoe een deeltjesmodel van Physarum een Steiner boom vormt. Zie hier een enthousiaste uitleg over Steiner bomen.
  11. Soorten mieren.*** Creëer twee of meer soorten mieren. Elke soort gedraagt zich anders dankzij andere parameterinstellingen.

Aanwijzingen

  1. Hou het klein. Werk in het begin met een kleiner canvas en een grotere patch size.
  2. Voortbeweging. In de bronnen staan verdere details, onder andere hoe mieren zich kunnen voortbewegen.
  3. Feromoondiffusie. Netlogo kent een primitief diffuse. Dit primitief wordt door de observer aangeroepen.
  4. Status “blessed”. In Jones' model mogen mieren alleen beginnen fermoon neer te leggen als zij tenminste één keer een etensplek zijn gepasseerd. Niet eerder. Een mier die tenminste één keer een etensplek is gepasseerd wordt door Jones aangeduid als blessed.
  5. Voedselplekken. Een voedselplek kan worden gemodelleerd door in een cirkel met een bepaalde straal (“straal-van-voedsel-plek”) elke patch elke tik de hoeveelheid fermoon op een constante hoge hoeveelheid, C, te zetten. Een voedselplek kan woren gevisualiseerd door er turtles van een bepaald breed (met een bepaalde kleur en vorm) neer te zetten, bv. cirkels met een straal die even groot is als de straal van de voedselplek. Maar voedselplekken zijn natuurlijk ook al te herkennen door de hoge hoeveelheid feromoon.
  6. Ingewikkelde turtle shapes. Kosten rekentijd. Gebruik in plaats daarvan kleine cirkeltjes. Je animatie loopt dan sneller.
  7. Raadpleeg bronnen. De slides “Zwerm-Intelligentie en Slime Moulds” bevat veel informatie. Ook het 2011 artikel van Jones en Adamatzky bevat veel informatie.
  8. Rechthoek of torus? Het makkelijkst is om mieren over een torus te laten lopen. Zo hoef je niet na te denken over de vraag wat een mier moet doen als deze niet verder kan.
  9. Rechthoek? Als je kiest voor een rechthoek, dan zul je zien dat mieren de neiging hebben doodlopende paden te vormen naar hoeken. Een manier om dit te ontmoedigen is om buiten een bepaalde afstand van de oorsprong de fermoon elke tik (elk tijdsframe) op 0 te zetten.
  10. Co-locatie. In Jones' model is het zo dat als een mier zich niet mag verplaatsen (omdat zijn doelpatch al is bezet door een andere mier en co-locatie verboden is), dat die mier dan geen fermoon deponeert. Merk op dat patches tussen de huidige positie van de mier en de doelpatch wel bezet mogen zijn. In Jones' model mogen mieren dus “haasje over” doen om hun doelpatch te bereiken. Of dat realistisch is? Tja...

Nakijkmodel

Het volgende nakijkmodel zal worden gebruikt.

  1. Gratis punt.
  2. Documentatie: in code, in tab-blad, *.png
  3. Kwaliteit GUI.
  4. Kwaliteit code.
  5. Correcte micro-werking (feromoon snuiven, feromoon deponeren, roteren).
  6. Correcte macro-werking (ontstaan van paden tussen voedselplekken, plausibele dynamiek).
  7. Voorafgaand aan de animatie kunnen instellen van: dekkingsgraad (gemiddeld aantal mieren per patch), of mieren centraal danwel verspreid danwel op voedselplekken starten. Aantal voedselplekken.
  8. Voorafgaand en tijdens animatie kunnen instellen van:
  9. Tijdens animatie:
  10. Extra feature.

Bronnen

  1. “Influences on the formation and evolution of Physarum Polycephalum inspired emergent transport networks” (Jones & Adamatzky, 2011), zie materiaal.
  2. The emergence and dynamical evolution of complex transport networks from simple low-level behaviours” (Jones, 2015).
  3. Slides “Slime moulds en mierenkolonieoptimalisatie”.


*Naast de algemene randvoorwaarden voor de programmeeropdrachten en de algemene randvoorwaarden voor de programmeeropdrachten die specifiek in Netlogo worden uitgevoerd. Zie de pagina met clausules.


Laatst gewijzigd op woensdag 24 maart 2021, om 11:17 uur ——— translate to ru, ro, or en ——— Auteur(s): Gerard Vreeswijk