四维数据的路径规划

Question

3

问题在于寻找一架飞机通过四维风（不同高度和随着旅行而变化的风（预测性风模型））的最佳路径。

我使用传统的A *搜索算法并将其修改为在三个维度和风矢量中工作。

它在很多情况下都有效但非常缓慢（我处理了大量数据节点）并且对某些边缘情况无效。

我觉得我已经使它“很好地”工作了，但感觉它非常混乱。

是否有更好更有效的寻路方式（也许是遗传算法或神经网络），或者我甚至没有考虑的东西？也许是流体力学？我不知道？

编辑：进一步细节。

数据是风向量（方向，大小）。数据在25个不同的海拔高度上间隔15x15km。

所谓“并非总是可行”，是指它会为一架飞机选择愚蠢的路径，因为路径权重与另一条路径相同。对于路径规划而言是可以接受的，但对于飞机来说则是次优的。

我为每个节点更改考虑了很多因素：

- 提升高度的成本大于下降的成本。 - 风阻力。 - 忽略阻力过高的节点。 - 对角线旅行成本与直行等的成本。

我使用欧几里得距离作为启发式或H值。我为我的权重或G值（上述列表）使用各种因素。

谢谢！

- jreid42

你的4D数组大小是多少？ - Saeed Amiri

3个回答

1

通过使用加权A*算法，您总是可以在时间优化上进行权衡。

加权A*（或A* epsilon）预计能够比A*更快地找到一条路径，但该路径可能不是最优路径（然而，它会给您一个关于其最优性的边界，作为epsilon/weight的参数）。

- amit

这就是我正在做的事情，所以有时会找到次优路径，但它运行良好。我只是好奇是否有更好的方法。 - jreid42

@jreid42：这要看你的启发式算法。如果你有一个完美的启发式算法——贪心最佳优先是最快的，而且也是最优的。但是如果启发式算法不完美，则可能不能达到最优。 - amit

0

你是计划线下还是线上的？

通常对于这些问题，直到你真正经历过它们，你才会知道风向如何。如果这确实是一个在线问题，你可能需要考虑尝试构建一个接近最优策略。在这个领域已经有相当多的研究了，其中最好的之一是 John Wharington 的《强化学习控制滑翔飞机》。

- Andrew Walker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Scott Hunter · Accepted Answer

A*算法并不是被宣传为最快的搜索算法；但是，它确保找到的第一个解决方案将是最佳的（假设您提供了一个可接受的启发式）。如果在某些情况下它不能正常工作，那么您的实现中可能有某些方面出了问题（也许是A*的机制，也许是特定于领域的问题；鉴于您没有提供任何细节，我们无法说更多）。

如果速度太慢，您可能需要重新考虑使用的启发式。

如果您不需要最优解，则其他一些技术可能更合适。同样，鉴于您提供的问题很少，我们无法说更多。