Implementation and Evaluation of Multi-Agent Path Finding

Project Background

This project is connected to a recently started research collaboration between Örebro University and the autonomous mobile robots company Kollmorgen. Our aim is to develop robust multi-robot coordination for real-world robot fleets (for example, warehouse robots). In this project, you will work with algorithms for Multi-Agent Path Finding (MAPF), meaning algorithms that coordinate multiple robots in a shared environment so that they each can reach their targets without colliding [1][2][3]. In particular, we are interested in evaluating how variants of common algorithms, which are usually demonstrated on simplified and simulated setups, behave with real-world settings and constraints.

Project Description

Your contribution will be to implement one or several algorithm selected by your supervisor and evaluate them on realistic, industrial, data provided by Kollmorgen. Your focus will be on:

• Implementation: Developing robust C++ versions of these algorithms based on academic papers and existing open-source references.
• Adaptation: Modifying the algorithms to support our problem formulation. A key consideration is that in continuous time MAPF, you have to account for overlapping edges, where the physical sweeps of vehicles may intersect and cause collisions. In your work, you will need to adapt the state of the art algorithms to be compatible with our specific representation of such collision constraints.
• Experimental Evaluation: Running your implementation on a provided test bench featuring realistic scenarios and real-world deployment data from Kollmorgen.
• Analysis: Assessing performance metrics like success rate and computational efficiency.

This project is suitable for either a pair of students or a single student.

What you will gain

• Working within a robotics and AI research environment with ongoing projects in autonomous systems and multi-robot coordination, in collaboration with an industrial partner at the forefront of mobile robotics,
• Hands-on experience with state-of-the-art multi-robot algorithms
• Exposure to real-world industrial robotics systems and data
• Strong experience in C++ and algorithmic system development
• Insight into how research ideas translate into deployable solutions

Candidate Profile

• Strong programming skills in C++.
• Interest in algorithms, robotics, or autonomous systems.

References

[1] Roni Stern et al. “Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks”, 2019 [1906.08291] Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks

[2] Shiyue Wang et al. “Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding” [2505.19219] Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding

[3] A. Andreychuk et al. “Multi-Agent Pathfinding (MAPF) with Continuous Time” (2019) . [1901.05506] Multi-Agent Pathfinding with Continuous Time