  This study explores the problem of Multi-Agent Path Finding with continuous
and stochastic travel times whose probability distribution is unknown. Our
purpose is to manage a group of automated robots that provide package delivery
services in a building where pedestrians and a wide variety of robots coexist,
such as delivery services in office buildings, hospitals, and apartments. It is
often the case with these real-world applications that the time required for
the robots to traverse a corridor takes a continuous value and is randomly
distributed, and the prior knowledge of the probability distribution of the
travel time is limited. Multi-Agent Path Finding has been widely studied and
applied to robot management systems; however, automating the robot operation in
such environments remains difficult. 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. We use a greedy heuristic to obtain solutions in a
limited computation time. Through simulations, we empirically compare the
performance of our method to those of existing methods in terms of the conflict
probability and the actual travel time of robots. The simulation results
indicate that the proposed method can find travel paths with at least 50% fewer
conflicts and a shorter actual total travel time than existing methods. The
proposed method requires a small number of trials to achieve the performance
because the parameter update is prioritized on the important edges for path
planning, thereby satisfying the requirements of quick implementation of robust
planning of automated delivery services.
