Probability-based Path Planning for Multi-Robot Systems with Stochastic Behavior in a Grid Map

For the multi-robot path planning on a grid map, the widely adopted robot model assumes that its motion is deterministic once a path has been decided. However, this assumption is not quite realistic because some interferences such as noise, friction and inaccurate control input could disturb the robot motion, leading to a stochastic behavior. In this paper, we tackle the problem of planning a multi-robot path based on the robot probabilistic motion model. At the beginning, we model the robot action with several probability distributions, where the basic actions include going forward, turning left/right, going backward, and wait. We then extend A-star algorithm incorporating these actions such that an optimal path can be planned for a single robot. Based on this result, we apply conflict-based search to optimally plan path for a multi-robot system. Because probability calculation demands too much computation we simplify the conflict detection scheme and make it applicable for online practice.