Ořezávání grafu pro multiagentní plánování cest
| Thesis title in Czech: | Ořezávání grafu pro multiagentní plánování cest |
|---|---|
| Thesis title in English: | Graph pruning for multi-agent pathfinding |
| Key words: | Multiagentní plánování cest|SAT|Ořezávání |
| English key words: | Multi-agent pathfinding|SAT|Pruning |
| Academic year of topic announcement: | 2020/2021 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Department of Software and Computer Science Education (32-KSVI) |
| Supervisor: | RNDr. Jiří Švancara, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 22.10.2020 |
| Date of assignment: | 27.10.2020 |
| Confirmed by Study dept. on: | 10.11.2020 |
| Date and time of defence: | 10.09.2021 09:00 |
| Date of electronic submission: | 18.07.2021 |
| Date of submission of printed version: | 22.07.2021 |
| Date of proceeded defence: | 10.09.2021 |
| Opponents: | Mgr. Marika Ivanová, Ph.D. |
| Guidelines |
| Ř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. |
| References |
| 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. |