Method, apparatus, and system for calculating optimal path on basis of node reduction
The present invention relates to a method, an apparatus, and a system for calculating an optimal path on the basis of node reduction and, more specifically, to a method, an apparatus, and a system for calculating an optimal path on the basis of node reduction, in which an optimal path from a departure node to a destination node can be effectively calculated on the basis of a graph including multiple nodes corresponding to a task space in a logistics automation system.
1 . A method for calculating an optimal path for a logistics robot from a first node to a second node to move the logistics robot in a task space, based on a graph comprising a plurality of nodes and an edge connecting the plurality of nodes corresponding to the task space, the method comprising:
a representative node graph configuration operation of configuring, by a server to control the logistics robot, a representative node graph comprising information about a plurality of representative nodes comprising a node connected to three or more edges among the plurality of representative nodes in the graph;
a representative node calculation operation of calculating a first representative node corresponding to the first node and a second representative node corresponding to the second node from the plurality of representative nodes;
a representative node optimal path calculation operation of calculating a representative node optimal path from the first representative node to the second representative node based on the representative node graph; and
an optimal path calculation operation of calculating an optimal path for the logistics robot from the first node to the second node including the representative node optimal path, the distance difference (offset) between the first representative node and the first node, and the distance difference (offset) between the second representative node and the second node, wherein the logistics robot moves or performs a task in the task space based on the calculating the optimal path.
2 . The method of claim 1 , wherein the representative node calculation operation comprises calculating a representative node closest to the plurality of nodes as a representative node for each node.
3 . The method of claim 2 , wherein the representative node calculation operation comprises calculating the first representative node and the second representative node by using a first table comprising information about the correspondence relationship between the plurality of nodes and the representative nodes.
4 . The method of claim 1 , wherein the representative node optimal path calculation operation comprises calculating the representative node optimal path by using a second table comprising information about the distance between the representative nodes.
5 . The method of claim 4 , wherein the representative node optimal path calculation operation comprises calculating the representative node optimal path by applying Dijkstra's algorithm or A* algorithm, based on the second table.
6 . The method of claim 1 , wherein the optimal path calculation operation comprises calculating the optimal path from the first node to the second node by using a first table comprising information about the correspondence relationship between the plurality of nodes and the representative nodes and the distance difference (offset) therebetween.
7 . The method of claim 6 , wherein the optimal path calculation operation comprises calculating the shortest path from the first node to the second node may be calculated using the representative node optimal path and the first table.
8 . The method of claim 1 , wherein the representative node graph is configured comprising information about a plurality of representative edges connecting the plurality of representative nodes.