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 .
Claim Objections
Claims 1, 10, and 19 objected to because of the following informalities: the limitation that recites, “the at least one encoder neural network” should be “at least one encoder neural network,” because this limitation is just now being introduced. Appropriate correction is required.
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 USC 101 because the claimed invention is directed to an abstract idea without significantly more.
At Step 1 of the 101 analysis, claims 1-9 and 19 are directed to one of the enumerated statutory categories, namely an apparatus. Claims 10-18 are directed to one of the enumerated statutory categories, namely a process.
Considering claim 1:
At Step 2A, Prong 1, the claim recites an abstract idea, as follows (with the abstract idea limitations in bold).
Claim 1 recites:
“A system for predicting road traffic speed comprising:
one or more processors; and a memory having instructions stored therein, the instructions, when executed by the one or more processors, causing the one or more processors to: receive and process raw trajectory data to determine processed trajectory data;
obtain node features representing information about road segment characteristics;
obtain edge features representing information about interactions between the node features;
determine a learned graph representation of a road network based on a node embedding of the node features and an edge embedding of the edge features;
determine at least one hidden states value based on a graph convolution of the learned graph representation through the at least one encoder neural network; and
predict road traffic speed based on the at least one hidden states value through at least one decoder neural network.”
The above limitations in bold are mathematical concepts and/or mental processes that may be carried out in the human mind or with the aid of pencil and paper. These limitations are therefore considered to be parts of an abstract idea.
At Step 2A, Prong 2, the abstract idea is not integrated into a practical application. The additional elements recited in the claim (beyond the abstract idea limitations identified above) are the processors, memory, encoder and decoder neural networks, and the “receiving and processing” step. The “receiving and processing” steps merely pertain to data gathering in order to perform the abstract idea. The processors, memory, and neural networks (encoder and decoder) are generic computer components used as tools to perform the abstract idea, which does not cause the claim as a whole to integrate the abstract idea into a particular practical application (see MPEP 2106.05(h)). The claim does not recite applying the abstract idea with, or by use of, any particular machine (see MPEP 2106.05(b)), nor does the claim affect a real-world transformation or reduction of a particular article to a different state or thing (see MPEP 2106.05(c)). As such, the additional elements do not impose meaningful limitations to the abstract idea, and do not integrate the claim into a particular practical application.
At Step 2B, the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception for the same reasons as discussed above with respect to Prong 2.
Claim 1 is therefore rejected as ineligible under 35 USC 101.
Claims 10 and 19 are analogous to claim 1, except that claim 19 additionally recites a non-transitory computer-readable medium. This is an additional element separate from the abstract idea that needs to be considered at Prong 2 of the 101 analysis. However, this additional element is merely a generic computer component that is invoked as a tool to perform the abstract idea, which does not cause the claim as a whole to integrate the abstract idea into a particular practical application or provide significantly more than the recited abstract idea (see MPEP 2106.05(f)). Claims 10 and 19 are therefore rejected as ineligible under 35 USC 101 as well.
Dependent claims 2-5, 7-9, 11-14, and 16-18 further add to the abstract idea limitations discussed above.
Dependent claim 6 and 15 add additional elements of the encoder and decoder, that further define the neural networks. These additional elements are used as tools to carry out the abstract idea and do not implement the abstract idea into a practical application for the same reasoning as claim 1 above.
None of the dependent claims recite any additional elements which would cause the claim as a whole to integrate the recited abstract idea into a particular practical application at Prong 2, or provide significantly more than the recited abstract idea at Step 2B for analogous reasoning as in claim 1. Dependent claims 2-9 and 11-18 are therefore rejected as ineligible under 35 USC 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.
Claims 1-4, 6-13, and 15-19 are rejected under 35 U.S.C. 103 as being unpatentable over Li et al. (CN109754605A (translation disclosed in IDS); hereinafter Li) in view of Sawal et al. (US 20220012433; hereinafter Sawal), and further view of HONG HUITING ET AL: "HetETA Heterogeneous Information Network Embedding for Estimating Time of Arrival", PROCEEDINGS OF THE 1ST INTERNATIONAL WORKSHOP ON EXTREME HETEROGENEITY SOLUTIONS, ACMPUB27, NEW YORK, NY, USA, 23 August 2020 (2020-08-23), pages 2444-2454. (disclosed in IDS); hereinafter Hong.
Regarding claims 1, 10, and 19, Li teaches: a system for predicting road traffic speed [see ¶0007 and ¶0058] comprising:
receive and process raw trajectory data to determine processed trajectory data [see ¶0041 taxi trajectory data processed into a data set and inputted into prediction model];
obtain node features representing information about road segment characteristics [see ¶0009 nodes represent road segments with time series attributes];
obtain edge features representing information about interactions between the node features [see ¶0009 edges represent connections between road segments];
determine a learned graph representation of a road network [see ¶0009 the urban road network is modeled as a graph structure];
determine at least one hidden states value based on a graph convolution of the learned graph representation [see ¶0010-0011]; and
predict road traffic speed based on the at least one hidden states value [see ¶0024 hidden states contain the spatiotemporal characteristics of the traffic flow; ¶0027 traffic speed; ¶0041 predicted traffic speed].
Li does not teach: one or more processors; and a memory having instructions stored therein, the instructions, when executed by the one or more processors, causing the one or more processors to perform the proposed invention; and a non-transitory computer-readable medium;
a node embedding of the node features and an edge embedding of the edge features;
and encoder and decoder neural networks.
Sawal teaches: one or more processors [see ¶0079]; and a memory having instructions stored therein, the instructions, when executed by the one or more processors, causing the one or more processors to perform a proposed invention [see ¶0079]; a non-transitory computer-readable medium [see ¶0079].
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Li with the teachings of Sawal, namely by having one or more processors; and a memory having instructions stored therein, the instructions, when executed by the one or more processors, causing the one or more processors to perform the proposed invention; and a non-transitory computer-readable medium in order to carry out the proposed invention more quickly and efficiently.
Sawal further teaches: encoder and decoder neural networks [see ¶0031].
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Li with the teachings of Sawal, namely by having encoder and decoder neural networks in order to encode features of input vectors into a hidden state and generate a prediction with the decoder [see ¶0033].
Hong teaches: a node embedding of the node features and an edge embedding of the edge features [see pgs. 2446-2448 section 3.1 and 3.2 spatiotemporal network embedding].
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the combination of Li and Sawal with the teachings of Hong, namely by node embedding the node features and by edge embedding the edge features in order to improve the performance of the neural network predictions [see pg. 2451 section 4.3.2 and 4.3.3].
Regarding claims 2 and 11, the combination of Li, Sawal, and Hong renders obvious the proposed invention of claims 1 and 10, and Li further teaches: wherein the raw trajectory data comprises speed readings of a vehicle matched to respective road segments that the vehicle is travelling on [see ¶0016 traffic speed is attribute of road network nodes; ¶0041 taxi speed data on the road sections at different times].
Regarding claims 3 and 12, the combination of Li, Sawal, and Hong renders obvious the proposed invention of claims 2 and 10, but Li does not teach: wherein the processor is configured to process the raw trajectory data by at least one of: removing negative speed readings; aggregating the speed readings over a predetermined time interval for individual road segments; and interpolating missing speed data by linear interpolation or replacing the missing speed data with a median speed value.
Hong teaches: for periods of time when no vehicles are passing by on a road segment, setting default values according to historic speed or the average speed of the same road type [see pg. 2449 section 4.1 ].
Several forms of average speed are known in the art, including mean and median speeds, and using the median speed as the average has the known advantage that it is less affected by extreme values (outliers) than mean speed is. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Li and Sawal with the teachings of Hong, namely by replacing the missing speed data with a median speed value.
One of ordinary skill in the art would have been motivated to do this in order to fill in data gaps for a consistent representation of a traffic flow.
Regarding claims 4 and 13, the combination of Li, Sawal, and Hong renders obvious the proposed invention of claims 1 and 10, and Li further teaches: wherein the node features are features regarding individual road segments [see ¶0009 nodes represent road segments with time series attributes; ¶0015 each road segment is regarded as a node], and the edge features are features regarding an intersection of the individual road segments [see ¶0009 edges represent connections between road segments].
Regarding claims 6 and 15, the combination of Li, Sawal, and Hong renders obvious the proposed invention of claims 1 and 10, but Li does not teach: an encoder and a decoder; wherein the encoder comprises the at least one encoder neural network and the decoder comprises the at least one decoder neural network; and wherein the at least one encoder bidirectional neural network, and the at least one decoder neural network is a unidirectional neural network.
Sawal teaches: an encoder and a decoder [see ¶0031-0033]; wherein the encoder comprises the at least one encoder bidirectional neural network [see ¶0031 encoder RNN is a bidirectional Long Short-Term Memory (LSTM) network] and the decoder comprises the at least one decoder unidirectional neural network [see ¶0031 decoder RNN 120 is a unidirectional LSTM network].
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the combination of Li and Hong with the teachings of Sawal, namely by having an encoder comprising a bidirectional neural network and decoder comprising a unidirectional neural network.
One of ordinary skill in the art would have been motivated to do this in order to encode features of input vectors (both forward and backward) into a hidden state and generate a prediction with the decoder [see ¶0033 and ¶0039].
Regarding claims 7 and 16, the combination of Li, Sawal, and Hong renders obvious the proposed invention of claims 1 and 10, but Li does not teach: wherein the processor is configured to perform the graph convolution of the learned graph representation by using the learned graph representation and a weighing matrix.
Li teaches: perform the graph convolution [see ¶0021 input into graph convolutional network model] of the learned graph representation [see ¶0023-0024 feature matrix X] by using the learned graph representation [matrix X] and a weighing matrix [see ¶0023-0024 weight matrices W0 and W1].
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the combination of Li and Hong with the processor of Sawal (as discussed in claim 1), namely by having the processor configured to perform the graph convolution of the learned graph representation by using the learned graph representation and a weighing matrix in order to more quickly and efficiently carry out the proposed invention.
Regarding claims 8 and 17, the combination of Li, Sawal, and Hong renders obvious the proposed invention of claims 1 and 10, but Li does not teach: wherein the processor is configured to use at least one binary adjacent matrix during the graph convolution for masking.
Li teaches: use at least one binary adjacent matrix during the graph convolution for masking [see ¶0015 and ¶0023 adjacency matrix A masks road segments during convolution].
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the combination of Li and Hong with the processor of Sawal (as discussed in claim 1) namely, by having the processor is configured to use at least one binary adjacent matrix during the graph convolution for masking in order to more quickly and efficiently carry out the proposed invention.
Regarding claims 9 and 18, the combination of Li, Sawal, and Hong renders obvious the proposed invention of claims 1 and 10, but Li does not teach: wherein the at least one hidden states value comprises a last hidden state value, and the processor is configured to predict road traffic speed based on the last hidden state value.
Li teaches: a last hidden state value [see ¶0011 hidden state] is used to predict road traffic speed based on the last hidden state value [see ¶0007 and ¶0011 hidden state predicts traffic flow on each road section].
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the combination of Li and Hong with the processor of Sawal (as discussed in claim 1) namely, by having the at least one hidden states value comprise a last hidden state value, and the processor is configured to predict road traffic speed based on the last hidden state value masking in order to more quickly and efficiently carry out the proposed invention.
Claims 5 and 14 are rejected under 35 U.S.C. 103 as being unpatentable over Li et al. (CN109754605A; hereinafter Li) in view of Sawal et al. (US 20220012433; hereinafter Sawal), and further view of HONG HUITING ET AL: "HetETA Heterogeneous Information Network Embedding for Estimating Time of Arrival", PROCEEDINGS OF THE 1ST INTERNATIONAL WORKSHOP ON EXTREME HETEROGENEITY SOLUTIONS, ACMPUB27, NEW YORK, NY, USA, 23 August 2020 (2020-08-23), pages 2444-2454.; hereinafter Hong, and Paranjpe et al. (US 10533862; hereinafter Paranjpe).
Regarding claims 5 and 14, the combination of Li, Sawal, and Hong renders obvious the proposed invention of claims 1 and 10, but Li does not teach: wherein the node features comprise at least one of road class, number of lanes and length of road segments, and wherein the edge features comprise at least one of Haversine distances between road segments, change in number of lanes between road segments, and change in road width between road segments.
Hong teaches: the node features comprise at least one of road class [road type], number of lanes [lane number] and length of road segments [segment length][see pg. 2449 section 4.1 col. 1].
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Li and Sawal with the teachings of Hong, namely by having the node features comprise at least one of road class, number of lanes and length of road segments in order to use these features to fill traffic data gaps (e.g. using data from a similar road class/type to generate data for road segments with data sparsity) [see pg. 2449 section 4.1].
Paranjpe teaches: determining a Haversine distance between two road segments [see col. 7 lines 4-24].
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Li, Sawal, and Hong with the teachings of Paranjpe, namely by having the edge features comprise Haversine distances between road segments in order to accurately model the learned graph representation of a road network.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's
disclosure.
Jain et al. (US 20100286899 ) – obtaining road sensor data reflecting speeds of traffic on road segments and determining speeds for road segments between road sensors by smoothing data from sensors near the road segments. This differs from the proposed invention because it doesn’t disclose a neural network specifically, but it does mention using machine learning techniques.
McGill et al. (US 20210302960) – uses a neural network to make driving recommendations by analyzing traffic speed and other data about the roads. This differs from the proposed invention because it is mostly concerned with vehicle navigation rather than the traffic speed in general.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to BRANDON G MACGREGOR whose telephone number is (571)272-2217. The examiner can normally be reached Mon-Fri 7:00-4:00pm CST.
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, Andrew Schechter can be reached at (571) 272-2302. 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.
/BRANDON GEORGE MACGREGOR/Examiner, Art Unit 2857
/ANDREW SCHECHTER/Supervisory Patent Examiner, Art Unit 2857
Prosecution Insights