三维跳点搜索算法

问题描述 投票:4回答:2

是否有3维(甚至D维)jump point search算法的实现?

目前,我只能找到一个二维的,但是我认为可以为更高的尺寸制定算法。

algorithm geometry path-finding a-star
2个回答
1
投票

跳点算法归功于Harabor和Grastien在2011年发表的论文“用于在网格地图上进行寻路的在线图修剪”。在此原始论文中,他们的摘要说:

在本文中,我们提出了一种新颖的,特定于网格的搜索策略,该策略快速,最优并且不需要内存开销。

他们的2012年和2014年的后续论文似乎受到类似的限制。

使用Google Scholar搜索2011年论文的引文,其中包含“三个”一词(如三维),没有发现任何有希望的线索。

所以,我认为没有3D跳点搜索的描述。不过,最好的选择是给Harabor或Grastien发一封简短,措辞合理的电子邮件,询问相同的问题。如果您的问题足够吸引人,也许他们会解决问题并推出另一本出版物。


0
投票

我知道这个线程很旧,但是只是添加答案,以防有人仍然需要答案。下面的链接是UPenn的MRSL实验室的2D和3D jps的实现。

https://github.com/KumarRobotics/jps3d

本文介绍了将跳转点搜索扩展到3D:

“ S。Liu,M。Watterson,K。Mohta,K。Sun,S。Bhattacharya,CJ Taylor和V. Kumar。在3-D复杂环境中使用安全飞行走廊为四旋翼飞机动态可行的轨迹。ICRA 2017” 。

© www.soinside.com 2019 - 2024. All rights reserved.