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 .
Information Disclosure Statement
The information disclosure statement (IDS) filed 01/05/2026 has been received and considered by the examiner. The submission is in compliance with the provisions of 37 CFR 1.97.
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-19 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
In January, 2019 (updated October 2019), the USPTO released new examination guidelines setting forth a two-step inquiry for determining whether a claim is directed to non-statutory subject matter. According to the guidelines, a claim is directed to non-statutory subject matter if:
STEP 1: the claim does not fall within one of the four statutory categories of invention (process, machine, manufacture or composition of matter), or
STEP 2: the claim recites a judicial exception, e.g. an abstract idea, without reciting additional elements that amount to significantly more than the judicial exception, as determined using the following analysis:
STEP 2A (PRONG 1): Does the claim recite an abstract idea, law of nature, or natural phenomenon?
STEP 2A (PRONG 2): Does the claim recite additional elements that integrate the judicial exception into a practical application?
STEP 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
Using the two-step inquiry, it is clear that claims 1, 9, and 15 are directed toward non-statutory subject matter, as shown below:
STEP 1: Do claims 1, 9, and 15 fall within one of the statutory categories? Yes. The claims is directed towards methods including at least one step.
STEP 2A (PRONG 1): Is the claim directed to a law of nature, a natural phenomenon or an abstract idea? Yes, the claims are directed to abstract ideas.
With regard to STEP 2A (PRONG 1), the guidelines provide three groupings of subject matter that are considered abstract ideas:
Mathematical concepts – mathematical relationships, mathematical formulas or equations, mathematical calculations;
Certain methods of organizing human activity – fundamental economic principles or practices (including hedging, insurance, mitigating risk); commercial or legal interactions (including agreements in the form of contracts; legal obligations; advertising, marketing or sales activities or behaviors; business relations); managing personal behavior or relationships or interactions between people (including social activities, teaching, and following rules or instructions); and
Mental processes – concepts that are practicably performed in the human mind (including an observation, evaluation, judgment, opinion).
Claim 1. A method for optimizing a route for execution by a system that controls one or more agricultural vehicles comprising:
defining an area of land to be worked by the one or more agricultural vehicles;
creating a plurality of passes that completely cover the area of land, wherein each pass comprises a first end and a second end;
transforming each first end and each second end of each of the plurality of passes into a plurality of nodes;
connecting the plurality of nodes to create one or more possible routes;
computing a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes;
computing a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; the time and distance matrix does not have to be computed in any particular order
applying constraints configured to ensure that each of the plurality of passes is worked exactly once by the one or more agricultural vehicles and also configured to ensure that time window requirements are met;
formulating a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions;
determining that a feasible solution to the non-convex optimization problem exists;
and solving the non-convex optimization problem using quantum annealing for agricultural vehicle routing to create an optimized route for controlling the one or more agricultural vehicles.
The method in claim 1, specifically the limitations “computing a distance matrix…”, “computing a time matrix…”, “applying constraints configured to ensure…”, “formulating a non-convex optimization problem…”, and “solving the non-convex optimization problem using quantum annealing…” emphasized above, recite mathematical concepts and, therefore, abstract ideas. As is evident from the specification, the claimed steps highlighted above are mathematical calculations and data analysis techniques, including computing matrices. These steps involve calculating distances and times between possible pairs of nodes and using the resulting matrices and constraints in an optimization problem. The process further includes formulating the non-convex optimization problem and solving the problem using quantum annealing. This constitutes an optimization process that evaluates and selects a solution based on mathematical relationships rather than by implementing any technological improvement to a computer or system. The grouping of “mathematical concepts” in the 2019 PEG is not limited to formulas or equations, and in fact specifically includes “mathematical calculations” as an exemplar of a mathematical concept. 2019 PEG Section I, 84 Fed. Reg. at 52. Thus the claim recites a concept that falls into the “mathematical concept” group of abstract ideas.
The method in claim 1, specifically the limitations “defining an area of land to be worked…”, “creating a plurality of passes that completely cover the area of land…”, “transforming each first end and each second end of each of the plurality of passes into a plurality of nodes”, “connecting the plurality of nodes to create one or more possible routes”, and “determining that a feasible solution to the non-convex optimization problem exists”, emphasized above, are mental processes that can be practicably performed in the human mind and, therefore, are abstract ideas. They merely consist of defining an area of land, creating multiple passes, transforming the first and second ends of passes into nodes, connecting the nodes to create possible routes, and determining that a solution to the non-convex problem exists. This is equivalent to a person mentally reviewing the land and defining the area, creating multiple passes, turning the ends of the passes into nodes and connecting the nodes to create routes, and determining that a solution to the non-convex problem exists.
Claim 9. A method for optimizing a route for execution by a system that controls one or more agricultural vehicles comprising:
defining an area of land to be worked by the one or more agricultural vehicles;
creating a plurality of passes that completely cover the area of land, wherein each pass comprises a first end and a second end;
transforming each first end and each second end of each of the plurality of passes into a plurality of nodes;
connecting the plurality of nodes to create one or more possible routes; computing a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes;
computing a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes;
applying constraints configured to ensure that each of the plurality of passes is worked exactly once by the one or more agricultural vehicles and also configured to ensure that time window requirements are met;
formulating a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions;
determining that a feasible solution to the non-convex optimization problem exists;
and solving the non-convex optimization problem to create an optimized route for controlling the one or more agricultural vehicles.
The method in claim 9, specifically the limitations “computing a distance matrix…”, “computing a time matrix…”, “applying constraints configured to ensure…”, “formulating a non-convex optimization problem…”, and “solving the non-convex optimization problem…” emphasized above, recite mathematical concepts and, therefore, abstract ideas. As is evident from the specification, the claimed steps highlighted above are mathematical calculations and data analysis techniques, including computing matrices. These steps involve calculating distances and times between possible pairs of nodes and using the resulting matrices and constraints in an optimization problem. The process further includes formulating the non-convex optimization problem and solving the problem. This constitutes an optimization process that evaluates and selects a solution based on mathematical relationships rather than by implementing any technological improvement to a computer or system. The grouping of “mathematical concepts” in the 2019 PEG is not limited to formulas or equations, and in fact specifically includes “mathematical calculations” as an exemplar of a mathematical concept. 2019 PEG Section I, 84 Fed. Reg. at 52. Thus the claim recites a concept that falls into the “mathematical concept” group of abstract ideas.
The method in claim 9, specifically the limitations “defining an area of land to be worked…”, “creating a plurality of passes that completely cover the area of land…”, “transforming each first end and each second end of each of the plurality of passes into a plurality of nodes”, “connecting the plurality of nodes to create one or more possible routes”, and “determining that a feasible solution to the non-convex optimization problem exists”, emphasized above, are mental processes that can be practicably performed in the human mind and, therefore, are abstract ideas. They merely consist of defining an area of land, creating multiple passes, transforming the first and second ends of passes into nodes, connecting the nodes to create possible routes, and determining that a solution to the non-convex problem exists. This is equivalent to a person mentally reviewing the land and defining the area, creating multiple passes, turning the ends of the passes into nodes and connecting the nodes to create routes, and determining that a solution to the non-convex problem exists.
Claim 15. A method for optimizing a route for execution by a system that controls one or more agricultural vehicles comprising:
defining an area of land to be worked by the one or more agricultural vehicles;
creating a plurality of passes that completely cover the area of land, wherein each pass comprises a first end and a second end;
transforming each first end and each second end of each of the plurality of passes into a plurality of nodes;
connecting the plurality of nodes to create one or more possible routes;
computing a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes;
computing a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; the time and distance matrix does not have to be computed in any particular order
applying constraints configured to ensure that each of the plurality of passes is worked exactly once by the one or more agricultural vehicles and also configured to ensure that time window requirements are met;
formulating a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions;
determining that a feasible solution to the non-convex optimization problem exists;
and solving the non-convex optimization problem using Grover's Algorithm to create an optimized route for controlling the one or more agricultural vehicles.
The method in claim 15, specifically the limitations “computing a distance matrix…”, “computing a time matrix…”, “applying constraints configured to ensure…”, “formulating a non-convex optimization problem…”, and “solving the non-convex optimization problem using Grover's Algorithm…” emphasized above, recite mathematical concepts and, therefore, abstract ideas. As is evident from the specification, the claimed steps highlighted above are mathematical calculations and data analysis techniques, including computing matrices. These steps involve calculating distances and times between possible pairs of nodes and using the resulting matrices and constraints in an optimization problem. The process further includes formulating the non-convex optimization problem and solving the problem using Grover's Algorithm. This constitutes an optimization process that evaluates and selects a solution based on mathematical relationships rather than by implementing any technological improvement to a computer or system. The grouping of “mathematical concepts” in the 2019 PEG is not limited to formulas or equations, and in fact specifically includes “mathematical calculations” as an exemplar of a mathematical concept. 2019 PEG Section I, 84 Fed. Reg. at 52. Thus the claim recites a concept that falls into the “mathematical concept” group of abstract ideas.
The method in claim 15, specifically the limitations “defining an area of land to be worked…”, “creating a plurality of passes that completely cover the area of land…”, “transforming each first end and each second end of each of the plurality of passes into a plurality of nodes”, “connecting the plurality of nodes to create one or more possible routes”, and “determining that a feasible solution to the non-convex optimization problem exists”, emphasized above, are mental processes that can be practicably performed in the human mind and, therefore, are abstract ideas. They merely consist of defining an area of land, creating multiple passes, transforming the first and second ends of passes into nodes, connecting the nodes to create possible routes, and determining that a solution to the non-convex problem exists. This is equivalent to a person mentally reviewing the land and defining the area, creating multiple passes, turning the ends of the passes into nodes and connecting the nodes to create routes, and determining that a solution to the non-convex problem exists.
STEP 2A (PRONG 2): Does the claim recite additional elements that integrate the judicial exception into a practical application? No, the claim does not recite additional elements that integrate the judicial exception into a practical application.
With regard to STEP 2A (prong 2), whether the claim recites additional elements that integrate the judicial exception into a practical application, the guidelines provide the following exemplary considerations that are indicative that an additional element (or combination of elements) may have integrated the judicial exception into a practical application:
an additional element reflects an improvement in the functioning of a computer, or an improvement to other technology or technical field;
an additional element that applies or uses a judicial exception to effect a particular treatment or prophylaxis for a disease or medical condition;
an additional element implements a judicial exception with, or uses a judicial exception in conjunction with, a particular machine or manufacture that is integral to the claim;
an additional element effects a transformation or reduction of a particular article to a different state or thing; and
an additional element applies or uses the judicial exception in some other meaningful way beyond generally linking the use of the judicial exception to a particular technological environment, such that the claim as a whole is more than a drafting effort designed to monopolize the exception.
While the guidelines further state that the exemplary considerations are not an exhaustive list and that there may be other examples of integrating the exception into a practical application, the guidelines also list examples in which a judicial exception has not been integrated into a practical application:
an additional element merely recites the words “apply it” (or an equivalent) with the judicial exception, or merely includes instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea;
an additional element adds insignificant extra-solution activity to the judicial exception; and
an additional element does no more than generally link the use of a judicial exception to a particular technological environment or field of use.
In the present case, there are no additional limitations beyond the above-noted abstract ideas.
STEP 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception? In the present case, there are no additional limitations beyond the above-noted abstract ideas.
With regard to STEP 2B, whether the claims recite additional elements that provide significantly more than the recited judicial exception, the guidelines specify that the pre-guideline procedure is still in effect. Specifically, that examiners should continue to consider whether an additional element or combination of elements:
adds a specific limitation or combination of limitations that are not well-understood, routine, conventional activity in the field, which is indicative that an inventive concept may be present; or
simply appends well-understood, routine, conventional activities previously known to the industry, specified at a high level of generality, to the judicial exception, which is indicative that an inventive concept may not be present.
Regarding Step 2B of the 2019 PEG, independents claim 1, 9, and 15 do not include additional elements (considered both individually and as an ordered combination) that are sufficient to amount to significantly more than the judicial exception for the same reasons to those discussed above with respect to determining that the claims do not integrate the abstract idea into a practical application.
Further, a conclusion that an additional element is insignificant extra-solution activity in Step 2A should be re-evaluated in Step 2B to determine if they are more than what is well-understood, routine, conventional activity in the field. There are no additional limitations beyond the above-noted abstract ideas.
CONCLUSION
Thus, since claims 1, 9, and 15 are: (a) directed toward an abstract idea, (b) do not recite additional elements that integrate the judicial exception into a practical application, and (c) do not recite additional elements that amount to significantly more than the judicial exception, it is clear that claims 1, 9, and 15 are directed towards non-statutory subject matter.
Dependent claims 2-8, 10-14, 16-19 further limit the abstract idea without integrating the abstract idea into practical application or adding significantly more. For example, in claim 2, the additional limitation of “connecting the plurality of nodes to create routes comprises connecting the plurality of nodes with Dubins paths” is an additional step that, under the broadest reasonable interpretation, covers performance of the limitation in the mind using a similar analysis applied to claim 1 above. The method in claim 2, specifically the limitation above, is a mental process that can be practicably performed in the human mind and, therefore, an abstract idea. It merely consists of connecting the plurality of nodes with Dubins paths. This is equivalent to a person mentally viewing the nodes and determining how to connect the nodes with Dubins paths.
As such, claims 1-19 are rejected under 35 USC 101 as being drawn to an abstract idea without significantly more, and thus are ineligible.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claim(s) 1 and 4 is/are rejected under 35 U.S.C. 103 as being unpatentable over Green (US 20190239416 A1) in view of Elisha (US 20210241625 A1) and USHIJIMA-MWESIGWA (US 20240085194 A1).
Regarding Claim 1, Green teaches A method for optimizing a route for execution by a system that controls one or more agricultural vehicles comprising: defining an area of land to be worked by the one or more agricultural vehicles (See at least paragraph [0036], “In a first aspect the present invention relates to a support system for determining a trajectory to be followed by an agricultural work vehicle, when working a field”, paragraph [0042], “The support system is designed with the view to aid in optimizing finding a trajectory to be followed upon working an agricultural field with a working vehicle or implement”, and paragraph [0060], [0065], “In one embodiment of the first aspect of the present invention said trajectory calculating unit is being configured to perform the following steps: e) defining a work area which corresponds to the area within said boundary polygon with the exclusion of the area corresponding to any headlands and with the exclusion of the area corresponding to any obstacle polygon.”); creating a plurality of passes that completely cover the area of land, wherein each pass comprises a first end and a second end (See at least paragraph [0060], [0066], “In one embodiment of the first aspect of the present invention said trajectory calculating unit is being configured to perform the following steps: f) in respect of the orientation of one or more sides of headlands, define an array of parallel working rows located within said work area”, paragraph [0227], “So that a vehicle can navigate the rows and the headlands, driven paths need to be generated for both the headlands and the working rows. The driven paths are plotted down the middle of the defined working rows and headlands. However an offset, IO=[IO.sub.x,IO.sub.y], can also be included between the vehicle centre and the implement centre in order for the implements centre to maintain a central position on the working row, see FIG. 14”, and paragraph [0228], “For each working row WR there are two, DR.sub.+ and DR.sub.−, one in same direction as the driving direction and one in the opposite direction as the driving direction. Each DR starts at SDR and ends at EDR.”); applying constraints configured to ensure that each of the plurality of passes is worked exactly once by the one or more agricultural vehicles (See at least paragraph [0060], [0067], “In one embodiment of the first aspect of the present invention said trajectory calculating unit is being configured to perform the following steps: g) in respect of one or more arrays of parallel working rows defined in step f), define an array of possible continuous driving paths by connecting separate entities, wherein said separate entities is being either headlands, or parts of a headland, and working rows, or parts of a working row; so as to define possible continuous driving paths, wherein each driving path is covering all headlands and all working rows” and paragraph [0268], “A cost matrix is built up of the minimal distance to connect two working row driven path, the field gates are also included in this cost matrix. The ends of the working row driven paths are not able to connect to themselves therefore the minimal distance between them is set to infinity, also two working row driven paths that cover the same working row are not able to be connected (this would not make sense are it would mean the working row was worked twice), therefore their connection in the cost matrix is also set to infinity.”); for agricultural vehicle routing to create an optimized route for controlling the one or more agricultural vehicles (See at least paragraph [0051], “These parameters are parameters which may be relevant in finding an optimized trajectory to follow when working a field”, paragraph [0052], “In one embodiment of the first aspect of the present invention said support system further comprising a display unit configured to be able to show on a map of said filed, the optimized trajectory to be followed by said work vehicle as calculated by said trajectory calculating unit”, and paragraph [0053], “This will enable the driver of the working vehicle or implement to easily follow the optimized trajectory, once this has been provided by the trajectory calculating unit.”).
Green does not explicitly disclose; however, Elisha, in the same field of endeavor, teaches transforming each first end and each second end of each of the plurality of passes into a plurality of nodes (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”); connecting the plurality of nodes to create one or more possible routes (See at least paragraph [0049], “In step 305, the routing module 201, for each cluster of the one or more clusters, separately computes a solution to a multiple vehicle routing problem for the set of rides in said each cluster. In one embodiment, the routing module 201 processes a subset of the enhanced ride data and/or the shared ride data corresponding to a subset of rides in a cluster to provide a ride sub-graph. By way of example, the ride sub-graph is a directed acyclic sub-graph (sub-DAG) that describes all possible (feasible) connections between rides in a VRP sub-problem for a cluster via parallel processes 415a-415k, k is the number of clusters. In other words, all rides in the subset belongs to one cluster, and all rides that belong to the cluster must appear in the same subset. In one embodiment, such ride sub-graph is constructed per cluster, by re-constructing the ride sub-graph from the respective ride data (using process 407). In another embodiment, such ride sub-graph is constructed per cluster, by extracting only the relevant nodes and edges in the ride graph generated in process 407 associated with the ride subset.”); computing a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”); computing a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”); the time and distance matrix does not have to be computed in any particular order (See at least paragraph [0037], “FIG. 3 is a flowchart of a process for providing large scale vehicle routing, according to one embodiment. In various embodiments, the routing platform 111 and/or any of the modules 201-207 of the routing platform 111 may perform one or more portions of the process 300 and may be implemented in, for instance, a chip set including a processor and a memory as shown in FIG. 9. As such, the routing platform 111 and/or the modules 201-207 can provide means for accomplishing various parts of the process 300, as well as means for accomplishing embodiments of other processes described herein in conjunction with other components of the system 100. Although the process 300 is illustrated and described as a sequence of steps, its contemplated that various embodiments of the process 300 may be performed in any order or combination and need not include all of the illustrated steps.”); and also configured to ensure that time window requirements are met (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”); formulating a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions (See at least paragraph [0026], “FIG. 1 is a diagram of a system capable of providing large scale vehicle routing, according to one embodiment. A vehicle routing problem (VRP), or more precisely multiple vehicle routing problem (mVRP), is a combinatorial optimization and integer programming problem to determine the optimal set of routes”, paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”, and paragraph [0050], “In one embodiment, the VRP solvers is designed for solving a mixed integer programing (MIP) problem, e.g., Gurobi Optimizers, OR-tools, etc., that can state the VRP as a mathematical model and automatically solve the VRP. MIP is a special case of linear programming (LP) where at least one of the variables can only take on integer values.”); determining that a feasible solution to the non-convex optimization problem exists (See at least paragraph [0049], “In step 305, the routing module 201, for each cluster of the one or more clusters, separately computes a solution to a multiple vehicle routing problem for the set of rides in said each cluster. In one embodiment, the routing module 201 processes a subset of the enhanced ride data and/or the shared ride data corresponding to a subset of rides in a cluster to provide a ride sub-graph. By way of example, the ride sub-graph is a directed acyclic sub-graph (sub-DAG) that describes all possible (feasible) connections between rides in a VRP sub-problem for a cluster via parallel processes 415a-415k, k is the number of clusters. In other words, all rides in the subset belongs to one cluster, and all rides that belong to the cluster must appear in the same subset. In one embodiment, such ride sub-graph is constructed per cluster, by re-constructing the ride sub-graph from the respective ride data (using process 407). In another embodiment, such ride sub-graph is constructed per cluster, by extracting only the relevant nodes and edges in the ride graph generated in process 407 associated with the ride subset” and paragraph [0050], “In one embodiment, the VRP solvers is designed for solving a mixed integer programing (MIP) problem, e.g., Gurobi Optimizers, OR-tools, etc., that can state the VRP as a mathematical model and automatically solve the VRP. MIP is a special case of linear programming (LP) where at least one of the variables can only take on integer values.”).
Green and Elisha do not explicitly disclose; however, USHIJIMA-MWESIGWA, in the same field of endeavor, teaches and solving the non-convex optimization problem using quantum annealing for vehicle routing (See a least paragraph [0028], “The annealer-based solver 102A may be special purpose hardware, for example, quantum or quantum-inspired hardware that may be useful to solve optimization problems. In one or more embodiments of the disclosure, the annealer-based solver 102A may be implemented as a generalized quantum computing device. In such an implementation, the generalized quantum computing device may use specialized optimization solving software applications (e.g., a Quadratic Unconstrained Binary Optimization (QUBO) or using a solver) at an application layer to implement searching algorithms or meta-heuristic algorithms, such as simulated annealing or quantum annealing, to search for a solution to the optimization problem (such as, the VRP) from a discrete solution space.”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Green with the teachings of Elisha and USHIJIMA-MWESIGWA such that the agricultural vehicle trajectory support system of Green is further configured to transform each first end and each second end of each of the plurality of passes into a plurality of nodes; connect the plurality of nodes to create one or more possible routes; compute a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes; compute a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; the time and distance matrix does not have to be computed in any particular order and also configured to ensure that time window requirements are met; formulate a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions; and determine that a feasible solution to the non-convex optimization problem exists, as taught by Elisha (See paragraph [0024], [0037], [0039], [0049], [0050].), and solve the non-convex optimization problem using quantum annealing for vehicle routing, as taught by USHIJIMA-MWESIGWA (See paragraph [0028].), with a reasonable expectation of success. The motivation for doing so would be to improve the ability to solve large-scale routing and fleet optimization problems in finite time, as taught by Elisha (See paragraph [0001].), and to provide more efficient optimization techniques that reduce the time and computing resources required to determine optimal vehicle routes, as taught by USHIJIMA-MWESIGWA (See paragraph [0002].).
Regarding Claim 4, Green, Elisha, and USHIJIMA-MWESIGWA teach The method of claim 1 as set forth in the obviousness rejection above. Green teaches wherein applying constraints further comprises integrating fuel capacity limits of the vehicle (See at least paragraph [0086]-[0089], “In a second aspect the present invention relates to a method for determining a trajectory to be followed by an agricultural work vehicle, when working a field, said method comprising the steps: b) providing information relating to: one or more capacity parameters relating to said working vehicle; c) performing a calculation of an optimized trajectory to be followed by said work vehicle; wherein said optimized trajectory is being calculated on the basis of said coordinates provided in step a) and b)”, paragraph [0095], “In one embodiment of the second aspect of the present invention said one or more capacity parameters being selected from the group comprising: effective working width of the work vehicle or the working implement, load of work vehicle as a function of distance travelled, fuel consumption as a function of distance travelled, minimum turning radius of vehicle or implement or both”, and paragraph [0096], “These parameters are parameters which may be relevant in finding an optimized trajectory to follow when working a field.”).
Claim(s) 2 and 3 is/are rejected under 35 U.S.C. 103 as being unpatentable over Green (US 20190239416 A1) in view of Elisha (US 20210241625 A1) and USHIJIMA-MWESIGWA (US 20240085194 A1) and Bunderson (US 20170202131 A1).
Regarding Claim 2, Green, Elisha, and USHIJIMA-MWESIGWA teach The method of claim 1 as set forth in the obviousness rejection above. Green, Elisha, and USHIJIMA-MWESIGWA do not explicitly disclose; however, Bunderson, in the same field of endeavor, teaches wherein connecting the plurality of nodes to create routes comprises connecting the plurality of nodes with Dubins paths (See at least paragraph [0037], “The three-segment non-continuous curvature 130 path may be a series of curves and/or straight segments (e.g., a second segment 138, a fourth segment 146, and a sixth segment 154) that are joined together at nodes (e.g., a second node 140 and a fourth node 148). As shown in FIG. 4, the second segment 138 begins at the starting point 132, which may correspond to the end point 90 of a row path 88. The starting point 132 may be defined by x.sub.i and y.sub.i (e.g., the initial position of the vehicle 12). At the starting point 132, the vehicle 12 has an initial heading, q.sub.i, and an initial curvature, κ.sub.i. The second segment 138 extends from the starting point 132 to the second node 140. The fourth segment 146 extends from the second node 140 to the fourth node 148. The sixth segment 154 extends from the fourth node 148 to an end point 160, which may correspond to the starting point 90 of a the subsequent row path 88. The three-segment non-continuous curvature path 130 may be a Dubins path. A Dubins path is defined as the shortest path that connects two points in two-dimensional plane with a constraint on the curvature of the path (e.g., minimum turning radius) and with prescribed initial and terminal tangents to the path. The Dubins path is sometimes used in robotics and control theory to plan paths for wheeled robots or vehicles. Typically, a Dubins path comprises a left or right turn arc (“R” or “L”), followed by another left or right turn arc (“R” or “L”) or a straight line (“S”), followed by another left or right turn arc (“R” or “L”).”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Green with the teachings of Elisha, USHIJIMA-MWESIGWA, and Bunderson such that the agricultural vehicle trajectory support system of Green is further configured to transform each first end and each second end of each of the plurality of passes into a plurality of nodes; connect the plurality of nodes to create one or more possible routes; compute a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes; compute a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; the time and distance matrix does not have to be computed in any particular order and also configured to ensure that time window requirements are met; formulate a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions; and determine that a feasible solution to the non-convex optimization problem exists, as taught by Elisha (See paragraph [0024], [0037], [0039], [0049], [0050].), solve the non-convex optimization problem using quantum annealing for vehicle routing, as taught by USHIJIMA-MWESIGWA (See paragraph [0028].), and wherein connecting the plurality of nodes to create routes comprises connecting the plurality of nodes with Dubins paths, as taught by Bunderson (See paragraph [0037].), with a reasonable expectation of success. The motivation for doing so would be to improve the ability to solve large-scale routing and fleet optimization problems in finite time, as taught by Elisha (See paragraph [0001].), to provide more efficient optimization techniques that reduce the time and computing resources required to determine optimal vehicle routes, as taught by USHIJIMA-MWESIGWA (See paragraph [0002].), and to reduce errors during end-of-row turns and improve the efficiency of agricultural operations, as taught by Bunderson (See paragraph [0002].)
Regarding Claim 3, Green, Elisha, and USHIJIMA-MWESIGWA teach The method of claim 1 as set forth in the obviousness rejection above. Green, Elisha, and USHIJIMA-MWESIGWA do not explicitly disclose; however, Bunderson, in the same field of endeavor, teaches wherein connecting the plurality of nodes to create routes comprises accommodating a turn radius, a speed, an implement, a time to raise the implement, and a time to lower the implement associated with the vehicle (See at least paragraph [0002], “Additionally, if the implement is not aligned with the subsequent swath at the time the implement is lowered or turned on, the implement may miss a portion of the subsequent swath, creating a skip, and/or overlap with another swath”, paragraph [0022], “For example, when the agricultural vehicle reaches the end of a first swath, the operator raises, turns off, or otherwise disengages the agricultural implement; the operator then manually controls the speed and steering of the agricultural vehicle to guide the vehicle through the end-of-row turn connecting the end of the first swath to the beginning of a second swath. The operator then lowers, turns on, or otherwise engages the agricultural implement and an automatic or semi-automatic control system guides the agricultural vehicle along the second swath”, paragraph [0023], “Present embodiments of the vehicle control system may generate a continuous curvature end of row turn path for the agricultural vehicle. The vehicle control system may take into account a number of factors (e.g., minimum turning radius, maximum turning rate, starting point, initial heading, speed, fuel consumption, etc.) in determining the end of row turn path. The end-of-row-turn path may include a number of clothoid segments arranged end-to-end. In some embodiments, the vehicle control system may implement the end-of-row turn path (e.g., guide the vehicle along the end-of-row turn path)”, and paragraph [0037], “The three-segment non-continuous curvature 130 path may be a series of curves and/or straight segments (e.g., a second segment 138, a fourth segment 146, and a sixth segment 154) that are joined together at nodes (e.g., a second node 140 and a fourth node 148). As shown in FIG. 4, the second segment 138 begins at the starting point 132, which may correspond to the end point 90 of a row path 88. The starting point 132 may be defined by x.sub.i and y.sub.i (e.g., the initial position of the vehicle 12). At the starting point 132, the vehicle 12 has an initial heading, q.sub.i, and an initial curvature, κ.sub.i. The second segment 138 extends from the starting point 132 to the second node 140. The fourth segment 146 extends from the second node 140 to the fourth node 148.”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Green with the teachings of Elisha, USHIJIMA-MWESIGWA, and Bunderson such that the agricultural vehicle trajectory support system of Green is further configured to transform each first end and each second end of each of the plurality of passes into a plurality of nodes; connect the plurality of nodes to create one or more possible routes; compute a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes; compute a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; the time and distance matrix does not have to be computed in any particular order and also configured to ensure that time window requirements are met; formulate a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions; and determine that a feasible solution to the non-convex optimization problem exists, as taught by Elisha (See paragraph [0024], [0037], [0039], [0049], [0050].), solve the non-convex optimization problem using quantum annealing for vehicle routing, as taught by USHIJIMA-MWESIGWA (See paragraph [0028].), and wherein connecting the plurality of nodes to create routes comprises accommodating a turn radius, a speed, an implement, a time to raise the implement, and a time to lower the implement associated with the vehicle, as taught by Bunderson (See paragraph [0002], [0022], [0023], [0037].), with a reasonable expectation of success. The motivation for doing so would be to improve the ability to solve large-scale routing and fleet optimization problems in finite time, as taught by Elisha (See paragraph [0001].), to provide more efficient optimization techniques that reduce the time and computing resources required to determine optimal vehicle routes, as taught by USHIJIMA-MWESIGWA (See paragraph [0002].), and to reduce errors during end-of-row turns and improve the efficiency of agricultural operations, as taught by Bunderson (See paragraph [0002].).
Claim(s) 5-8 is/are rejected under 35 U.S.C. 103 as being unpatentable over Green (US 20190239416 A1) in view of Elisha (US 20210241625 A1) and USHIJIMA-MWESIGWA (US 20240085194 A1) and Israel (US 20150205759 A1).
Regarding Claim 5, Green, Elisha, and USHIJIMA-MWESIGWA teach The method of claim 1 as set forth in the obviousness rejection above. Green teaches configured to ensure that each of the plurality of passes is worked exactly once by the one or more agricultural vehicles (See at least paragraph [0060], [0067], “In one embodiment of the first aspect of the present invention said trajectory calculating unit is being configured to perform the following steps: g) in respect of one or more arrays of parallel working rows defined in step f), define an array of possible continuous driving paths by connecting separate entities, wherein said separate entities is being either headlands, or parts of a headland, and working rows, or parts of a working row; so as to define possible continuous driving paths, wherein each driving path is covering all headlands and all working rows” and paragraph [0268], “A cost matrix is built up of the minimal distance to connect two working row driven path, the field gates are also included in this cost matrix. The ends of the working row driven paths are not able to connect to themselves therefore the minimal distance between them is set to infinity, also two working row driven paths that cover the same working row are not able to be connected (this would not make sense are it would mean the working row was worked twice), therefore their connection in the cost matrix is also set to infinity.”).
Green does not explicitly disclose; however, Elisha, in the same field of endeavor, teaches and also configured to ensure that time window requirements are met (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”).
Green, Elisha, and USHIJIMA-MWESIGWA do not explicitly disclose; however, Israel, in the same field of endeavor, teaches further comprising determining that a feasible solution to the non-convex optimization problem does not exist (See at least paragraph [0029], “determining, by the at least one processor, one or more members of a feasible set for the constraint; determining, by the at least one processor, one or more members of an infeasible set for the constraint… identifying a new penalty function constraint, not in the initial subset of penalty function constraints, that is violated by an initial solution to the first instance of the problem.”), adjusting the constraints; create adjusted constraints; and reformulating the non-convex optimization problem with the adjusted constraints before determining that a feasible solution to the non-convex optimization problem exists (See at least paragraph [0029], “adding the identified new penalty function constraint to the subset of penalty function constraints to produce a revised subset of penalty function constraints; and solving a second instance of the linear program based on the revised subset of penalty function constraints…The method may further include: generating one or more ancillary variables for each of the respective Ising model penalty functions: re-formulating, by the at least one processor, the received problem as a feasibility problem…re-formulating the feasibility problem by generating one or more inequalities, one or more continuous message variables and one or more binary variables.”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Green with the teachings of Elisha, USHIJIMA-MWESIGWA, and Israel such that the agricultural vehicle trajectory support system of Green is further configured to transform each first end and each second end of each of the plurality of passes into a plurality of nodes; connect the plurality of nodes to create one or more possible routes; compute a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes; compute a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; the time and distance matrix does not have to be computed in any particular order and also configured to ensure that time window requirements are met; formulate a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions; and determine that a feasible solution to the non-convex optimization problem exists, as taught by Elisha (See paragraph [0024], [0037], [0039], [0049], [0050].), solve the non-convex optimization problem using quantum annealing for vehicle routing, as taught by USHIJIMA-MWESIGWA (See paragraph [0028].), and further comprising determining that a feasible solution to the non-convex optimization problem does not exist; and reformulating the non-convex optimization problem with the adjusted constraints before determining that a feasible solution to the non-convex optimization problem exists, as taught by Israel (See paragraph [0029].), with a reasonable expectation of success. The motivation for doing so would be to improve the ability to solve large-scale routing and fleet optimization problems in finite time, as taught by Elisha (See paragraph [0001].), to provide more efficient optimization techniques that reduce the time and computing resources required to determine optimal vehicle routes, as taught by USHIJIMA-MWESIGWA (See paragraph [0002].), and to increase the likelihood that quantum annealing hardware will find a solution and to provide better protection against noise and limitations in precision, as taught by Israel (See paragraph [0018].).
Regarding Claim 6, Green, Elisha, and USHIJIMA-MWESIGWA teach The method of claim 1 as set forth in the obviousness rejection above. Green teaches for agricultural vehicle routing; incorporating distance, time, and agricultural constraints (See at least paragraph [0001], “The present invention generally relates to the field of optimizing work trajectories of agricultural working vehicles for working a field. More specifically the present invention relates in a first aspect to a support system for determining a trajectory to be followed by an agricultural work vehicle when working a field”, paragraph [0048], “In one embodiment of the first aspect of the present invention said optimized trajectory is being an optimized trajectory in terms of total operational time for working the field; total productive time for working the field; total fuel consumption for working the field; total non-working distance for working the field; total distance travelled twice or more; total distance travelled through crops; total area covered twice or more”, paragraph [0050], “In one embodiment of the first aspect of the present invention said one or more capacity parameters is being selected from the group comprising: effective working width of the work vehicle or the working implement, load of work vehicle as a function of distance travelled, fuel consumption as a function of distance travelled, minimum turning radius of vehicle or implement or both”, and paragraph [0051], “These parameters are parameters which may be relevant in finding an optimized trajectory to follow when working a field.”).
Green, Elisha, and USHIJIMA-MWESIGWA do not explicitly disclose; however, Israel, in the same field of endeavor, teaches wherein using quantum annealing…comprises formulating a quadratic unconstrained binary optimization matrix having a cost function (See at least paragraph [0004], “A quadratic unconstrained binary optimization (QUBO) problem is a form of discrete optimization problem that involves finding a set of N binary variables {xi} that minimizes an objective function of the form: E ( x 1 , , x N ) = i .ltoreq. j N Q ij x i y j ##EQU00001## where Q is typically a real-valued upper triangular matrix that is characteristic of the particular problem instance being studied. QUBO problems and applications arise in many different fields, for example machine learning, pattern matching, and statistical mechanics, to name a few”, paragraph [0007], “Quantum annealing is a heuristic optimization approach applicable to certain discrete optimization problems. For example, quantum annealing can be used to find a low-energy state of a system, such as the ground state of the system”, paragraph [0009], “Since the solution to a hard problem, such as a combinatorial optimization problem, can be encoded in the ground state of a system, quantum annealing can be used to find the solution to such hard problems.”); loading the quadratic unconstrained binary optimization matrix into a quantum annealer (See at least paragraph [0010], “Quantum hardware can be used to minimize the dimensionless energy of an Ising model mathematically equivalent to the QUBO described above: E ( s | h , J ) = i .di-elect cons. V ( G ) h i s i + ( i , j ) .di-elect cons. E ( G ) J i , j s i s j ##EQU00002##” and paragraph [0011], “A quantum annealing process can minimize the Ising energy by evolving the ground state of an initial Hamiltonian to the ground state of a problem Hamiltonian.”), performing quantum annealing on the quadratic unconstrained binary optimization matrix to create one or more resulting quantum states (See at least paragraph [0010], “Quantum hardware can be used to minimize the dimensionless energy of an Ising model mathematically equivalent to the QUBO described above: E ( s | h , J ) = i .di-elect cons. V ( G ) h i s i + ( i , j ) .di-elect cons. E ( G ) J i , j s i s j ##EQU00002##” and paragraph [0011], “A quantum annealing process can minimize the Ising energy by evolving the ground state of an initial Hamiltonian to the ground state of a problem Hamiltonian. The ground state of the initial Hamiltonian is a superposition state in which all spin configurations are equally likely. After annealing, the spin configurations with the smallest energy with respect to the problem Hamiltonian are the most likely to be measured.”), determining an energy level for each of the resulting quantum states (See at least paragraph [0008], “Similar in concept to classical annealing, the method relies on the underlying principle that natural systems tend toward lower energy states because lower energy states are more stable. Whereas classical annealing can use classical thermal fluctuations to guide a system to its global energy minimum, quantum annealing can use natural quantum fluctuations, such as quantum tunneling, to reach a global energy minimum more accurately and/or more quickly”, paragraph [0010], “Quantum hardware can be used to minimize the dimensionless energy of an Ising model mathematically equivalent to the QUBO described above: E ( s | h , J ) = i .di-elect cons. V ( G ) h i s i + ( i , j ) .di-elect cons. E ( G ) J i , j s i s j ##EQU00002##”, and paragraph [0011], “A quantum annealing process can minimize the Ising energy by evolving the ground state of an initial Hamiltonian to the ground state of a problem Hamiltonian. The ground state of the initial Hamiltonian is a superposition state in which all spin configurations are equally likely. After annealing, the spin configurations with the smallest energy with respect to the problem Hamiltonian are the most likely to be measured.”), selecting as an optimized solution a resulting quantum state having an energy level lower than any other resulting quantum state (See at least paragraph [0007], “Quantum annealing is a heuristic optimization approach applicable to certain discrete optimization problems. For example, quantum annealing can be used to find a low-energy state of a system, such as the ground state of the system”, paragraph [0008], “Similar in concept to classical annealing, the method relies on the underlying principle that natural systems tend toward lower energy states because lower energy states are more stable. Whereas classical annealing can use classical thermal fluctuations to guide a system to its global energy minimum, quantum annealing can use natural quantum fluctuations, such as quantum tunneling, to reach a global energy minimum more accurately and/or more quickly”, paragraph [0009], “Since the solution to a hard problem, such as a combinatorial optimization problem, can be encoded in the ground state of a system, quantum annealing can be used to find the solution to such hard problems”, paragraph [0010], “Quantum hardware can be used to minimize the dimensionless energy of an Ising model mathematically equivalent to the QUBO described above: E ( s | h , J ) = i .di-elect cons. V ( G ) h i s i + ( i , j ) .di-elect cons. E ( G ) J i , j s i s j ##EQU00002##”, and paragraph [0011], “A quantum annealing process can minimize the Ising energy by evolving the ground state of an initial Hamiltonian to the ground state of a problem Hamiltonian. The ground state of the initial Hamiltonian is a superposition state in which all spin configurations are equally likely. After annealing, the spin configurations with the smallest energy with respect to the problem Hamiltonian are the most likely to be measured.”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Green with the teachings of Elisha, USHIJIMA-MWESIGWA, and Israel such that the agricultural vehicle trajectory support system of Green is further configured to transform each first end and each second end of each of the plurality of passes into a plurality of nodes; connect the plurality of nodes to create one or more possible routes; compute a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes; compute a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; the time and distance matrix does not have to be computed in any particular order and also configured to ensure that time window requirements are met; formulate a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions; and determine that a feasible solution to the non-convex optimization problem exists, as taught by Elisha (See paragraph [0024], [0037], [0039], [0049], [0050].), solve the non-convex optimization problem using quantum annealing for vehicle routing, as taught by USHIJIMA-MWESIGWA (See paragraph [0028].), and wherein using quantum annealing…comprises formulating a quadratic unconstrained binary optimization matrix having a cost function; loading the quadratic unconstrained binary optimization matrix into a quantum annealer, performing quantum annealing on the quadratic unconstrained binary optimization matrix to create one or more resulting quantum states, determining an energy level for each of the resulting quantum states, and selecting as an optimized solution a resulting quantum state having an energy level lower than any other resulting quantum state, as taught by Israel (See paragraph [0004], [0007]-[0011].), with a reasonable expectation of success. The motivation for doing so would be to improve the ability to solve large-scale routing and fleet optimization problems in finite time, as taught by Elisha (See paragraph [0001].), to provide more efficient optimization techniques that reduce the time and computing resources required to determine optimal vehicle routes, as taught by USHIJIMA-MWESIGWA (See paragraph [0002].), and to increase the likelihood that quantum annealing hardware will find a solution and to provide better protection against noise and limitations in precision, as taught by Israel (See paragraph [0018].).
Regarding Claim 7, Green, Elisha, USHIJIMA-MWESIGWA, and Israel teach The method of claim 6 as set forth in the obviousness rejection above. Green teaches further comprising verifying that the optimized solution meets agricultural and routing constraints (See at least paragraph [0050], “In one embodiment of the first aspect of the present invention said one or more capacity parameters is being selected from the group comprising: effective working width of the work vehicle or the working implement, load of work vehicle as a function of distance travelled, fuel consumption as a function of distance travelled, minimum turning radius of vehicle or implement or both”, paragraph [0051], “These parameters are parameters which may be relevant in finding an optimized trajectory to follow when working a field”, paragraph [0272], “The cost matrix can be used to determine a feasible route to navigate the field. Since the problem to find the optimal route to navigate the field can be consider an NP-hard problem (i.e. it may not be possible to find a solution in a nominal time frame) the heuristic solvers can be used to find a near optimal route. The solver must also account for the fact working row driven paths are associated to one another by the working row they cover”, paragraph [0274], “Firstly a starting gate is chosen. The gate is chosen by considering all the connections from gates to the working row driven paths. The connections to the working row driven paths are in the rows labelled for each gate. The gate which has the shortest connection to any working row driven path is chosen as the starting gate and the working row driven path is chosen as the first working row driven path in the route. Since this working row driven path has been chosen as a “destination” it cannot be chosen as a destination from another working row driven path again, therefore all the values in the column associated with it are set to infinity. Also the other working row driven path associated with the same working row cannot be chosen as either as destination or a start so all of the values in both the column and the row associated with the other working row driven path are also set to infinity”, and paragraph [0275], “The first working row driven path is now considered the start point and shortest connection from it to another working row driven path is now sought after. The shortest connection is that in the row associated with the first working row driven path with the lowest value. The working row driven path with the lowest value is considered the second working row driven path in the route. Again all of the values in the column associated with the second working row driven path and that of the working row driven path associated with the same working row are set to infinity as is the row of values of the working row driven path associated with the same working row. This method continues until only the gates remain as possible destinations. The sum of all of the chosen connections is the estimation of the non-working distance needed to navigate the field.”).
Regarding Claim 8, Green, Elisha, USHIJIMA-MWESIGWA, and Israel teach The method of claim 6 as set forth in the obviousness rejection above. Green teaches to determine a final route (See at least paragraph [0272], “The cost matrix can be used to determine a feasible route to navigate the field.”).
Green, Elisha, and USHIJIMA-MWESIGWA do not explicitly disclose; however, Israel, in the same field of endeavor, teaches further comprising determining that the optimized solution is not feasible (See at least paragraph [0029], “identifying a new penalty function constraint, not in the initial subset of penalty function constraints, that is violated by an initial solution to the first instance of the linear program” and paragraph [0030], “A method of operation in a problem solving system which includes at least a first processor and at least one non-transitory processor-readable medium communicatively coupled to the first processor and which stores at least one of processor-executable instructions or data, wherein one of a number of hardware limitations of a second processor imposes a number of bounds on a set of programmable parameters, may be summarized as including: receiving, by the first processor, a constraint; representing, by the first processor, the constraint as an Ising model penalty function and a penalty gap associated therewith, the penalty gap separating a set of feasible solutions to the constraint from a set of infeasible solutions to the constraint; and determining, by the first processor, the Ising model penalty function subject to the bounds on the programmable parameters imposed by the hardware limitations of the second processor, where the penalty gap exceeds a predetermined threshold greater than zero. The set of feasible solutions to the constraint may be enumerated by the first processor.”), adjusting the quadratic unconstrained binary optimization matrix (See at least paragraph [0029], “adding the identified new penalty function constraint to the subset of penalty function constraints to produce a revised subset of penalty function constraints; and employing the revised subset of penalty function constraints” and paragraph [0105], “The process in method 300 is an example of moving from a constraint focused problem to an optimization focused problem. The optimization problem of interest here is QUBO, but a person of ordinary skill in the art will appreciate that a QUBO problem can be mapped to an Ising problem or to a weighted MAX-2-SAT, and vice versa, and between the three classes of problems. Elsewhere in this application, an Ising model is used to describe the problem of interest. The systems and methods for QUBO problem finding and Ising model finding can be the same.”), and repeatedly performing quantum annealing (See at least paragraph [0007], “Quantum annealing is a heuristic optimization approach applicable to certain discrete optimization problems. For example, quantum annealing can be used to find a low-energy state of a system, such as the ground state of the system”, paragraph [0008], “Similar in concept to classical annealing, the method relies on the underlying principle that natural systems tend toward lower energy states because lower energy states are more stable. Whereas classical annealing can use classical thermal fluctuations to guide a system to its global energy minimum, quantum annealing can use natural quantum fluctuations, such as quantum tunneling, to reach a global energy minimum more accurately and/or more quickly”, paragraph [0009], “Since the solution to a hard problem, such as a combinatorial optimization problem, can be encoded in the ground state of a system, quantum annealing can be used to find the solution to such hard problems”, paragraph [0010], “Quantum hardware can be used to minimize the dimensionless energy of an Ising model mathematically equivalent to the QUBO described above: E ( s | h , J ) = i .di-elect cons. V ( G ) h i s i + ( i , j ) .di-elect cons. E ( G ) J i , j s i s j ##EQU00002##”, paragraph [0011], “A quantum annealing process can minimize the Ising energy by evolving the ground state of an initial Hamiltonian to the ground state of a problem Hamiltonian. The ground state of the initial Hamiltonian is a superposition state in which all spin configurations are equally likely. After annealing, the spin configurations with the smallest energy with respect to the problem Hamiltonian are the most likely to be measured”, and paragraph [0029], “The method may further include: until no subsequent new penalty function constraints is found that is violated by a solution of a most recent instance of the linear program, repeatedly: identifying a new penalty function constraint, not in a most recently revised subset of penalty function constraints, that is violated by a solution to a most recent instance of the linear program; adding the identified new penalty function constraint to the most recently revised subset of penalty function constraints to produce subsequent revised subset of penalty function constraints; and solving subsequent instances of the linear program based on respective ones of the subsequent revised subsets of penalty function constraints.”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Green with the teachings of Elisha, USHIJIMA-MWESIGWA, and Israel such that the agricultural vehicle trajectory support system of Green is further configured to transform each first end and each second end of each of the plurality of passes into a plurality of nodes; connect the plurality of nodes to create one or more possible routes; compute a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes; compute a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; the time and distance matrix does not have to be computed in any particular order and also configured to ensure that time window requirements are met; formulate a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions; and determine that a feasible solution to the non-convex optimization problem exists, as taught by Elisha (See paragraph [0024], [0037], [0039], [0049], [0050].), solve the non-convex optimization problem using quantum annealing for vehicle routing, as taught by USHIJIMA-MWESIGWA (See paragraph [0028].), and wherein using quantum annealing…comprises formulating a quadratic unconstrained binary optimization matrix having a cost function; loading the quadratic unconstrained binary optimization matrix into a quantum annealer, performing quantum annealing on the quadratic unconstrained binary optimization matrix to create one or more resulting quantum states, determining an energy level for each of the resulting quantum states, selecting as an optimized solution a resulting quantum state having an energy level lower than any other resulting quantum state; determining that the optimized solution is not feasible, adjusting the quadratic unconstrained binary optimization matrix, and repeatedly performing quantum annealing, as taught by Israel (See paragraph [0004], [0007]-[0011], [0029], [0030].), with a reasonable expectation of success. The motivation for doing so would be to improve the ability to solve large-scale routing and fleet optimization problems in finite time, as taught by Elisha (See paragraph [0001].), to provide more efficient optimization techniques that reduce the time and computing resources required to determine optimal vehicle routes, as taught by USHIJIMA-MWESIGWA (See paragraph [0002].), and to increase the likelihood that quantum annealing hardware will find a solution and to provide better protection against noise and limitations in precision, as taught by Israel (See paragraph [0018].).
Claim(s) 9, 12, and 14 is/are rejected under 35 U.S.C. 103 as being unpatentable over Green (US 20190239416 A1) in view of Elisha (US 20210241625 A1).
Regarding Claim 9, Green teaches A method for optimizing a route for execution by a system that controls one or more agricultural vehicles comprising: defining an area of land to be worked by the one or more agricultural vehicles (See at least paragraph [0036], “In a first aspect the present invention relates to a support system for determining a trajectory to be followed by an agricultural work vehicle, when working a field”, paragraph [0042], “The support system is designed with the view to aid in optimizing finding a trajectory to be followed upon working an agricultural field with a working vehicle or implement”, and paragraph [0060], [0065], “In one embodiment of the first aspect of the present invention said trajectory calculating unit is being configured to perform the following steps: e) defining a work area which corresponds to the area within said boundary polygon with the exclusion of the area corresponding to any headlands and with the exclusion of the area corresponding to any obstacle polygon.”); creating a plurality of passes that completely cover the area of land, wherein each pass comprises a first end and a second end; (See at least paragraph [0060], [0066], “In one embodiment of the first aspect of the present invention said trajectory calculating unit is being configured to perform the following steps: f) in respect of the orientation of one or more sides of headlands, define an array of parallel working rows located within said work area”, paragraph [0227], “So that a vehicle can navigate the rows and the headlands, driven paths need to be generated for both the headlands and the working rows. The driven paths are plotted down the middle of the defined working rows and headlands. However an offset, IO=[IO.sub.x,IO.sub.y], can also be included between the vehicle centre and the implement centre in order for the implements centre to maintain a central position on the working row, see FIG. 14”, and paragraph [0228], “For each working row WR there are two, DR.sub.+ and DR.sub.−, one in same direction as the driving direction and one in the opposite direction as the driving direction. Each DR starts at SDR and ends at EDR.”); applying constraints configured to ensure that each of the plurality of passes is worked exactly once by the one or more agricultural vehicles (See at least paragraph [0060], [0067], “In one embodiment of the first aspect of the present invention said trajectory calculating unit is being configured to perform the following steps: g) in respect of one or more arrays of parallel working rows defined in step f), define an array of possible continuous driving paths by connecting separate entities, wherein said separate entities is being either headlands, or parts of a headland, and working rows, or parts of a working row; so as to define possible continuous driving paths, wherein each driving path is covering all headlands and all working rows” and paragraph [0268], “A cost matrix is built up of the minimal distance to connect two working row driven path, the field gates are also included in this cost matrix. The ends of the working row driven paths are not able to connect to themselves therefore the minimal distance between them is set to infinity, also two working row driven paths that cover the same working row are not able to be connected (this would not make sense are it would mean the working row was worked twice), therefore their connection in the cost matrix is also set to infinity.”); create an optimized route for controlling the one or more agricultural vehicles (See at least paragraph [0051], “These parameters are parameters which may be relevant in finding an optimized trajectory to follow when working a field”, paragraph [0052], “In one embodiment of the first aspect of the present invention said support system further comprising a display unit configured to be able to show on a map of said filed, the optimized trajectory to be followed by said work vehicle as calculated by said trajectory calculating unit”, and paragraph [0053], “This will enable the driver of the working vehicle or implement to easily follow the optimized trajectory, once this has been provided by the trajectory calculating unit.”).
Green does not explicitly disclose; however, Elisha, in the same field of endeavor, teaches transforming each first end and each second end of each of the plurality of passes into a plurality of nodes (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”); connecting the plurality of nodes to create one or more possible routes (See at least paragraph [0049], “In step 305, the routing module 201, for each cluster of the one or more clusters, separately computes a solution to a multiple vehicle routing problem for the set of rides in said each cluster. In one embodiment, the routing module 201 processes a subset of the enhanced ride data and/or the shared ride data corresponding to a subset of rides in a cluster to provide a ride sub-graph. By way of example, the ride sub-graph is a directed acyclic sub-graph (sub-DAG) that describes all possible (feasible) connections between rides in a VRP sub-problem for a cluster via parallel processes 415a-415k, k is the number of clusters. In other words, all rides in the subset belongs to one cluster, and all rides that belong to the cluster must appear in the same subset. In one embodiment, such ride sub-graph is constructed per cluster, by re-constructing the ride sub-graph from the respective ride data (using process 407). In another embodiment, such ride sub-graph is constructed per cluster, by extracting only the relevant nodes and edges in the ride graph generated in process 407 associated with the ride subset.”); computing a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”); computing a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”); and also configured to ensure that time window requirements are met (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”); formulating a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions (See at least paragraph [0026], “FIG. 1 is a diagram of a system capable of providing large scale vehicle routing, according to one embodiment. A vehicle routing problem (VRP), or more precisely multiple vehicle routing problem (mVRP), is a combinatorial optimization and integer programming problem to determine the optimal set of routes”, paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”, and paragraph [0050], “In one embodiment, the VRP solvers is designed for solving a mixed integer programing (MIP) problem, e.g., Gurobi Optimizers, OR-tools, etc., that can state the VRP as a mathematical model and automatically solve the VRP. MIP is a special case of linear programming (LP) where at least one of the variables can only take on integer values.”); determining that a feasible solution to the non-convex optimization problem exists (See at least paragraph [0049], “In step 305, the routing module 201, for each cluster of the one or more clusters, separately computes a solution to a multiple vehicle routing problem for the set of rides in said each cluster. In one embodiment, the routing module 201 processes a subset of the enhanced ride data and/or the shared ride data corresponding to a subset of rides in a cluster to provide a ride sub-graph. By way of example, the ride sub-graph is a directed acyclic sub-graph (sub-DAG) that describes all possible (feasible) connections between rides in a VRP sub-problem for a cluster via parallel processes 415a-415k, k is the number of clusters. In other words, all rides in the subset belongs to one cluster, and all rides that belong to the cluster must appear in the same subset. In one embodiment, such ride sub-graph is constructed per cluster, by re-constructing the ride sub-graph from the respective ride data (using process 407). In another embodiment, such ride sub-graph is constructed per cluster, by extracting only the relevant nodes and edges in the ride graph generated in process 407 associated with the ride subset” and paragraph [0050], “In one embodiment, the VRP solvers is designed for solving a mixed integer programing (MIP) problem, e.g., Gurobi Optimizers, OR-tools, etc., that can state the VRP as a mathematical model and automatically solve the VRP. MIP is a special case of linear programming (LP) where at least one of the variables can only take on integer values.”); and solving the non-convex optimization problem to create an optimized route for controlling the one or more vehicles (See at least paragraph [0049], “In step 305, the routing module 201, for each cluster of the one or more clusters, separately computes a solution to a multiple vehicle routing problem for the set of rides in said each cluster. In one embodiment, the routing module 201 processes a subset of the enhanced ride data and/or the shared ride data corresponding to a subset of rides in a cluster to provide a ride sub-graph. By way of example, the ride sub-graph is a directed acyclic sub-graph (sub-DAG) that describes all possible (feasible) connections between rides in a VRP sub-problem for a cluster via parallel processes 415a-415k, k is the number of clusters. In other words, all rides in the subset belongs to one cluster, and all rides that belong to the cluster must appear in the same subset. In one embodiment, such ride sub-graph is constructed per cluster, by re-constructing the ride sub-graph from the respective ride data (using process 407). In another embodiment, such ride sub-graph is constructed per cluster, by extracting only the relevant nodes and edges in the ride graph generated in process 407 associated with the ride subset” and paragraph [0050], “Then after, the routing module 201 use VRP solvers to process in parallel the enhanced ride data, the shared ride data, and/or the ride sub-graph corresponding to subsets of rides in clusters to provide optimal clusters/plans via parallel processes 417a-417k. In one embodiment, the VRP solvers is designed for solving a mixed integer programing (MIP) problem, e.g., Gurobi Optimizers, OR-tools, etc., that can state the VRP as a mathematical model and automatically solve the VRP. MIP is a special case of linear programming (LP) where at least one of the variables can only take on integer values. LP is a method to maximize or minimize a linear objective function subject to one or more constraints/requirements that are represented by a linear relationship. An optimization procedure requires solving a MIP problem which, like linear programing, is a sub-field of combinatorial optimization.”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Green with the teachings of Elisha such that the agricultural vehicle trajectory support system of Green is further configured to transform each first end and each second end of each of the plurality of passes into a plurality of nodes; connect the plurality of nodes to create one or more possible routes; compute a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes; compute a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; and also configured to ensure that time window requirements are met; formulate a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions; determine that a feasible solution to the non-convex optimization problem exists; and solving the non-convex optimization problem to create an optimized route for controlling the one or more vehicles, as taught by Elisha (See paragraph [0024], [0037], [0039], [0049], [0050].), with a reasonable expectation of success. The motivation for doing so would be to improve the ability to solve large-scale routing and fleet optimization problems in finite time, as taught by Elisha (See paragraph [0001].).
Regarding Claim 12, Green and Elisha teach The method of claim 9 as set forth in the obviousness rejection above. Green teaches wherein applying constraints further comprises integrating fuel capacity limits of the vehicle (See at least paragraph [0086]-[0089], “In a second aspect the present invention relates to a method for determining a trajectory to be followed by an agricultural work vehicle, when working a field, said method comprising the steps: b) providing information relating to: one or more capacity parameters relating to said working vehicle; c) performing a calculation of an optimized trajectory to be followed by said work vehicle; wherein said optimized trajectory is being calculated on the basis of said coordinates provided in step a) and b)”, paragraph [0095], “In one embodiment of the second aspect of the present invention said one or more capacity parameters being selected from the group comprising: effective working width of the work vehicle or the working implement, load of work vehicle as a function of distance travelled, fuel consumption as a function of distance travelled, minimum turning radius of vehicle or implement or both”, and paragraph [0096], “These parameters are parameters which may be relevant in finding an optimized trajectory to follow when working a field.”).
Regarding Claim 14, Green and Elisha teach The method of claim 9 as set forth in the obviousness rejection above. Green teaches wherein solving the non-convex optimization problem comprises employing heuristic and meta-heuristic techniques (See at least paragraph [0079], “In one embodiment of the first aspect of the present invention said support system is being configured to find said optimized trajectory by means of a heuristic method, such as a greedy heuristic method, a tabu search solver, an ant colony solver, a genetic algorithm”, paragraph [0272], “The cost matrix can be used to determine a feasible route to navigate the field. Since the problem to find the optimal route to navigate the field can be consider an NP-hard problem (i.e. it may not be possible to find a solution in a nominal time frame) the heuristic solvers can be used to find a near optimal route. The solver must also account for the fact working row driven paths are associated to one another by the working row they cover”, and paragraph [0273], “In this example a greedy heuristic method is used to find a route to navigate the field. This method provides a simple estimate of what the optimal solution might be. However different solvers could be used, such as a tabu search solver, ant colony solver, genetic algorithms, etc., to give similar results.”).
Claim(s) 10 and 11 is/are rejected under 35 U.S.C. 103 as being unpatentable over Green (US 20190239416 A1) in view of Elisha (US 20210241625 A1) and Bunderson (US 20170202131 A1).
Regarding Claim 10, Green and Elisha teach The method of claim 9 as set forth in the obviousness rejection above. Green and Elisha do not explicitly disclose; however, Bunderson, in the same field of endeavor, teaches wherein connecting the plurality of nodes to create routes comprises connecting the plurality of nodes with Dubins paths (See at least paragraph [0037], “The three-segment non-continuous curvature 130 path may be a series of curves and/or straight segments (e.g., a second segment 138, a fourth segment 146, and a sixth segment 154) that are joined together at nodes (e.g., a second node 140 and a fourth node 148). As shown in FIG. 4, the second segment 138 begins at the starting point 132, which may correspond to the end point 90 of a row path 88. The starting point 132 may be defined by x.sub.i and y.sub.i (e.g., the initial position of the vehicle 12). At the starting point 132, the vehicle 12 has an initial heading, q.sub.i, and an initial curvature, κ.sub.i. The second segment 138 extends from the starting point 132 to the second node 140. The fourth segment 146 extends from the second node 140 to the fourth node 148. The sixth segment 154 extends from the fourth node 148 to an end point 160, which may correspond to the starting point 90 of a the subsequent row path 88. The three-segment non-continuous curvature path 130 may be a Dubins path. A Dubins path is defined as the shortest path that connects two points in two-dimensional plane with a constraint on the curvature of the path (e.g., minimum turning radius) and with prescribed initial and terminal tangents to the path. The Dubins path is sometimes used in robotics and control theory to plan paths for wheeled robots or vehicles. Typically, a Dubins path comprises a left or right turn arc (“R” or “L”), followed by another left or right turn arc (“R” or “L”) or a straight line (“S”), followed by another left or right turn arc (“R” or “L”).”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Green with the teachings of Elisha and Bunderson such that the agricultural vehicle trajectory support system of Green is further configured to transform each first end and each second end of each of the plurality of passes into a plurality of nodes; connect the plurality of nodes to create one or more possible routes; compute a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes; compute a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; and also configured to ensure that time window requirements are met; formulate a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions; determine that a feasible solution to the non-convex optimization problem exists; and solving the non-convex optimization problem to create an optimized route for controlling the one or more vehicles, as taught by Elisha (See paragraph [0024], [0037], [0039], [0049], [0050].), and wherein connecting the plurality of nodes to create routes comprises connecting the plurality of nodes with Dubins paths, as taught by Bunderson (See paragraph [0037].), with a reasonable expectation of success. The motivation for doing so would be to improve the ability to solve large-scale routing and fleet optimization problems in finite time, as taught by Elisha (See paragraph [0001].), and to reduce errors during end-of-row turns and improve the efficiency of agricultural operations, as taught by Bunderson (See paragraph [0002].)
Regarding Claim 11, Green and Elisha teach The method of claim 9 as set forth in the obviousness rejection above. Green and Elisha do not explicitly disclose; however, Bunderson, in the same field of endeavor, teaches wherein connecting the plurality of nodes to create routes comprises accommodating a turn radius, a speed, an implement, a time to raise the implement, and a time to lower the implement associated with the vehicle (See at least paragraph [0002], “Additionally, if the implement is not aligned with the subsequent swath at the time the implement is lowered or turned on, the implement may miss a portion of the subsequent swath, creating a skip, and/or overlap with another swath”, paragraph [0022], “For example, when the agricultural vehicle reaches the end of a first swath, the operator raises, turns off, or otherwise disengages the agricultural implement; the operator then manually controls the speed and steering of the agricultural vehicle to guide the vehicle through the end-of-row turn connecting the end of the first swath to the beginning of a second swath. The operator then lowers, turns on, or otherwise engages the agricultural implement and an automatic or semi-automatic control system guides the agricultural vehicle along the second swath”, paragraph [0023], “Present embodiments of the vehicle control system may generate a continuous curvature end of row turn path for the agricultural vehicle. The vehicle control system may take into account a number of factors (e.g., minimum turning radius, maximum turning rate, starting point, initial heading, speed, fuel consumption, etc.) in determining the end of row turn path. The end-of-row-turn path may include a number of clothoid segments arranged end-to-end. In some embodiments, the vehicle control system may implement the end-of-row turn path (e.g., guide the vehicle along the end-of-row turn path)”, and paragraph [0037], “The three-segment non-continuous curvature 130 path may be a series of curves and/or straight segments (e.g., a second segment 138, a fourth segment 146, and a sixth segment 154) that are joined together at nodes (e.g., a second node 140 and a fourth node 148). As shown in FIG. 4, the second segment 138 begins at the starting point 132, which may correspond to the end point 90 of a row path 88. The starting point 132 may be defined by x.sub.i and y.sub.i (e.g., the initial position of the vehicle 12). At the starting point 132, the vehicle 12 has an initial heading, q.sub.i, and an initial curvature, κ.sub.i. The second segment 138 extends from the starting point 132 to the second node 140. The fourth segment 146 extends from the second node 140 to the fourth node 148.”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Green with the teachings of Elisha and Bunderson such that the agricultural vehicle trajectory support system of Green is further configured to transform each first end and each second end of each of the plurality of passes into a plurality of nodes; connect the plurality of nodes to create one or more possible routes; compute a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes; compute a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; and also configured to ensure that time window requirements are met; formulate a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions; determine that a feasible solution to the non-convex optimization problem exists; and solving the non-convex optimization problem to create an optimized route for controlling the one or more vehicles, as taught by Elisha (See paragraph [0024], [0037], [0039], [0049], [0050].), and wherein connecting the plurality of nodes to create routes comprises accommodating a turn radius, a speed, an implement, a time to raise the implement, and a time to lower the implement associated with the vehicle, as taught by Bunderson (See paragraph [0002], [0022], [0023], [0037].), with a reasonable expectation of success. The motivation for doing so would be to improve the ability to solve large-scale routing and fleet optimization problems in finite time, as taught by Elisha (See paragraph [0001].), and to reduce errors during end-of-row turns and improve the efficiency of agricultural operations, as taught by Bunderson (See paragraph [0002].).
Claim(s) 13 is/are rejected under 35 U.S.C. 103 as being unpatentable over Green (US 20190239416 A1) in view of Elisha (US 20210241625 A1) and Israel (US 20150205759 A1).
Regarding Claim 13, Green and Elisha teach The method of claim 9 as set forth in the obviousness rejection above. Green teaches configured to ensure that each of the plurality of passes is worked exactly once by the one or more agricultural vehicles (See at least paragraph [0060], [0067], “In one embodiment of the first aspect of the present invention said trajectory calculating unit is being configured to perform the following steps: g) in respect of one or more arrays of parallel working rows defined in step f), define an array of possible continuous driving paths by connecting separate entities, wherein said separate entities is being either headlands, or parts of a headland, and working rows, or parts of a working row; so as to define possible continuous driving paths, wherein each driving path is covering all headlands and all working rows” and paragraph [0268], “A cost matrix is built up of the minimal distance to connect two working row driven path, the field gates are also included in this cost matrix. The ends of the working row driven paths are not able to connect to themselves therefore the minimal distance between them is set to infinity, also two working row driven paths that cover the same working row are not able to be connected (this would not make sense are it would mean the working row was worked twice), therefore their connection in the cost matrix is also set to infinity.”).
Green does not explicitly disclose; however, Elisha, in the same field of endeavor, teaches and also configured to ensure that time window requirements are met (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”).
Green and Elisha do not explicitly disclose; however, Israel, in the same field of endeavor, teaches further comprising determining that a feasible solution to the non-convex optimization problem does not exist (See at least paragraph [0029], “determining, by the at least one processor, one or more members of a feasible set for the constraint; determining, by the at least one processor, one or more members of an infeasible set for the constraint… identifying a new penalty function constraint, not in the initial subset of penalty function constraints, that is violated by an initial solution to the first instance of the problem.”), adjusting the constraints; create adjusted constraints, and reformulating the non-convex optimization problem with the adjusted constraints before determining that a feasible solution to the non-convex optimization problem exists (See at least paragraph [0029], “adding the identified new penalty function constraint to the subset of penalty function constraints to produce a revised subset of penalty function constraints; and solving a second instance of the linear program based on the revised subset of penalty function constraints…The method may further include: generating one or more ancillary variables for each of the respective Ising model penalty functions: re-formulating, by the at least one processor, the received problem as a feasibility problem…re-formulating the feasibility problem by generating one or more inequalities, one or more continuous message variables and one or more binary variables.”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Green with the teachings of Elisha and Israel such that the agricultural vehicle trajectory support system of Green is further configured to transform each first end and each second end of each of the plurality of passes into a plurality of nodes; connect the plurality of nodes to create one or more possible routes; compute a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes; compute a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; and also configured to ensure that time window requirements are met; formulate a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions; determine that a feasible solution to the non-convex optimization problem exists; and solving the non-convex optimization problem to create an optimized route for controlling the one or more vehicles, as taught by Elisha (See paragraph [0024], [0037], [0039], [0049], [0050].), and further comprising determining that a feasible solution to the non-convex optimization problem does not exist; and reformulating the non-convex optimization problem with the adjusted constraints before determining that a feasible solution to the non-convex optimization problem exists, as taught by Israel (See paragraph [0029].), with a reasonable expectation of success. The motivation for doing so would be to improve the ability to solve large-scale routing and fleet optimization problems in finite time, as taught by Elisha (See paragraph [0001].), and to increase the likelihood that quantum annealing hardware will find a solution and to provide better protection against noise and limitations in precision, as taught by Israel (See paragraph [0018].).
Claim(s) 15 and 18 is/are rejected under 35 U.S.C. 103 as being unpatentable over Green (US 20190239416 A1) in view of Elisha (US 20210241625 A1) and Wang (US 20200133947 A1).
Regarding Claim 15, Green teaches A method for optimizing a route for execution by a system that controls one or more agricultural vehicles comprising: defining an area of land to be worked by the one or more agricultural vehicles (See at least paragraph [0036], “In a first aspect the present invention relates to a support system for determining a trajectory to be followed by an agricultural work vehicle, when working a field”, paragraph [0042], “The support system is designed with the view to aid in optimizing finding a trajectory to be followed upon working an agricultural field with a working vehicle or implement”, and paragraph [0060], [0065], “In one embodiment of the first aspect of the present invention said trajectory calculating unit is being configured to perform the following steps: e) defining a work area which corresponds to the area within said boundary polygon with the exclusion of the area corresponding to any headlands and with the exclusion of the area corresponding to any obstacle polygon.”); creating a plurality of passes that completely cover the area of land, wherein each pass comprises a first end and a second end (See at least paragraph [0060], [0066], “In one embodiment of the first aspect of the present invention said trajectory calculating unit is being configured to perform the following steps: f) in respect of the orientation of one or more sides of headlands, define an array of parallel working rows located within said work area”, paragraph [0227], “So that a vehicle can navigate the rows and the headlands, driven paths need to be generated for both the headlands and the working rows. The driven paths are plotted down the middle of the defined working rows and headlands. However an offset, IO=[IO.sub.x,IO.sub.y], can also be included between the vehicle centre and the implement centre in order for the implements centre to maintain a central position on the working row, see FIG. 14”, and paragraph [0228], “For each working row WR there are two, DR.sub.+ and DR.sub.−, one in same direction as the driving direction and one in the opposite direction as the driving direction. Each DR starts at SDR and ends at EDR.”); applying constraints configured to ensure that each of the plurality of passes is worked exactly once by the one or more agricultural vehicles (See at least paragraph [0060], [0067], “In one embodiment of the first aspect of the present invention said trajectory calculating unit is being configured to perform the following steps: g) in respect of one or more arrays of parallel working rows defined in step f), define an array of possible continuous driving paths by connecting separate entities, wherein said separate entities is being either headlands, or parts of a headland, and working rows, or parts of a working row; so as to define possible continuous driving paths, wherein each driving path is covering all headlands and all working rows” and paragraph [0268], “A cost matrix is built up of the minimal distance to connect two working row driven path, the field gates are also included in this cost matrix. The ends of the working row driven paths are not able to connect to themselves therefore the minimal distance between them is set to infinity, also two working row driven paths that cover the same working row are not able to be connected (this would not make sense are it would mean the working row was worked twice), therefore their connection in the cost matrix is also set to infinity.”); create an optimized route for controlling the one or more agricultural vehicles (See at least paragraph [0051], “These parameters are parameters which may be relevant in finding an optimized trajectory to follow when working a field”, paragraph [0052], “In one embodiment of the first aspect of the present invention said support system further comprising a display unit configured to be able to show on a map of said filed, the optimized trajectory to be followed by said work vehicle as calculated by said trajectory calculating unit”, and paragraph [0053], “This will enable the driver of the working vehicle or implement to easily follow the optimized trajectory, once this has been provided by the trajectory calculating unit.”).
Green does not explicitly disclose; however, Elisha, in the same field of endeavor, teaches transforming each first end and each second end of each of the plurality of passes into a plurality of nodes (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”); connecting the plurality of nodes to create one or more possible routes (See at least paragraph [0049], “In step 305, the routing module 201, for each cluster of the one or more clusters, separately computes a solution to a multiple vehicle routing problem for the set of rides in said each cluster. In one embodiment, the routing module 201 processes a subset of the enhanced ride data and/or the shared ride data corresponding to a subset of rides in a cluster to provide a ride sub-graph. By way of example, the ride sub-graph is a directed acyclic sub-graph (sub-DAG) that describes all possible (feasible) connections between rides in a VRP sub-problem for a cluster via parallel processes 415a-415k, k is the number of clusters. In other words, all rides in the subset belongs to one cluster, and all rides that belong to the cluster must appear in the same subset. In one embodiment, such ride sub-graph is constructed per cluster, by re-constructing the ride sub-graph from the respective ride data (using process 407). In another embodiment, such ride sub-graph is constructed per cluster, by extracting only the relevant nodes and edges in the ride graph generated in process 407 associated with the ride subset.”); computing a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”); computing a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”); the time and distance matrix does not have to be computed in any particular order (See at least paragraph [0037], “FIG. 3 is a flowchart of a process for providing large scale vehicle routing, according to one embodiment. In various embodiments, the routing platform 111 and/or any of the modules 201-207 of the routing platform 111 may perform one or more portions of the process 300 and may be implemented in, for instance, a chip set including a processor and a memory as shown in FIG. 9. As such, the routing platform 111 and/or the modules 201-207 can provide means for accomplishing various parts of the process 300, as well as means for accomplishing embodiments of other processes described herein in conjunction with other components of the system 100. Although the process 300 is illustrated and described as a sequence of steps, its contemplated that various embodiments of the process 300 may be performed in any order or combination and need not include all of the illustrated steps.”); and also configured to ensure that time window requirements are met (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”); formulating a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions (See at least paragraph [0026], “FIG. 1 is a diagram of a system capable of providing large scale vehicle routing, according to one embodiment. A vehicle routing problem (VRP), or more precisely multiple vehicle routing problem (mVRP), is a combinatorial optimization and integer programming problem to determine the optimal set of routes”, paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”, and paragraph [0050], “In one embodiment, the VRP solvers is designed for solving a mixed integer programing (MIP) problem, e.g., Gurobi Optimizers, OR-tools, etc., that can state the VRP as a mathematical model and automatically solve the VRP. MIP is a special case of linear programming (LP) where at least one of the variables can only take on integer values.”); determining that a feasible solution to the non-convex optimization problem exists (See at least paragraph [0049], “In step 305, the routing module 201, for each cluster of the one or more clusters, separately computes a solution to a multiple vehicle routing problem for the set of rides in said each cluster. In one embodiment, the routing module 201 processes a subset of the enhanced ride data and/or the shared ride data corresponding to a subset of rides in a cluster to provide a ride sub-graph. By way of example, the ride sub-graph is a directed acyclic sub-graph (sub-DAG) that describes all possible (feasible) connections between rides in a VRP sub-problem for a cluster via parallel processes 415a-415k, k is the number of clusters. In other words, all rides in the subset belongs to one cluster, and all rides that belong to the cluster must appear in the same subset. In one embodiment, such ride sub-graph is constructed per cluster, by re-constructing the ride sub-graph from the respective ride data (using process 407). In another embodiment, such ride sub-graph is constructed per cluster, by extracting only the relevant nodes and edges in the ride graph generated in process 407 associated with the ride subset” and paragraph [0050], “In one embodiment, the VRP solvers is designed for solving a mixed integer programing (MIP) problem, e.g., Gurobi Optimizers, OR-tools, etc., that can state the VRP as a mathematical model and automatically solve the VRP. MIP is a special case of linear programming (LP) where at least one of the variables can only take on integer values.”).
Green and Elisha do not explicitly disclose; however, Wang, in the same field of endeavor, teaches and solving the non-convex optimization problem using Grover's Algorithm (See at least paragraph [0038], “FIG. 1 shows an example flow chart of a method 100 for global optimization that may be performed by a quantum computer and/or a quantum computer emulator. At 110, the method may receive a search request that may include an input. At 120, the amount of rotations necessary to perform the search request with a Grover Search algorithm may be determined. Further, at 130, the method may determine that the amount of rotations is less than a predefined amount. After this determination, at 140, one or more quantum walks may be generated. Then, at 150, the rotations associated with the Grover search algorithm may be replaced with the one or more quantum walks. At 160, the global optimization algorithm may be generated based on the Grover Search algorithm and the one or more quantum walks. At 170, the global optimization algorithm may be executed by, for example, a quantum computer to identify the input.”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Green with the teachings of Elisha and Wang such that the agricultural vehicle trajectory support system of Green is further configured to transform each first end and each second end of each of the plurality of passes into a plurality of nodes; connect the plurality of nodes to create one or more possible routes; compute a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes; compute a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; the time and distance matrix does not have to be computed in any particular order and also configured to ensure that time window requirements are met; formulate a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions; and determine that a feasible solution to the non-convex optimization problem exists, as taught by Elisha (See paragraph [0024], [0037], [0039], [0049], [0050].), and solving the non-convex optimization problem using Grover's Algorithm, as taught by Wang (See paragraph [0038].), with a reasonable expectation of success. The motivation for doing so would be to improve the ability to solve large-scale routing and fleet optimization problems in finite time, as taught by Elisha (See paragraph [0001].), and to improve computational efficiency, as taught by Wang (See paragraph [0003].).
Regarding Claim 18, Green, Elisha, and Wang teach The method of claim 15 as set forth in the obviousness rejection above. Green teaches wherein applying constraints further comprises integrating fuel capacity limits of the vehicle (See at least paragraph [0086]-[0089], “In a second aspect the present invention relates to a method for determining a trajectory to be followed by an agricultural work vehicle, when working a field, said method comprising the steps: b) providing information relating to: one or more capacity parameters relating to said working vehicle; c) performing a calculation of an optimized trajectory to be followed by said work vehicle; wherein said optimized trajectory is being calculated on the basis of said coordinates provided in step a) and b)”, paragraph [0095], “In one embodiment of the second aspect of the present invention said one or more capacity parameters being selected from the group comprising: effective working width of the work vehicle or the working implement, load of work vehicle as a function of distance travelled, fuel consumption as a function of distance travelled, minimum turning radius of vehicle or implement or both”, and paragraph [0096], “These parameters are parameters which may be relevant in finding an optimized trajectory to follow when working a field.”).
Claim(s) 16 and 17 is/are rejected under 35 U.S.C. 103 as being unpatentable over Green (US 20190239416 A1) in view of Elisha (US 20210241625 A1), Wang (US 20200133947 A1), and Bunderson (US 20170202131 A1).
Regarding Claim 16, Green, Elisha, and Wang teach The method of claim 15 as set forth in the obviousness rejection above. Green, Elisha, and Wang do not explicitly disclose; however, Bunderson, in the same field of endeavor, teaches wherein connecting the plurality of nodes to create routes comprises connecting the plurality of nodes with Dubins paths (See at least paragraph [0037], “The three-segment non-continuous curvature 130 path may be a series of curves and/or straight segments (e.g., a second segment 138, a fourth segment 146, and a sixth segment 154) that are joined together at nodes (e.g., a second node 140 and a fourth node 148). As shown in FIG. 4, the second segment 138 begins at the starting point 132, which may correspond to the end point 90 of a row path 88. The starting point 132 may be defined by x.sub.i and y.sub.i (e.g., the initial position of the vehicle 12). At the starting point 132, the vehicle 12 has an initial heading, q.sub.i, and an initial curvature, κ.sub.i. The second segment 138 extends from the starting point 132 to the second node 140. The fourth segment 146 extends from the second node 140 to the fourth node 148. The sixth segment 154 extends from the fourth node 148 to an end point 160, which may correspond to the starting point 90 of a the subsequent row path 88. The three-segment non-continuous curvature path 130 may be a Dubins path. A Dubins path is defined as the shortest path that connects two points in two-dimensional plane with a constraint on the curvature of the path (e.g., minimum turning radius) and with prescribed initial and terminal tangents to the path. The Dubins path is sometimes used in robotics and control theory to plan paths for wheeled robots or vehicles. Typically, a Dubins path comprises a left or right turn arc (“R” or “L”), followed by another left or right turn arc (“R” or “L”) or a straight line (“S”), followed by another left or right turn arc (“R” or “L”).”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Green with the teachings of Elisha, Wang, and Bunderson such that the agricultural vehicle trajectory support system of Green is further configured to transform each first end and each second end of each of the plurality of passes into a plurality of nodes; connect the plurality of nodes to create one or more possible routes; compute a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes; compute a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; the time and distance matrix does not have to be computed in any particular order and also configured to ensure that time window requirements are met; formulate a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions; and determine that a feasible solution to the non-convex optimization problem exists, as taught by Elisha (See paragraph [0024], [0037], [0039], [0049], [0050].), solving the non-convex optimization problem using Grover's Algorithm, as taught by Wang (See paragraph [0038].), and wherein connecting the plurality of nodes to create routes comprises connecting the plurality of nodes with Dubins paths, as taught by Bunderson (See paragraph [0037].), with a reasonable expectation of success. The motivation for doing so would be to improve the ability to solve large-scale routing and fleet optimization problems in finite time, as taught by Elisha (See paragraph [0001].), to improve computational efficiency, as taught by Wang (See paragraph [0003].), and to reduce errors during end-of-row turns and improve the efficiency of agricultural operations, as taught by Bunderson (See paragraph [0002].).
Regarding Claim 17, Green, Elisha, and Wang teach The method of claim 15 as set forth in the obviousness rejection above. Green, Elisha, and Wang do not explicitly disclose; however, Bunderson, in the same field of endeavor, teaches wherein connecting the plurality of nodes to create routes comprises accommodating a turn radius, a speed, an implement, a time to raise the implement, and a time to lower the implement associated with the vehicle (See at least paragraph [0002], “Additionally, if the implement is not aligned with the subsequent swath at the time the implement is lowered or turned on, the implement may miss a portion of the subsequent swath, creating a skip, and/or overlap with another swath”, paragraph [0022], “For example, when the agricultural vehicle reaches the end of a first swath, the operator raises, turns off, or otherwise disengages the agricultural implement; the operator then manually controls the speed and steering of the agricultural vehicle to guide the vehicle through the end-of-row turn connecting the end of the first swath to the beginning of a second swath. The operator then lowers, turns on, or otherwise engages the agricultural implement and an automatic or semi-automatic control system guides the agricultural vehicle along the second swath”, paragraph [0023], “Present embodiments of the vehicle control system may generate a continuous curvature end of row turn path for the agricultural vehicle. The vehicle control system may take into account a number of factors (e.g., minimum turning radius, maximum turning rate, starting point, initial heading, speed, fuel consumption, etc.) in determining the end of row turn path. The end-of-row-turn path may include a number of clothoid segments arranged end-to-end. In some embodiments, the vehicle control system may implement the end-of-row turn path (e.g., guide the vehicle along the end-of-row turn path)”, and paragraph [0037], “The three-segment non-continuous curvature 130 path may be a series of curves and/or straight segments (e.g., a second segment 138, a fourth segment 146, and a sixth segment 154) that are joined together at nodes (e.g., a second node 140 and a fourth node 148). As shown in FIG. 4, the second segment 138 begins at the starting point 132, which may correspond to the end point 90 of a row path 88. The starting point 132 may be defined by x.sub.i and y.sub.i (e.g., the initial position of the vehicle 12). At the starting point 132, the vehicle 12 has an initial heading, q.sub.i, and an initial curvature, κ.sub.i. The second segment 138 extends from the starting point 132 to the second node 140. The fourth segment 146 extends from the second node 140 to the fourth node 148.”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Green with the teachings of Elisha, Wang, and Bunderson such that the agricultural vehicle trajectory support system of Green is further configured to transform each first end and each second end of each of the plurality of passes into a plurality of nodes; connect the plurality of nodes to create one or more possible routes; compute a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes; compute a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; the time and distance matrix does not have to be computed in any particular order and also configured to ensure that time window requirements are met; formulate a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions; and determine that a feasible solution to the non-convex optimization problem exists, as taught by Elisha (See paragraph [0024], [0037], [0039], [0049], [0050].), solving the non-convex optimization problem using Grover's Algorithm, as taught by Wang (See paragraph [0038].), and wherein connecting the plurality of nodes to create routes comprises accommodating a turn radius, a speed, an implement, a time to raise the implement, and a time to lower the implement associated with the vehicle, as taught by Bunderson (See paragraph [0002], [0022], [0023], [0037].), with a reasonable expectation of success. The motivation for doing so would be to improve the ability to solve large-scale routing and fleet optimization problems in finite time, as taught by Elisha (See paragraph [0001].), to improve computational efficiency, as taught by Wang (See paragraph [0003].), and to reduce errors during end-of-row turns and improve the efficiency of agricultural operations, as taught by Bunderson (See paragraph [0002].).
Claim(s) 19 is/are rejected under 35 U.S.C. 103 as being unpatentable over Green (US 20190239416 A1) in view of Elisha (US 20210241625 A1), Wang (US 20200133947 A1), and Israel (US 20150205759 A1).
Regarding Claim 19, Green, Elisha, and Wang teach The method of claim 15 as set forth in the obviousness rejection above. Green teaches configured to ensure that each of the plurality of passes is worked exactly once by the one or more agricultural vehicles (See at least paragraph [0060], [0067], “In one embodiment of the first aspect of the present invention said trajectory calculating unit is being configured to perform the following steps: g) in respect of one or more arrays of parallel working rows defined in step f), define an array of possible continuous driving paths by connecting separate entities, wherein said separate entities is being either headlands, or parts of a headland, and working rows, or parts of a working row; so as to define possible continuous driving paths, wherein each driving path is covering all headlands and all working rows” and paragraph [0268], “A cost matrix is built up of the minimal distance to connect two working row driven path, the field gates are also included in this cost matrix. The ends of the working row driven paths are not able to connect to themselves therefore the minimal distance between them is set to infinity, also two working row driven paths that cover the same working row are not able to be connected (this would not make sense are it would mean the working row was worked twice), therefore their connection in the cost matrix is also set to infinity.”).
Green does not explicitly disclose; however, Elisha, in the same field of endeavor, teaches and also configured to ensure that time window requirements are met (See at least paragraph [0039], “In one embodiment, the VRP is defined as follows: G(V,A) is a graph with a vertex set V (rides) and an arc set A. Vertex v.sub.0 represents an initial depot, all other vertices/nodes, called “intermediate nodes”, correspond to customers. A is associated with some cost matrix (c.sub.ij) and a travel time matrix (t.sub.ij). In the classical definition, each customer has a non-negative demand q.sub.i and a service time t.sub.i. a fleet of N vehicles of capacity Q is based at the depot. The number of vehicles is either known in advance or treated as a decision variable. The VRP consists of finding tours for all N vehicles, which all start at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The cost metric can be defined in terms of distance, time, number of drivers, etc. A common variant is where a time window [a.sub.i, b.sub.i] is imposed on the visit of each customer. The nodes to be visited (rides to complete) are structed as a graph, where the edges (arches) between nodes include an estimated driving time from drop-off ride.sub.i to pick-up ride.sub.j, a distance between rides, a time lag between rides, etc.”).
Green, Elisha, and Wang do not explicitly disclose; however, Israel, in the same field of endeavor, teaches further comprising determining that a feasible solution to the non-convex optimization problem does not exist (See at least paragraph [0029], “determining, by the at least one processor, one or more members of a feasible set for the constraint; determining, by the at least one processor, one or more members of an infeasible set for the constraint… identifying a new penalty function constraint, not in the initial subset of penalty function constraints, that is violated by an initial solution to the first instance of the problem.”), adjusting the constraints; create adjusted constraints, and reformulating the non-convex optimization problem with the adjusted constraints before determining that a feasible solution to the non-convex optimization problem exists (See at least paragraph [0029], “adding the identified new penalty function constraint to the subset of penalty function constraints to produce a revised subset of penalty function constraints; and solving a second instance of the linear program based on the revised subset of penalty function constraints…The method may further include: generating one or more ancillary variables for each of the respective Ising model penalty functions: re-formulating, by the at least one processor, the received problem as a feasibility problem…re-formulating the feasibility problem by generating one or more inequalities, one or more continuous message variables and one or more binary variables.”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Green with the teachings of Elisha, Wang, and Israel such that the agricultural vehicle trajectory support system of Green is further configured to transform each first end and each second end of each of the plurality of passes into a plurality of nodes; connect the plurality of nodes to create one or more possible routes; compute a distance matrix by calculating distances between every possible pair of nodes for each of the one or more possible routes; compute a time matrix by calculating times required to travel between every possible pair of nodes for each of the one or more possible routes; the time and distance matrix does not have to be computed in any particular order and also configured to ensure that time window requirements are met; formulate a non-convex optimization problem incorporating the distance matrix, the time matrix, the constraints, and the time window requirements, the non-convex optimization problem having one or more solutions; and determine that a feasible solution to the non-convex optimization problem exists, as taught by Elisha (See paragraph [0024], [0037], [0039], [0049], [0050].), solving the non-convex optimization problem using Grover's Algorithm, as taught by Wang (See paragraph [0038].), and further comprising determining that a feasible solution to the non-convex optimization problem does not exist; and reformulating the non-convex optimization problem with the adjusted constraints before determining that a feasible solution to the non-convex optimization problem exists, as taught by Israel (See paragraph [0029].), with a reasonable expectation of success. The motivation for doing so would be to improve the ability to solve large-scale routing and fleet optimization problems in finite time, as taught by Elisha (See paragraph [0001].), to improve computational efficiency, as taught by Wang (See paragraph [0003].), and to increase the likelihood that quantum annealing hardware will find a solution and to provide better protection against noise and limitations in precision, as taught by Israel (See paragraph [0018].).
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JEWEL ASHLEY KUNTZ whose telephone number is (571)270-5542. The examiner can normally be reached M-F 8:30am-5:30pm.
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, Anne Antonucci can be reached at (313) 446-6519. 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.
/JEWEL A KUNTZ/Examiner, Art Unit 3666
/ANNE MARIE ANTONUCCI/Supervisory Patent Examiner, Art Unit 3666
