Multi-Robot Path Planning for Each Robot with Several Jobs in a Single Trip

The path planning problem is important and has been well-studied in multi-robot systems. Current approaches have a common assumption that each robot is required to move from a start point to another one, while implicitly ignoring the fact that a robot may be assigned several jobs in a single trip. In this paper, we take this fact into account and propose optimal path planning solutions. The studied problem is modeled as a max-flow problem of a network, and integer linear programming(ILP) solver can be used to find its optimal solution. However, the optimal solver suffers the problem of dimensional disaster and becomes impractical for a large-scale system. We thus propose a heuristic approach to find a sub-optimal solution with an acceptable computation time. Experimental results demonstrate the high effectiveness of our proposed approaches.