Directed Rooted Forest-based Planning Method Powers the Next Generation of Building Safety 

Study conducted by Prof. Tsz Yin Jacqueline LO and her research team
 

In the midst of an emergency, every second counts; whether it is a fire, earthquake or other hazard, the ability of occupants to swiftly and safely evacuate from a building can be a matter of life and death. Traditionally, static exit signs have served as the silent sentinels of safety, pointing the way to the nearest exit with unwavering certainty. Yet, as buildings become more complex and emergencies more unpredictable, these static signs reveal their limitations. They cannot adapt to changing conditions such as blocked passages or uneven crowd distribution, and may inadvertently direct people into danger or congestion.

This is where the concept of Automated Dynamic Exit Signs (ADES) comes into play. 

ADESs are designed to be "smart", capable of adjusting their directional guidance in real time based on the evolving situation inside a building. By leveraging real-time information about evacuees and hazards derived from sensors or other intelligent components, these signs can point evacuees towards the safest and most efficient exit routes, even as conditions change. However, the challenge lies not just in displaying dynamic directions, but also in determining those directions rapidly and reliably. Until now, the computational burden of simulating crowd movement and optimising guidance in real time has posed a major barrier to practical implementation.

Prof. Tsz Yin Jacqueline LO, Assistant Professor of the Department of Civil and Environmental Engineering at The Hong Kong Polytechnic University, and her research team addressed this challenge by introducing a novel approach based on the Directed Rooted Forest (DRF) planning method. This technique offers a promising solution for the rapid and effective adjustment of exit sign directions, potentially transforming the way we manage emergency evacuations in smart buildings. Their study was published in Journal of Building Engineering [1].

Figure 1. Schematic diagram of the decomposition from EN to DRF

At the heart of the DRF-based method is a sophisticated way of encoding and optimising the directions displayed on dynamic exit signs. In essence, the building’s interior is mapped as a network, with each exit sign represented as a node and possible evacuation routes as edges. The DRF structure deconstructs this evacuation network (EN) into a collection of directed rooted trees, each rooted at an exit. A schematic diagram of the deconstruction is shown in Figure 1. This ensures that every sign points evacuees towards an accessible exit, avoiding loops and conflicting directions that could cause confusion or delay.
 

Figure 2. Signs-oriented space partitioning and EN construction

The process begins with the construction of a sign-oriented EN, informed by real-time building and hazard data. An example is illustrated in Figure 2. Each sub-area of the building is associated with a sign, and the influence range of each sign is determined using visibility catchment areas and Voronoi partitioning. This granular mapping allows the system to account for both direct visibility and indirect influence, such as memory effects and following behaviour among evacuees.

Once the network is established, the initial DRF is generated using an assignment algorithm that considers the evacuation times predicted by the linear model. This initial solution aims to balance the load across exits, minimising congestion and ensuring balanced utilisation of the capacities of all exits. The assignment relies on a simplified linear model to estimate evacuation times, factoring in both travel distance and queuing effects at exits.

However, real-world evacuations are far more complex than any linear model can capture. To refine the initial DRF, the method incorporates detailed feedback from crowd simulations, specifically using the Social Force Model (SFM) to simulate individual movements and interactions. 

The optimisation process employs two key algorithms: Branch Grafting and Leaf Grafting. Branch Grafting allows for the reassignment of entire branches of the network to different exits, facilitating global optimisation, while Leaf Grafting enables fine-tuning by reallocating individual nodes. These algorithms iteratively adjust the DRF, guided by simulation outputs such as evacuation times and flow rates, until an optimal or near-optimal configuration is achieved.

Crucially, the method also accounts for partial compliance among evacuees, recognising that not everyone will follow the signs perfectly. This is operationalised through the incorporation of predefined compliance rates, which underpin robust optimisation under these more realistic scenarios. 

Figure 3. (a) Internal layout of the university canteen (b) The distribution of 750 evacuees

To evaluate the effectiveness of the DRF-based direction setting method, the team conducted extensive numerical tests in a university canteen. The venue, characterised by high crowd density and a complex internal layout, was equipped with 92 hypothetical dynamic exit signs (Figure 3a). Tests were performed under varying conditions, including different crowd sizes (350, 500, 600 and 750 evacuees), distributions, network scales and compliance rates. An example is shown in Figure 3b. 

Figure 4. DRF obtained by reallocating at the end of the (a) 1st, (b) 2nd, (c) 3rd, (d) 4th, (e) 5th and (f) 6th round under the population size of 750

The results are compelling. In scenarios involving 750 evacuees, the DRF-based method achieves equilibrium in merely 5–6 optimisation iterations, each of which requires the execution of a computationally intensive SFM simulation. The resultant DRF structures from successive iterations in a single process are illustrated in Figure 4. This represents a dramatic reduction in computational cost compared to traditional metaheuristic approaches, which typically require 300–500 simulation evaluations to achieve similar results. Even as crowd size and network complexity increased, the number of optimisation iterations grew only marginally, demonstrating the scalability of the approach.

Further analysis revealed that the efficiency of the method was influenced by factors such as crowd distribution and network scale. Uniform distributions facilitated faster optimisation, while highly uneven distributions and larger networks required more iterations. Notably, increasing the number of exits not only reduced overall evacuation time but also improved optimisation efficiency, highlighting the importance of architectural design in emergency planning.

The study also explored the impact of evacuee compliance. When compliance rates were reduced from 100% to 50%, the volatility in optimisation rounds increased, but the overall computational cost remained manageable. Robustness tests showed that mis-estimating compliance rates during optimisation could lead to significant underperformance, with the relative range of evacuation times increasing from 2.63% (accurate compliance) to over 21% (50% deviation). This underscores the need for accurate behavioural modelling and suggests that adopting a moderate preset compliance rate parameter may help mitigate bias when precise rates are unknown.

In summary, the DRF-based direction setting method represents a significant step forward in the practical implementation of ADESs. By intelligently encoding direction information and leveraging simulation feedback, the approach achieves rapid convergence and maintains high optimisation efficiency, even in large and complex buildings. The reduction in simulation executions by two orders of magnitude is particularly noteworthy, making real-time evacuation planning a feasible goal.

Looking ahead, this study highlights several avenues for further research and development. Integrating hazard spread modelling and multi-storey co-ordination could enhance system applicability in even more challenging scenarios. Meanwhile, the potential for machine learning models to replace traditional simulation and optimisation processes offers exciting prospects for real-time, data-driven evacuation guidance.

As buildings become smarter and more responsive, the ability to guide occupants dynamically and efficiently will be a cornerstone of safety engineering. The DRF-based approach, with its blend of mathematical rigour and practical adaptability, is poised to play a pivotal role in this evolution.

Prof. Lo is currently an Assistant Professor of the Department of Civil and Environmental Engineering at The Hong Kong Polytechnic University. Her research interests include innovation management and performance evaluations, data-driven multi-criterion decision-making, smart transportation management systems, system dynamic modelling supporting public policy making, urban resilience and analytics, smart cities, pedestrian and crowd simulations for smart infrastructure and urban planning, and industrialised construction.

[1] Zhang, B., Lo, J. T. Y., Fang, H., Xie, C., Tang, T. & Lo, S. (2024). Directed rooted forest based direction setting method: A step toward automated dynamic exit signs, Journal of Building Engineering, Volume 85, 2024, 108504, ISSN 2352-7102, https://doi.org/10.1016/j.jobe.2024.108504.

Prof. Tsz Yin Jacqueline LO Assistant Professor, Department of Civil and Environmental Engineering