Improved graph pruning for multi-agent pathfinding using heuristics
| Název práce v češtině: | Vylepšení ořezávání grafu pro multiagentní plánování cest pomocí heuristik |
|---|---|
| Název v anglickém jazyce: | Improved graph pruning for multi-agent pathfinding using heuristics |
| Klíčová slova: | Multiagentní plánování cest|SAT|Heuristiky pro ořezávání|Klíčové vrcholy |
| Klíčová slova anglicky: | Multi-agent pathfinding|SAT|Pruning heuristics|Ground vertices |
| Akademický rok vypsání: | 2023/2024 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra teoretické informatiky a matematické logiky (32-KTIML) |
| Vedoucí / školitel: | RNDr. Jiří Švancara, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 15.09.2023 |
| Datum zadání: | 15.09.2023 |
| Datum potvrzení stud. oddělením: | 22.09.2023 |
| Datum a čas obhajoby: | 09.06.2025 09:00 |
| Datum odevzdání elektronické podoby: | 30.04.2025 |
| Datum odevzdání tištěné podoby: | 30.04.2025 |
| Datum proběhlé obhajoby: | 09.06.2025 |
| Oponenti: | prof. RNDr. Roman Barták, Ph.D. |
| Zásady pro vypracování |
| Multi-agent pathfinding (MAPF) is the task of navigating a set of agents in a shared environment in a collision-free manner. The task of this thesis is to improve an existing reduction-based algorithm [2] for solving MAPF. In the existing approach, a random shortest path is chosen for each agent, and vertices far from the shortest paths are pruned. The student's task is to further improve the approach by selecting the shortest paths more sophistically. The selection methods may include heuristic approaches as well as learning approaches. Experimental comparison and evaluation will also be part of the thesis. |
| Seznam odborné literatury |
| [1] Roni Stern, Nathan R. Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T. Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Satish Kumar, Roman Barták, Eli Boyarski. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks. SOCS 2019: 151-159
[2] Matej Husár, Jirí Svancara, Philipp Obermeier, Roman Barták, Torsten Schaub. Reduction-based Solving of Multi-agent Pathfinding on Large Maps Using Graph Pruning. AAMAS 2022: 624-632 [3] Stuart Russell, Peter Norvig. Artificial Intelligence: A Modern Approach (4th Edition). Pearson 2020, ISBN 9780134610993 [4] Christopher M. Bishop. Pattern recognition and machine learning, 5th Edition. Information science and statistics, Springer 2007, ISBN 9780387310732, pp. I-XX, 1-738 |