  In multi-agent applications such as surveillance and logistics, fleets of
mobile agents are often expected to coordinate and safely visit a large number
of goal locations as efficiently as possible. The multi-agent planning problem
in these applications involves allocating and sequencing goals for each agent
while simultaneously producing conflict-free paths for the agents. In this
article, we introduce a new algorithm called MS* which computes an optimal
solution for this multi-agent problem by fusing and advancing state of the art
solvers for multi-agent path finding (MAPF) and multiple travelling salesman
problem (mTSP). MS* leverages our prior subdimensional expansion approach for
MAPF and embeds the mTSP solvers to optimally allocate and sequence goals for
agents. Numerical results show that our new algorithm can solve the multi-agent
problem with 20 agents and 50 goals in a minute of CPU time on a standard
laptop.
