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.