Dual Dijkstra search for planning multipe paths
AssigneeThe University of Tokyo
InventorsYoshihiko Nakamura, Yusuke Fujita
Life of this patent
Estimating the term…
Abstract
The dual Dijkstra search for planning multiple paths is performed by: (1) calculating a first shortest cost from start to all nodes by utilizing an algorithm known as the Dijkstra algorithm; (2) calculating a second shortest cost from goal to all nodes by utilizing the Dijkstra algorithm; (3) summing up the first shortest cost and the second shortest cost to obtain a summed up shortest cost; and (4a) storing at all nodes the summed up shortest cost as a cost of shortest path from start to goal via respective nodes, or, (4b) obtaining at all nodes a shortest path from start to goal via respective nodes with reference to the summed up shortest cost, thereby searching a path from start to goal.
Claims5
The dual Dijkstra search for planning multiple paths, comprising the steps of:
- calculating a first lowest cost from start to all nodes by utilizing an algorithm known as the Dijkstra algorithm;
- calculating a second lowest cost from goal to all nodes by utilizing the Dijkstra algorithm;
- summing up the first lowest cost and the second lower cost to obtain a summed up the lowest cost;
- and storing at all nodes the summed up lower cost as a cost of the lower path from start to goal via respective nodes, thereby searching a path from start to goal.
The dual Dijkstra search for planning multiple paths, comprising the steps of:
- calculating a first lowest cost from start to all nodes by utilizing an algorithm known as the Dijkstra algorithm;
- calculating a second shortest cost from goal to all nodes by utilizing the Dijkstra algorithm;
- summing up the first shortest cost and the second shortest cost to obtain a summed up shortest cost;
- and obtaining at all nodes a shortest path from start to goal via respective nodes with reference to the summed up shortest cost, thereby searching a path from start to goal.
Dependencies are inferred from the claim text.