Škálovatelné plánování cest pro více agentů v rozsáhlých prostředích
| Název práce v češtině: | Škálovatelné plánování cest pro více agentů v rozsáhlých prostředích |
|---|---|
| Název v anglickém jazyce: | Scalable Multi-Agent Pathfinding in Large Environments |
| Akademický rok vypsání: | 2023/2024 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | |
| Ústav: | Katedra teoretické informatiky a matematické logiky (32-KTIML) |
| Vedoucí / školitel: | RNDr. Jiří Švancara, Ph.D. |
| Řešitel: | Vendula Pokludová - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 11.12.2023 |
| Datum zadání: | 16.12.2023 |
| Datum potvrzení stud. oddělením: | 16.12.2023 |
| Zásady pro vypracování |
| Multi-agent pathfinding (MAPF) is the task of navigating a set of agents in a shared environment without collisions. Finding an optimal solution in terms of the length of the plan is a computationally expensive task. Therefore, it may be beneficial to sacrifice optimality for scalability. The topic of the thesis is to design an approach to solve MAPF for large maps and large numbers of agents effectively by navigating each agent independently, and only if a collision is imminent an optimal solver is called on a constrained localized part of the map to avoid the collision. The bachelor thesis will include several approaches to creating such instances and an experimental evaluation comparing the approaches. |
| 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] Kyle Vedder, Joydeep Biswas. X*: Anytime Multi-Agent Path Finding for Sparse Domains using Window-Based Iterative Repairs. Artif. Intell. 291: 103417 (2021) [3] Poom Pianpak, Tran Cao Son. Improving Problem Decomposition and Regulation in Distributed Multi-Agent Path Finder (DMAPF). PRIMA 2022: 156-172. |