🤖 AI

Declarative Problem Solving in UAM Strategic Deconfliction

本文提出了一种用于城市空中交通战略冲突解解的答案集编程（ASP）方法，并通过与约束规划的基准测试证明，在中小规模飞行规划场景中，ASP 具有更优越的执行速度和可扩展性。

原作者： Gioacchino Sterlicchio, Angelo Oddi, Riccardo Rasconi, Francesca Alessandra Lisi

发布于 2026-07-24

📖 1 分钟阅读☕ 轻松阅读

原作者： Gioacchino Sterlicchio, Angelo Oddi, Riccardo Rasconi, Francesca Alessandra Lisi

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，我们城市上空的景象即将变得繁忙得多。未来的天空不再只有寥寥几架飞机和直升机，而是充满了成千上万辆电动飞行器——比如巨大的无人机和空中出租车——在摩天大楼之间穿梭，进行包裹递送或载人通勤。这被称为“城市空中交通”（UAM）。大问题在于：如果每个人都想随心所欲地飞行，他们就会互相碰撞，或者陷入大规模的空中交通拥堵。为了解决这个问题，科学家们需要一种方法，在每个人起飞之前就规划好他们的飞行路径。这被称为“策略性冲突解解”（strategic deconfliction），这只是一个高级说法，意思就是“确保没有两个飞行物体试图同时出现在同一个位置”。为了解决这个问题，研究人员使用特殊的计算机语言，它们就像超级聪明的拼图求解器。一种求解器被称为“约束编程”（CP），它就像一位非常严格的图书管理员，在允许书籍借出前会检查每一条规则。另一种则是“答案集编程”（ASP），它更像是一位富有创造力的建筑师，能够快速勾勒出许多可能的蓝图，并从中挑选出最符合所有安全规则的那一个。

这篇论文介绍了一个名为 STRADA 的新系统，它使用这种富有创造力的建筑师方法（ASP）来解决 UAM 交通谜题。作者们是一支来自意大利的研究团队，他们想看看这种创造性的方法是否能比严格的图书管理员方法（CP）更好地处理繁忙城市天空中的混乱。他们利用“航道”（就像空中的隐形高速公路）构建了一个数字化的天空模型，并模拟了数千辆飞行器试图通过这些航道的场景。他们通过增加飞行器的数量以及让起飞时间窗口变宽或变窄来测试他们的系统。

实验结果有点像短跑选手与马拉松选手之间的比赛。当飞行器数量较少或中等规模（约 30 0 辆）时，ASP 系统（STRADA）速度极快，能在几秒钟内找到安全的飞行计划。它比 CP 系统快得多，后者甚至要花很长时间才能找到一个解。然而，ASP 系统也有一个代价：它消耗了大量的计算机内存。当团队尝试模拟拥有 5,000 辆飞行器的极度拥挤的天空或非常宽的起飞窗口时，ASP 系统耗尽了内存并崩溃了，就像大脑试图同时思考太多想法而导致宕机一样。相比之下，CP 系统虽然速度较慢，但在管理内存方面表现得更好；即使它完成工作需要很长时间，但它不会像那样轻易崩溃。

简而言之，这篇论文表明，对于中小规模的城市天空，富有创造力的 ASP 方法是赢家，因为它既快速又高效。但如果天空变得过于拥挤，或者规划规则变得过于宽松，该系统就会撞上一堵墙。作者们总结道，虽然他们的新方法是管理未来空中交通的一个很好的第一步，但他们需要找到方法，使其在不耗尽内存的情况下处理更大规模的流量。他们还计划在真实世界的数据和不同的计算机系统上测试他们的想法，以观察其在现实世界中是否依然有效。

技术摘要：用于 UAM 战略冲突解脱的声明式问题求解

问题定义

本文探讨了城市空中交通 (UAM) 战略冲突解脱 (Strategic Deconfliction, SD)，这是空中交通管理中一个关键的预飞行规划层。随着人口密集地区航空飞行器（无人机、空中出租车、eVTOL）需求的增加，空中碰撞以及与现有交通发生冲突的风险也随之上升。核心问题是生成一组计划飞行路径，使得没有任何两架飞行器在时间和空间上违反指定的安全距离或间隔 (headway) ( $h$ )。

该问题被形式化为一个二元组 $(N, F)$ ，其中 $N$ 是代表空中交通网络（节点作为入口/出口点或航路点，边作为单向走廊）的有向图， $F$ 是待调度的飞行集合。每个飞行 $f_i$ 由其航线（一个无环子图）、起始/终止节点、速度以及请求的发射时间区间 $[e_i, l_i]$ 定义。目标是为每架飞行分配特定的航线和出发时间，使得：

飞行在请求的时间区间内出发。
共享起始节点的飞行具有至少间隔 $h$ 的不同出发时间。
在任何时刻占据相同节点或航道的飞行保持至少间隔 $h$ 的安全时间间隔。
总延迟（实际发射时间与最早请求时间之差）最小化。

方法论

作者提出了 STRADA（基于 ASP 的可扩展轨迹解析架构），这是一个基于回答集编程 (Answer Set Programming, ASP) 的框架。这种方法与传统的数值方法和现有的约束规划 (Constraint Programming, CP) 编码形成了对比。

1. 建模方法

STRADA 使用基于车道 (lane-based) 的空中结构对 SD 问题进行建模，其中车道是有向图。该框架支持两种变体：

恒定速度： 所有飞行器在所有车道上保持固定速度。
可变速度： 速度可以根据障碍物或天气进行调整，这需要对编码中的速度谓词进行修改。

ASP 编码（使用 clingo 求解器实现）利用了：

事实 (Facts)： 用于定义网络拓扑（节点、边、长度）、间隔约束和飞行规格（航线、速度、时间窗口）。
规则 (Rules)： 用于计算飞行器穿越车道时的预计到达时间 (ETA)，即基于距离和速度。
完整性约束 (Integrity Constraints)： 用于消除违反安全约束（例如，两个飞行器在时间间隔不足的情况下处于同一节点，或两个飞行器在同一车道上交叉路径）的无效回答集。
优化 (Optimization)： 使用 #minimize 指令来最小化所有飞行的总延迟。

2. 对照基准

将 ASP 方法与 约束规划 (CP) 编码（使用 Minizink/Gecode 求解）进行基准测试。CP 通过变量、定义域和约束来定义问题，旨在找到满足所有条件的解。

主要贡献

本文做出了三个主要贡献：

ASP 形式化： 提供了首次基于逻辑的 UAM 战略冲突解脱问题形式化，定义了冲突无关轨迹规划的必要条件。
STRADA 框架： 引入了一个完整的框架，能够模拟空中网络拓扑、无人机机队，并进行 SD 编码，能够处理恒定速度和可变速度场景。
实证评估： 通过在不同飞行量、发射间隔大小和网络拓扑（城内、城际、机场穿梭、合成网格）下，对 STRADA (ASP) 与 CP 进行全面的可扩展性分析比较。

实验结果

实验在一台笔记本电脑（AMD Ryzen 5, 8GB RAM）上进行，设置了 900 秒的超时时间。研究改变了飞行数量（15–400）、发射间隔（5–50 分钟）和网络规模（3x3 到 5x5 网格）。

执行时间 vs. 可扩展性：
- ASP (STRADA)： 对于中小规模问题（例如，较少的飞行次数、较窄的间隔）表现出卓越的执行速度。然而，随着复杂度的增加，它在可扩展性方面面临挑战。对于高飞行计数（300+）或较大的发射间隔，ASP 经常达到时间限制或耗尽内存（出现内存溢出错误），在归约 (grounding) 阶段表现出“组合爆炸”。
- CP： 通常比 ASP 需要显著更多的执行时间，即使在处理中等规模问题时，也经常无法在时限内找到最优解。然而，CP 在不同问题规模下表现出更稳定且高效的内存使用，很少出现 ASP 失败时遇到的内存限制问题。
网络拓扑的影响：
- ASP 的执行时间随飞行数量呈线性增长，但由于原子和规则的生成，随网络规模的变化呈非线性增长。
- 在 5x5 网格及 5,000 架次飞行的实验中观察到一个关键阈值，此时内存使用量从 ~80 MB 激增至 7.10 GB，表明当前模型在高密度场景下的极限。

重要性与主张

本文声称引入了首个基于 ASP 的 UAM 战略冲突解脱公式。作者强调了其方法的三个关键优势：

简化且易读的建模： ASP 的声明式特性允许对复杂约束进行简洁的表示。
支持复杂优化： ASP 有效地处理了轨迹规划的组合性质。
适应性： 该框架可以在无需重大重编程的情况下适应规格变化（例如，可变速度）。

研究结论指出，虽然 ASP 对于较小的实时战略冲突解脱任务提供了更快的执行速度，但其可扩展性目前受限于高密度场景下的内存约束。相反，CP 提供了更好的内存稳定性，但存在执行时间较差的问题。作者指出，目前的实验参数符合当代 UAM 基准，但也建议未来的工作必须针对现实世界数据集验证模型，并探索跨平台求解器性能，以全面评估在高密度城市环境下的可扩展性。