|
|
Ořezávání grafu pro multiagentní plánování cest
Husár, Matej ; Švancara, Jiří (vedoucí práce) ; Ivanová, Marika (oponent)
V tejto práci sa zameriame na zrýchlenie celkového výpočtu optimálneho multiagentového plánovania ciest, ktoré je NP-ťažkým problémom, preto jeho riešenie budeme hľadať pomocou SAT riešiča. Na dosiahnutie tohto výsledku využijeme orezávanie grafu, ktoré spočíva v odstránení takých vrcholov z pôvodného grafu, ktoré agenti nemusia využiť, a preto predstavujú takéto vrcholy zbytočnú záťaž pre SAT riešič. Na riešenie tejto úlohy navrhneme tri algoritmy, pričom ich následne experimentálne porovnáme so základným bežným algoritmom. Na jednotlivých navrhovaných algoritmoch nás bude zaujímať ich celková rýchlosť výpočtu, ale taktiež aj optimalita nimi nájdeného výsledku. Ukážeme si, že jeden z navrhovaných algoritmov zachováva optimalitu a tiež prináša aj značné zrýchlenie vo výpočte na veľkých grafoch.
|
host ::
RSS.