  Multi-agent path planning (MAPP) is the problem of planning collision-free
trajectories from start to goal locations for a team of agents. This work
explores a relatively unexplored setting of MAPP where streams of agents have
to go through the starts and goals with high throughput. We tackle this problem
by formulating a new variant of MAPP called periodic MAPP in which the timing
of agent appearances is periodic. The objective with periodic MAPP is to find a
periodic plan, a set of collision-free trajectories that the agent streams can
use repeatedly over periods, with periods that are as small as possible. To
meet this objective, we propose a solution method that is based on constraint
relaxation and optimization. We show that the periodic plans once found can be
used for a more practical case in which agents in a stream can appear at random
times. We confirm the effectiveness of our method compared with baseline
methods in terms of throughput in several scenarios that abstract autonomous
intersection management tasks.
