Schválené projekty 2017

Rozdělení přidělené dotace z MŠMT na specifický vysokoškolský výzkum po fakultách se zohledněním celoškolských pracovišť na rok 2017

Celková přidělená částka z MŠMT na specifický vysokoškolský výzkum na VŠB-TUO - 54 573 242 Kč

Z toho 2.5% - 1 364 331 Kč - úhrada způsobilých nákladů spojených s organizací SGS

fakulta přidělená částka v Kč
FBI  1 210 137
EKF  3 929 534
FAST  2 465 732
FS  9 344 630
FEI 13 996 004
HGF  5 272 251
FMMI  7 123 785
VC  8 743 333
CP  1 123 505
CELKEM 53 208 911

KódSP2017/182
Název projektuŘešení grafových úloh na časoprostorových grafech zatížených neurčitostí pomocí HPC
ŘešitelMartinovič Jan Ing., Ph.D.
Školitel projektu
Období řešení projektu01.01.2017 - 31.12.2017
Předmět výzkumuAnotace:

Rozsáhlé grafové úlohy patří mezi dominantní problémy současnosti. Tyto úlohy vznikají např. v moderních navigačních algoritmech, problémech řešených v souvislosti se Smart City anebo při analýze sociálních sítí. Specifickou vlastností těchto úloh je změna charakteristik grafu v čase a jejich zatížení neurčitostí. Hlavním úkolem tohoto projektu je návrh a implementace paralelních algoritmů schopných řešit tyto problémy. Algoritmy budou založené na grafových metodách jako je Dijkstrův algoritmus nebo betweenness centrality, které budou rozšířené o dynamickou a pravděpodobnostní složku. Dále budou využity metody z oblasti statistiky, machine learningu a dynamických systémů. Tyto metody budou využity jak pro samotnou implementaci, tak pro ověření efektivity vyvinutých algoritmů na simulovaných i reálných datech. Použité metody budou zahrnovat rekurenční matice, 0-1 test chaosu a aproximační entropii a umožní popsat dynamické vlastnosti implementovaných algoritmů. Cílem projektu je tedy vytvoření algoritmů umožňujících efektivní výpočty daných charakteristik rozsáhlých dynamických grafů zatížených neurčitostí a analýza těchto algoritmů pomocí metod dynamických systémů.

Řešitelský tým a jeho výstupy:

Ing. Jan Martinovič, Ph.D. - garant
Ing. Tomáš Martinovič
Ing. Adam Silber
Ing. Michal Běloch
Bc. Jan Křenek
Ing. Robert Skopal – kombinovaný
Ing. Radek Tomis – kombinovaný
neurčený student Mgr. studia (9.-12. měsíc)

Slaninová, K., Martinovič, J., Golasowski, M., Reduction of user profiles for behavioral graphs, (2016) Smart Innovation, Systems and Technologies, 58, pp. 219-229. DOI: 10.1007/978-3-319-39883-9_18

Režnar, T., Martinovič, J., Slaninová, K., Grakova, E., Vondrák, V., Probabilistic time-dependent vehicle routing problem, (2016) Central European Journal of Operations Research, pp. 1-16. Article in Press. DOI: 10.1007/s10100-016-0459-2

Tomis, R., Rapant, L., Martinovič, J., Slaninová, K., Vondrák, I., Probabilistic time-dependent travel time computation using Monte Carlo simulation, (2016) Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9611, pp. 161-170. DOI: 10.1007/978-3-319-40361-8_12

Tomis, R., Martinovič, J., Slaninová, K., Rapant, L., Vondrák, I., Time-dependent route planning for the highways in the Czech Republic, (2015) Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9339, pp. 145-153. DOI: 10.1007/978-3-319-24369-6_12

Martinovič, T., Chaotic behaviour of noisy traffic data, (2016) Mathematical Methods in the Applied Sciences, Article in Press. DOI: 10.1002/mma.4234

Hanzelka, J., Skopal, R., Slaninová, K., Martinovič, J., Dvorský, J., Graph problems performance comparison using Intel Xeon and Intel Xeon-Phi, (2016) Advances in Intelligent Systems and Computing.
Členové řešitelského týmuIng. Michal Běloch
Ing. Jan Křenek
Ing. Tomáš Martinovič, Ph.D.
Ing. Jan Martinovič, Ph.D.
Ing. Vít Ptošek
Ing. Adam Silber
Ing. Radek Tomis
Ing. Jan Vargovský
Ing. Radim Vavřík
Specifikace výstupů projektu (cíl projektu)Cíle projektu a očekávané výstupy

Cílem projektu je navrhnout a implementovat algoritmy pro výpočty nejkratších cest a centralit v dynamických grafech zatížených neurčitostí a analýza dynamických vlastností jejich výstupů. Důraz bude kladen na správnou definici řešených problémů a vytvoření paralelních algoritmů schopných řešit tyto úlohy. Implementované algoritmy budou prezentovány prostřednictvím příspěvků na konferencích nebo v časopisech indexovaných v databázích WoS a Scopus. Cílem je publikace dvou až tří příspěvků. Tyto algoritmy budou navrženy tak, aby mohly být začleněny do existujících řešení v rámci ADAS laboratoře jako je routing v projektu ANTAREX či srážkový model v projektu FLOREON.

Impakt navrhovaného projektu

Toto téma se objevuje v několika projektech řešených ADAS laboratoří, kde se vyskytují úlohy na rozsáhlých sítích, které jsou zatíženy neurčitostí a jejich popis se mění v čase. Například je potřeba dynamicky přepočítávat betweenness centrality silniční sítě pod vlivem záplav a na jejím základě určit kritická místa v dopravní síti. Tento výpočet se normálně provádí pro celý graf, ale existují metody umožňující výpočet jenom pro vybrané části grafu. Pro praktické použití je nezbytné vytvořit efektivní paralelní algoritmy, které budou řešit podobné grafové úlohy v reálném čase na rozsáhlých grafech.

Aktuálnost tématu lze také doložit publikací článků, které se zabývají efektivními postupy výpočtu betweenness centrality, nejkratší cesty a propojení analýzy dynamických systémů s teorií grafů. Například Puzis et al. [1] se zabývají zrychlením výpočtu betweenness centrality pomocí využití topologie grafu. Riondato a Kornaropoulos [2] ve svém článku řeší efektivní aproximací výpočtu betwenness centrality pomocí náhodného vzorkování. Prezentují algoritmy jak pro výpočet celé sítě, tak pro K nejdůležitějších vrcholů. Článek napsaný Jasikou et al. [3] se zaměřuje na srovnání sériové a paralelní verze Dijsktrova algoritmu. Řešením problému nejkratší cesty v nejistém prostředí za využití fuzzy teorie se zabývá Deng et. al. [4]. Lampart a Zapoměl [5] používají test 0-1 chaosu k identifikaci dynamických vlastností experimentálních časových řad.
Postup řešení

Postup vypracování projektu lze shrnout do následujících dílčích cílů. Prvním postupným cílem je vypracování rešerše v oblasti práce s rozsáhlými dynamickými grafy zatíženými nejistotou. Tento postupný cíl bude splněn v březnu. Po splnění tohoto dílčího cíle bude následovat základní úprava metod vybraných na základě zpracované rešerše. Tyto metody budou vybrány na základě kvality jejich výstupů a možností jejich paralelizace. Splnění tohoto cíle je naplánováno na červenec. Následovat bude implementace těchto metod a také jejich případná příprava pro nasazení do jednotlivých projektů. Tohoto cíle bude dosaženo v listopadu. V průběhu celého roku pak bude probíhat práce na publikování výstupů z tohoto projektu a jejich výsledků.

[1] Puzis, R., Elovici, Y., Zilberman, P., Dolev, S., Brandes, U., Topology manipulations for speeding betweenness centrality computation, Journal of Complex Networks, 2015.
[2] Riondato, M., Kornaropoulos, E.M., Fast approximation of betweenness centrality through sampling, Data Mining and Knowledge Discovery, 2016.
[3] Jasika, N., Alispahic, N., Elma, A., Ilvana, K., Elma, L., Nosovic, N., Dijkstra's shortest path algorithm serial and parallel execution performance analysis, MIPRO 2012 Electronics and Microelectronics - Proceedings.
[4] Deng, Y., Chen, Y., Zhang, Y., Mahadevan, S., Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment, Applied Soft Computing Journal, 2012.
[5] Lampart, M., Zapoměl, J., Dynamical properties of a non-autonomous bouncing ball model forced by non-harmonic excitation, Mathematical Methods in the Applied Sciences, 2016.

Rozpočet projektu - uznané náklady

NávrhSkutečnost
1. Osobní náklady
Z toho
0,-0,-
1.1. Mzdy (včetně pohyblivých složek)0,-0,-
1.2. Odvody pojistného na veřejné zdravotně pojištění a pojistného na sociální zabezpečení a příspěvku na státní politiku zaměstnanosti0,-0,-
2. Stipendia64000,-64000,-
3. Materiálové náklady0,-0,-
4. Drobný hmotný a nehmotný majetek0,-0,-
5. Služby0,-0,-
6. Cestovní náhrady130000,-130000,-
7. Doplňkové (režijní) náklady max. do výše 10% poskytnuté podpory0,-0,-
8. Konference pořádané VŠB-TUO k prezentaci výsledků studentského grantu (max. do výše 10% poskytnuté podpory)0,-0,-
9. Pořízení investic0,-0,-
Plánované náklady194000,-
Uznané náklady194000,-
Celkem běžné finanční prostředky194000,-194000,-