Learn all about Multi-Agent Path Finding (MAPF)
W. Hoenig, J. Preiss, S. Kumar, G. Sukhatme and N. Ayanian. Trajectory Planning for Quadrotor Swarms. IEEE Transactions on Robotics, 34, (4), 856-869, 2018.
Abstract: We describe a method for multirobot trajectory planning in known, obstacle-rich environments. We demonstrate our approach on a quadrotor swarm navigating in a warehouse setting. Our method consists of following three stages: 1) roadmap generation that generates sparse roadmaps annotated with possible interrobot collisions; 2) discrete planning that finds valid execution schedules in discrete time and space; 3) continuous refinement that creates smooth trajectories. We account for the downwash effect of quadrotors, allowing safe flight in dense formations. We demonstrate computational efficiency in simulation with up to 200 robots and physical plausibility with an experiment on 32 nano-quadrotors. Our approach can compute safe and smooth trajectories for hundreds of quadrotors in dense environments with obstacles in a few minutes.