Ořezávání grafu pro multiagentní plánování cest
| Název práce v češtině: | Ořezávání grafu pro multiagentní plánování cest |
|---|---|
| Název v anglickém jazyce: | Graph pruning for multi-agent pathfinding |
| Klíčová slova: | Multiagentní plánování cest|SAT|Ořezávání |
| Klíčová slova anglicky: | Multi-agent pathfinding|SAT|Pruning |
| Akademický rok vypsání: | 2020/2021 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | čeština |
| Ústav: | Katedra softwaru a výuky informatiky (32-KSVI) |
| Vedoucí / školitel: | RNDr. Jiří Švancara, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 22.10.2020 |
| Datum zadání: | 27.10.2020 |
| Datum potvrzení stud. oddělením: | 10.11.2020 |
| Datum a čas obhajoby: | 10.09.2021 09:00 |
| Datum odevzdání elektronické podoby: | 18.07.2021 |
| Datum odevzdání tištěné podoby: | 22.07.2021 |
| Datum proběhlé obhajoby: | 10.09.2021 |
| Oponenti: | Mgr. Marika Ivanová, Ph.D. |
| Zásady pro vypracování |
| Řešiče multiagentního plánování cest (MAPF), které jsou založené na převodu na problém splnitelnosti (SAT) nejsou v současnosti efektivní při řešení velkých map. Důvodem je velké množství proměnných reprezentující pozice, které vstupují do SAT solveru. Cílem práce je navrhnout efektivní postup jak ořezat velké mapy a zefektivnit tak výpočet při zachování optimality. |
| Seznam odborné literatury |
| Roni Stern, Nathan R. Sturtevant, Ariel Felner, Sven Koenig, Hang
Ma,Thayne T. Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. SatishKumar, Roman Barták, and Eli Boyarski. Multi-agent pathfinding: Definitions, variants, and benchmarks. In Proceedings of the Twelfth International Symposium on Combinato-rial Search, SOCS 2019, Napa, California, 16-17 July 2019, pages 151–159. AAAI Press, 2019. Roman Barták and Jiří Švancara. On sat-based approaches for multi-agent path finding with the sum-of-costs objective. In Proceedings of the Twelfth International Symposium on Combinatorial Search, SOCS 2019, Napa, California, 16-17 July 2019, pages 10–17, 2019. Roman Barták, Neng-Fa Zhou, Roni Stern, Eli Boyarski, and Pavel Surynek. Modeling and solving the multi-agent pathfinding problem in picat. In 29th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2017, Boston, MA, USA, November 6-8, 2017, pages 959–966, 2017. |