DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Status of the Claims
Applicant filed claims 1-10 of US application 18/852,830 on 9/30/24.
On 10/3/25, applicant filed a preliminary amendment. Claims 1-10 were amended. Claims 11-13 were newly added. Claims 1-13 are presently pending and presented for examination.
Claim Objections
Claims 1-3, 5-6, 9 and 13 are objected to because of the following informalities:
In claim 1, “related to the drone route for the predetermined area, and by setting edges” should be “related to [[the]] a drone route for the predetermined area, and by setting a plurality of edges”
In claim 1, “selected inspection object edges among a plurality of edges;” should be “selected inspection object edges among [[a]] the plurality of edges;”
In claim 2, “related to the movement of the drone between the corresponding two nodes.” should be “related to the movement of the drone between the corresponding two nodes forming each edge.”
In claim 3, “at least one of the edge lengths connecting the corresponding nodes and the movement time” should be “at least one of [[the]] edge lengths connecting the corresponding nodes and [[the]] a movement time”
In claim 5, “set the nodes so that they are not included in the obstacle information when setting the nodes,” should be “set the plurality of nodes so that they are not included in the obstacle information when setting the plurality of nodes,”
In claim 5, “set the edges so that at least a portion of the edges is not included in the obstacle information when setting the edges.” should be “set the plurality of edges so that at least a portion of the plurality of edges is not included in the obstacle information when setting the plurality of edges.”
In claim 6, “define the spatial information of each node” should be “define [[the]] spatial information of each node”
In claim 6, “at least one of the latitude, longitude, and altitude” should be “at least one of [[the]] a latitude, longitude, and altitude”
In claim 9, “configured to: add the nodes and edges” should be “configured to: add [[the]] nodes and edges”
In claim 9, “based on the shortest path” should be “based on [[the]] a shortest path”
In claim 13, “compare the total cost of a plurality of third graphs” should be “compare [[the]] total costs of a plurality of third graphs”
In claim 13, “determine the third graph with the minimum total cost” should be “determine [[the]] a third graph with [[the]] a minimum total cost”
In claim 13, “wherein the total cost of the third graph is the sum of the cost information” should be “wherein the total cost of the third graph is [[the]] a sum of [[the]] cost information”
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) because the claim limitations uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitations are:
“a first graph generation module configured to generate a first graph” in claims 1 and 5-6
“a second graph generation module configured to generate a second graph” in claims 1 and 7
“a third graph generation module configured to generate a third graph” in claims 1 and 10
“an inspection setting part configured to set an inspection start node and an inspection end node” in claim 7
“an edge selection part configured to select inspection object edges” in claim 7
“a preliminary graph generation part configured to generate a preliminary graph” in claim 7
“a post-processing part configured to post-process the preliminary graph” in claims 7-9
“a duplicate node identification part configured to identify duplicate nodes” in claim 10
“a supplement edge setting part configured to set supplement edges” in claims 10-11
“a final path determination module configured to determine the optimal path” in claims 12-13
Because these claim limitations are being interpreted under 35 U.S.C. 112(f), they are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof. A review of the specification reveals the following:
“a first graph generation module” – appears in at least [12] and [70]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“a second graph generation module” – appears in at least [12] and [70]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“a third graph generation module” - appears in at least [12] and [70]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“an inspection setting part” - appears in at least [106]-[107]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“an edge selection part” - appears in at least [111]-[115]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“a preliminary graph generation part” - appears in at least [119]-[121]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“a post-processing part” - appears in at least [123]-[137]. But there is no indications whatsoever as to whether it is hardware, software, or something else entirely.
“a duplicate node identification part” - appears in at least [149]-[154]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“a supplement edge setting part” - appears in at least [149] and [156]-[161]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“a final path determination module” - appears in at least [12], [21], [70], [171]-[174], and [177]-[179]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
As demonstrated above, the specification recites no structure whatsoever for any of the above limitations. Instead, the limitations themselves appear without any clarification whatsoever as to whether they take the form of hardware, software, or another form entirely. Therefore, all of the claims lack written description and are rejected under 35 USC 112(a) and 112(b) in the section of this office action titled “Claim Rejections – 35 USC 112”.
Examiner’s note to help applicant overcome the 112(f) interpretation and corresponding 112 rejections: applicant can make the following amendments to overcome the 112(f) claim interpretation and the accompanying 112 rejections:
1. (Currently Amended) 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 [[the]] 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 [[a]] 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. (Currently Amended) 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. (Currently Amended) The optimal path planning method for drones of claim 2,
wherein the cost information includes at least one of [[the]] edge lengths connecting the corresponding nodes and [[the]] a movement time of the drone between the corresponding nodes.
4. (Currently Amended) 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. (Currently Amended) 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. (Currently Amended) The optimal path planning method for drones of claim 5,
further comprising defining [[the]] spatial information of each node when setting the nodes,
wherein the spatial information includes at least one of [[the]] a latitude, longitude, and altitude of each of the nodes.
7. (Currently Amended) 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. (Currently Amended) 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. (Currently Amended) The optimal path planning method for drones of claim 8,
further comprising:
adding [[the]] 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. (Currently Amended) The optimal path planning method for drones of claim 1,
further comprising
ing duplicate nodes among the nodes of the second graph that do not satisfy predetermined Eulerian path conditions, and
ting supplement edges connecting the identified duplicate nodes and determining the second graph with the set supplement edges as the third graph.
11. (Currently Amended) 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. (Currently Amended) 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. (Currently Amended) The optimal path planning device for drones of claim 12,
further comprising:
comparing [[the]] 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 [[the]] a third graph with [[the]] a minimum total cost as the optimal path of the drone,
wherein the total cost of the third graph is [[the]] a sum of [[the]] cost information corresponding to all the edges included in the third graph.
Claim Rejections - 35 USC § 112
The following is a quotation of the first paragraph of 35 U.S.C. 112(a):
(a) IN GENERAL.—The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor or joint inventor of carrying out the invention.
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
Claims 1-13 are rejected under both 35 USC 112(a) and 35 USC 112(b) because the following claim limitations invoke 35 U.S.C. 112(f):
“a first graph generation module configured to generate a first graph” in claims 1 and 5-6
“a second graph generation module configured to generate a second graph” in claims 1 and 7
“a third graph generation module configured to generate a third graph” in claims 1 and 10
“an inspection setting part configured to set an inspection start node and an inspection end node” in claim 7
“an edge selection part configured to select inspection object edges” in claim 7
“a preliminary graph generation part configured to generate a preliminary graph” in claim 7
“a post-processing part configured to post-process the preliminary graph” in claims 7-9
“a duplicate node identification part configured to identify duplicate nodes” in claim 10
“a supplement edge setting part configured to set supplement edges” in claims 10-11
“a final path determination module configured to determine the optimal path” in claims 12-13
However, the written description fails to disclose the corresponding structure, material, or acts for performing the entire claimed function and to clearly link the structure, material, or acts to the function. In particular, a review of the specification reveals the following:
“a first graph generation module” – appears in at least [12] and [70]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“a second graph generation module” – appears in at least [12] and [70]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“a third graph generation module” - appears in at least [12] and [70]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“an inspection setting part” - appears in at least [106]-[107]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“an edge selection part” - appears in at least [111]-[115]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“a preliminary graph generation part” - appears in at least [119]-[121]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“a post-processing part” - appears in at least [123]-[137]. But there is no indications whatsoever as to whether it is hardware, software, or something else entirely.
“a duplicate node identification part” - appears in at least [149]-[154]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“a supplement edge setting part” - appears in at least [149] and [156]-[161]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
“a final path determination module” - appears in at least [12], [21], [70], [171]-[174], and [177]-[179]. But there is no indication whatsoever as to whether it is hardware, software, or something else entirely.
Therefore, the claim limitations both lack written description and are indefinite and are accordingly rejected under 35 U.S.C. 112(a) and 35 U.S.C. 112(b).
Examiner’s note to help applicant overcome the 112(f) interpretation and corresponding 112 rejections: applicant can make the following amendments to overcome the 112(f) claim interpretation and the accompanying 112 rejections:
1. (Currently Amended) 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 [[the]] 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 [[a]] 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. (Currently Amended) 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. (Currently Amended) The optimal path planning method for drones of claim 2,
wherein the cost information includes at least one of [[the]] edge lengths connecting the corresponding nodes and [[the]] a movement time of the drone between the corresponding nodes.
4. (Currently Amended) 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. (Currently Amended) 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. (Currently Amended) The optimal path planning method for drones of claim 5,
further comprising defining [[the]] spatial information of each node when setting the nodes,
wherein the spatial information includes at least one of [[the]] a latitude, longitude, and altitude of each of the nodes.
7. (Currently Amended) 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. (Currently Amended) 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. (Currently Amended) The optimal path planning method for drones of claim 8,
further comprising:
adding [[the]] 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. (Currently Amended) The optimal path planning method for drones of claim 1,
further comprising
ing duplicate nodes among the nodes of the second graph that do not satisfy predetermined Eulerian path conditions, and
ting supplement edges connecting the identified duplicate nodes and determining the second graph with the set supplement edges as the third graph.
11. (Currently Amended) 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. (Currently Amended) 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. (Currently Amended) The optimal path planning device for drones of claim 12,
further comprising:
comparing [[the]] 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 [[the]] a third graph with [[the]] a minimum total cost as the optimal path of the drone,
wherein the total cost of the third graph is [[the]] a sum of [[the]] cost information corresponding to all the edges included in the third graph.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-13 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea) without significantly more. The claimed invention is directed to the concept of generating multiple graphs describing an environment of a drone based on obstacle information of the environment. This judicial exception is not integrated into a practical application. The claims do not include additional elements that are sufficient to amount to significantly more than the judicial exception and do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea.
Regarding claim 1, applicant recites An optimal path planning device for drones, comprising:
a first graph generation module configured to generate a first graph by setting a plurality of nodes in a predetermined area based on obstacle information and industrial structure information related to the drone route for the predetermined area, and by setting edges that connect each of the nodes;
a second graph generation module configured to generate a second graph related to selected inspection object edges among a plurality of edges; and
a third graph generation module configured to generate 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.
The claim recites a device that performs a series of steps and therefore is directed to an apparatus, which satisfies step 1 of the Section 101 analysis. Under the two-prong inquiry, the claim is eligible at revised step 2A unless: Prong One: the claim recites a judicial exception; and Prong Two: the exception is not integrated into a practical application of the exception.
The above claim steps are directed to the concept of generating multiple graphs describing an environment of a drone based on obstacle information of the environment, which is an abstract idea that can be performed by a user mentally or manually and falls within the Mental Processes grouping. (Prong one: YES, recites an abstract idea).
Other than reciting the use of An optimal path planning device, a first graph generation module, a first graph generation module, a second graph generation module, and a third graph generation module, nothing in the claim elements precludes the steps from being performed entirely by a human. The use of one or more computing devices is insufficient to amount to significantly more than the judicial exception and does not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. (Prong Two: NO, does not recite additional elements that integrate the abstract idea into a practical application similar to that shown in MPEP 2106.05).
Under step 2B, the claimed invention does not recite additional elements that are indicative of an inventive concept. The additional elements when considered both individually and as an ordered combination do not amount to significantly more than the abstract idea. As discussed previously in the “Claim Interpretation” section of the non-final rejection, applicant completed fails to describe any sort of structure for any of these additional elements at all. However, even if applicant did recite computational structures to perform the functions of these additional elements, these additional limitations would be no more than mere instructions to apply the exception using generic computer components. The recitation of generic processors/computers does not take the above limitations out of the mental processes grouping.
Moreover, the implementation of the abstract idea on generic computers and/or generic computer components does not add significantly more, similar to how the recitation of the computer in Alice amounted to mere instructions to apply the abstract idea on a generic computer. The claims merely invoke the additional elements as tools that are being used in their ordinary capacity. Further, the courts have found that simply limiting the use of the abstract idea to a particular environment does not add significantly more. Thus, taken alone, the additional elements do not amount to significantly more than the above-identified judicial exception (the abstract idea). Looking at the limitations as an ordered combination adds nothing that is not already present when looking at the elements taken individually. There is no indication that the combination of elements improves the functioning of a computer or improves any other technology. Their collective functions merely provide generic computer implementation.
Examiner’s note to help applicant overcome the 101 rejections: applicant can overcome the 101 rejections by amending claim 1 to include the following limitation:
“wherein the drones fly based on commands derived from the optimal path planning method.”
This amendment would clarify that the claims are directed to ultimately controlling flight of a drone, which is not something that a human can do mentally or manually.
Regarding claim 2, applicant recites The optimal path planning device for drones of The optimal path planning device for drones of wherein the edges include cost information related to the movement of the drone between the corresponding two nodes.
However, a human can assign values to edges of a graph. That is what graph theory is.
Regarding claim 3, applicant recites The optimal path planning device for drones of claim 2,
wherein the cost information includes at least one of the edge lengths connecting the corresponding nodes and the movement time of the drone between the corresponding nodes.
However, a human can create a graph like this. That is what graph theory is.
Regarding claim 4, applicant recites The optimal path planning device for drones of claim 1,
wherein the obstacle information includes topographical information of restricted areas where the drone cannot pass.
However, a human can create a graph like this based on this kind of real-world information. That is what graph theory is.
Regarding claim 5, applicant recites The optimal path planning device for drones of claim 4,
wherein the first graph generation module is configured to:
set the nodes so that they are not included in the obstacle information when setting the nodes, and
set the edges so that at least a portion of the edges is not included in the obstacle information when setting the edges.
However, a human can create a graph like this based on this kind of real-world information. That is what graph theory is.
Regarding claim 6, applicant recites The optimal path planning device for drones of claim 5,
wherein the first graph generation module is configured to define the 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.
However, a human can create a graph like this based on this kind of real-world information. That is what graph theory is.
Regarding claim 7, applicant recites The optimal path planning device for drones of The optimal path planning device for drones of claim 1,
wherein the second graph generation module includes:
an inspection setting part configured to set an inspection start node and an inspection end node from among the plurality of nodes in the generated first graph;
an edge selection part configured to select inspection object edges from among the plurality of edges in the first graph;
a preliminary graph generation part configured to generate a preliminary graph including the inspection object edges and the nodes corresponding to the inspection object edges; and
a post-processing part configured to post-process the preliminary graph into a connected graph and determine the post-processed preliminary graph as the second graph.
However, a human can create a graph like this based on this kind of real-world information. That is what graph theory is.
Regarding claim 8, applicant recites The optimal path planning device for drones of wherein the post-processing part is configured to:
generate an assistant graph based on the generated preliminary graph, and
post-process the preliminary graph into the connected graph by adding the nodes and edges in the generated assistant graph to the preliminary graph without duplication.
However, a human can create a graph like this based on this kind of real-world information. That is what graph theory is.
Regarding claim 9, applicant recites The optimal path planning device for drones of The optimal path planning device for drones of wherein the post-processing part is configured to:
add the 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, set 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.
However, a human can create a graph like this based on this kind of real-world information. That is what graph theory is.
Regarding claim 10, applicant recites The optimal path planning device for drones of claim 1,
wherein the third graph generation module includes:
a duplicate node identification part configured to identify duplicate nodes among the nodes of the second graph that do not satisfy predetermined Eulerian path conditions, and
a supplement edge setting part configured to set supplement edges connecting the identified duplicate nodes and determine the second graph with the set supplement edges as the third graph.
However, a human can create a graph like this based on this kind of real-world information. That is what graph theory is.
Regarding claim 11, applicant recites The optimal path planning device for drones of claim 10,
wherein the supplement edge setting part is configured to set the supplement edges based on the shortest path between the duplicate nodes searched in the first graph.
However, a human can create a graph like this based on this kind of real-world information. That is what graph theory is.
Regarding claim 12, applicant recites The optimal path planning device for drones of claim 2, further comprising:
a final path determination module configured to determine the optimal path of the drone based on the total cost of the generated third graph.
However, a human can create a graph like this based on this kind of real-world information and perform computations on it. That is what graph theory is.
Regarding claim 13, applicant recites The optimal path planning device for drones of claim 12,
wherein the final path determination module is configured to:
compare the total cost of a plurality of third graphs generated by setting at least one of the inspection start node and the inspection end node differently, and
determine the third graph with the minimum total cost as the optimal path of the drone,
wherein the total cost of the third graph is the sum of the cost information corresponding to all the edges included in the third graph.
However, a human can create a graph like this based on this kind of real-world information and perform computations on it. That is what graph theory is.
Examiner’s note to help applicant overcome the 101 rejections: applicant can overcome the 101 rejections by amending claim 1 to include the following limitation:
“wherein the drones fly based on commands derived from the optimal path planning method.”
This amendment would clarify that the claims are directed to ultimately controlling flight of a drone, which is not something that a human can do mentally or manually.
Allowable Subject Matter
Claims 1-13 are objected to for containing allowable subject matter. They will be allowable if applicant amends the claims as suggested by examiner to resolve the previously discussed objections and rejections. Please see the subsequent section called “Suggested Amendments to Immediately Place the Case in Condition for Allowance” for a compilation of these suggestions.
The closest prior art of record is Mucci et al. (US 20160107749 A1) in view of Garcia Morchon et al. (US 20170221394 A1), hereinafter referred to Mucci and Garcia, respectively. The following is a statement of reasons for the indication of allowable subject matter:
Regarding claim 1, Mucci discloses An optimal path planning device for drones (See at least Fig. 3 in Mucci: Mucci discloses a flow diagram showing an example process for determining surveillance mapping [See at least Mucci, 0017]. It will be appreciated that steps 52, 54, and 66 all involve route planning), comprising:
a first graph generation module configured to generate a first graph by setting a plurality of nodes (Mucci discloses that A flight plan is essentially a navigation map structure that is produced and includes paths between a starting waypoint and an ending waypoint [See at least Mucci, 0036]. Mucci further discloses that The navigation map is stored as a structure such as a graph data structure that includes a set of nodes and a set of edges that establish relationships (connections) between the nodes [See at least Mucci, 0036]) in a predetermined area (See at least Fig. 3 in Mucci: Mucci discloses that the drone is autonomously programmed 52 by the server with a route that starts from the drone's initial location, typically a home station to a location where the alarm condition was asserted [See at least Mucci, 0025]. Mucci further discloses that The drone has stored the flight plan that takes into consideration the relevant building or environment [See at least Mucci, 0035]) based on obstacle information (Mucci discloses that The drone has stored the flight plan that takes into consideration the relevant building or environment [See at least Mucci, 0035]) and industrial structure information related to the drone route for the predetermined area (Mucci further discloses that The drone has stored the flight plan that takes into consideration the relevant building or environment [See at least Mucci, 0035]), and by setting edges that connect each of the nodes (Mucci discloses that A flight plan is essentially a navigation map structure that is produced and includes paths between a starting waypoint and an ending waypoint [See at least Mucci, 0036]. Mucci further discloses that The navigation map is stored as a structure such as a graph data structure that includes a set of nodes and a set of edges that establish relationships (connections) between the nodes [See at least Mucci, 0036]);
a second graph generation module configured to generate a second graph related to selected inspection object edges among a plurality of edges (See at least Fig. 3 in Mucci: Mucci discloses, with regard to steps 54 and 56, that The drone is launched, and as the drone flies the programmed pattern it collects such sensor data [See at least Mucci, 0026]. Mucci further discloses that the drone is programmed to fly to a particular location within a facility [See at least Mucci, 0026]. It will be appreciated that this particular pattern culminating in this particular location may be regarded as a “second graph” that is a subgraph of the first graph of [Mucci, 0036]).
However, none of the prior art of record, taken either alone or in combination, teaches or suggests the device further comprising a third graph generation module configured to generate 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 (emphasis added).
In order for a reference to read on this limitation, the reference would have to teach where, based on one or more previous flight plan graphs related to obstacle information and industrial structure information, a third graph with an Eulerian path is generated for the drone. However, this is not taught in the prior art of record.
An Eulerian path, in the context of graph theory, is a path through a graph that traverses every edge of a graph exactly once, potentially revisiting vertices but never revisiting a previous edge. This type of graph is extremely difficult to generate in most scenarios. For a third graph to be generated such that it has an Eulerian path, the third graph must meet very stringent standards as far as the numbers of edges and vertices that the graph has and the number of edges connected to each vertex in the graph. In other words, not just any generated graph can have an Eulerian path. Such graphs must be very carefully designed with that exact purpose in mind and comparatively few graphs even have an Eulerian path at all. Insofar as the prior art discusses successive generation of multiple graph theory graphs to control flight paths of drones, the prior art is silent as to any such care as far as generating a third graph such that the third graph an Eulerian path based on the generated second graph, which contains information about objects, obstacles, and industrial structures. While Mucci does navigate the vehicle with respect to structures detected via imaging, there is nothing in Mucci about an Eulerian path.
Conversely, Garcia does teach the use of Eulerian paths for drones (See at least [Garcia, 0104]). However, Garcia is silent as to whether the graphs which have the Eulerian paths are related to obstacles, objects, or infrastructure detected in the environment. In fact, rather than detecting obstacles, objects, or infrastructure and turning them into Eulerian graphs, the drones of Garcia instead create an Eulerian route to write letters in the sky with a portable smoke machine, without any consideration of the topography of an obstacle (See at least [Garcia, 0070] and Fig. 3 in Garcia). Sky-writing with a complete absence of obstacle detection for graph creation is not the same as the claimed invention, which creates Eulerian graphs for the much more utilitarian and less aesthetic purpose of mapping topography and flying a drone with respect to that topography. In addition to having nothing to do with topography or structure of an observed area, the Eulerian path of [Garcia, 0104] is also not the result of successive iterations and improvements of a graph; instead, there is a just one graph that is designed to have an Eulerian path that has no relation to topography of any imaged area (See at least [Garcia, 0104]). In other words, the graphs of Mucci and Garcia represent such different and unrelated data from each other, and are calculated in such different ways, that there is no reasonable way to combine them so that the Eulerian path of Garcia is somehow applicable to the completely unrelated graph of Mucci.
None of the other prior art of record resolves these deficiencies of Mucci and Garcia.
Therefore, the prior art fails to read on the above missing limitations and claim 1 is objected to for containing allowable subject matter.
Regarding claims 2-13, these claims are also objected to for containing allowable subject matter at least by virtue of their dependence from claim 1.
Suggested Amendments to Immediately Place the Case in Condition for Allowance
In order to expedite prosecution, examiner includes the below set of amendments which would immediately place the case in condition for allowance. It is of course up to applicant whether or not applicant chooses to take examiner’s suggestions. The suggestions are as follows:
1. (Currently Amended) 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 [[the]] 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 [[a]] 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. (Currently Amended) 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. (Currently Amended) The optimal path planning method for drones of claim 2,
wherein the cost information includes at least one of [[the]] edge lengths connecting the corresponding nodes and [[the]] a movement time of the drone between the corresponding nodes.
4. (Currently Amended) 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. (Currently Amended) 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. (Currently Amended) The optimal path planning method for drones of claim 5,
further comprising defining [[the]] spatial information of each node when setting the nodes,
wherein the spatial information includes at least one of [[the]] a latitude, longitude, and altitude of each of the nodes.
7. (Currently Amended) 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. (Currently Amended) 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. (Currently Amended) The optimal path planning method for drones of claim 8,
further comprising:
adding [[the]] 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. (Currently Amended) The optimal path planning method for drones of claim 1,
further comprising
ing duplicate nodes among the nodes of the second graph that do not satisfy predetermined Eulerian path conditions, and
ting supplement edges connecting the identified duplicate nodes and determining the second graph with the set supplement edges as the third graph.
11. (Currently Amended) 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. (Currently Amended) 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. (Currently Amended) The optimal path planning device for drones of claim 12,
further comprising:
comparing [[the]] 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 [[the]] a third graph with [[the]] a minimum total cost as the optimal path of the drone,
wherein the total cost of the third graph is [[the]] a sum of [[the]] cost information corresponding to all the edges included in the third graph.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to NAEEM T ALAM whose telephone number is (571)272-5901. The examiner can normally be reached M-F, 9am-5pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, FADEY JABR can be reached at (571) 272-1516. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/NAEEM TASLIM ALAM/Examiner, Art Unit 3668