27.09.2021

Transformacje grafowe pomogą w symulacjach propagacji zanieczyszczeń nad Małopolską


Rysunek prezentuje trójwymiarową symulację ruchu powietrza nad Tatrami. Teren jest pokryty siatką topograficzną zbudowaną z trójkątnych elementów. Niebieski kolor mają niższe partie gór, a wyższe szczyty przechodzą stopniowo w kolor pomarańczowy. Północno-zachodni wiatr został oznaczony szarymi strzałkami.

Wiatr północno-zachodni nad terenem Małopolski pokrytym grafem zbudowanym z elementów trójkątnych. Rys. Zespół Algorytmów i Systemów Adaptacyjnych

Rysunek prezentuje trójwymiarową symulację propagacji zanieczyszczeń nad Tatrami. Teren jest pokryty siatką topograficzną zbudowaną z trójkątnych elementów. Góry mają niebieski kolor, a zanieczyszczenia mają kolor pomarańczowy, którego intensywność zależy od ich stężenia. Zanieczyszczenia są zatrzymywane przez Tatry i nie przedostają się na słowacką stronę. Obok rysunku znajduje się pionowa niebiesko-pomarańczowa skala od punktu 0 do punktu 1.

Propagacja zanieczyszczeń w Małopolsce przez wiatr północno-wschodni. Zanieczyszczenia nie przedostają się na teren Słowacji dzięki pasmu Tatr. Rys. Zespół Algorytmów i Systemów Adaptacyjnych

Rysunek prezentuje przekrój przez trójwymiarowy profil zanieczyszczeń. Teren jest pokryty siatką topograficzną zbudowaną z trójkątnych elementów. Kolejne warstwy przyjmują barwy od niebieskiego, który odpowiada minimalnemu stężeniu zanieczyszczeń, do pomarańczowego, który odpowiada maksymalnemu stężeniu zanieczyszczeń. Im niższe warstwy, tym kolor pomarańczowy jest intensywniejszy, czyli stężenie substancji jest wyższe. Obok rysunku jest pionowa niebiesko-pomarańczowa skala od punktu minimalnego do punktu maksymalnego.

Przekrój przez trójwymiarowy profil zanieczyszczeń ukazujący koncentracje zanieczyszczeń na różnych wysokościach nad powierzchnią terenu. Rys. Zespół Algorytmów i Systemów Adaptacyjnych

Jak potężnych komputerów potrzeba, aby skutecznie przewidzieć rozprzestrzenianie się zanieczyszczeń na terenie całej Małopolski? Grupa badawcza pod kierownictwem prof. dr. hab. Macieja Paszyńskiego z Wydziału Informatyki, Elektroniki i Telekomunikacji dowodzi, że do wykonania takiej symulacji wystarczy nawet laptop. Wszystko za sprawą zastosowania pionierskich technik modelowania matematycznego przy pomocy tak zwanych gramatyk grafowych. Ta pomysłowa metoda polega w skrócie na tym, że modelowany teren pokrywa się trójkątnymi grafami, które są następnie algorytmicznie przetransformowane w nowe grafy, przy czym ich wielkość zależy od ukształtowania powierzchni. W podobny też sposób modeluje się atmosferę – tu natomiast najlepiej przydają się czworościany, które zostają wypełnione wirtualnymi zanieczyszczeniami. Wyniki prac zespołu z AGH zostały opublikowane w prestiżowym czasopiśmie Engineering with Computers, zwracając uwagę światowej klasy badaczy w dziedzinie symulacji matematycznych.

Zespół badawczy A2S

Artykuł w jednym z najbardziej prestiżowych czasopism naukowych, w którym publikowane są prace poświęcone interdyscyplinarnym zastosowaniom informatyki, nie jest tutaj wcale przypadkiem i wpisuje się w długą działalność Zespołu Algorytmów i Systemów Adaptacyjnych, który działa na WIET. Badania prowadzone przez grupę pod kierunkiem prof. Macieja Paszyńskiego koncentrują się na projektowaniu modeli, które mają zdolność adaptacji, czyli automatycznego dopasowania się do rozwiązywanego problemu. Podstawowy cel, do jakiego dążą badacze, to skrócenie czasu potrzebnego do wykonania zadania, co staje się możliwe dzięki wykorzystaniu zdobyczy nauk obliczeniowych oraz technik sztucznej inteligencji. Uzyskana redukcja złożoności obliczeniowej pozwala istotnie zredukować koszty energetyczne związane z pracą komputerów.

Opracowane algorytmy są tworzone po to, by symulować rzeczywiste procesy w świecie wirtualnym. Naukowcy z AGH prowadzą swoje badania, skupiając się na trudnych i potrzebnych zastosowaniach informatyki, do jakich należą przewidywania progresji lub regresji nowotworów podczas różnych terapii, symulacje środowiskowe w aspekcie wydobycia złóż naturalnych oraz modelowanie zjawisk atmosferycznych, a zwłaszcza zjawisk propagacji zanieczyszczeń. Ostatnia kwestia stanowi jeden z największych problemów Małopolski, gdzie zanieczyszczenia są często przywiewane z zachodu przez północno-zachodni wiatr. W celu opracowania adekwatnej symulacji tego zjawiska atmosferycznego uczeni z grupy wykorzystują analizę izogeometryczną i gramatykę grafową, które są dynamicznie rozwijającymi się dziedzinami współczesnej informatyki.

Siatka topograficzna

Transformacje grafowe stanowią jedną z prężnie rozwijających się technik w dziedzinie nauk obliczeniowych, która pozwala zmniejszyć moce obliczeniowe potrzebne do rozwiązania problemu. Krótko mówiąc, polega ona na automatycznym przekształcaniu pierwotnych grafów w nowe struktury przy pomocy odpowiedniego algorytmu. W przypadku modelu odtwarzającego propagację zanieczyszczeń pierwszy krok to pokrycie terenu trójkątnymi grafami, które są dalej transformowane przez zaprojektowany program w mniejsze trójkątne struktury, przy czym ich rozmiar zależy od ukształtowania powierzchni. Podobnie atmosferę nad terenem wypełnia się czworościanami, dla których następnie oblicza się konkretne stężenie zanieczyszczeń. W jednym i drugim przypadku wykorzystuje się trójkątne figury, ponieważ można je dobrze dopasować do nierównej powierzchni. W ten właśnie sposób otrzymuje się siatkę topograficzną, która stanowi matematyczny model opisywanego regionu – w tym przypadku ziem Małopolski – na podstawie czego można wykonać komputerową symulację propagacji obecnych zanieczyszczeń powietrza.

Korzystna współpraca

Stworzony przez prof. Macieja Paszyńskiego model transformacji grafowych spotkał się z uznaniem zagranicznych uczonych zajmujących się zastosowaniem metod numerycznych w symulacjach zanieczyszczeń. Praca zespołu badawczego A2S zaciekawiła grupę pod kierunkiem prof. Rafaela Montenegro Armas z Uniwersytetu Las Palmas de Gran Canaria, który zajmował się modelami propagacji szkodliwych cząstek z elektrowni na Wyspach Kanaryjskich. Korzystna kooperacja wywiązała się również między zespołem z AGH i grupą pod kierunkiem prof. Keshava Pingali z Uniwersytetu Teksańskiego w Austin, z którym prof. Maciej Paszyński współpracował już wcześniej, będąc częstym gościem w Instytucie Odena, gdzie pracuje ten uznany w świecie specjalista. Symulacje rozprzestrzeniania się zanieczyszczeń na terenie Małopolski, jakie zostały przeprowadzone przy pomocy opracowanej przez niego biblioteki GALOIS, dostarczyły bardzo ciekawych danych, powalając ulepszyć jego system. Transnarodowa współpraca zaowocowała w końcu również wspólnym tekstem w prestiżowym czasopiśmie Engineering with Computer.

Gdy wykonuje się tego typu symulacje, trzeba transformować grafy. W wielu miejscach grafu musimy łamać trójkąty, aby dokładniej oddawały one teren. Laptopy bądź stacje robocze mają wiele rdzeni, czasem nawet kilkadziesiąt. Biblioteka GALOIS służy z kolei do równoległego przetwarzania grafów, czyli umożliwia nam jednoczesne wykonywanie transformacji grafowych w różnych miejscach tego grafu, używając wielu rdzeni w tym samym czasie. Jest to potrzebne do tego, żeby obliczenia były kilkadziesiąt razy szybsze. Bibliotekę GALOIS stworzył prof. Keshav Pingali, który jest także współautorem artykułu i mamy przyjemność z nim współpracować. On wraz ze swoim zespołem tworzy tę bibliotekę, a my przyspieszamy symulacje, z czego jest bardzo zadowolony, ponieważ dajemy mu ciekawe zastosowania, które jednocześnie weryfikują, czy jego biblioteka dobrze działa – tłumaczy prof. Paszyński, podkreślając korzyści z tej współpracy.

Symulacja ruchu powietrza

By odtworzyć proces rozprzestrzeniania się szkodliwych substancji w niskich warstwach atmosfery potrzebne były jeszcze dane dotyczące siły oraz kierunku wiatru. Te parametry są do pobrania z aktualnych pomiarów wykonywanych przez stacje metereologiczne, dzięki czemu symulacja może być wykonana nie tylko na laptopie, lecz także w czasie rzeczywistym. Projekt stworzony przez międzynarodową grupę pod kierunkiem prof. Macieja Paszyńskiego odtwarza trzy różne procesy ściśle powiązane z ruchem mas powietrza: proces adwekcji, czyli poziomego przemieszczania się cząsteczek, proces dyfuzji, czyli ich wzajemnego mieszania się oraz proces reakcji, czyli oddziaływania odmiennych substancji. To sprawia, że symulacja rozprzestrzeniania się zanieczyszczeń jest o wiele bardziej precyzyjna, przez co pozwala również na dokładniejsze prognozowanie drogi propagacji szkodliwych związków. Na podstawie wizualizacji, które można zobaczyć w opublikowanym na stronie internetowej czasopisma artykule, można dla przykładu wyciągnąć wniosek, że Tatry blokują zanieczyszczenia przed ich propagacją na słowacką stronę.

Praktyczne zastosowania

Na koniec pozostaje rozważyć pytanie: jakie to wszystko ma zastosowania? Otóż modele grafowe opracowane przez naukowców mogą służyć do zaprogramowania symulacji ruchu mas powietrza na wirtualnie zmodyfikowanej powierzchni. Modelując w odpowiedni sposób siatkę topograficzną, można by między innymi sprawdzić, jakie rozłożenie zabudowań w mieście jest najlepsze w kontekście przewietrzania konkretnej miejscowości z zanieczyszczeń. Chodzi zatem o możliwość projektowania korzystnych korytarzy powietrznych, co byłoby z pewnością cenną wskazówką dla urbanistów i planistów, a więc specjalistów zajmujących się tworzeniem planów przestrzennego zagospodarowania miasta. Tego typu badaniami, czyli tak zwanymi problemami odwrotnymi, zajmuje się w grupie A2S przede wszystkim prof. dr hab. inż. Robert Schaefer. W swojej pracy zastanawia się mianowicie, w jaki sposób dobrać parametry w danej symulacji, aby odtwarzała pożądane zjawiska. Poza walorami badawczymi, które płyną z rozwijania nauk obliczeniowych, istnieją wobec tego walory praktyczne, czyniące pracę naukowców z AGH podwójnie potrzebną.

Opracowany kod można zastosować do symulacji korytarzy powietrznych. To ciekawe, praktyczne zastosowanie. Wymaga jednak podłączenia się do bazy, gdzie są budynki. Symulację wykonywaliśmy bowiem w skali całej Małopolski, a wtedy trzeba byłoby się skupić na pewnym fragmencie Krakowa i siatkę topograficzną zbudować na podstawie rozmieszczenia zabudowań. To jest właśnie ten problem odwrotny, polegający na odpowiednim dopasowaniu parametrów symulacji. Na przykład: w którym miejscu zrobić korytarz w Krakowie, żeby te zanieczyszczenia były jak najlepiej wydmuchiwane, albo których miejsc nie zabudowywać, aby się nie pogorszyło – opowiada prof. Paszyński, zwracając uwagę na praktyczne zastosowania nauk obliczeniowych.