Pionír alkalmazási lehetőségek egy műegyetemi algoritmusban

Először nyertek magyarországi kutatók támogatást az Amazon nemzetközi kutatás-fejlesztési pályázatán.

Bankok pénzügyi folyamatainak elemzéséhez, vasúti fékrendszerek automatikus teszteléséhez, biológiai molekulák gráfalapú szemléltetéséhez és repülőgépgyártó modellező program ellenőrzéséhez is felhasználhatják azt a gráfgeneráló algoritmust, amelyet Semeráth Oszkár, a BME Villamosmérnöki és Informatikai Kar (BME VIK) Méréstechnika és Információs Rendszerek Tanszék tudományos munkatársa, valamint kutatótársa, Varró Dániel, a tanszék egyetemi tanára, az MTA-BME Lendület Kiber-fizikai Rendszerek Kutatócsoport korábbi vezetője alkotott meg. (Varró Dániel a pályázat elnyerésekor főállásban a McGill University oktató-kutatója volt – szerk.) A kutatópáros gráfgenerátor algoritmusa minden eddiginél nagyobb és összetettebb rendszerek problémáinak modellezésére és pontosabb eredménybecslésre is alkalmas. A műegyetemi szakemberek elgondolásukkal - ezidáig egyedüli magyarországi kutatókként - sikerrel pályáztak az Amazon kutatás-fejlesztési felhívására (Amazon Research Award). Elképzeléseik kidolgozásában a kanadai McGill University-n dolgozó kollégáikkal működtek együtt.

A BME VIK kutatói győztes pályázatukban kézzelfogható- megoldást nyújtottak egy Amazonnál is jelentkező rendszerigényre: gráfalapú következtetésekkel szisztematikusan felderíthetők egy számítógépes program akár többszörösen összetett hibái, és azok pontos helye a rendszerben.

„Óriási megtiszteltetés és egyben elismerés, hogy sikerrel pályáztunk a felhívásra. Különösen azért, mert az informatikán belül leginkább egy másik terület, a szoftvertudományok művelői vagyunk, holott e pályamunkánkban inkább a formális verifikáció terén értünk el nemzetközi viszonylatban is ígéretes eredményeket” – fogalmazott a díj kapcsán a kutatópáros a bme.hu-nak adott interjúban.

Semeráth Oszkár és Varró Dániel mintegy másfél évtizede dolgozik egy olyan matematikai algoritmus kifejlesztésén, amelyet széleskörű problémamegoldásra is alkalmazhatnak a legkülönbözőbb témák logikai kapcsolatokon alapuló rendszereiben. A kutatópáros a gráfok gyakorlati alkalmazási lehetőségeit vizsgálja: a gráfok a legegyszerűbb struktúrák a természettudományban és az informatikában, amelyekkel az egyes rendszerszereplők közötti viszonyok jellemezhetők. Gráfok segítségével többek között leírhatók az adatbázisok és adatszerkezetek, modellező eszközökben is használják ezt a lehetőséget, és például önvezető autók tesztelésekor a lehetséges forgalmi szituációk meghatározásánál is nagy szerepük van. „E gyakorlati példák mindegyike egy közös matematikai modellre épül, ezt a modellt nevezzük gráfnak. A rendszerek és eszközök teljesítményének megítélése, mérése visszavezethető a logikailag hozzájuk tartozó gráfok generálásának modellezésére. E logikai helyzetek elemezzük a kutatásunkban. A gráfok segítségével automatikusan ellenőrizhető például az, hogy egy folyamat helyesen zajlott-e le, vannak-e egy adott rendszerben hibák, vagy éppen milyen lehetséges kimenetelei lehetnek egy adott eljárásnak” – foglalták össze keretrendszerük gyakorlati hasznosulásáról a BME VIK kutatói. A műegyetemi szakemberek munkájának tudományos szenzációja, hogy algoritmusuk lehetővé teszi minden eddiginél nagyobb és komplexebb rendszerek biztonságos, szisztematikus és automatikus elemzését. A Microsoft Research és az MIT-n kifejlesztett rendszerekhez képest 8-10-szer akkora méretű rendszereket is górcső alá tudnak venni, amit azt jelenti, hogy még összetettebb problémák automatikus elemzését hajtják végre, amelyhez algoritmusuk megadja a lehetséges megoldásokat is.

„Önvezető járművek tesztelése a budapesti Krisztina körútra automatikusan előállított forgalmi szituációkban.” (Forrás: Google Maps, Carla, szimulációt készítette: Ficsor Attila és Pintér Balázs)

A kutatópáros már több gyakorlati, ipari esetnél is sikerrel alkalmazta a keretrendszert, többek között lézervezérlésű önvezető targoncagép robotok tesztelésére. Egy hazai vállalattal együttműködésben különböző vasúti pályaudvar architektúrákat állítottak elő, amellyel a vasúti váltók integrációs tesztjének megbízhatóságát vizsgálták. Vendégelőadóként bemutatták elképzeléseket tengerentúli kollégáknak is: New Yorkban tartott előadásukon a molekulák kémiai leírásának gráfját szemléltették keretrendszerükkel. Gráfgenerálással vizsgálták egy brazil repülőgépgyártó modellező program helyességét, gépészeti tervrajzokat is elemeztek, és számítógépes játékok pályáinak generálásához is alkalmazták már a fejlesztésüket.

A pályázaton elnyert ösztöndíjat a páros a téma további kutatásira fordítja. Első lépésben egy stabilan működő, még pontosabb gráfgenerálást biztosító modell megépítése a céljuk. A gráfgeneráló algoritmust nyílt platformon, webböngészőben teszik majd elérhetővé bárki számára. Egy olyan architektúrát, illetve felületet fejlesztenek a programhoz, amelyet egyszerűen, különösebb előképzettség nélkül is használhatnak majd a mérnöktársak. A projektet az Amazon a számítási kapacitást végző háttéreszközökkel is támogatja.

Egy modellezőeszköz teszteléséhez generált gráf. Az ilyen gráfok az informatika számos területén alkalmazhatók. (Az illusztrációt Varró Dániel és Semeráth Oszkár által alkalmazott eszköz állított elő.)

„A gráfelmélet és gráfok gyakorlati hasznosítása még sok kiaknázatlan lehetőséggel kecsegtet. Sokáig egy nagyon általános témaként vagy inkább alapkutatásként tekintettek a gráfgenerálásra, ugyanis közvetlen alkalmazási lehetőségeik még felfedezésre várnak. Ám minden jel arra mutat, hogy nagy potenciál rejlik a gráfgenerálás jövőbeli gyakorlati, piaci hasznosulásában, amellyel az elemző vállalatok eddig még nem számoltak. „Kutatási elképzeléseinket abba az irányba visszük, hogy algoritmusunk minél nagyobb gráfok biztonságos elemzésére legyen alkalmas, ezért arra számítunk, hogy a gyakorlati hasznosulás lehetőségei is kitárulnak előttünk” – árulták el a BME VIK kutatói, akik új partnereket keresnek gráfgeneráló algoritmusuk gyakorlati bevetéséhez. Emellett továbbra is együttműködnek az Amazonnal, ahol számítógépes rendszerek hibaelemzéséhez bizonyul hatékony megoldásnak a műegyetemi szakemberek gráfgeneráló algoritmusa.

TZS-KJ

Fotók forrása: Semeráth Oszkár