This paper presents an efficient approach to global path planning for multiple agents during large-scale map deformation. The problem of planning using dense data during large-scale map deformation is addressed by using a hybrid metric-topological planner that maintains locally consistent policies. These policies are cached, providing efficiency gains relative to alternate planning approaches that are characterized using complexity analysis. Simulation results show the effectiveness of this approach in handling notable map deformation while achieving good efficiency. © 2011 IEEE.