Při navigaci skladových robotů, koordinaci dronů i řízení leteckého provozu nastává zásadní problém: jak naplánovat trasy stovek agentů tak, aby se ve stejném místě a čase nesrazili? Hledání cest pro více agentů (MAPF) představuje jedno z nejsledovanějších a nejžhavějších témat současné informatiky. Tradiční výpočetní postupy na velkých mapách narážejí na své limity a výpočet často ani nedokončí. Vendula Pokludová ve své bakalářské práci zvolila kombinovaný přístup, který nejprve najde trasy jednotlivců a následně řeší jen místa se skutečnými konflikty. V rozhovoru popisuje, jak jí při odhalování chyb pomohla vlastní vizualizace i proč má její postup potenciál pro využití v praxi.
O čem přesně vaše bakalářská práce je a jaký problém řeší?
Cílem mé práce bylo představit nový přístup k řešení problému víceagentního hledání cest (Multi-Agent Pathfinding, dale jen MAPF). Tento problém spočívá v tom, že je třeba naplánovat pohyb agentů po společné mapě tak, aby se navzájem nedostali do konfliktu. Každý agent má určenou počáteční a cílovou pozici a ke konfliktu dochází tehdy, když se agenti ve stejný okamžik nachází na stejném místě nebo se pohybují po stejné hraně. V práci zkoumám kombinovaný přístup, který nejprve využije jednoduchý algoritmus pro nalezení cest jednotlivých agentů a následně vyhledává a řeší pouze ty části mapy, ve kterých ke konfliktům skutečně dochází.
Co vás inspirovalo k tomu, abyste se zaměřila právě na toto téma?
Jednou z mých hlavních priorit bylo najít vedoucího práce, u kterého jsem věděla, že mi dokáže pomoci jak s programátorskou částí bakalářské práce, tak i s jejím samotným sepsáním. V oblasti umělé inteligence jsem byla poměrně nová, ale věděla jsem, že chci najít téma z tohoto oboru. Se svým vedoucím, RNDr. Jiřím Švancarou, Ph.D., jsem se už znala, protože vedl mé cvičení k předmětu Úvod do umělé inteligence. Jeho předchozí práce mě velmi zaujaly, protože mě vždy přitahovala témata spojená s mapami a navigací, a proto mi to připadalo jako ideální volba, když mi navrhl toto téma bakalářské práce.
Jaký konkrétní přínos má vaše práce?
Práce se zaměřila na návrh řešení problému víceagentního hledání cest (MAPF), které bude dostatečně škálovatelné. Cílem tedy bylo, aby navržený postup fungoval spolehlivě i na velmi rozsáhlých mapách a při velkém počtu agentů. Podobně rozsáhlé úlohy se objevují i v praxi, například při navigaci skladových robotů, ve swarm robotice nebo při řízení leteckého provozu.
S jakými technologiemi jste pracovala, jaké metody jste využívala, a proč zrovna tyto?
Nepoužila jsem žádné speciální technologie, ale k lepšímu pochopení problému mi velmi pomohlo, že jsem si napsala kód pro vizualizaci konkrétní instance úlohy. Představit si pohyb velkého počtu agentů na mřížce jen podle seznamů jejich souřadnic bylo dost obtížné. Jakmile jsem ale měla možnost jejich pozice a pohyby zobrazit přímo na mapě i s překážkami a hranicemi, byla jsem schopna chyby odhalovat mnohem rychleji.
Vizualizace
pohybu agentů před vyřešením konfliktů a po něm
Co bylo během psaní vaší práce nejtěžší, bylo něco, na čem jste se zasekla, nějaká cesta, co nikam nevedla? Je něco, co byste zpětně udělala jinak?
Samotné psaní kódu nebylo příliš obtížné, jakmile jsem měla představu, jak začít a jak konflikty rozdělit do jednotlivých typů. Od té chvíle jsem spíše zkoušela různé nápady a experimentovala s možnými řešeními. Aby to celé fungovalo, bylo ale nesmírně důležité všechno pečlivě a srozumitelně dokumentovat. Občas jsem na to zapomněla a pak jsem se ve vlastní práci hůře orientovala.
Jakým způsobem jste ověřovala výsledky své práce?
Pro experimentální část jsem zvolila pět různých map o velikostech od 48×48 až po 256×256, které jsem získala z webu poskytujícího referenční scénáře pro testování problému víceagentního hledání cest (movingai.com/benchmarks/mapf/index.html). Každá mapa obsahovala stovky definic agentů a na každé z nich jsme zkoušeli různé počty agentů (vždy po stovkách). Během těchto experimentů jsem sbírala téměř všechny metriky, které mě napadly, abych získala co nejvíce informací. Mezi sledované metriky patřil například počet konfliktů po vyřešení, celkový čas běhu programu nebo maximální délka cesty před a po vyřešení konfliktů. Celkem jsem při každém spuštění zaznamenávala osm různých typů metrik.
Co považujete za nejdůležitější výsledek nebo závěr své práce?
Výsledky provedeného výzkumu lze chápat jako přesvědčivý důkaz proveditelnosti zvoleného přístupu. Zároveň ukazují, že při zapojení dalších prostředků a provedení vhodných optimalizací by mohl tento kombinovaný postup představovat velmi užitečné řešení i pro rozsáhlé instance problému MAPF. Je důležité zdůraznit, že současné optimální přístupy by na takto velkých mapách vůbec nedokončily výpočet, zatímco navržený přístup byl schopen poskytnout výsledky v rozumném čase.
Máte pocit, že vaše práce může být inspirací pro další studenty nebo odborníky v dané oblasti?
Téma považuji za zajímavé i z hlediska dalšího rozšíření, protože dosud nebylo detailněji prozkoumáno. Zároveň vidím možnost, aby se někdo inspiroval kombinovaným přístupem k MAPF a pokusil se jej uplatnit i na jiné problémy, které lze podobně rozdělit na menší části.
Jaké jsou vaše plány do budoucna?
Aktuálně studuji na Matfyzu v navazujícím magisterském programu a zároveň absolvuji stáž ve firmě JetBrains. S touto firmou také plánuji spolupracovat na své diplomové práci.
Odkazy:
Bakalářská práce: Škálovatelné plánování cest pro více agentů v rozsáhlých prostředích
Zdrojové kódy a projekt na GitHubu
Původní materiál Informatické sekce
