Dual Dijkstra search for paths with different topologies

This paper describes a new search algorithm, Dual Dijkstra Search. From a given initial and final configuration, Dual Dijkstra Search finds various paths which have different topologies simultaneously. This alogrithm 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[10], which is populary 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 3DOF 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 7DOF arm manipulation problem and succeeded in obtaining variety of motion candidates.