PWS percolatie en verkeersstromen

pascalv

Hallo Lennard,

Bedankt voor je reactie. Door een drukke periode reageren we nu pas. We zijn eigenlijk nog aan het nadenken over een geschikt experiment. We zijn uitgegaan van percolatie in koffie en hoe dat werkt. Daarna hebben we gekeken hoe we in Python iets konden maken waarmee je percolatie kan vaststellen. Dat hebben we nu voor een rooster uitgezocht waarvan we de afmetingen kunnen aanpassen. Daarmee kunnen we de drempelwaarde bepalen. De percolatie hangt af van p, dus de kans of een cel in het rooster geblokkeerd is of niet. Dus van dit model zijn we uitgegaan.

We wilden eigenlijk iets doen met de verkeersstromen op Schiphol en hoe je daar iets over kan zeggen met de theorie van percolatie. We hebben wel cijfers over het aantal passagiers dat Schiphol dagelijks kan verwerken, maar het is ons nog niet helemaal duidelijk hoe we dat kunnen gebruiken met ons model.
Het zal afhangen van het aantal mensen dat op een dag naar Schiphol komt, hoeveel incheckpunten en poortjes er zijn en hoeveel personeel er werkt en hoeveel vluchten er zijn. Dit zal dan op een of andere manier de waarde van p bepalen.

Dat wordt waarschijnlijk erg ingewikkeld als overal rekening mee gehouden moet worden. Dus onze vraag is hoe we dit op een eenvoudige manier verder kunnen aanpakken.
Het artikel van Wang over percolatie en verkeer is voor ons al vrij ingewikkeld. We hebben nog wel wat uitgezocht. Een van de Chinese auteurs heeft later nog iets over percolatie geschreven: https://ieeexplore.ieee.org/document/8272794. maar dat is alleen een samenvatting. De laatste auteur (Havlin) heeft het meeste onderzoek gedaan over dit onderwerp: Percolation_on_Spatial_Anisotropic_Spatial_Networks en Interdependent transport via percolation backbones in spatial networks

Deze onderzoeker uit Israël hebben we benaderd omdat we zijn mailadres konden achterhalen. Die heeft onze vraag naar de code doorgestuurd naar een onderzoeker in China en die heeft weer verwezen naar de eerste auteur die nu in Washington zit. Dit is zijn antwoord dat we deze week ontvingen:

[link text]([link url](link url))The codes were developed in C++ not in Python. Honestly, I myself have switched to Python 7 years ago; the C++ codes are kind of barriers to me now.. I would suggest that you follow the rules defined in the paper and code them in Python on your own. I believe this would be even easier for you: some codes like BFS algorithm are directly available from python package, so that you do not need to code them from scratch like me using C++.
Another issue with the code sharing is that these codes are likely integrated to some bigger project that is patented by the lab PI. I am not sure what procedures I need to take to share the code.

Dus hij heeft ons uiteindelijk niet verder kunnen helpen met code. Het zelf omzetten van het artikel in een uitgebreid percolatie-model in Python is voor ons nogal lastig, omdat onze kennis maar beperkt is. We hadden zelf na veel uitzoekwerk al wat in Python opgezet (zie hieronder) maar dit was nog een hele klus. Zou dat nog makkelijk aan te passen zijn? Verder hebben we voor ons werkstuk maar beperkte tijd dus we willen eigenlijk kiezen voor een eenvoudige aanpak waar we verder mee aan de slag kunnen.
Zou jij nog iets voor ons kunnen betekenen of heb je misschien nog wat suggesties voor ons?

Met vriendelijke groet,
Matthias en Pascal

percolatie_plot_1

import numpy as np
import imagesc as im
import matplotlib as plt
from scipy.ndimage import label
def union(a, b):
labels[find(b)] = find(a)
def find(a):
while labels[a] != a:
a = labels[a]
print (a)
return a

print("Er worden 2 figuren gemaakt in kleur en zwart wit")
print("na afloop worden de waarden die bij de bezettingskans horen weergegeven")
print("en er wordt gemeld of er sprake is van percolatie")
print(" ")

grid_size = input('Wat zijn de afmetingen van het grid? (gescheiden met komma) ')
grid_size = tuple(int(item) for item in grid_size.split(','))
p = float(input('Wat is de bezettingskans? (tussen 0 en 1, decimale punt) '))

print(type(grid_size))

print(grid_size)

grid = np.empty(shape = grid_size, dtype= int)
for i in range(np.size(grid, 0)): # Gehele grid invullen met bezetting
for j in range(np.size(grid, 1)):
grid[i, j] = np.random.binomial(1, p)
# binominale verdeling uitvoeren met p als kans op succes

print(labels)

label_grid, aantal_groepen = label(grid)
print(label_grid)

print(aantal_groepen)

im.plot(label_grid, origin='lower',cmap = 'rainbow')
cluster_nummers = np.arange(1,label_grid.max()+1)

print(cluster_nummers)

np.random.shuffle(cluster_nummers)
cluster_nummers = np.append(0,cluster_nummers)

print(cluster_nummers)

label_grid_shuffled = cluster_nummers[label_grid]
im.plot(label_grid_shuffled, origin='lower',cmap = 'gray')
a =np.intersect1d(label_grid[0,:],label_grid[len(label_grid)-1,:])
percolatie_clusters= a[a != 0]
if percolatie_clusters.any():
print("Er is sprake van percolatie")
print(percolatie_clusters)
else:
print("Er is geen sprake van percolatie")

Percolatie_plot_2

import numpy as np
import imagesc as im
import matplotlib.pyplot as plt
from scipy.ndimage import label

grid_size = input('Wat zijn de afmetingen van het grid? (gescheiden met komma) ')
grid_size = tuple(int(item) for item in grid_size.split(','))
aantal_runs = input('Hoevaak itereren? ')

p = float(input('Wat is de bezettingskans? '))

p= np.linspace(0,1,num=50)
aantal_percolaties = np.zeros(len(p))
for l in range(len(p)):
for k in range (int(aantal_runs)):
grid = np.empty(shape = grid_size, dtype= int)
for i in range(np.size(grid, 0)): # Gehele grid invullen met bezetting
for j in range(np.size(grid, 1)):
grid[i, j] = np.random.binomial(1, p[l])

        label_grid, aantal_groepen  = label(grid)
        # print(label_grid)
        a =np.intersect1d(label_grid[0,:],label_grid[len(label_grid)-1,:])
        # print(a)
        percolatie_clusters= a[a != 0]
        if percolatie_clusters.any():
            aantal_percolaties[l] =  aantal_percolaties[l] +1

print(aantal_percolaties)

plt.plot(p, aantal_percolaties)

naming the x axis

plt.xlabel('x - axis')

naming the y axis

plt.ylabel('y - axis')

giving a title to my graph

plt.title('Aantal percolatie vs p voor '+ aantal_runs +' runs')

function to show the plot

plt.show()

lennardd

Hey @pascalv,

Goed om te zien dat jullie er al zo mee bezig zijn, maar vervelend dat het nog niet is gelukt om code te vinden. Er zijn een aantal richtingen die je op kunt met je werkstuk. Welke je uiteindelijk kiest is afhankelijk van ervaring in Python, tijd die je hebt en hoe nauwkeurig model je wilt hebben. Hoe dan ook blijft een model altijd een vereenvoudiging van de werkelijkheid en je zult de verkeersstromen op Schiphol dus nooit perfect zullen beschrijven. Dat is iets wat je moet accepteren, maar intussen wel proberen om het model zo realistisch mogelijk te maken. Ook zul je meer gedetailleerde data van Schiphol moeten vinden (bezoekers per uur, aantal vluchten, aantal poortjes/incheckpunten). De hoeveelheid personeel zou ik niet meenemen omdat het dan erg snel erg complex wordt. Als je bepaalde data niet kunt vinden, is het ook prima om een inschatting te maken.

Het eerste wat je kunt doen is beginnen met een erg simpel model (het model dat jullie noemen in je eerste post) en dit uitbreiden zodat er aan de ene kant passagiers bijkomen (door de poortjes) en aan de andere kant passagiers weg gaan (met het vliegtuig). Dit is waarschijnlijk de meest simpele optie die het minste tijd kost. Als je dit dan hebt geprogrammeerd zou je dit model nog wat kunnen verfijnen en uitbreiden.

Het tweede wat je kunt doen is een wat complexer model opzoeken dat al gecodeerd is en werkt met verkeersstromen. Je zult dan zelf minder nieuwe dingen moeten programmeren, maar het begrijpen van deze code kost vaak minstens zoveel tijd. Je zou bijvoorbeeld eens naar deze code kunnen kijken. Omdat zulke algoritmes vaak erg lang zijn, is het lastig om te bepalen wat er precies gebeurt. Hier zou ik jullie eventueel wel bij kunnen helpen of je kunt contact opnemen met de auteur van de code.

De derde optie is een paper opzoeken waar een algoritme in beschreven staat en dit nabouwen, maar tenzij het erg duidelijk beschreven staat, zou ik dit afraden. Papers zijn zo geschreven dat een ingewikkeld model in een enkele alinea wordt samengevat, wat het voor een leek erg lastig maakt om te reproduceren.

Ten slotte kun je ook proberen om contact te zoeken met een data-analist binnen schiphol, daar fysiek langs gaan en kijken wat hij voor jullie kan betekenen met betrekking tot data en misschien zelfs een simpel model. Ik zou jullie sowieso aanraden om dit te proberen. Een beproefde methode is via LinkedIn wat mensen opzoeken, de 1 maand gratis premium activeren, hen wat berichten sturen. Er is er allicht één met wie je in gesprek kunt. Zij zullen je hierin wel verder kunnen helpen.

Als je tegen problemen aanloopt met het coderen kan ik jullie wellicht helpen, misschien ook door een keer te videobellen en mee te kijken met jullie code. Als jullie dit willen, zou ik wel willen vragen om jullie code als bijlage toe te voegen, nu kan ik er niet zo veel mee.

Hopelijk heb ik jullie hiermee op wat ideeën kunnen brengen, maar als je verder nog vragen hebt, hoor ik het graag!

Groetjes,
Lennard

pascalv

Hallo Lennard,

Vanwege een toetsweek een late reactie. We willen graag het eenvoudige model aanpassen, door er de variabele tijd aan toe te voegen. Hoe kunnen wij onze code die we nu hebben als bijlage toevoegen?

Vriendelijke groet,
Pascal en Matthias

lennardd

Hey @pascalv,

Via de button met het documentje:

Ik ziet het wel verschijnen.

Groetjes,
Lennard

pascalv

Hallo Lennard,

Hierbij de codes v02 en v03 van het simpele model, waarbij het grid en de p-waarden vastliggen in de code. Bij de code v04 kunnen de afmetingen van het grid en de bezettingskans. worden opgegeven. Dit geeft gekleurde plots. Met v05 kan de afmeting van het grid worden opgegeven en het aantal iteraties bij een bepaalde waarde van p. Het gedeelte tussen 0 en 1 is hierbij opgesplistst in 50 p-waarden. Dat geeft een plot waarin te zien is bij welke drempelwaarde van p er percoltaie plaatsvindt.

Wat we zouden willen is dat er op een of ander manier iets van tijd in het proces in te bouwen is. Dan gaat het vooral om code v04. Als het zou gaan om de doorstroming van een hal in Schiphol heb je steeds een veranderend aantal instroom en uitstroom. De route kan geblokkeerd worden door personen die stoppen of in groepjes ergens staan. Ook zou je bepaalde cellen in het grid voortdurend willen blokkeren (p=0) omdat daar iets staat waar men omheen moet. En de bezettingskans kan ook samen hangen met de instroom. Dus bij hoge instroom zou de p laag zijn, omdat er weinig doorstroom is.

Mocht je suggesties hebben hoe dit in te bouwen is in onze code dan zou dat mooi zijn.

Vriendelijke groet,
Pascal en Matthias

PS het gebruk van de document-button geeft de melding : Fout Onvoldoende rechten om deze actie uit te voeren.

Dus hieronder de codes als tekst toegevoegd (dit ging de vorige keer niet helemaal goed).

Percolatie_v02

import random
import numpy as np
import matplotlib.pyplot as plt
from scipy.ndimage import label

def generate_percolation_matrix(n, p):
return np.random.rand(n, n) < p

def percolates(matrix):
labeled_matrix, num_labels = label(matrix)
top_labels = labeled_matrix[0, :]
bottom_labels = labeled_matrix[-1, :]
common_labels = np.intersect1d(top_labels, bottom_labels)
return len(common_labels) > 0

def visualize_percolation(matrix):
plt.imshow(matrix, cmap='binary')
plt.title("Percolation Matrix")
plt.colorbar()
plt.show()

Define matrix size and percolation probability

matrix_size = 10
percolation_probability = 0.7

Generate the percolation matrix

percolation_matrix = generate_percolation_matrix(matrix_size, percolation_probability)

Visualize the percolation matrix

visualize_percolation(percolation_matrix)

Check if percolation occurs

if percolates(percolation_matrix):
print("Percolation occurs!")
else:
print("No percolation.")

Percolatie_v03

import random
import numpy as np
import matplotlib.pyplot as plt
import sys

def generate_percolation_matrix(n, p):
return np.random.rand(n, n) < p

def percolates(matrix):
def dfs(x, y):
if x < 0 or x >= matrix.shape[0] or y < 0 or y >= matrix.shape[1]:
return False
if matrix[x, y] == 0:
return False
if visited[x, y]:
return False

    visited[x, y] = True

    if x == matrix.shape[0] - 1:
        return True

    # Recursively check neighboring cells
    result = (dfs(x + 1, y) or
              dfs(x - 1, y) or
              dfs(x, y + 1) or
              dfs(x, y - 1))
    return result

visited = np.zeros_like(matrix, dtype=bool)
for y in range(matrix.shape[1]):
    if matrix[0, y] == 1:
        if dfs(0, y):
            return True

return False

def visualize_percolation(matrix):
plt.imshow(matrix, cmap='binary')
plt.title("Percolation Matrix")
plt.colorbar()
plt.show()

Define matrix size and percolation probability

matrix_size = 10
percolation_probability = 0.4

Generate the percolation matrix

percolation_matrix = generate_percolation_matrix(matrix_size, percolation_probability)

Visualize the percolation matrix

visualize_percolation(percolation_matrix)

Check if percolation occurs

if percolates(percolation_matrix):
sys.stdout.write("Percolation occurs!\n")
else:
sys.stdout.write("No percolation.\n")

Percolatie_v04

import numpy as np
import imagesc as im
import matplotlib as plt
from scipy.ndimage import label
def union(a, b):
labels[find(b)] = find(a)
def find(a):
while labels[a] != a:
a = labels[a]
print (a)
return a

grid_size = input('Wat zijn de afmetingen van het grid? (gescheiden met komma) ')
grid_size = tuple(int(item) for item in grid_size.split(','))
p = float(input('Wat is de bezettingskans? '))

print(type(grid_size))

print(grid_size)

grid = np.empty(shape = grid_size, dtype= int)
for i in range(np.size(grid, 0)): # Gehele grid invullen met bezetting
for j in range(np.size(grid, 1)):
grid[i, j] = np.random.binomial(1, p)
# binominale verdeling uitvoeren met p als kans op succes

# print(labels)

label_grid, aantal_groepen = label(grid)
print(label_grid)

print(aantal_groepen)

im.plot(label_grid, origin='lower',cmap = 'rainbow')
cluster_nummers = np.arange(1,label_grid.max()+1)

print(cluster_nummers)

np.random.shuffle(cluster_nummers)
cluster_nummers = np.append(0,cluster_nummers)

print(cluster_nummers)

label_grid_shuffled = cluster_nummers[label_grid]
im.plot(label_grid_shuffled, origin='lower',cmap = 'rainbow')
a =np.intersect1d(label_grid[0,:],label_grid[len(label_grid)-1,:])
percolatie_clusters= a[a != 0]
if percolatie_clusters.any():
print("Er is sprake van percolatie")
print(percolatie_clusters)
else:
print("Er is geen sprake van percolatie")

percolatie_v05

import numpy as np
import imagesc as im
import matplotlib.pyplot as plt
from scipy.ndimage import label

grid_size = input('Wat zijn de afmetingen van het grid? (gescheiden met komma) ')
grid_size = tuple(int(item) for item in grid_size.split(','))
aantal_runs = input('Hoevaak itereren? ')

p = float(input('Wat is de bezettingskans? '))

p= np.linspace(0,1,num=50)
aantal_percolaties = np.zeros(len(p))
for l in range(len(p)):
for k in range (int(aantal_runs)):
grid = np.empty(shape = grid_size, dtype= int)
for i in range(np.size(grid, 0)): # Gehele grid invullen met bezetting
for j in range(np.size(grid, 1)):
grid[i, j] = np.random.binomial(1, p[l])

        label_grid, aantal_groepen  = label(grid)
        # print(label_grid)
        a =np.intersect1d(label_grid[0,:],label_grid[len(label_grid)-1,:])
        # print(a)
        percolatie_clusters= a[a != 0]
        if percolatie_clusters.any():
            aantal_percolaties[l] =  aantal_percolaties[l] +1

print(aantal_percolaties)

plt.plot(p, aantal_percolaties)

naming the x axis

plt.xlabel('x - axis')

naming the y axis

plt.ylabel('y - axis')

giving a title to my graph

plt.title('Aantal percolatie vs p voor '+ aantal_runs +' runs')

function to show the plot

plt.show()

pascalv

Zo te zien gaat het nu ook weer niet goed. Er worden dik en dungedrukte regels van gemaakt. Is er nog een andere manier om documenten tioe te voegen?

pascalv

Of kunnen we misschien rechten krijgen om bestanden aan een bericht toe te voegen?

lennardd

Hey @pascalv,

Dat is vervelend! Kun je dan misschien je code uploaden naar Google Drive of OneDrive en een gedeelde link (alleen bekijken) hier op het forum plakken?
Dan kan ik jullie code wat beter bekijken.

Groetjes,
Lennard

pascalv

@lennardd zegt in PWS percolatie en verkeersstromen:

Dat is vervelend! Kun je dan misschien je code uploaden naar Google Drive of OneDrive en een gedeelde link (alleen bekijken) hier op het forum plakken?
Dan kan ik jullie code wat beter bekijken.

Hallo Lennard,

Hierbij de links.
v02 https://drive.google.com/file/d/1kMhvoBBt3At6HitCF77h1w-5RfxAyeZK/view?usp=sharing
v03 https://drive.google.com/file/d/1DnLZ1n618dXdLieiR9J_H2Sok7upxG74/view?usp=sharing
v04 https://drive.google.com/file/d/1clvg3uoPcWSxH2q0dgeBA4DK9EJpLU61/view?usp=sharing
v05 https://drive.google.com/file/d/1IfgYTrtnU4wf4Chb4JUR95vVYXP7EQV1/view?usp=sharing

Met vriendelijke groet,
Pascal en Matthias

lennardd

Hey @pascalv,

Excuses voor mijn late reactie! Het lukte me in eerste instantie niet om wat tijd te vinden me te verdiepen in jullie code. Vandaag wel! De eerste twee bestanden kan ik runnen, de laatste twee lukte niet omdat daarin wat verouderde functies van Numpy worden gebruikt. Het idee is me echter wel duidelijk. Om een blokkade in te bouwen is het belangrijk om eerst tijdsafhankelijkheid in te bouwen, anders heeft een blokkade ook niet zoveel zin. Hiervoor zou je bijvoorbeeld kunnen kijken naar de volgende code in Java die dit op een heel eenvoudige manier doet. Hierbij is zowel tijdsafhankelijkheid ingebouwd als een blokkade zodat je kunt onderzoeken wat dit voor effect heeft in de tijd. Enige punt is dat je dit nog wel moet vertalen naar Python, maar de belangrijkste ideeën kun je hier in ieder geval uithalen.

Alternatief kun je deze code gebruiken die ik even snel heb gemaakt vanmiddag. Ik had geen tijd om from scratch alles te maken, dus ik heb ChatGPT gevraagd een mooi stukje code te schrijven en hier de onvermijdelijke fouten uitgehaald. Hopelijk helpt dit jullie wat op weg. Het aantal tijdstappen is variabel evenals de grootte van het grid en de output is een mooie animatie van de percolatiematrix. Wat je kunt doen om vaste blokkades in te voeren is door een list objects te maken met punten die je moet overslaan in de loop (if (i,j) in objects: continue o.i.d.). Ook is er nu nog niets gemaakt wat de in- of uitstroom van passagiers kan simuleren, maar dit is in ieder geval al een stap in de juiste richting.

Nogmaals excuses voor mijn late reactie, dit was helaas niet binnen mijn standaard 3 dagen. Hopelijk heb ik jullie hiermee toch wat kunnen helpen, maar als je verder nog vragen hebt, hoor ik het graag! Ook een keer videobellen kan altijd, laat maar weten.

Groetjes,
Lennard

pascalv

Lennard bedankt!

Bij het draaien (grid 10, p=0.6) valt op dat vooral de linkerkant zwart is, dus daar is vaker percolatie. Kun je verder nog de tijdsduur per time-step instellen? Nu gaat het zo snel dat je niet kunt zien hoe de percolatie verloopt. Verder is niet duidelijk welke code in java precies bedoeld wordt, waar staat die precies? Die tekst met java lijkt ook veel op https://rstudio-pubs-static.s3.amazonaws.com/241232_eebe419a0aaa4eb89398ee2a61ad3dc2.html. In dat stuk staat ook dat er geen wiskundige oplossing is om de drempelwaarde te bepalen en dat je die alleen maar kunt schatten. Klopt dat? We willen ook nog een praktisch experiment doen met percolatie, maar we zoeken daar eigenlijk formules bij die we hiervoor kunnen gebruiken., zijn die er ook?

Alvast bedankt voor een reactie.

Met vriendelijke groet,
Matthias en Pascal

lennardd

Hey @pascalv,

Om de tijdstap aan te passen kun je in FuncAnimation toevoegen interval=1000, waarbij het interval in ms wordt gemeten. Op de gestuurde pagina staan links naar Java files, e.g. VerticalPercolation.java. De tekst van jullie link is inderdaad een op een vergelijkbaar met de tekst van Princeton University die ik stuurde; deze wordt ook als bron vermeld voor jullie pagina. Voor formules en wiskundige oplossingen zou je eens een boek over percolatie moeten openslaan. Ik denk dat dit al veel zou helpen om wat meer de diepte in te duiken. Je kunt bijvoorbeeld eens kijken naar een van de volgende boeken die gebruikt worden op veel universiteiten. Hoewel dit vooral gaat om de toepassingen van percolatie in natuurkunde, blijft de wiskunde erachter natuurlijk hetzelde:
https://drive.google.com/drive/folders/19eRYoR4YjE37_GVfgFfLOn0w81vU7Aqo?usp=sharing

Hopelijk heb ik jullie hiermee kunnen helpen, maar als je verder nog vragen hebt, hoor ik het graag!

Groetjes,
Lennard

pascalv

Lennard, bedankt voor je snelle reactie, dit werkt! Een vraag die we nog hebben is hoe we de p-waarde in de praktijk kunnen interpreteren als het gaat over de doorstroming op Schiphol, dus wat invloed kan hebben op de p-waarde. Heb je daar nog suggesties voor?

Vriendelijke groeten,
Pascal en Matthias.

lennardd

Hey @pascalv,

In de praktijk is de p-waarde niet meer dan de dichtheid van de bezoekers. Je zou dat uit kunnen drukken als N/M waarbij N het aantal bezoekers is en M het maximum aantal bezoekers. Zo heb je dus ook een waarde tussen 0 en 1. Volgens mij hangt dit voornamelijk af van twee factoren: de instroom op het vliegveld en de uitstroom op het vliegveld. Als de uitstroom lager is dan de instroom zal de p-waarde steeds hoger worden en uiteindelijk percolatie optreden.

Laat maar weten als jullie nog meer vragen hebben!

Groetjes,
Lennard