Een algoritme dat helpt bij het ontsnappen uit brandende gebouwen

​Het is goed mis gegaan op de tiende verdieping; er is een brand uitgebroken en het vuur verspreidt zich snel. Nog niet iedereen heeft precies door wat er gebeurt, en de brandweer is pas net aangekomen. Eén van de trappen is geblokkeerd en de accounting afdeling is in totale paniek. De besluiten die nu genomen worden, zullen het lot van de mensen in het gebouw bepalen. Welke weg kiezen ze?

Een paper uit het Journal of Computer Science en Applied Mathematical Sciences claimen dat een wetenschappelijk antwoord op deze vraag besloten ligt in Dijkstra's algoritme. Beide papers werden geschreven door een team van de technische universiteit van Maleisië in Malacca. In één van de papers wordt een algoritme beschreven en in de ander een theoretical autonomous evacuation navigation (AEN) systeem gebaseerd op het eerder beschreven algoritme.

Het idee is vrij simpel: neem een gebouw, en voeg het samen met een abstracte weergave in de vorm van een graaf (zoals die gebruikt worden in netwerktheorie). Dit komt neer op een serie van punten die met elkaar in verband staan vie lijnen. In hun versie zijn er een aantal obstakels - zoals polygonale hoeken - die vermeden moeten worden. Het is gemakkelijker om het voor je te zien als je het beeld hier beneden bekijkt. Terwijl je door de graaf heen navigeert, moet je steeds de kortste route om de obstakels heen zien te vinden.

Beeld: stanford.edu

De oplossing voor dit probleem komt van Dijkstra's algoritme. De Nederlander die kampioen is in het vinden van kortste paden (zijn algoritme helpt Google Maps bijvoorbeeld met de snelste route vinden). Het algoritme is ongelofelijk efficiënt en tegelijkertijd duidelijk en simpel.

Het bekende idee is dat je van punt naar punt beweegt, en het algoritme tijdens dit proces constant update zodat het korste pad naar alle omliggende nodes steeds bekend is. Het is echter een tijdrovend proces; als je een kleine graaf hebt, is computationeel gezien een zware taak om alle mogelijke paden constant te blijven berekenen.

Een graaf van een verdieping van een gebouw. Beeld: Samah et al

"Besluitvorming tijdens een situatie moet geperfectioneerd worden wat timing betreft om de evacuaties zonder gewonden te kunnen laten verlopen," schrijven de onderzoekers in hun paper. "De beste beslissing maken tijdens een evacuatie is heel moeilijk voor de mensen die zich in zo'n situatie bevinden. Een groot deel van de tijd weten ze niet wat ze moeten doen zonder ongeschonden de uitgang te vinden, vooral als ze onbekend zijn met het gebouw waarin ze zich bevinden. Bovendien veranderd de structuur van het gebouw tijdens gevaar, wat naar buiten komen nog moeilijker maakt."

Het AEN-systeem is gebaseerd op dynamische bewegwijzering. Dus als er een noodsituatie ontstaat, kunnen de mensen in het gebouw de meest veilige route nemen bijvoorbeeld op basis van bordjes boven de deuren: groen voor optimaal, geel voor veilig maar niet het snelst en rood voor onveilig. De papers wijden verder niet uit over de daadwerkelijke implementatie, maar het punt is vooral dat het moet gaan werken, de exacte implementatie is nog niet duidelijk.

"Dijkstra's algoritme heeft bewezen dat de voordelen van deze methode kunnen worden toegepast bij het vinden van veilige routes tijdens een evacuatie," concluderen de onderzoekers. "Dankzij dit onderzoek is het mogelijk om gevaarlijke gebieden op veilige wijze te ontruimen. Het algoritme draagt bij aan de ontwikkeling van een AEN-systeem, waardoor het intelligenter en beter geautomatiseerd is."