Dual Dijkstra Search for paths with different topologies
Dual Dijkstra Search for paths with different topologies
复制标题
双 Dijkstra 搜索具有不同拓扑的路径
DOI：
10.1109/robot.2003.1242109
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Z. Shiller
中科院分区：
文献类型：
--
作者：
Y. Fujita;Yoshihiko Nakamura;Z. Shiller
本文介绍了一种新的搜索算法——双Dijkstra搜索。从给定的初始和最终配置中，双Dijkstra搜索可以同时找到具有不同拓扑结构的各种路径。该算法不仅可以枚举最优路径，还可以枚举局部最小路径中各种有意义的候选路径。它基于Dijkstra算法，这是一种常用的寻找最优解的算法。该方法包括两个步骤：首先计算局部极小值，并按最优性排序。然后根据它们的拓扑性质对它们进行分类，并在每一组中只取出最优路径。算例包括沿二维空间产生无碰撞运动和三自由度机器人的运动规划。我们还提出了运动压缩的思想，简化了高维运动规划问题。结合这一思想，我们将双Dijkstra搜索应用于七自由度手臂操作问题，成功地获得了多种候选运动。
This paper describes a new search algorithm, the Dual Dijkstra Search. From a given initial and final configuration, Dual Dijkstra Search finds various paths which have different topologies simultaneously. This algorithm allows you to enumerate not only the optimal one but variety of meaningful candidates among local minimum paths. It is based on the algorithm of Dijkstra, which is popularly used to find an optimal solution. The method consists of two procedures: First computes local minima and ranks the paths in order of optimality. Then classify them with their topological properties and take out only the optimal paths in each groups. Computed examples include generating collision-free motion along 2D space and motion planning of 3-DOF robot. We also proposed the idea of motion compression, which simplifies the high dimensional motion planning problem. Together with this idea, we applied Dual Dijkstra Search to 7-DOF arm manipulation problem and succeeded in obtaining variety of motion candidates.