The multi-agent path fifinding (MAPF) problem is defifined as follows: Given a graph and a set of agents with unique start and goal vertices, fifind collision-free paths for all agents from their respective start vertices to their respective goal vertices. Our objective is to minimize the the total arrival time. MAPF has many applications such as video games, traffific control and robotics. Solving the MAPF problem optimally, whether the objective is to minimize the makespan, the total distance traveled or the total arrival time, is NP-hard [Yu and LaValle, 2013]. Optimal MAPF approaches, such as Conflflict-Based Search (CBS) [Sharon et al., 2015] and M⇤ [Wagner and Choset, 2015], therefore can be used only for low numbers of agents. Yet, fifinding low-cost solutions is important because the same throughput can then be achieved with fewer agents. It is therefore common to use bounded-suboptimal1 MAPF approaches for higher numbers of agents. Existing bounded-suboptimal MAPF approaches, such as EnhancedCBS (ECBS) [Barer et al., 2014] and inflflated-rM* [Wagner and Choset, 2015], fifind solutions quickly when the MAPF instances are not tightly-coupled (that is, when ECBS does not need to resolve many conflflicts or inflflated-rM* does not need to expand large subdimensions). However, in many application domains this is not the case, and the runtime of these approaches degrades severely. For example, ECBS was shown to scale poorly on a model of an automated warehousing system used by Amazon (formerly called Kiva) with many agents and long narrow corridors [Cohen et al., 2015].