Fast, near-optimal computation for multi-robot path planning on graphs

摘要

We report a new method for computing near optimal makespan solutions to multi-robot path planning problem on graphs. Our focus here is with hard instances- those with up to 85 % of all graph nodes occupied by robots. Our method yields 100-1000x speedup compared with existing methods. At the same time, our solutions have much smaller and often optimal makespans. Introduction and Problem Formulation In this paper, we study centralized multi-robot path plan-ning problems on graphs, also known as cooperative path-finding (Silver 2005; Ryan 2008; Standley and Korf 2011; Surynek 2012b). Our focus is on finding plans with opti-