Online Re-Planning and Adaptive Parameter Update for Multi-Agent Path Finding with Stochastic Travel Times

This study explores the problem of Multi-Agent Path Finding with continuous and stochastic travel times whose probability distribution is unknown. It is often the case with real-world applications (e.g., automated delivery services in office buildings) that the time required for the robots to traverse a corridor takes a continuous value and is randomly distributed because pedestrians and a wide variety of robots coexist, and the prior knowledge of the probability distribution of the travel time is limited. We propose 1) online re-planning to update the action plan of robots while it is executed and 2) parameter update to estimate the probability distribution of travel time using Bayesian inference as the delay is observed. Through simulations, we empirically compare the performance of our method to those of existing methods.