Multi-Agent pathfinding (MAPF) is the problem of finding collision-free paths for multiple agents to their respective goal locations. MAPF has applications in navigation, warehouse automation, package delivery and games. Finding optimal solutions to MAPF problems is NP-hard (Yu and LaValle 2013). However, sub-optimal solutions are acceptable for some applications. Polynomial time sub-optimal solvers exist for unit cost graphs (Kornhauser, Miller, and Spirakis 1984), but may not produce valid solutions in complex domains with non-unit costs, non-uniform action durations, shaped agents and/or non-holonomic or kinodynamic movement constraints.