Dual Dijkstra Search for paths with different topologies

Abstract

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.