Graph Transformations to Help with Simulations of Pollution Propagation over Małopolska Province

The picture shows 3D simulation of air movement over the Tatra Mountains in Poland. The terrain is covered with a topographic mesh made of triangular elements. Lower parts of the mountains are coloured in blue and higher parts gradually change to orange. The northwest wind is marked with grey arrows.

Northwest wind over the territory of the Małopolska Province covered with a graph made of triangular elements. Pic. A2S Team

The picture shows 3D simulation of pollution propagation over the Tatra Mountains in Poland. The terrain is covered with a topographic mesh constructed from triangular elements. The mountains are coloured blue and the pollution is coloured orange, the intensity of which depends on the concentration. The pollution stops by the Tatra Mountains and does not travel to the Slovak side. On the right side of the picture, there is a vertical scale that goes from blue to orange, from zero to one.

Pollution propagation in the Małopolska Province due to the northwest wind. The pollution does not travel to the Slovak side due to the mountains. Pic. A2S Team

The picture shows a cross-section of the 3D pollution profile. The terrain is covered with a topographic mesh made of triangular elements. Subsequent layers assume various shades of blue, which corresponds to minimal pollution concentration, and orange, which corresponds to maximal pollution concentration. The lower the layers, the more intensive the colour orange, i.e. the concentration of a substance is higher. On the right side of the picture, there is a vertical scale that goes from blue to orange, from minimum to maximum points.

A corss-section of the 3D pollution profile showing pollution concentration on various elevations above the surface of the terrain. Pic. A2S Team

How powerful should computers be to effectively predict the propagation of pollution throughout the territory of the Małopolska Province? A research group headed by Professor Maciej Paszyński from the Faculty of Computer Science, Electronics and Telecommunications proves that an ordinary laptop would suffice to carry out such simulations. All this thanks to the pioneering techniques of mathematical modelling using the so-called graph grammars. In a nutshell, this ingenious method relies on the premise that the modelled terrain is covered with triangular graphs, which are subsequently algorithmically transformed into new graphs, whereby their size depends on the topography of the terrain. Similarly, scientists model the atmosphere – in this case, however, tetrahedrons, which are later filled with virtual pollution, are more useful. The results of the AGH UST research group were published in a prestigious Engineering with Computers journal, focusing the attention of world-class researchers in the field of mathematical simulations.

A2S research team

The article published in one of the most prestigious scientific journals, which contains works on interdisciplinary applications of computer science, is not a coincidence and subscribes to the long-lasting activity of the A2S team, operating at the Faculty of Computer Science, Electronics and Telecommunications. Research conducted by the team headed by Professor Maciej Paszyński revolves around designing adaptable models, i.e., models with the ability to adjust themselves automatically to the problem at hand. The chief objective of the researchers is to shorten the time needed to perform a given task, which is becoming possible due to the development of computational sciences and AI technology. The obtained reduction in computational complexity causes a significant reduction in energy costs related to computer operation.

The algorithms are designed to simulate real-life processes in virtual space. In their research, the AGH UST scientists focus on difficult and much needed applications of computer science, such as predicting the progression or regression of cancers during various kinds of therapies, the environmental simulations in the field of natural deposits extraction, and modelling atmospheric phenomena, especially in relation to pollution propagation phenomena. The last issue constitutes one of the most burning problems of the Małopolska Province, where pollution is frequently transported by northwest winds. To develop an accurate simulation of this atmospheric phenomenon, the research group uses isogeometric analyses and grammar-based graphs, which are dynamically evolving fields of modern computer science.

Topographic mesh

Graph transformations constitute one of the dynamically evolving techniques in the field of computational sciences, which allows the reduction of the processing power needed to solve a particular problem. In short, it relies on an automatic transformation of original graphs into new structures by means of a specifically designed algorithm. In the case of the model simulating the pollution propagation, the first step is to cover the terrain with triangular graphs, which are then transformed by a specific programme into smaller triangular structures, whereby their size depends on the topography of the terrain. Similarly, the atmosphere above the terrain is filled with tetrahedrons, for which a specific concentration of pollution is calculated. In both cases, triangular shapes are used because they can be adjusted accordingly to an uneven surface. This is how scientists produce a topographic mesh which is a mathematical model of the region in question – in this case, the Małopolska Province. On the basis of that, the scientists are able to create a computer simulation of the current air pollution propagation.

Beneficial cooperation

The model of graph transformations created by Professor Maciej Paszyński has been recognised by foreign researchers dealing with the application of numerical methods in pollution simulations. The work of the A2S team has interested a research group headed by Professor Rafael Montenegro Armas from the Universidad de Las Palmas de Gran Canaria, who has dealt with models of propagation of harmful particles from the power plant on the Canary Islands. Another beneficial cooperation was established with a research group headed by Professor Keshav Pingali from the University of Texas at Austin, with whom Professor Paszyński had worked before frequently visiting the Oden Institute, where Professor Pingali works. The simulations of pollution propagation in the Małopolska Province conducted with the help of the GALOIS library designed by him have provided very interesting data, which helped to improve the system. This international cooperation has also eventually resulted in the co-authorship of an article published in the prestigious Engineering with Computer journal.

When you perform such simulations, graphs have to be transformed. In several places on the graph, we have to break the triangles to make them mirror the terrain more accurately. Laptops or work stations have multiple cores, sometimes even several dozen. The GALOIS library is used, in turn, to process graphs, i.e. it allows us to simultaneously perform graph transformations in various places of the original graph, using multiple cores at the same time. It is necessary to make the calculations several dozen times faster. The GALOIS library was created by Professor Pingali, who has also co-authored the article, and we have the pleasure of working with him. He and his team are creating this library and we are accelerating the simulations, which makes him very happy, because we provide him with interesting applications, which simultaneously verify whether his library is operating well’, explains Professor Paszyński, emphasising the beneficial nature of this cooperation.

Air movement simulation

To recreate the process of propagation of harmful substances in the lower layers of the atmosphere, scientists also needed data on the force and direction of the wind. These parameters are available to download from the current measurements carried out by meteorological stations, making it possible to run the simulation not only on a laptop but also in real time. The project coordinated by an international group headed by Professor Maciej Paszyński recreates three different processes, which are strictly connected with the movement of air mass: the advection process, i.e., horizontal particle movement; the diffusion process, i.e., mixing of particles; and the process of reaction, i.e., reaction of diverse substances. This makes the pollution propagation simulation much more precise, allowing scientists to create more accurate predictions with regard to the way of propagation of harmless compounds. Based on the visualisations, which are part of the article published on the journal’s website, it can be concluded that the Tatra Mountains prevent the propagation of pollution on the Slovak side.

Practical application

Finally, there is only one question to answer: how can we apply all this in practice? Graph models developed by scientists can be used in programming air mass movement simulations on a virtually modified surface. By modelling the topographic mesh accordingly, they can also see which variant of urban infrastructure distribution is best in relation to ventilating a particular town or city. Therefore, this is all about the possibility of designing favourable air corridors, which would definitely be a valuable guideline for urban planners, i.e., specialists dealing with the creation of urban development plans. In the A2S team, Professor Robert Schaefer is predominantly occupied with such research, that is, the so-called inverse problems. In his work, Professor Schaefer deliberates on how to accurately choose parameters in a given simulation so that it delivers the desired phenomena. Apart from the scientific benefits that abound in developing computational sciences, there are also practical advantages that render the work of the AGH UST scientists even more necessary.

‘The designed code can be used to simulate air corridors. This is an interesting and practical application. However, we would have to connect it to a building database. The simulation was created for the entire territory of the Małopolska Province, and we would have to focus on a particular fragment of Krakow, constructing the topographic mesh based on the urban layout of the city. This is the inverse problem, which relies on the accurate adjustment of the simulation parameters. For instance: in which place in Krakow should we make an air corridor so that the pollution can be better blown out of the city; or in which spaces should we not construct buildings so that we do not make matters worse’, explains Professor Paszyński, directing our attention to practical applications of computational sciences.