Optimal path planning device and method for drones considering obstacles

1 . An optimal path planning method for drones, comprising:

generating a first graph by setting a plurality of nodes in a predetermined area based on obstacle information and industrial structure information related to a drone route for the predetermined area, and by setting a plurality of edges that connect each of the nodes;

generating a second graph related to selected inspection object edges among the plurality of edges; and

generating a third graph with an Eulerian path based on the generated second graph,

wherein the industrial structure information includes topographical information of industrial structures to be inspected by the drone, and

wherein the drones fly based on commands derived from the optimal path planning method.

2 . The optimal path planning method for drones of claim 1 , wherein the edges include cost information related to the movement of the drone between the corresponding two nodes forming each edge.

3 . The optimal path planning method for drones of claim 2 , wherein the cost information includes at least one of edge lengths connecting the corresponding nodes and a movement time of the drone between the corresponding nodes.

4 . The optimal path planning method for drones of claim 1 , wherein the obstacle information includes topographical information of restricted areas where the drone cannot pass.

5 . The optimal path planning method for drones of claim 4 , further comprising:

setting the plurality of nodes so that they are not included in the obstacle information when setting the plurality of nodes, and

setting the edges so that at least a portion of the edges is not included in the obstacle information when setting the edges.

6 . The optimal path planning method for drones of claim 5 , further comprising:

defining spatial information of each node when setting the nodes,

wherein the spatial information includes at least one of the latitude, longitude, and altitude of each of the nodes.

7 . The optimal path planning method for drones of claim 1 , further comprising:

setting an inspection start node and an inspection end node from among the plurality of nodes in the generated first graph;

selecting inspection object edges from among the plurality of edges in the first graph;

generating a preliminary graph including the inspection object edges and the nodes corresponding to the inspection object edges; and

post-processing the preliminary graph into a connected graph and determining the post-processed preliminary graph as the second graph.

8 . The optimal path planning method for drones of claim 7 , further comprising:

generating an assistant graph based on the generated preliminary graph, and

post-processing the preliminary graph into the connected graph by adding the nodes and edges in the generated assistant graph to the preliminary graph without duplication.

9 . The optimal path planning method for drones of claim 8 , further comprising:

adding nodes and edges present in the preliminary graph to the assistant graph, which initially starts as an empty graph, and

for all pairs of nodes in the assistant graph, if an edge connecting the two nodes does not exist in the assistant graph, setting auxiliary nodes and auxiliary edges in the assistant graph to connect the two nodes based on the first graph,

wherein the auxiliary nodes and auxiliary edges are set in the assistant graph based on the shortest path between the two nodes identified in the first graph.

10 . The optimal path planning method for drones of claim 1 , further comprising:

identifying duplicate nodes among the nodes of the second graph that do not satisfy predetermined Eulerian path conditions, and

setting supplement edges connecting the identified duplicate nodes and determining the second graph with the set supplement edges as the third graph.

11 . The optimal path planning method for drones of claim 10 , further comprising:

setting the supplement edges based on the shortest path between the duplicate nodes searched in the first graph.

12 . The optimal path planning method for drones of claim 2 , further comprising:

determining the optimal path of the drone based on the total cost of the generated third graph.

13 . The optimal path planning method for drones of claim 12 , further comprising:

comparing total costs of a plurality of third graphs generated by setting at least one of the inspection start node and the inspection end node differently, and

determining a third graph with a minimum total cost as the optimal path of the drone,

wherein the total cost of the third graph is a sum of cost information corresponding to all the edges included in the third graph.