Probabilistically Robust Continuous-time Multi-Agent Path Finding Dynamic Risk Allocation and Chance-Constrained Planning under Execution Uncertainty

Abstract

Automated logistics and multi-robot systems use Multi-Agent Path Finding (MAPF) algorithms to coordinate collision-free routes. In real-world industrial deployments, execution uncertainties such as mechanical variations and friction inevitably cause delays. Current robust MAPF algorithms handle this either through conservative worst-case deterministic bounds (in both discrete and continuous time) or through probabilistic models limited to discrete-time grids. This thesis bridges that gap by introducing a probabilistically robust framework for continuous-time MAPF, which is essential for maintaining predictable throughput by enabling proactive scheduling instead of reactive halting. To accurately model execution uncertainty, the proposed approach uses Gaussian distributions bounded by strict kinematic hardware limits. Instead of bounding maximum delays, the proposed approach models execution uncertainty using chance constrained programming, evaluating the overlapping probability density of agent trajectories. The framework uses a modified Continuous Conflict-Based Search (CCBS) paired with Safe Interval Path Planning (SIPP), and evaluates several heuristic risk allocation strategies to dynamically distribute a user-defined global risk budget across local interactions. The framework was evaluated on a standard benchmark environment, assessing metrics such as scalability, computational cost, risk utilization, and plan quality. Furthermore, Monte Carlo simulations were conducted to verify the robustness of the generated plans. The results show that the empirical execution success rate accurately matches the theoretical global risk calculated via the Union Bound. Ultimately, this confirms that the proposed framework successfully guarantees the collision risk of the system to be within the user-defined global risk budget, enabling a practical balance between schedule efficiency and system safety.