Robust Execution of MAPF Plans on Graphs with Continuous Space

• Thesis title in Czech: Robustní provádění MAPF plánů na grafech se spojitým prostorem
• Thesis title in English: Robust Execution of MAPF Plans on Graphs with Continuous Space
• Key words: multi-agentní hledání cest|provádění plánů|spojitý prostor
• English key words: multi-agent pathfinding|plan execution|continuous space
• Academic year of topic announcement: 2023/2024
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Supervisor: prof. RNDr. Roman Barták, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 22.07.2024
• Date of assignment: 22.07.2024
• Confirmed by Study dept. on: 22.07.2024
• Date and time of defence: 20.06.2025 09:00
• Date of electronic submission: 06.05.2025
• Date of submission of printed version: 06.05.2025
• Date of proceeded defence: 20.06.2025
• Opponents: Stefan Edelkamp, Dr. rer. nat.

Guidelines

Multi-agent pathfinding (MAPF) deals with the problem of finding collision-free paths for a group of mobile agents such that the agents reach their destinations. Usually, discrete space modelled by a graph is assumed, where agents are of the same size and each move step over any edge takes the same time. This thesis covers the problem with agents of different sizes and distances between the nodes of different lengths, where also the edges may overlap imposing more possible collisions. In particular, the goal of thesis is to explore and compare robust execution strategies in the above setting such that the strategy guarantees execution of given plans without collisions.

References

Anton Andreychuk, Konstantin S. Yakovlev, Dor Atzmon, Roni Stern: Multi-Agent Pathfinding with Continuous Time. IJCAI 2019: 39-45

Dor Atzmon, Roni Stern, Ariel Felner, Glenn Wagner, Roman Barták, Neng-Fa Zhou: Robust Multi-Agent Path Finding and Executing. J. Artif. Intell. Res. 67: 549-579 (2020)

Alexander Berndt, Niels van Duijkeren, Luigi Palmieri, Tamás Keviczky: A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph. CoRR abs/2010.05254 (2020)

Wolfgang Hönig, Scott Kiesel, Andrew Tinka, Joseph W. Durham, Nora Ayanian: Persistent and Robust Execution of MAPF Schedules in Warehouses. IEEE Robotics Autom. Lett. 4(2): 1125-1131 (2019)

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-158