Heterogeneous Multi-Robot Path Planning Based on Probabilistic Motion Model

An important problem in multi-robot system is how to coordinate robot's motion such that each robot can complete its task without collision. Previous approaches assume that robots' motion is deterministic once their paths have been planned, which is however not realistic because random interferences such as noise, friction and inaccurate control input in real-life system could disturb the robot motion, leading to a stochastic behavior. In this paper, we take this stochastic behavior into account when planning the path for a heterogeneous multi-robot system. We assume that the motion time of a robot from a location to another can be modeled as a probability distribution. Every robot has its own probability distribution of motion time between any two neighbor locations. We develop a conflict-detection scheme for this model and propose using the conflict-based search algorithm via probability calculation to find the optimal path that minimizes the entire motion time. We also simplify this conflict detection such that our proposed approach is applicable online for a large-scale system. Experimental results demonstrate the high effectiveness of our proposed approaches.