Spring 2026
Master Thesis Project
Probabilistically Robust Continuous-time Multi-agent Path Finding
Turn your thesis into real innovation
Are you passionate about algorithms and optimization? Join us for a thesis project where your skills in programming and problem-solving can shape real-world solutions.
Project Description
Muti-Agent Path Finding (MAPF) addresses the fundamental problem of computing collision-free paths for multiple agents moving from their current locations to designated goals. This problem has gained importance across diverse applications, from warehouse and production automation to airport logistics, drone swarm operations, and video game character navigation.
The practical deployment of MAPF faces a critical challenge: real-world execution rarely matches the deterministic assumptions of planning algorithms. Agent speeds vary due to mechanical differences, environmental conditions, or dynamic obstacles, and unexpected events cause temporary slowdowns or accelerations. These uncertainties can lead to original movement plans being abandoned, else a collision may occur.
Traditional MAPF algorithms operate in discrete time, assuming agents move at every regular time-step. Recently, continuous-time algorithms have emerged to better match reality by eliminating these restrictive assumptions and allowing more realistic modeling of agent dynamics. Building on this progression toward realism, we aim to extend MAPF algorithms further to incorporate the unpredictability of real life, where execution times naturally vary.
This thesis proposes to develop probabilistic robustness techniques for continuous-time MAPF. Rather than planning for worst-case delays, we model each agent movement by a probability distribution, allowing plans to be optimized for specified confidence levels, Wait actions naturally serve as buffers that can reduce cumulative uncertainty propagation along trajectories, providing a mechanism for trading efficiency against robustness.
Tasks
The candidates will explore probabilistic robustness concepts in continuous-time MAPF, developing approaches that ensure probabilistic collision-free movement. The research direction is flexible, allowing the candidates to pursue their preferred approach to incorporating uncertainty modeling and confidence-based planning.
Concretely, the candidates will:
-
Conduct a comprehensive literature review covering robust MAPF variants, continuous-time path finding algorithms, and probabilistic planning under uncertainty.
-
Formalize the probabilistic continuous-time MAPF problem, defining how traversal time distributions propagate uncertainty and interact with collision constraints.
-
Delop algorithmic approaches that incorporate probabilistic robustness objectives and confidence-level constraints
-
Implement and evaluate the proposed algorithms on standard MAPF benchmarks, comparing against existing approaches across metrics of solution quality, robustness achievement, and computational efficiency.
-
Analyze the theoretical properties of the approach, including optimality guarantees and computational complexity.
The project offers significant flexibility for pursuing additional research directions, such as:
-
Investigating different probability distributions for modeling traversal uncertainties (Gaussian, exponential, heavy-tailed).
-
Exploring online replanning strategies when actual execution deviates from probabilistic predictions
-
Developing approximation algorithms for large-scale instances where exact probabilistic calculations become intractable.
-
Creating interactive visualizations to demonstrate probabilistic path planning and uncertainty propagation.
-
Benchmarking on realistic datasets with measured traversal time distributions.
Who Should Apply?
We seek motivated candidates with backgrounds in computer science, applied mathematics, operations research, or other algorithmic fields. Essential qualifications include programming proficiency and interest in algorithmic optimization. Having experience in optimization, path finding algorithms, probabilistic modeling, optimization methods, or multi-agent systems are advantageous, however not necessary.
What You Can Expect
This research addresses a fundamental limitation of current MAPF deployment by providing principled methods for planning under uncertainty, potentially enabling more reliable autonomous multi-agent systems in practical applications.
-
Supervision by experts in MAPF algorithms and probabilistic planning.
-
Access to computational resources for large-scale experimental evaluation.
-
A scientifically compelling project with strong publication potential.
-
Opportunity to contribute to next-generation robust multi-agent coordination systems with real world impact.
Practical Information
-
Start Date
Flexible, but ideally January or February 2026.
-
Supervisors
Alvin Combrink (Main supervisor) and Sabino Francesco Roselli (Co-supervisor), both working in the Department of Electrical Engineering, Automation research group at Chalmers University.
-
Application
Send an email to combrink@chalmers.se with short CV and grades transcript. Applications will be reviewed on a rolling basis.