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 statements (IDS) submitted on 31 July 2024 is being considered by the examiner.
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-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
[Step 1] Representative claim 1 teaches a system for generating an optimize vehicle route. This falls under “machine”, which is a statutory invention category.
[Step 2A: Prong 1] This is a mathematical relationship. But for the vehicle, the memory, and the processor required to carry out the steps which are not explicitly recited in the claims, claim 1 is merely drawn to a series of steps:
obtain an origin-destination (OD) matrix of a predefined time period indicating a plurality of traffic volume values for a plurality of OD pairs in a geographical area
identify one or more OD pairs of the plurality of OD pairs having traffic volume values greater than a traffic threshold
generate a network graph for the predefined time period based on the identified one or more OD pairs, the network graph comprising a plurality of nodes and a plurality of edges, wherein the plurality of nodes is associated with a plurality of locations within the geographical area, and wherein each of the plurality of edges is associated with a weight value indicative a trip volume
determine one or more critical edges of the plurality of edges for the predefined time period based on the weight value of each of the plurality of edges
store edge data associated with the one or more critical edges for the predefined time period in a map database
The steps are, essentially, a process for generating a vehicle trajectory that avoids known traffic section. This is an abstract idea or ideas characterized under mathematical relationship.
[Step 2A: Prong 2] This judicial exception is not integrated into a practical application. Other than the above-cited abstract idea, claim 1 doesn’t explicitly claim a specific type of vehicle, memory, and the processor that would be necessary to carry out the steps. There are no special hardware features of the process recited in the claims as presented. The hardware of a vehicle, a memory, and a processor is recited in the specification at a high-level of generality, (see [Specification Para. 36, 61]) such that it amounts to no more than mere instructions of the judicial exception linked to a particular technological environment. Accordingly, these additional elements do not integrate the abstract idea into a practical application because they not impose any meaningful limits on practicing the abstract idea. These limitations essentially linking the use of a judicial exception to a particular technological environment or field of use (MPEP2106.05(h), MPEP2106.04(d)). This claim is directed to an abstract idea.
[Step 2B] This claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a vehicle, a memory, and a processor to no more than mere instructions of the judicial exception linked to a particular technological environment. There is no inventive concept in the vehicle, the memory, and the processor. Mere linking the judicial exception to a particular technological environment cannot provide an integrated inventive concept. This claim is not patent eligible.
The dependent claims 2-10 have been rejected on the same grounds and recite substantially similar abstract ideas to the cited independent claim 1.
2. The system of claim 1, wherein each of the plurality of edges indicates a travel path between a corresponding pair of nodes from the plurality of nodes, and wherein the one or more critical edges correspond to one or more travel paths having the weight value greater than a weight threshold during the predefined time period.
3. The system of claim 2, wherein the one or more processors are further configured to: determine an average travel time for each of the one or more travel paths associated with the plurality of edges for the predefined time period; and store the average travel time in association with the corresponding weight value for each of the plurality of edges.
4. The system of claim 1, wherein the one or more processors are further configured to: determine a plurality of subset matrices for a plurality of time instants within the predefined time period based on the OD matrix; generate a plurality of network graphs for each of the plurality of time instants based on the corresponding plurality of subset matrices, wherein each of the plurality of network graphs comprise the plurality of nodes and one or more edges, and wherein each of the one or more edges have an associated weight indicative of a time instant trip volume; and generate the network graph for the predefined time period based on an aggregation of the plurality of network graphs for each of the plurality of time instants.
5. The system of claim 1, wherein the one or more processors are further configured to: generate a tree graph for the predefined time period based on the plurality of nodes and an inverse of the weight value of each of the plurality of edges; and determine the one or more critical edges of the plurality of edges for the predefined time period based on the tree graph.
6. The system of claim 5, wherein the one or more processors are further configured to: generate a plurality of historical network graphs, wherein each of the plurality of historical network graphs correspond to historical periods of time associated with the predefined time period; generate a plurality of historical tree graphs corresponding to each of the plurality of historical network graphs; compare the tree graph and the plurality of historical tree graphs to determine a stability score; and generate a trip flow pattern graph for the geographical area based on the tree graph and the plurality of historical tree graphs on ascertaining the stability score to be greater than a stability threshold.
7. The system of claim 5, wherein the tree graph is a minimum spanning tree graph.
8. The system of claim 1, wherein the one or more processors are further configured to: generate navigation instructions for a vehicle associated with the geographical area based on the one or more critical edges for the predefined time period.
9. The system of claim 8, wherein one or more processors are further configured to: receive a source location and a destination location associated with navigation of the vehicle; identify a pair of nodes from the plurality of nodes of the network graph corresponding to the source location and the destination location; determine whether at least one edge between the pair of nodes includes one of the one or more critical edges; and generate the navigation instructions based on the determination, wherein the navigation instructions include an alternative edge for one of the one or more critical edges in the at least one edge.
10. The system of claim 1, wherein the network graph is a maximum trip flow graph (MTFG).
The 101 analysis for claim 1 would apply similarly to the dependent claims above. Therefore, dependent claims 2-10 are also rejected under 35 U.S.C. 101.
[Step 1] Representative claim 11 teaches a method for generating an optimize vehicle route. This falls under “process”, which is a statutory invention category.
[Step 2A: Prong 1] This is a mathematical relationship. But for the vehicle, the memory, and the processor required to carry out the steps which are not explicitly recited in the claims, claim 11 is merely drawn to a series of steps:
obtain an origin-destination (OD) matrix of a predefined time period indicating a plurality of traffic volume values for a plurality of OD pairs in a geographical area
obtaining an origin-destination (OD) matrix of a predefined time period indicating a plurality of traffic volume values for a plurality of OD pairs in a geographical area
identifying one or more OD pairs of the plurality of OD pairs having traffic volume values greater than a traffic threshold
generating a network graph for the predefined time period based on the identified one or more OD pairs, the network graph comprising a plurality of nodes and a plurality of edges, wherein the plurality of nodes is associated with a plurality of locations within the geographical area, and wherein each of the plurality of edges is associated with a weight value indicative a trip volume
determining one or more critical edges of the plurality of edges for the predefined time period based on the weight value of each of the plurality of edges
storing edge data associated with the one or more critical edges for the predefined time period in a map database
The steps are, essentially, a method for generating a vehicle trajectory that avoids known traffic section. This is an abstract idea or ideas characterized under mathematical relationship.
[Step 2A: Prong 2] This judicial exception is not integrated into a practical application. Other than the above-cited abstract idea, claim 11 doesn’t explicitly claim a specific type of vehicle, memory, and the processor that would be necessary to carry out the steps. There are no special hardware features of the process recited in the claims as presented. The hardware of a vehicle, a memory, and a processor is recited in the specification at a high-level of generality, (see [Specification Para. 36, 61]) such that it amounts to no more than mere instructions of the judicial exception linked to a particular technological environment. Accordingly, these additional elements do not integrate the abstract idea into a practical application because they not impose any meaningful limits on practicing the abstract idea. These limitations essentially linking the use of a judicial exception to a particular technological environment or field of use (MPEP2106.05(h), MPEP2106.04(d)). This claim is directed to an abstract idea.
[Step 2B] This claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a vehicle, a memory, and a processor to no more than mere instructions of the judicial exception linked to a particular technological environment. There is no inventive concept in the vehicle, the memory, and the processor. Mere linking the judicial exception to a particular technological environment cannot provide an integrated inventive concept. This claim is not patent eligible.
The dependent claims 12-17 have been rejected on the same grounds and recite substantially similar abstract ideas to the cited independent claim 11.
12. The method of claim 11, wherein each of the plurality of edges indicates a travel path between a corresponding pair of nodes from the plurality of nodes, and wherein the one or more critical edges correspond to one or more travel paths having the weight value greater than a weight threshold during the predefined time period.
13. The method of claim 12, further comprising: determining an average travel time for each of the one or more travel paths associated with the plurality of edges for the predefined time period; and storing the average travel time in association with the corresponding weight value for each of the plurality of edges.
14. The method of claim 11, further comprising: determining a plurality of subset matrices for a plurality of time instants within the predefined time period based on the OD matrix; generating a plurality of network graphs for each of the plurality of time instants based on the corresponding plurality of subset matrices, wherein each of the plurality of network graphs comprise the plurality of nodes and one or more edges, and wherein each of the one or more edges have an associated weight indicative of a time instant trip volume; and generating the network graph for the predefined time period based on an aggregation of the plurality of network graphs for each of the plurality of time instants.
15. The method of claim 11, further comprising: generating a tree graph for the predefined time period based on the plurality of nodes and an inverse of the weight value of each of the plurality of edges; and determining the one or more critical edges of the plurality of edges for the predefined time period based on the tree graph.
16. The method of claim 11, further comprising: generating a plurality of historical network graphs, wherein each of the plurality of historical network graphs correspond to historical periods of time associated with the predefined time period; generating a plurality of historical tree graphs corresponding to each of the plurality of historical network graphs; comparing the tree graph and the plurality of historical tree graphs to determine a stability score; and generating a trip flow pattern graph for the geographical area based on the tree graph and the plurality of historical tree graphs on ascertaining the stability score to be greater than a stability threshold.
17. The method of claim 11, further comprising: receiving a source location and a destination location associated with navigation of the vehicle; identifying a pair of nodes from the plurality of nodes of the network graph corresponding to the source location and the destination location; determining whether at least one edge between the pair of nodes includes one of the one or more critical edges; and generating navigation instructions for a vehicle associated with the geographical area based on the determination, wherein the navigation instructions include an alternative edge for one of the one or more critical edges in the at least one edge.
The 101 analysis for claim 11 would apply similarly to the dependent claims above. Therefore, dependent claims 12-17 are also rejected under 35 U.S.C. 101.
[Step 1] Representative claim 18 teaches a system for generating an optimize vehicle route. This falls under “machine”, which is a statutory invention category.
[Step 2A: Prong 1] This is a mathematical relationship. But for the vehicle, the memory, and the processor required to carry out the steps which are not explicitly recited in the claims, claim 18 is merely drawn to a series of steps:
obtain an origin-destination (OD) matrix of a predefined time period indicating a plurality of traffic volume values for a plurality of OD pairs in a geographical area
identify one or more OD pairs of the plurality of OD pairs having traffic volume values greater than a traffic threshold
generate a network graph for the predefined time period based on the identified one or more OD pairs, the network graph comprising a plurality of nodes and a plurality of edges, wherein the plurality of nodes is associated with a plurality of locations within the geographical area, and wherein each of the plurality of edges is associated with a weight value indicative a trip volume
determine one or more critical edges of the plurality of edges for the predefined time period based on the weight value of each of the plurality of edges
store edge data associated with the one or more critical edges for the predefined time period in a map database
The steps are, essentially, a process for generating a vehicle trajectory that avoids known traffic section. This is an abstract idea or ideas characterized under mathematical relationship.
[Step 2A: Prong 2] This judicial exception is not integrated into a practical application. Other than the above-cited abstract idea, claim 18 doesn’t explicitly claim a specific type of vehicle, memory, and the processor that would be necessary to carry out the steps. There are no special hardware features of the process recited in the claims as presented. The hardware of a vehicle, a memory, and a processor is recited in the specification at a high-level of generality, (see [Specification Para. 36, 61]) such that it amounts to no more than mere instructions of the judicial exception linked to a particular technological environment. Accordingly, these additional elements do not integrate the abstract idea into a practical application because they not impose any meaningful limits on practicing the abstract idea. These limitations essentially linking the use of a judicial exception to a particular technological environment or field of use (MPEP2106.05(h), MPEP2106.04(d)). This claim is directed to an abstract idea.
[Step 2B] This claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a vehicle, a memory, and a processor to no more than mere instructions of the judicial exception linked to a particular technological environment. There is no inventive concept in the vehicle, the memory, and the processor. Mere linking the judicial exception to a particular technological environment cannot provide an integrated inventive concept. This claim is not patent eligible.
The dependent claims 19-20 have been rejected on the same grounds and recite substantially similar abstract ideas to the cited independent claim 18.
19. The computer programmable product of claim 18, wherein the operations further comprise: generating a tree graph for the predefined time period based on the plurality of nodes and an inverse of the weight value of each of the plurality of edges; and determining the one or more critical edges of the plurality of edges for the predefined time period based on the tree graph.
20. The computer programmable product of claim 18, wherein the operations further comprise: generating a plurality of historical network graphs, wherein each of the plurality of historical network graphs correspond to historical periods of time associated with the predefined time period; generating a plurality of historical tree graphs corresponding to each of the plurality of historical network graphs; comparing the tree graph and the plurality of historical tree graphs to determine a stability score; and generating a trip flow pattern graph for the geographical area based on the tree graph and the plurality of historical tree graphs on ascertaining the stability score to be greater than a stability threshold.
The 101 analysis for claim 18 would apply similarly to the dependent claims above. Therefore, dependent claims 19-20 are also rejected under 35 U.S.C. 101.
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 text of those sections of Title 35, U.S. Code not included in this action can be found in a prior Office action.
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.
Claims 1-4, 8-14, 16-18, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Yang et al. (US Publication 2023/0115110 A1) in view of Huang et al. (US Patent 10,963,705 B2).
Regarding claim 1, Yang teaches a system comprising: a memory configured to store computer executable instructions; and one or more processors configured to execute the instructions to: (Yang: Para. 9; when the computer-readable instruction, when being executed by the one or more processors, causing the one or more processors to perform the operations of the foregoing traffic simulation method) obtain an origin-destination (OD) matrix of a predefined time period (Yang: Para. 70; the historical vehicle trajectory data and historical traffic flow data in the historical time period corresponding to the current time period are obtained) indicating a plurality of traffic volume values for a plurality of OD pairs in a geographical area (Yang: Para. 69; obtain a target traffic flow corresponding to the OD pair in the target trip matrix); identify one or more OD pairs of the plurality of OD pairs having traffic volume values greater than a traffic threshold (Yang: Para. 131; a traffic flow corresponding to the same segment in traffic reproduction is greater than that in system optimization); ……… , and wherein each of the plurality of edges is associated with a weight value indicative a trip volume (Yang: Para. 69; performing, taking an origin-destination (OD) pair in the historical trip matrix as an OD pair in the target trip matrix, weighted summation on estimated traffic flows corresponding to the same OD pair); determine one or more critical edges of the plurality of edges for the predefined time period based on the weight value of each of the plurality of edges (Yang: Para. 131; at least one better candidate navigation path that avoids a segment where congestion may occur, and transmits the candidate navigation path to the terminal); and store edge data associated with the one or more critical edges for the predefined time period in a map database (Yang: Para. 61; obtain traffic section flow data, such as checkpoint data and geomagnetic coil data, and mobile signaling data of each segment in the historical time period from a second terminal and a second server as historical traffic flow data).
Yang doesn’t explicitly teach generate a network graph for the predefined time period based on the identified one or more OD pairs, the network graph comprising a plurality of nodes and a plurality of edges, wherein the plurality of nodes is associated with a plurality of locations within the geographical area.
However Huang, in the same field of endeavor, teaches generate a network graph for the predefined time period based on the identified one or more OD pairs, the network graph comprising a plurality of nodes and a plurality of edges, wherein the plurality of nodes is associated with a plurality of locations within the geographical area (Huang: Col. 13 Lines 18-35; random forest regression model may be used to predict the ratio of the maximum volume between OD pairs; averaged distance between the two nodes of OD pair i and the two nodes of OD pair j, and loc.sub.i is the latitude and longitude of both nodes of pair i).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G) with a reasonable expectation of success because a random forest regression model using historical and current data can predict the maximum flow between OD pairs (Huang: Col. 13 Lines 18-35).
Regarding claim 2, Yang teaches the system of claim 1, wherein each of the plurality of edges indicates a travel path between a corresponding pair of nodes from the plurality of nodes (Yang: Para. 72; candidate travel paths corresponding to the same intermediate origin and intermediate destination to obtain multiple target trip combinations), and wherein the one or more critical edges correspond to one or more travel paths having the weight value greater than a weight threshold during the predefined time period (Yang: Para. 130-131; auxiliary navigation data may include information such as a traffic index, average travel speed, traffic flow, and simulation requirement of each segment; traffic index may be calculated based on the average travel speed and traffic flow of the segment; if a traffic flow corresponding to the same segment in traffic reproduction is greater than that in system optimization, the segment is avoided during navigation path planning, so that the traffic flow of the segment is reduced to a certain extent to approach system optimization).
Regarding claim 3, Yang teaches the system of claim 2, wherein the one or more processors are further configured to: determine an average travel time for each of the one or more travel paths associated with the plurality of edges for the predefined time period; and store the average travel time in association with the corresponding weight value for each of the plurality of edges (Yang: Para. 117; obtain average travel time corresponding to each candidate travel path and further calculate, based on the average travel time corresponding to each candidate travel path corresponding to the same target trip combination, target travel time corresponding to each target vehicle corresponding to the target trip combination).
Regarding claim 4, Yang teaches the system of claim 1, wherein the one or more processors are further configured to: determine a plurality of subset matrices for a plurality of time instants within the predefined time period based on the OD matrix (Yang: Para. 69; merging the multiple historical trip matrices may specifically be performing, taking an origin-destination (OD) pair in the historical trip matrix as an OD pair in the target trip matrix, weighted summation on estimated traffic flows corresponding to the same OD pair (i.e., the same origin and destination) in the respective historical trip matrices to obtain a target traffic flow corresponding to the OD pair in the target trip matrix); …… , and wherein each of the one or more edges have an associated weight indicative of a time instant trip volume (Yang: Para. 69; performing, taking an origin-destination (OD) pair in the historical trip matrix as an OD pair in the target trip matrix, weighted summation on estimated traffic flows corresponding to the same OD pair).
Yang doesn’t explicitly teach generate a plurality of network graphs for each of the plurality of time instants based on the corresponding plurality of subset matrices, wherein each of the plurality of network graphs comprise the plurality of nodes and one or more edges ……….. generate the network graph for the predefined time period based on an aggregation of the plurality of network graphs for each of the plurality of time instants.
However Huang, in the same field of endeavor, teaches generate a plurality of network graphs for each of the plurality of time instants based on the corresponding plurality of subset matrices, wherein each of the plurality of network graphs comprise the plurality of nodes and one or more edges (Huang: Col. 13 Lines 28-35, Fig. 3G; a multitude of regression trees for training and outputting the mean prediction of the individual trees) ……….. generate the network graph for the predefined time period based on an aggregation of the plurality of network graphs for each of the plurality of time instants (Huang: Col. 4 Lines 45-56; point-to-point flow data refer to information of traffic (e.g., the number of vehicles) flowing from one point to another within a certain period of time; origin-destination (O-D or OD) traffic, that is, traffic passing through an origin point at an earlier time and through a destination point at a later time).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G) with a reasonable expectation of success because a random forest regression model using historical and current data can predict the maximum flow between OD pairs (Huang: Col. 13 Lines 18-35).
Regarding claim 8, Yang teaches the system of claim 1, wherein the one or more processors are further configured to: generate navigation instructions for a vehicle associated with the geographical area based on the one or more critical edges for the predefined time period (Yang: Para. 131; navigation request containing a navigation origin and a navigation destination; performs navigation path planning for the terminal based on auxiliary navigation data to plan at least one better candidate navigation path that avoids a segment where congestion may occur).
Regarding claim 9, Yang teaches the system of claim 8, wherein one or more processors are further configured to: receive a source location and a destination location associated with navigation of the vehicle (Yang: Para. 131; navigation request containing a navigation origin and a navigation destination); ………. ; determine whether at least one edge between the pair of nodes includes one of the one or more critical edges (Yang: Para. 131; performs navigation path planning for the terminal based on auxiliary navigation data to plan at least one better candidate navigation path that avoids a segment where congestion may occur, and transmits the candidate navigation path to the terminal); and generate the navigation instructions based on the determination, wherein the navigation instructions include an alternative edge for one of the one or more critical edges in the at least one edge (Yang: Para. 131; navigation request containing a navigation origin and a navigation destination; performs navigation path planning for the terminal based on auxiliary navigation data to plan at least one better candidate navigation path that avoids a segment where congestion may occur).
Yang doesn’t explicitly teach identify a pair of nodes from the plurality of nodes of the network graph corresponding to the source location and the destination location.
However Huang, in the same field of endeavor, teaches identify a pair of nodes from the plurality of nodes of the network graph corresponding to the source location and the destination location (Huang: Col. 8 Lines 49-57; anonymous vehicle trajectory data may be collected through various ways, such as a vehicle platform Application; smart phone location can track the vehicle location, and the time-location series can be used as the trajectory data).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G) with a reasonable expectation of success because a random forest regression model using historical and current data can predict the maximum flow between OD pairs (Huang: Col. 13 Lines 18-35).
Regarding claim 10, Yang doesn’t explicitly teach wherein the network graph is a maximum trip flow graph (MTFG).
However Huang, in the same field of endeavor, teaches wherein the network graph is a maximum trip flow graph (MTFG) (Huang: Col. 13 Lines 18-20; random forest regression model may be used to predict the ratio of the maximum volume between OD pairs).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G) with a reasonable expectation of success because a random forest regression model using historical and current data can predict the maximum flow between OD pairs (Huang: Col. 13 Lines 18-35).
Regarding claim 11, Yang teaches a method comprising: obtaining an origin-destination (OD) matrix of a predefined time period (Yang: Para. 70; the historical vehicle trajectory data and historical traffic flow data in the historical time period corresponding to the current time period are obtained) indicating a plurality of traffic volume values for a plurality of OD pairs in a geographical area (Yang: Para. 69; obtain a target traffic flow corresponding to the OD pair in the target trip matrix); identifying one or more OD pairs of the plurality of OD pairs having traffic volume values greater than a traffic threshold (Yang: Para. 131; a traffic flow corresponding to the same segment in traffic reproduction is greater than that in system optimization); ……….. , and wherein each of the plurality of edges is associated with a weight value indicative a trip volume (Yang: Para. 69; performing, taking an origin-destination (OD) pair in the historical trip matrix as an OD pair in the target trip matrix, weighted summation on estimated traffic flows corresponding to the same OD pair); determining one or more critical edges of the plurality of edges for the predefined time period based on the weight value of each of the plurality of edges (Yang: Para. 131; at least one better candidate navigation path that avoids a segment where congestion may occur, and transmits the candidate navigation path to the terminal); and storing edge data associated with the one or more critical edges for the predefined time period in a map database (Yang: Para. 61; obtain traffic section flow data, such as checkpoint data and geomagnetic coil data, and mobile signaling data of each segment in the historical time period from a second terminal and a second server as historical traffic flow data).
Yang doesn’t explicitly teach generating a network graph for the predefined time period based on the identified one or more OD pairs, the network graph comprising a plurality of nodes and a plurality of edges, wherein the plurality of nodes is associated with a plurality of locations within the geographical area.
However Huang, in the same field of endeavor, teaches generating a network graph for the predefined time period based on the identified one or more OD pairs, the network graph comprising a plurality of nodes and a plurality of edges, wherein the plurality of nodes is associated with a plurality of locations within the geographical area (Huang: Col. 13 Lines 18-35; random forest regression model may be used to predict the ratio of the maximum volume between OD pairs; averaged distance between the two nodes of OD pair i and the two nodes of OD pair j, and loc.sub.i is the latitude and longitude of both nodes of pair i).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G) with a reasonable expectation of success because a random forest regression model using historical and current data can predict the maximum flow between OD pairs (Huang: Col. 13 Lines 18-35).
Regarding claim 12, Yang teaches the method of claim 11, wherein each of the plurality of edges indicates a travel path between a corresponding pair of nodes from the plurality of nodes (Yang: Para. 72; candidate travel paths corresponding to the same intermediate origin and intermediate destination to obtain multiple target trip combinations), and wherein the one or more critical edges correspond to one or more travel paths having the weight value greater than a weight threshold during the predefined time period (Yang: Para. 130-131; auxiliary navigation data may include information such as a traffic index, average travel speed, traffic flow, and simulation requirement of each segment; traffic index may be calculated based on the average travel speed and traffic flow of the segment; if a traffic flow corresponding to the same segment in traffic reproduction is greater than that in system optimization, the segment is avoided during navigation path planning, so that the traffic flow of the segment is reduced to a certain extent to approach system optimization).
Regarding claim 13, Yang teaches the method of claim 12, further comprising: determining an average travel time for each of the one or more travel paths associated with the plurality of edges for the predefined time period; and storing the average travel time in association with the corresponding weight value for each of the plurality of edges (Yang: Para. 117; obtain average travel time corresponding to each candidate travel path and further calculate, based on the average travel time corresponding to each candidate travel path corresponding to the same target trip combination, target travel time corresponding to each target vehicle corresponding to the target trip combination).
Regarding claim 14, Yang teaches the method of claim 11, further comprising: determining a plurality of subset matrices for a plurality of time instants within the predefined time period based on the OD matrix (Yang: Para. 69; merging the multiple historical trip matrices may specifically be performing, taking an origin-destination (OD) pair in the historical trip matrix as an OD pair in the target trip matrix, weighted summation on estimated traffic flows corresponding to the same OD pair (i.e., the same origin and destination) in the respective historical trip matrices to obtain a target traffic flow corresponding to the OD pair in the target trip matrix); ……… , and wherein each of the one or more edges have an associated weight indicative of a time instant trip volume (Yang: Para. 69; performing, taking an origin-destination (OD) pair in the historical trip matrix as an OD pair in the target trip matrix, weighted summation on estimated traffic flows corresponding to the same OD pair).
Yang doesn’t explicitly teach generating a plurality of network graphs for each of the plurality of time instants based on the corresponding plurality of subset matrices, wherein each of the plurality of network graphs comprise the plurality of nodes and one or more edges ………. generating the network graph for the predefined time period based on an aggregation of the plurality of network graphs for each of the plurality of time instants.
However Huang, in the same field of endeavor, teaches generating a plurality of network graphs for each of the plurality of time instants based on the corresponding plurality of subset matrices, wherein each of the plurality of network graphs comprise the plurality of nodes and one or more edges (Huang: Col. 13 Lines 28-35, Fig. 3G; a multitude of regression trees for training and outputting the mean prediction of the individual trees) ………. generating the network graph for the predefined time period based on an aggregation of the plurality of network graphs for each of the plurality of time instants (Huang: Col. 4 Lines 45-56; point-to-point flow data refer to information of traffic (e.g., the number of vehicles) flowing from one point to another within a certain period of time; origin-destination (O-D or OD) traffic, that is, traffic passing through an origin point at an earlier time and through a destination point at a later time).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G) with a reasonable expectation of success because a random forest regression model using historical and current data can predict the maximum flow between OD pairs (Huang: Col. 13 Lines 18-35).
Regarding claim 16, Yang doesn’t explicitly teach generating a plurality of historical network graphs, wherein each of the plurality of historical network graphs correspond to historical periods of time associated with the predefined time period; generating a plurality of historical tree graphs corresponding to each of the plurality of historical network graphs; comparing the tree graph and the plurality of historical tree graphs to determine a stability score; and generating a trip flow pattern graph for the geographical area based on the tree graph and the plurality of historical tree graphs on ascertaining the stability score to be greater than a stability threshold.
However Huang, in the same field of endeavor, teaches generating a plurality of historical network graphs, wherein each of the plurality of historical network graphs correspond to historical periods of time associated with the predefined time period (Huang: Col. 8 Lines 17-20; train the algorithm by semi-supervised learning based on known historical data (trajectory data and traffic volume data) of a plurality of point pairs); generating a plurality of historical tree graphs corresponding to each of the plurality of historical network graphs (Huang: Col. 8 Lines 17-20; historical data (trajectory data and traffic volume data) of a plurality of point pairs); comparing the tree graph and the plurality of historical tree graphs to determine a stability score (Huang: Col. 9 Lines 50-57, 62-67; determines the type of regression relationship between historical data and future data; penetration rate over all OD pairs obtain a median mean absolute percentage error (MAPE) of 20.3% in main hour); and generating a trip flow pattern graph for the geographical area based on the tree graph and the plurality of historical tree graphs on ascertaining the stability score to be greater than a stability threshold (Huang: Col. 1 Lines 63-67, Col. 8 Lines 17-20; determining the predicted future traffic volume to exceed a threshold; train the algorithm by semi-supervised learning based on known historical data (trajectory data and traffic volume data) of a plurality of point pairs).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G) with a reasonable expectation of success because a random forest regression model using historical and current data can predict the maximum flow between OD pairs (Huang: Col. 13 Lines 18-35).
Regarding claim 17, Yang teaches the method of claim 11, further comprising: receiving a source location and a destination location associated with navigation of the vehicle (Yang: Para. 131; navigation request containing a navigation origin and a navigation destination); ……….. ; determining whether at least one edge between the pair of nodes includes one of the one or more critical edges (Yang: Para. 131; performs navigation path planning for the terminal based on auxiliary navigation data to plan at least one better candidate navigation path that avoids a segment where congestion may occur, and transmits the candidate navigation path to the terminal); and generating navigation instructions for a vehicle associated with the geographical area based on the determination, wherein the navigation instructions include an alternative edge for one of the one or more critical edges in the at least one edge (Yang: Para. 131; navigation request containing a navigation origin and a navigation destination; performs navigation path planning for the terminal based on auxiliary navigation data to plan at least one better candidate navigation path that avoids a segment where congestion may occur).
Yang doesn’t explicitly teach identifying a pair of nodes from the plurality of nodes of the network graph corresponding to the source location and the destination location.
However Huang, in the same field of endeavor, teaches identifying a pair of nodes from the plurality of nodes of the network graph corresponding to the source location and the destination location (Huang: Col. 8 Lines 49-57; anonymous vehicle trajectory data may be collected through various ways, such as a vehicle platform Application; smart phone location can track the vehicle location, and the time-location series can be used as the trajectory data).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G) with a reasonable expectation of success because a random forest regression model using historical and current data can predict the maximum flow between OD pairs (Huang: Col. 13 Lines 18-35).
Regarding claim 18, Yang teaches a computer programmable product comprising a non-transitory computer readable medium having stored thereon computer executable instructions, which when executed by one or more processors, cause the one or more processors to conduct operations comprising: obtaining an origin-destination (OD) matrix of a predefined time period (Yang: Para. 70; the historical vehicle trajectory data and historical traffic flow data in the historical time period corresponding to the current time period are obtained) indicating a plurality of traffic volume values for a plurality of OD pairs in a geographical area (Yang: Para. 69; obtain a target traffic flow corresponding to the OD pair in the target trip matrix); identifying one or more OD pairs of the plurality of OD pairs having traffic volume values greater than a traffic threshold (Yang: Para. 131; a traffic flow corresponding to the same segment in traffic reproduction is greater than that in system optimization); ………. , and wherein each of the plurality of edges is associated with a weight value indicative a trip volume (Yang: Para. 69; performing, taking an origin-destination (OD) pair in the historical trip matrix as an OD pair in the target trip matrix, weighted summation on estimated traffic flows corresponding to the same OD pair); determining one or more critical edges of the plurality of edges for the predefined time period based on the weight value of each of the plurality of edges (Yang: Para. 131; at least one better candidate navigation path that avoids a segment where congestion may occur, and transmits the candidate navigation path to the terminal); and storing edge data associated with the one or more critical edges for the predefined time period in a map database (Yang: Para. 61; obtain traffic section flow data, such as checkpoint data and geomagnetic coil data, and mobile signaling data of each segment in the historical time period from a second terminal and a second server as historical traffic flow data).
Yang doesn’t explicitly teach generating a network graph for the predefined time period based on the identified one or more OD pairs, the network graph comprising a plurality of nodes and a plurality of edges, wherein the plurality of nodes is associated with a plurality of locations.
However Huang, in the same field of endeavor, teaches generating a network graph for the predefined time period based on the identified one or more OD pairs, the network graph comprising a plurality of nodes and a plurality of edges, wherein the plurality of nodes is associated with a plurality of locations (Huang: Col. 13 Lines 18-35; random forest regression model may be used to predict the ratio of the maximum volume between OD pairs; averaged distance between the two nodes of OD pair i and the two nodes of OD pair j, and loc.sub.i is the latitude and longitude of both nodes of pair i).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G) with a reasonable expectation of success because a random forest regression model using historical and current data can predict the maximum flow between OD pairs (Huang: Col. 13 Lines 18-35).
Regarding claim 20, Yang doesn’t explicitly teach generating a plurality of historical network graphs, wherein each of the plurality of historical network graphs correspond to historical periods of time associated with the predefined time period; generating a plurality of historical tree graphs corresponding to each of the plurality of historical network graphs; comparing the tree graph and the plurality of historical tree graphs to determine a stability score; and generating a trip flow pattern graph for the geographical area based on the tree graph and the plurality of historical tree graphs on ascertaining the stability score to be greater than a stability threshold.
However Huang, in the same field of endeavor, teaches generating a plurality of historical network graphs, wherein each of the plurality of historical network graphs correspond to historical periods of time associated with the predefined time period (Huang: Col. 8 Lines 17-20; train the algorithm by semi-supervised learning based on known historical data (trajectory data and traffic volume data) of a plurality of point pairs); generating a plurality of historical tree graphs corresponding to each of the plurality of historical network graphs (Huang: Col. 8 Lines 17-20; historical data (trajectory data and traffic volume data) of a plurality of point pairs); comparing the tree graph and the plurality of historical tree graphs to determine a stability score (Huang: Col. 9 Lines 50-57, 62-67; determines the type of regression relationship between historical data and future data; penetration rate over all OD pairs obtain a median mean absolute percentage error (MAPE) of 20.3% in main hour); and generating a trip flow pattern graph for the geographical area based on the tree graph and the plurality of historical tree graphs on ascertaining the stability score to be greater than a stability threshold (Huang: Col. 1 Lines 63-67, Col. 8 Lines 17-20; determining the predicted future traffic volume to exceed a threshold; train the algorithm by semi-supervised learning based on known historical data (trajectory data and traffic volume data) of a plurality of point pairs).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G) with a reasonable expectation of success because a random forest regression model using historical and current data can predict the maximum flow between OD pairs (Huang: Col. 13 Lines 18-35).
Claims 5-6, 15, and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Yang et al. (US Publication 2023/0115110 A1) in view of Huang et al. (US Patent 10,963,705 B2) and in further view of Stetson et al. (US Publication 2020/0081445 A1).
Regarding claim 5, Yang and Huang don’t explicitly teach generate a tree graph for the predefined time period based on the plurality of nodes and an inverse of the weight value of each of the plurality of edges; and determine the one or more critical edges of the plurality of edges for the predefined time period based on the tree graph.
However Stetson, in the same field of endeavor, teaches generate a tree graph for the predefined time period based on the plurality of nodes and an inverse of the weight value of each of the plurality of edges (Stetson: Para. 8, 106, 114, 175; hierarchical knowledge graph is a tree in which independent risk scenarios are stored at the leaves; a metric proportional to the inverse of the number of nodes and/or edges in I; any number of different metrics can be used as appropriate to the requirements of specific applications; leverage the graph structure both exhaustively encode the set of possible risk scenarios to traverse, and also to identify areas of interest such as edge cases; dataset of vehicle trajectories only includes very common traffic features such as cars, trucks, pedestrians and traffic signals); and determine the one or more critical edges of the plurality of edges for the predefined time period based on the tree graph (Stetson: Para. 8, 106; leverage the graph structure both exhaustively encode the set of possible risk scenarios to traverse, and also to identify areas of interest such as edge cases, hierarchical knowledge graph is a tree in which independent risk scenarios are stored at the leaves).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G) using a risk metric proportional to the inverse (Stetson: Para. 114, 175) with a reasonable expectation of success because data in a graph tree for possible risk scenarios as a vehicle traverses a road can be leveraged to identify areas of interest such as edge cases (Stetson: Para. 8, 106, 114, 175).
Regarding claim 6, Yang doesn’t explicitly teach generate a plurality of historical network graphs, wherein each of the plurality of historical network graphs correspond to historical periods of time associated with the predefined time period; generate a plurality of historical tree graphs corresponding to each of the plurality of historical network graphs; compare the tree graph and the plurality of historical tree graphs to determine a stability score; and generate a trip flow pattern graph for the geographical area based on the tree graph and the plurality of historical tree graphs on ascertaining the stability score to be greater than a stability threshold.
However Huang, in the same field of endeavor, teaches generate a plurality of historical network graphs, wherein each of the plurality of historical network graphs correspond to historical periods of time associated with the predefined time period (Huang: Col. 8 Lines 17-20; train the algorithm by semi-supervised learning based on known historical data (trajectory data and traffic volume data) of a plurality of point pairs); generate a plurality of historical tree graphs corresponding to each of the plurality of historical network graphs (Huang: Col. 8 Lines 17-20; historical data (trajectory data and traffic volume data) of a plurality of point pairs); compare the tree graph and the plurality of historical tree graphs to determine a stability score (Huang: Col. 9 Lines 50-57, 62-67; determines the type of regression relationship between historical data and future data; penetration rate over all OD pairs obtain a median mean absolute percentage error (MAPE) of 20.3% in main hour); and generate a trip flow pattern graph for the geographical area based on the tree graph and the plurality of historical tree graphs on ascertaining the stability score to be greater than a stability threshold (Huang: Col. 1 Lines 63-67, Col. 8 Lines 17-20; determining the predicted future traffic volume to exceed a threshold; train the algorithm by semi-supervised learning based on known historical data (trajectory data and traffic volume data) of a plurality of point pairs).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G) with a reasonable expectation of success because a random forest regression model using historical and current data can predict the maximum flow between OD pairs (Huang: Col. 13 Lines 18-35).
Regarding claim 15, Yang and Huang don’t explicitly teach generating a tree graph for the predefined time period based on the plurality of nodes and an inverse of the weight value of each of the plurality of edges; and determining the one or more critical edges of the plurality of edges for the predefined time period based on the tree graph.
However Stetson, in the same field of endeavor, teaches generating a tree graph for the predefined time period based on the plurality of nodes and an inverse of the weight value of each of the plurality of edges (Stetson: Para. 8, 106, 114, 175; hierarchical knowledge graph is a tree in which independent risk scenarios are stored at the leaves; a metric proportional to the inverse of the number of nodes and/or edges in I; any number of different metrics can be used as appropriate to the requirements of specific applications; leverage the graph structure both exhaustively encode the set of possible risk scenarios to traverse, and also to identify areas of interest such as edge cases; dataset of vehicle trajectories only includes very common traffic features such as cars, trucks, pedestrians and traffic signals); and determining the one or more critical edges of the plurality of edges for the predefined time period based on the tree graph (Stetson: Para. 8, 106; leverage the graph structure both exhaustively encode the set of possible risk scenarios to traverse, and also to identify areas of interest such as edge cases, hierarchical knowledge graph is a tree in which independent risk scenarios are stored at the leaves).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G) using a risk metric proportional to the inverse (Stetson: Para. 114, 175) with a reasonable expectation of success because data in a graph tree for possible risk scenarios as a vehicle traverses a road can be leveraged to identify areas of interest such as edge cases (Stetson: Para. 8, 106, 114, 175).
Regarding claim 19, Yang and Huang don’t explicitly teach generating a tree graph for the predefined time period based on the plurality of nodes and an inverse of the weight value of each of the plurality of edges; and determining the one or more critical edges of the plurality of edges for the predefined time period based on the tree graph.
However Stetson, in the same field of endeavor, teaches generating a tree graph for the predefined time period based on the plurality of nodes and an inverse of the weight value of each of the plurality of edges (Stetson: Para. 8, 106, 114, 175; hierarchical knowledge graph is a tree in which independent risk scenarios are stored at the leaves; a metric proportional to the inverse of the number of nodes and/or edges in I; any number of different metrics can be used as appropriate to the requirements of specific applications; leverage the graph structure both exhaustively encode the set of possible risk scenarios to traverse, and also to identify areas of interest such as edge cases; dataset of vehicle trajectories only includes very common traffic features such as cars, trucks, pedestrians and traffic signals); and determining the one or more critical edges of the plurality of edges for the predefined time period based on the tree graph (Stetson: Para. 8, 106; leverage the graph structure both exhaustively encode the set of possible risk scenarios to traverse, and also to identify areas of interest such as edge cases, hierarchical knowledge graph is a tree in which independent risk scenarios are stored at the leaves).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G) using a risk metric proportional to the inverse (Stetson: Para. 114, 175) with a reasonable expectation of success because data in a graph tree for possible risk scenarios as a vehicle traverses a road can be leveraged to identify areas of interest such as edge cases (Stetson: Para. 8, 106, 114, 175).
Claim 7 is rejected under 35 U.S.C. 103 as being unpatentable over Yang et al. (US Publication 2023/0115110 A1) in view of Huang et al. (US Patent 10,963,705 B2), Stetson et al. (US Publication 2020/0081445 A1), and in further view of Jha et al. (US Publication 2023/0110467 A1).
Regarding claim 7, Yang, Huang, and Stetson don’t explicitly teach wherein the tree graph is a minimum spanning tree graph.
However Jha, in the same field of endeavor, teaches wherein the tree graph is a minimum spanning tree graph (Jha: Para. 26, 297; Minimum Spanning Tree).
It would have been obvious to one having ordinary skill in the art to modify the OD traffic matrix (Yang: Para. 70) with the random forest regression model and tree graphs (Huang: Col. 13 Lines 18-35, Fig. 3G), using a risk metric proportional to the inverse (Stetson: Para. 114, 175), and the minimum spanning tree (Jha: Para. 297) with a reasonable expectation of success because using a minimum spanning tree graph of analyzed road data to improve traffic efficiency or travel time (Jha: Para. 26, 297).
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to LAURA E LINHARDT whose telephone number is (571) 272-8325. The examiner can normally be reached on M-TR, M-F: 8am-4pm.
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, Angela Ortiz can be reached on (571) 272-1206. The fax phone number for the organization where this application or proceeding is assigned is (571) 273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at (866) 217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call (800) 786-9199 (IN USA OR CANADA) or (571) 272-1000.
/L.E.L./Examiner, Art Unit 3663
/ANGELA Y ORTIZ/Supervisory Patent Examiner, Art Unit 3663