Quoting from Wang and Botea 2011:
An instance is characterized by a graph representation of a map, and a non-empty collection of mobile units $U$. Units are homogeneous in speed and size. Each unit $u \in U$ has an associated start-target pair $(s_u, t_u)$. All units have distinct starting and target positions.
The objective is to navigate all units from their start positions to the targets while avoiding all fixed and mobile obstacles.
The MAPP algorithm presented in this paper is complete for most instances of this (Multi-Agent Path Planning) problem.
After implementing MAPP myself (even using the suggested "replanning with counting" technique), it seemed that many of the solutions obtained were far from optimal in path length, having many units that went near their goals than back near their starts multiple times.
Specifically, I'm interested in the subset of this problem that has groups of units very near each other and groups of goals very near each other, as you might see in an RTS, for example. Are there better algorithms for these kinds of instances, or better repositioning strategies for MAPP?