cursus Inleiding Adaptieve Systemen Opleiding Kunstmatige Intelligentie 2020-21

Opdracht 2: Hadimassa

Inleiding

Het simuleren van mensenmassa's (Eng.: crowd simulation) kent veel toepassingen. Zo is het bijvoorbeeld een belangrijk hulpmiddel om te bepalen of omgevingen waar veel mensen bij elkaar komen veilig zijn. Denk aan stadions, vliegvelden en festivalterreinen. Over Corona wil ik het niet heben.

Globale omschrijving

Implementeer met een eenvoudige flockingtechniek een mensenmassa die zich beweegt van een bron (bijvoorbeeld ingang) naar een doel (bijvoorbeeld uitgang). De ruimte kan worden ingericht met obstakels. Er wordt aangenomen dat mensen op ieder moment volledige kennis hebben van de kortste weg naar het doel. Het probleem is alleen dat andere mensen dit doel ook hebben en dus in weg kunnen lopen ...

Voorkennis: flocking, zie TCBoN, Sec. 16.3.

Werking

Bewegingsalgoritme

(*) Overal waar “zijn” staat kan ook “haar” worden gelezen. Maar eigenlijk doen we hier aan antropomorfisme.

Vloerplan

Randvoorwaarden

Hier staat wat moet.* Bij afwijking van randvoorwaarden worden punten in mindering gebracht. Sommige randvoorwaarden zijn opgesteld om later de beoordeling van je programma te vergemakkelijken.

Tips

  1. Perceptie. Het gezichtsveld en de persoonlijke ruimte kunnen gelijktijdig worden geïmplementeerd met het primitief in-cone.
  2. Afstand. Voor de Manhattan-metriek (zie boven) kan neighbors4 worden gebruikt.
  3. Draaien. Om slechts een stukje in de goede richting te draaien kan het primitief subtract-headings worden gebruikt.
  4. Draaisnelheid. Als er gedraaid wordt bij vrijheid, is een draaisnelheid van 20 (per keer) een aardige keuze. Maar andere snelheden werken ook. Kijk wat werkt! Varieer desnoods met een tijdelijk aangebrachte schuifbalk.
  5. Perceptie vs. actie. Merk op dat perceptie wordt bepaald door het gezichtsveld en de persoonlijke ruimte, maar draaien-bij-vrijheid door de Moore omgeving. Afstand wordt dan weer bepaald door de Manhattan-metriek, dus door de Von Neumann omgeving. Dus er spelen hier 3 verschillende omgevingen. Je kunt het er inderdaad over hebben of dit waarheidsgetrouw en/of intuïtief is, echter deze discussie valt een beetje buiten de opdracht.
  6. Een stapje terug. forward my-speed / -8 lijkt goed te werken. Maar andere snelheden werken ook.
  7. Volledig draaien naar een veld. Kan met face.
  8. Patch sets. Als het vloerplan eenmaal is gedefinieerd (of tussendoor is gewijzigd) is het handig meteen daarna vier of zelfs vijf patch sets te definiëren: bronvelden, doelvelden, hindernisvelden, zwarte velden, en bewandelbare velden (= alle niet-hindernisvelden). De naamgeving hier is een suggestie. Het wordt aangemoedigd zelf geschikte namen te kiezen voor deze patch sets. Herinner: doelvelden zijn inwendige rode velden, dus rode velden met alleen rode velden in hun Moore-omgeving.
  9. Kortste afstand. Voor alle bewandelbare velden kan de kortste afstand tot het doel eenvoudig berekend worden met een reverse floodfill. Dit werkt zo: alle doelvelden bezitten kortste afstand nul tot het doel. Vervolgens kijk je welke bewandelbare velden (waarvan de kortste afstand tot het doel nog onbekend is) grenzen aan bewandelbare velden waarvan de kortste afstand tot het doel al wél bekend is. Deze velden krijgen kortste afstand gelijk aan 1 + kortste afstand van een bewandelbare buurveld met minimale kortste afstand tot het doel. Dit proces wordt herhaald totdat van alle bewandelbare velden de kortste afstand tot het doel berekend is. (Zie ook “Snippets”.)
  10. Signaleren. Dingen signaleren kun je met een zg. “vlag”. Initeel staat de vlag op FALSE. Gebeurt er iets wat wilde bijhouden (bv. een slider is verschoven), dan zet je vlag op TRUE.
  11. Herberekenen van kortste afstand. Na elke paint actie kun je laten signaleren dat het vloerplan is gewijzigd.
  12. Elementaire functies. Netlogo bezit geen tekenfunctie (Eng. sign function), en het bezit ook geen generator voor de uniforme verdeling. Definieer deze zelf in aparte functies. Netlogo bezit al wel een generator voor de uniforme verdeling op het eenheidsinterval, te weten random-float.

Snippets

Hieronder volgen snippets (codefragmenten). De snippets zijn facultatief. Het is niet verplicht ze te gebruiken, we hebben misschien zelfs liever dat je je eigen code schrijft. De snippets behoren niet tot de opdracht, en zijn zeker niet bedoeld als stappenplan. De snippets zijn meer bedoeld om je op weg te helpen mocht je vastlopen. De werking van de snippets is niet gegaranderd, en de practicumleiding is niet verplicht om er uitleg over te geven.

  1. Patches kleuren met de muis
    to paint [ c ]
      if mouse-down? [
        ask patch mouse-xcor mouse-ycor [
          set pcolor c
        ]
      ]
    end
  2. Draai een stukje in de goede richting
    right rotation-angle * sign subtract-headings (towards goal-patch) heading
    
    De draaihoek heb je zelf gedefinieerd (bv. 20). Het doelveld is eerder in je programma bepaald. De functie sign is de tekenfunctie: sign(x) = 1 als x > 0, -1 als x < 0, en 0 anders. Netlogo bezit zelf geen tekenfunctie.

  3. Voorbeeld van een reverse flood fill
    ; initially, all patches are very distant from the source
    ask patches [ set dist TOO_FAR ]
    
    ; inner red patches have distance zero to goal
    ask red-patches with [ all? neighbors [ pcolor = red ] ] [ set dist 0 ]
    
    ; do a reversed flood fill to determine, for the rest of the walkable patches,
    ; the distance to the source
    loop [
     ; from patches with unknown shortest distance to goal that have neighbors
     ; with known shortest distance to goal, it is possible to compute their
     ; shortest distance to goal.  such patches are called "the front"
     let front walkable-patches with [ dist = TOO_FAR and any? neighbors4 with [ dist < TOO_FAR ] ]
     if not any? front [ stop ]
     ask front [
       set dist 1 + min [ dist ] of neighbors4 with [ dist < TOO_FAR ]
     ]
    ]
    
    De constante TOO_FAR zul je zelf moeten definiëren. Je kunt 'm op 9E9 zetten (kortste manier om een vrij groot getal in Netlogo op te schrijven), of, intelligenter, world-width ^ 2 + world-height ^ 2.

Extra

Extra punten kunnen worden verdiend door het aanbrengen van extra features. Het aantal extra punten hangt af van het gewicht van een feature en de implementatie-kwaliteit. Geef, voor de puntentelling, duidelijk aan wat je extra features zijn, onder een kopje “Extra features” in de “Information” tab. Voorbeelden van extra features:

Overig

Over de titel van dit document: Hadimassa was een populair satirisch Nederlands televisieprogramma dat van 1967 tot 1972 door de VARA werd uitgezonden. Hadimassa werd in 1970 de bekroond met de Zilveren Nipkowschijf, een prestigieuze Nederlandse televisieonderscheiding.

Nakijkmodel

Het volgende nakijkmodel zal worden gebruikt.

   ------------------------------------------------------

    1. gratis punt
    2. complete, nette, en intuitieve GUI
    3. randvoorwaarden (kleuren, veldgrootte, stapgrootte, ..)
    4. correct gedrag op wandelaar-niveau
    5. correcte plot
    6. kwaliteit code   ; functionele one-liners zijn cool
    7. executiesnelheid ; maar imperatieve constructies werken meestal sneller ...
    8. documentatie (in code, in tab, *.png)

   ----- cijfer acht ------------------------------------

    9. best of extra feature
   10. "

   ----- cijfer tien ------------------------------------

Een uitgewerkt voorbeeld

Wijzigingen

18 maart 2020
  • “Elke wandelaar bezit een constante stapgrootte die bij initalisatie gekozen wordt uit een uniforme verdeling op het interval [0.7, 1.3].” gewijzigd naar “Elke wandelaar bezit een constante stapgrootte die bij initalisatie gekozen wordt uit een uniforme verdeling op het interval [0.7x0.35, 1.3x0.35].” Het getal 0.35 is daarmee nu wel het midden.
  • -->


    *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 dinsdag 30 maart 2021, om 11:29 uur ——— translate to ru, ro, or en ——— Auteur(s): Gerard Vreeswijk