Efficient Optimal Search of Euclidean-Cost Grids and Lattices
Efficient Optimal Search of Euclidean-Cost Grids and Lattices
复制标题
欧氏成本网格和格子的高效最优搜索
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
J. Kuffner
中科院分区：
文献类型：
--
作者：
J. Kuffner
我们描述了一个简单的技术，以加快最优路径规划的欧氏成本网格和格子。许多机器人导航规划算法构建环境的近似网格表示，并使用Replikstra算法或A * 来搜索所得到的嵌入图，以获得给定起始位置和目标位置之间的最佳路径。然而，这些搜索算法的经典实现被设计为在具有任意正权重值的边的任意图上找到最优路径。本文介绍了如何利用欧几里德成本网格和格的最优路径的结构，以减少在节点扩展步骤中考虑的相邻节点的数量。其结果是减少了检查的总节点以及搜索的总成本。该算法提高了机器人导航规划的效率，在2D和3D网格，并推广到任何其他搜索问题，涉及搜索欧几里德成本网格和格在更高的维度。
We describe a simple technique to speed up optimal path planning on Euclidean-cost grids and lattices. Many robot navigation planning algorithms build approximate grid representations of the environment and use Djikstra’s algorithm or A* to search the resulting embedded graph for an optimal path between given start and goal locations. However, the classical implementations of these search algorithms were designed to find optimal paths on arbitrary graphs with edges having arbitrary positive weight values. This paper explains how to exploit the structure of optimal paths on Euclidean-cost grids and lattices in order to reduce the number of neighboring nodes considered during a node expansion step. The result is a reduction in both the total nodes examined as well as the overall cost of the search. The algorithm presented increases the efficiency of robot navigation planning on 2D and 3D grids, and generalizes to any other search problem that involves searching Euclideancost grids and lattices in higher dimensions.