Efficient optimal search of uniform-cost grids and lattices
Efficient optimal search of uniform-cost grids and lattices
复制标题
均匀成本网格和点阵的高效最优搜索
DOI：
10.1109/iros.2004.1389682
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
J. Kuffner
中科院分区：
文献类型：
--
作者：
J. Kuffner
一个简单的技术，以加快最优路径规划的欧氏成本网格和格子。许多机器人导航规划算法构建环境的近似网格表示，并使用Replikstra算法或A* 来搜索所得到的嵌入图，以获得给定起始位置和目标位置之间的最佳路径。然而，这些搜索算法的经典实现被设计为在具有任意正权重值的边的任意图上找到最优路径。本文介绍了如何利用欧几里德成本网格和格的最优路径的结构，以减少在节点扩展步骤中考虑的相邻节点的数量。结果是检查的总节点的适度减少，这降低了搜索的总体内存需求和计算成本。这些改进提高了2D和3D网格上的最优机器人导航规划的效率，并且该技术推广到任何其他搜索问题，包括在更高维度的网格和网格上找到最优路径，其边缘成本服从三角不等式。
A simple technique is described 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 moderate reduction in the total nodes examined, which reduces the overall memory requirements and computational cost of the search. These improvements increase the efficiency of optimal robot navigation planning on 2D and 3D grids, and the technique generalizes to any other search problem that involves finding optimal paths on grids and lattices in higher dimensions whose edge costs obey the triangle inequality.