CPS: Small: Novel Algorithmic Techniques for Drone Flight Planning on a Large Scale

Abstract: Good algorithmic foundations for flight planning on the scale required for managing dense urban drone traffic we can expect to see in the future are currently still missing. This project provides prototype algorithms for managing this dense drone traffic. The project develops a concept for a coordination system that is able to find collision-free paths for a large number of flying unmanned air vehicles of different size and capability. It uses a hierarchical approach, combining centralized and local coordination, to manage complexity for a large-scale problem. The approach developed here can scale up to handle thousands of drones and lead to conflict free flight. It demonstrates the concept using mixed-reality simulations and using existing helicopter-like robots on a smaller scale. Current multi-robot trajectory-planning algorithms typically operate on a single level (which limits their scalability) and assume holonomic robots that can hover motionlessly (which limits their applicability). The core of the project is the development of a novel hierarchical system that addresses these limitations, combining centralized methods with a divide-and-conquer approach. The hierarchical approach allows the system to negotiate collision-free trajectories on a local level, while ensuring that robots complete their tasks on the global level. Additional research integrates several speed-up techniques into the hierarchical system and generalizes its functionality, for example, to accommodate robots of different priorities (such as drones that deliver blood to hospitals). The research involves not only graduate but also undergraduate students and trains them in cross-disciplinary research.