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

在管理密集的城市无人机交通所需的规模上进行飞行规划的良好算法基础目前仍然缺乏。该项目为管理这种密集的无人机流量提供了原型算法。该项目开发了一个协调系统的概念，该系统能够为大量不同大小和能力的飞行无人机找到无碰撞路径。它使用分层方法，将集中协调和本地协调相结合，以管理大规模问题的复杂性。这里开发的方法可以扩展到处理数千架无人机，并导致无冲突飞行。它使用混合现实模拟和较小规模的现有直升机状机器人来演示这一概念。当前的多机器人轨迹规划算法通常只在一个层面上运行(这限制了它们的可扩展性)，并假设完整机器人可以静止悬停(这限制了它们的适用性)。该项目的核心是开发一种新的层级系统，以解决这些限制，将集中化方法与分而治之的方法相结合。这种分层方法允许系统在局部级别协商无碰撞轨迹，同时确保机器人在全局级别上完成任务。其他研究将几种加速技术整合到分级系统中，并推广其功能，例如，容纳不同优先级的机器人(如向医院输送血液的无人机)。这项研究不仅涉及研究生，也包括本科生，并对他们进行跨学科研究培训。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.