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 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 they are directed towards a mental process without significantly more.
Claim 1 cites:
A system comprising:
a memory configured to store computer executable instructions; and
one or more processors configured to execute the instructions to:
obtain an origin-destination (OD) matrix associated with one or more routes, the OD matrix comprising a plurality of historical traffic values for one or more predefined time slots for each of the one or more routes;
generate one or more network graphs based on the plurality of historical traffic values of the OD matrix, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of nodes and a plurality of edges having corresponding weight values;
determine one or more desired routes from the one or more routes based on the weight values, wherein each of the one or more desired routes is associated with one of the one or more network graphs;
determine travel frequency data for each of the one or more desired routes at least in the one or more predefined time slots based on the one or more network graphs; and
determine a modal route based on the one or more desired routes and the travel frequency data.
Step 2A prong one evaluation: Judicial Exception – Yes – Mental Processes
The Office submits that the foregoing bolded limitation(s) constitutes judicial exceptions in terms of “mental processes” because under its broadest reasonable interpretation, the claim covers performance using mental.
The claims recite generating one or more network graphs. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the OD matrix and generate a map of an area with nodes and edges with estimations of traffic density for different times based on that data. Thus this step is directed to a mental process.
The claims recite determining one or more desired routes based on the weight values. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the weight values of the network graph and determine a route that appears to avoid traffic. Thus this step is directed to a mental process.
The claims recite determining a travel frequency for each of the desired routes based on the time slots of the network graphs. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the different time slots and the network graphs and determine additional traffic expectations for the routes. Thus this step is directed to a mental process.
The claims recite determining a modal route from the desired routes and travel frequency data. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the different routes and travel frequency data and could pick an optimal route. Thus this step is directed to a mental process.
Step 2A Prong Two evaluations
Claims are evaluated whether as a whole it integrates the recited judicial exception into a practical application. As noted in the 2019 PEG, it must be determined whether any additional elements in the claim beyond the abstract idea integrate the exception into a practical application in a manner that imposes a meaningful limit on the judicial exception. The courts have indicated that additional elements merely using a computer to implement an abstract idea or adding/performing insignificant extra solution activity, or generally linking use of a judicial exception to a particular technological environment or field of use do not integrate a judicial exception into a “practical application.”
In the present case, the additional limitations beyond the above-noted abstract idea are as follows (where the underlined portions are the “additional limitations” while the bolded portions continue to represent the “abstract idea”).
The claims cite “obtaining an origin destination matrix”. This is listed at a high level of generality and there is nothing that indicates that this is more than mere data retrieval or reception. Therefore it is insignificant extra solution activity.
The claims recite generating network graphs, determining desired routes, determining travel frequency data, and determine a modal route using a device, a processor, a memory, a computer, processing circuitry, and a non-transitory computer readable storage medium. The above listed actions are recited at a high level of generality. The computer/circuitry that facilitate the steps are described by the specification at a high level of generality. The generically recited computer merely describes how to generally “apply” the otherwise mental/extra solution processes using a generic or general-purpose processor. Accordingly, even in combination, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea.
The claim is not patent eligible.
2B Evaluation: Inventive Concept – No
Claims are evaluated as to whether the claims as a whole amount to significantly more than the recited exception, i.e., whether any additional element, or combination of additional elements, adds an inventive concept to the claim.
As discussed with respect to Step 2A Prong Two, the additional elements in the claim amount to no more than possible uses for the output of the abstract idea. The same analysis applies here in 2B, i.e., possible uses for information or mere instructions to apply an exception on a generic computer cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Thus the claims are not patent eligible.
Claim 12 cites:
A method comprising:
obtaining an origin-destination (OD) matrix associated with one or more routes, the OD matrix comprising a plurality of historical traffic values for one or more predefined time slots for each of the one or more routes;
generating one or more network graphs based on the plurality of historical traffic values of the OD matrix, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprise a plurality of nodes and a plurality of edges having corresponding weight values;
determining one or more desired routes from the one or more routes based on the weight values, wherein each of the one or more desired routes is associated with one of the one or more network graphs;
determining travel frequency data for each of the one or more desired routes at least in the one or more predefined time slots based on the one or more network graphs; and
determining a modal route based on the one or more desired routes and the travel frequency data.
Step 2A prong one evaluation: Judicial Exception – Yes – Mental Processes
The Office submits that the foregoing bolded limitation(s) constitutes judicial exceptions in terms of “mental processes” because under its broadest reasonable interpretation, the claim covers performance using mental.
The claims recite generating one or more network graphs. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the OD matrix and generate a map of an area with nodes and edges with estimations of traffic density for different times based on that data. Thus this step is directed to a mental process.
The claims recite determining one or more desired routes based on the weight values. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the weight values of the network graph and determine a route that appears to avoid traffic. Thus this step is directed to a mental process.
The claims recite determining a travel frequency for each of the desired routes based on the time slots of the network graphs. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the different time slots and the network graphs and determine additional traffic expectations for the routes. Thus this step is directed to a mental process.
The claims recite determining a modal route from the desired routes and travel frequency data. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the different routes and travel frequency data and could pick an optimal route. Thus this step is directed to a mental process.
Step 2A Prong Two evaluations
Claims are evaluated whether as a whole it integrates the recited judicial exception into a practical application. As noted in the 2019 PEG, it must be determined whether any additional elements in the claim beyond the abstract idea integrate the exception into a practical application in a manner that imposes a meaningful limit on the judicial exception. The courts have indicated that additional elements merely using a computer to implement an abstract idea or adding/performing insignificant extra solution activity, or generally linking use of a judicial exception to a particular technological environment or field of use do not integrate a judicial exception into a “practical application.”
In the present case, the additional limitations beyond the above-noted abstract idea are as follows (where the underlined portions are the “additional limitations” while the bolded portions continue to represent the “abstract idea”).
The claims cite “obtaining an origin destination matrix”. This is listed at a high level of generality and there is nothing that indicates that this is more than mere data retrieval or reception. Therefore it is insignificant extra solution activity.
The claims recite generating network graphs, determining desired routes, determining travel frequency data, and determine a modal route using a device, a processor, a memory, a computer, processing circuitry, and a non-transitory computer readable storage medium. The above listed actions are recited at a high level of generality. The computer/circuitry that facilitate the steps are described by the specification at a high level of generality. The generically recited computer merely describes how to generally “apply” the otherwise mental/extra solution processes using a generic or general-purpose processor. Accordingly, even in combination, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea.
The claim is not patent eligible.
2B Evaluation: Inventive Concept – No
Claims are evaluated as to whether the claims as a whole amount to significantly more than the recited exception, i.e., whether any additional element, or combination of additional elements, adds an inventive concept to the claim.
As discussed with respect to Step 2A Prong Two, the additional elements in the claim amount to no more than possible uses for the output of the abstract idea. The same analysis applies here in 2B, i.e., possible uses for information or mere instructions to apply an exception on a generic computer cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Thus the claims are not patent eligible.
Claim 20 cites:
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 associated with one or more routes, the OD matrix comprising a plurality of historical traffic values for one or more predefined time slots for each of the one or more routes;
generating one or more network graphs based on the plurality of historical traffic values of the OD matrix, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprise a plurality of nodes and a plurality of edges having corresponding weight values;
determining one or more desired routes from the one or more routes based on the weight values, wherein each of the one or more desired routes is associated with one of the one or more network graphs;
determining travel frequency data for each of the one or more desired routes at least in the one or more predefined time slots based on the one or more network graphs; and
determining a modal route based on the one or more desired routes and the travel frequency data.
Step 2A prong one evaluation: Judicial Exception – Yes – Mental Processes
The Office submits that the foregoing bolded limitation(s) constitutes judicial exceptions in terms of “mental processes” because under its broadest reasonable interpretation, the claim covers performance using mental.
The claims recite generating one or more network graphs. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the OD matrix and generate a map of an area with nodes and edges with estimations of traffic density for different times based on that data. Thus this step is directed to a mental process.
The claims recite determining one or more desired routes based on the weight values. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the weight values of the network graph and determine a route that appears to avoid traffic. Thus this step is directed to a mental process.
The claims recite determining a travel frequency for each of the desired routes based on the time slots of the network graphs. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the different time slots and the network graphs and determine additional traffic expectations for the routes. Thus this step is directed to a mental process.
The claims recite determining a modal route from the desired routes and travel frequency data. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the different routes and travel frequency data and could pick an optimal route. Thus this step is directed to a mental process.
Step 2A Prong Two evaluations
Claims are evaluated whether as a whole it integrates the recited judicial exception into a practical application. As noted in the 2019 PEG, it must be determined whether any additional elements in the claim beyond the abstract idea integrate the exception into a practical application in a manner that imposes a meaningful limit on the judicial exception. The courts have indicated that additional elements merely using a computer to implement an abstract idea or adding/performing insignificant extra solution activity, or generally linking use of a judicial exception to a particular technological environment or field of use do not integrate a judicial exception into a “practical application.”
In the present case, the additional limitations beyond the above-noted abstract idea are as follows (where the underlined portions are the “additional limitations” while the bolded portions continue to represent the “abstract idea”).
The claims cite “obtaining an origin destination matrix”. This is listed at a high level of generality and there is nothing that indicates that this is more than mere data retrieval or reception. Therefore it is insignificant extra solution activity.
The claims recite generating network graphs, determining desired routes, determining travel frequency data, and determine a modal route using a device, a processor, a memory, a computer, processing circuitry, and a non-transitory computer readable storage medium. The above listed actions are recited at a high level of generality. The computer/circuitry that facilitate the steps are described by the specification at a high level of generality. The generically recited computer merely describes how to generally “apply” the otherwise mental/extra solution processes using a generic or general-purpose processor. Accordingly, even in combination, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea.
The claim is not patent eligible.
2B Evaluation: Inventive Concept – No
Claims are evaluated as to whether the claims as a whole amount to significantly more than the recited exception, i.e., whether any additional element, or combination of additional elements, adds an inventive concept to the claim.
As discussed with respect to Step 2A Prong Two, the additional elements in the claim amount to no more than possible uses for the output of the abstract idea. The same analysis applies here in 2B, i.e., possible uses for information or mere instructions to apply an exception on a generic computer cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Thus the claims are not patent eligible.
Claim 2 cites:
The system of claim 1, wherein the one or more predefined time slots correspond to one or more historical occurrences of a predefined time period of a day.
Claim 3 cites:
The system of claim 1, wherein each of the plurality of edges of each of the one or more network graphs is associated with one of the one or more routes, and wherein the weight value of each of the plurality of edges is associated with historical traffic volume of a corresponding route from the one or more routes.
Claim 4 cites:
The system of claim 1, wherein the one or more routes lie between a source location and a destination location.
Claim 5 cites:
The system of claim 1, wherein the one or more processors are configured to: generate a navigation recommendation based on the modal route.
Claim 6 cites:
The system of claim 5, wherein the navigation recommendation is generated in an offline manner.
Claim 7 cites:
The system of claim 1, wherein the one or more processors are configured to:
determine the one or more desired routes based on the one or more network graphs associated with the one or more predefined time slots;
determine the travel frequency data for each of the one or more desired routes; and
determine the modal route from the one or more desired routes based on an aggregation of the one or more desired routes and the corresponding travel frequency data.
Claim 8 cites:
The system of claim 1, wherein the one or more processors are configured to: determine the one or more desired routes based on applying a shortest path function on each of the one or more network graphs.
Claim 9 cites:
The system of claim 1, wherein the one or more processors are further configured to:
predict, using a machine learning (ML) model, the modal route from the one or more desired routes for a future time slot associated with the one or more predefined time slots, wherein the ML model is trained based on a plurality of training network graphs and training trip frequency data.
Claim 10 cites:
The system of claim 1, wherein a travel time associated with each of the one or more desired routes is shortest among one or more travel times associated with the one or more routes other than the one or more desired routes in a corresponding network graph from the one or more network graphs.
Claim 11 cites:
The system of claim 1, wherein the historical traffic values comprise traffic volume distribution for each of the one or more routes during the one or more predefined time slots.
Claim 13 cites:
The method of claim 12, further comprising:
generating a navigation recommendation based on the modal route.
Claim 14 cites:
The method of claim 12, further comprising:
determining the one or more desired routes based on the one or more network graphs associated with the one or more predefined time slots;
determining travel frequency data for each of the one or more desired routes; and
determining the modal route from the one or more desired routes based on an aggregation of the one or more desired routes and the corresponding travel frequency data.
Claim 15 cites:
The method of claim 12, further comprising:
determining the one or more desired routes based on applying a shortest path function on each of the one or more network graphs.
Claim 16 cites:
The method of claim 12, further comprising:
predicting, using a machine learning (ML) model, the modal route from the one or more desired routes for a future time slot associated with the one or more predefined time slots, wherein the ML model is trained based on a plurality of training network graphs and training trip frequency data.
Claim 17 cites:
The method of claim 12, wherein the one or more predefined time slots correspond to one or more historical occurrences of a predefined time period of a day.
Claim 18 cites:
The method of claim 12, wherein each of the plurality of edges of each of the one or more network graphs is associated with one of the one or more routes, and wherein the weight value of each of the plurality of edges is associated with historical traffic volume of a corresponding route from the one or more routes.
Claim 19 cites:
The method of claim 12, wherein the one or more routes lie between a source location and a destination location.
Claims 5 and 13 cite generating a navigation recommendation based on the modal route. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider modal route and consider navigation instructions. Thus this step is directed to a mental process.
Claims 7 and 14 cite determining the one or more desired routes based on the one or more network graphs. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider desired or optimal routes based on the network graphs and the traffic data contained. Thus this step is directed to a mental process.
Claims 7 and 14 cite determining the travel frequency data for the routes. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the route and the traffic data and travel frequency data based on the network graph and matrix. Thus this step is directed to a mental process.
Claims 7 and 14 cite determining the modal route from the desired routes based on the aggregation of the desired routes and corresponding travel frequency data. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the desired routes, aggregate them in a way to determine a good compromise between them, and consider the travel frequency data. Thus this step is directed to a mental process.
Claims 8 and 15 cite determining the one or more desired routes using a shortest path function on the graphs. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the network graph, and mentally consider shortest paths to determine desired routes. Thus this step is directed to a mental process.
Claims 9 and 16 cite predicting the modal route from the desired routes for a future time slot. This limitation, as drafted, is a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind, but for the limitation that processing circuitry be programed to perform the task. That is, other than reciting “processor”, or “memory”, nothing in the claim precludes the element being done in the mind. A person could mentally consider the previous desired routes, make notes on when traffic at certain areas is high or low, and mentally predict future desired routes from that information. Thus this step is directed to a mental process.
Step 2A Prong Two evaluations
Claims are evaluated whether as a whole it integrates the recited judicial exception into a practical application. As noted in the 2019 PEG, it must be determined whether any additional elements in the claim beyond the abstract idea integrate the exception into a practical application in a manner that imposes a meaningful limit on the judicial exception. The courts have indicated that additional elements merely using a computer to implement an abstract idea or adding/performing insignificant extra solution activity, or generally linking use of a judicial exception to a particular technological environment or field of use do not integrate a judicial exception into a “practical application.”
In the present case, the additional limitations beyond the above-noted abstract idea are as follows (where the underlined portions are the “additional limitations” while the bolded portions continue to represent the “abstract idea”).
The claims cite “obtaining an origin destination matrix”. This is listed at a high level of generality and there is nothing that indicates that this is more than mere data retrieval or reception. Therefore it is insignificant extra solution activity.
The claims recite generating navigation instructions, determining desired routes, travel frequency data, modal routes using shortest path function, and predicting desired routes using a device, a processor, a memory, a computer, processing circuitry, and a non-transitory computer readable storage medium. The above listed actions are recited at a high level of generality. The computer/circuitry that facilitate the steps are described by the specification at a high level of generality. The generically recited computer merely describes how to generally “apply” the otherwise mental/extra solution processes using a generic or general-purpose processor. Accordingly, even in combination, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea.
The claim is not patent eligible.
2B Evaluation: Inventive Concept – No
Claims are evaluated as to whether the claims as a whole amount to significantly more than the recited exception, i.e., whether any additional element, or combination of additional elements, adds an inventive concept to the claim.
As discussed with respect to Step 2A Prong Two, the additional elements in the claim amount to no more than possible uses for the output of the abstract idea. The same analysis applies here in 2B, i.e., possible uses for information or mere instructions to apply an exception on a generic computer cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Thus the claims are not patent eligible.
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-5, 9-13, and 16-20 are rejected under 35 U.S.C. 103 as being unpatentable over Yang et al (US Pub 2023/0115110 A1), hereafter known as Yang in light of Huang et al (US Pub 2020/0042799 A1), hereafter known as Huang in light of Fink et al (US Pub 2011/0161001 A1), hereafter known as Fink.
For Claim 1, Yang teaches A system comprising:
a memory configured to store computer executable instructions; and ([0009] A computer device is provided, including a memory and one or more processors, the memory storing computer-readable instructions, and 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.)
one or more processors configured to execute the instructions to: ([0009] A computer device is provided, including a memory and one or more processors, the memory storing computer-readable instructions, and 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 associated with one or more routes, the OD matrix comprising a plurality of historical traffic values for one or more predefined time slots for each of the one or more routes; ([0083] Urban traffic requirement mining refers to analyzing a trip requirement by a big data technology. Referring to FIG. 4, the computer device may mine traffic flows between different OD pairs in a city by combining historical vehicle trajectories of a private vehicle, a taxi, a bus, a truck, and an on-line hailed vehicle, mobile signaling, mobile APP positioning, a bus trip code, a geomagnetic coil, a checkpoint, and other data, to generate an OD matrix. Specifically, the computer device first segments a trip trajectory of a user from collected multi-source data to obtain a candidate travel path including a candidate origin and destination. Then, the computer device performs traffic cell absorption on the candidate origin/candidate destination. Traffic cell absorption is performed by searching for a closest reference point of interest according to the origin/destination. That is, origin clustering and destination clustering are performed. In this manner, the computer device may obtain a most primitive initial OD matrix statistically, i.e., a traffic OD matrix and candidate travel paths sampled from the reality. The initial OD matrix may include initial traffic flows corresponding to different OD pairs respectively. Further, the initial OD matrix may also include travel heat of different transportation means on paths between different OD pairs, i.e., the initial traffic flows corresponding to different transportation means between different OD pairs. Anomaly filtering is mainly for abnormal trajectories. For example, abnormal trajectories may be determined based on abnormal driving behaviors of a driver, such as abnormal stopping, waiting for an order by the road, staying for a long time in a region, and positioning trajectory drifting.
[0084] Then, the computer device checks and expands the initial OD matrix by combining a traffic section flow such as a geomagnetic coil and a checkpoint, and complete data such as mobile signaling, to estimate a traffic OD matrix closest to the reality and used for describing complete trip information, so as to complete OD matrix estimation to obtain a historical OD matrix. The computer device may generate a target OD matrix based on the historical OD matrix, the target OD matrix describing a trip requirement in the current time period. Further, the computer device may perform traffic simulation based on the target OD matrix. The target OD matrix provides the trip requirement for traffic simulation. The target OD matrix or the initial OD matrix provides a candidate travel path for traffic simulation. In addition, parameter calibration may be performed on a traffic flow model in mesoscopic traffic simulation and an autonomous driving model in microscopic traffic simulation based on traffic data collected from the reality. The computer device may extract a traffic flow sample from a basic road network (i.e., the real road network), and perform data analysis on the traffic flow sample, so as to perform parameter calibration on the traffic flow model and the autonomous driving model. The traffic flow sample include massive statistical data of speeds, densities, flows, etc., of segments and sensor data returned in a real vehicle road test.)
wherein each of the one or more Matrices corresponds to one of the one or more predefined time slots, and wherein each of the one or more Matrices comprises a plurality of edges having corresponding weight values; ([0090] Step S504: Add each target vehicle to the simulated road network according to departure time and initial travel path corresponding to each target vehicle.
[0091] Step S506: Adjust a travel speed of each target vehicle dynamically during simulated traveling of each target vehicle based on the real-time mesoscopic simulated traffic condition data of the simulated road network until each target vehicle stops traveling.
[0092] Specifically, after determining the initial travel path corresponding to each target vehicle, the computer device may add each target vehicle to the simulated road network according to departure time and initial travel path corresponding to each target vehicle such that each target vehicle travels in the simulated road network. The computer device may adjust a travel speed of each target vehicle dynamically during simulated traveling of each target vehicle based on the real-time mesoscopic simulated traffic condition data of the simulated road network until each target vehicle travels to the corresponding destination, namely each target vehicle stops traveling. The departure time corresponding to each target vehicle may be determined according to historical path departure time distribution information. The historical path departure time distribution information refers to a distribution of departure time of vehicles on each candidate travel path corresponding to the same OD pair. Different OD pairs may correspond to different historical path departure time distribution information. For example, historical path departure time distribution information corresponding to an OD pair is that 20% of vehicles depart every 5 minutes on candidate travel path 1, 30% of vehicles depart every 3 minutes on candidate travel path 2, and 40% of vehicles depart every 7 minutes on candidate travel path 3.
[0069] Specifically, the computer device may obtain the target trip matrix based on the historical trip matrix, namely predicting the target trip matrix according to the historical trip matrix. The computer device may merge multiple historical trip matrices to obtain the target trip matrix. For example, it is assumed that a current moment in a real road network is 8:00 on Monday, actual traffic data after 8:00 is yet not generated, and the current time period is 8:00 to 8:15 on Monday. In such case, the computer device may obtain target vehicle trajectory data and target traffic flow data from 7:45 to 8:00 on Monday to generate a historical trip matrix A from 7:45 to 8:00 on Monday, obtain target vehicle trajectory data and target traffic flow data from 8:00 to 8:15 last week to generate a historical trip matrix B in 8:00 to 8:15 last week, and generate a target trip matrix corresponding to the current time period based on the historical trip matrix A and the historical trip matrix B. 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.)
determine one or more desired routes from the one or more routes based on the weight values, wherein each of the one or more desired routes is associated with one of the one or more OD Networks; ([0097] Step S512: Obtain target travel data of each target vehicle in the current time period based on the target travel path and departure time corresponding to each target vehicle.
[0098] Specifically, after determining the target travel path corresponding to each target vehicle, the computer device may obtain target travel data of each target vehicle in the current time period based on the target travel path and departure time corresponding to each target vehicle.
[0081] Specifically, the computer device may obtain a historical traffic flow corresponding to each target trip combination and a historical traffic flow corresponding to each segment based on the target traffic flow data. The computer device may perform an expansion process on the initial traffic flow corresponding to each target trip combination based on the target traffic flow data to roughly increase OD pairs passing through a specific segment in a certain ratio according to a historical section traffic flow to obtain an intermediate traffic flow corresponding to each target trip combination. For example, if an initial traffic flow corresponding to an OD pair in an initial trip matrix is 80, and it is determined according to the target traffic flow data that a historical traffic flow corresponding to the OD pair is 100, the initial traffic flow may be preliminarily expanded to 100. It can be understood that expansion ratios of different OD pairs may be the same or different. For example, a corresponding expansion ratio may be determined according to the corresponding initial traffic flow and historical traffic flow.
It should be noted that the weight can be representative of Traffic flow, which Yang does provide for each segment.)
determine travel frequency data for each of the one or more desired routes at least in the one or more predefined time slots based on the one or more OD Matrix; and ([0076] Further, the computer device may cluster the candidate travel paths corresponding to the same intermediate origin and intermediate destination to obtain multiple target trip combinations, the target trip combination including at least one candidate travel path corresponding to the same intermediate origin and intermediate destination. That is, the candidate travel paths corresponding to the same OD pair are clustered to obtain multiple different OD pairs and at least one candidate travel path corresponding to each OD pair. The computer device may obtain a number of the candidate vehicles corresponding to the same target trip combination statistically to obtain an initial traffic flow corresponding to each target trip combination, and further generate the initial trip matrix based on each target trip combination and the corresponding initial traffic flow and candidate travel path. The initial trip matrix includes multiple OD pairs, an initial traffic flow corresponding to each OD pair, and at least one candidate travel path corresponding to each OD pair. It can be understood that there may be at least one travel path from point A to point B, and thus an OD pair may correspond to at least one candidate travel path.
[0077] In this embodiment, trajectory segmentation is performed on the target vehicle trajectory data to obtain the candidate travel paths respectively corresponding to the multiple candidate vehicles, the candidate travel path including the candidate origin and the candidate destination, and origin clustering and destination clustering are performed on each candidate travel path based on the reference point of interest to obtain the intermediate origin and intermediate destination corresponding to each candidate travel path. In this manner, scattered origins and destinations may be clustered to landmark geographic positions to obtain candidate travel paths capable of reflecting a real traffic requirement more accurately. Then, the candidate travel paths corresponding to the same intermediate origin and intermediate destination are clustered to obtain the multiple target trip combinations. The number of the candidate vehicles corresponding to the same target trip combination is obtained statistically to obtain the initial traffic flow corresponding to each target trip combination, the target trip combination including the at least one candidate travel path corresponding to the same intermediate origin and intermediate destination. The initial trip matrix may be generated rapidly based on each target trip combination and the corresponding initial traffic flow and candidate travel path.
[0078] In an embodiment, the initial trip matrix includes multiple target trip combinations and an initial traffic flow corresponding to each target trip combination. The operation of adjusting the initial trip matrix based on the target traffic flow data to obtain a historical trip matrix corresponding to the historical time period includes:
[0079] performing an expansion process on the initial traffic flow corresponding to each target trip combination based on the target traffic flow data to obtain an intermediate traffic flow corresponding to each target trip combination; performing a check process on each intermediate traffic flow based on the target traffic flow data to obtain an estimated traffic flow corresponding to each target trip combination; and adjusting, based on the estimated traffic flow corresponding to each target trip combination, the corresponding initial traffic flow to obtain the historical trip matrix.)
determine a modal route based on the one or more desired routes and the travel frequency data. [0131] Specifically, the computer device may generate auxiliary navigation data based on the simulated traffic condition in the current time period, and transmit the auxiliary navigation data to the navigation server. After receiving the auxiliary navigation data, the navigation server may learn a traffic condition corresponding to traffic reproduction in the current time period based on the auxiliary navigation data, and further perform navigation path planning for the terminal. For example, if a current moment is 8:00, and the current time period is 8:15 to 8:30, the simulated traffic condition in the current time period is a predicted future traffic condition. The user may initiate a navigation request with the terminal. The terminal transmits the navigation request containing a navigation origin and a navigation destination to the navigation server. The navigation server 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. After receiving the candidate navigation path, the terminal may display it to the user. Alternatively, the navigation server may learn a traffic condition corresponding to each simulation requirement in the current time period based on the auxiliary navigation data, and further perform navigation path planning for the terminal. For example, the navigation server may learn traffic conditions respectively corresponding to traffic reproduction and system optimization based on the auxiliary navigation data, and further perform navigation path planning based on a difference between the traffic conditions respectively corresponding to traffic reproduction and system optimization. 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.
Yang does not teach generate one or more network graphs based on the plurality of historical traffic values of the OD matrix, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of edges having corresponding weight values;
Huang, however, does teach generate one or more network graphs based on the plurality of historical traffic values of the OD matrix, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of edges having corresponding weight values; ([0068] In some embodiments, a random forest regression model may be used to predict {circumflex over (R)}.sub.i,j, the ratio of the maximum volume between OD pairs i and j:
[00006]R^i,j=f(ximax,xjmax,disi,j,ximaxxjmax,loci,locj)≈Yscale:iYscale:j
[0069] where the function f(⋅) stands for a random forest regression function. Random forests can be viewed as an ensemble learning method for regression that operates by constructing a multitude of regression trees for training and outputting the mean prediction of the individual trees. x.sub.i.sup.max is the maximum volume of the trajectory data for point pair i within one day, is the 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. For example, a toy size tree with only 5 leaf nodes is shown in FIG. 3E. This random forest model makes prediction for the maximum volume over certain OD pair based on this OD pair's geographical information and its neighboring information. In FIG. 3F, a standard factor importance analysis shows that the most important factor, x_ratio, is the ratio of the trajectory counts between pair i and j. The next two most important factors are x_max_i and x_max_j, the maximum trajectory volume on pair i and pair j, respectively. x_max_i is the maximum trajectory volume on pair i. dist_ij is the averaged distance between OD pair i and j. st_i_x and st_i_y stands for the longitude and latitude of the starting node of pair i. Similarly, end_i_x and end_i_y stands for the longitude and latitude of the destination node of pair i. This factor importance analysis shows that the random forest model is mostly based on the information from the trajectory data.
[0088] Block 401 comprises obtaining, by a processor (e.g., the processor 104) and from a plurality of computing devices (e.g., the computing devices 110, 111), time-series locations of a plurality of vehicles respectively associated with the computing devices, wherein: the time-series locations form first trajectory data comprising corresponding trajectories at least passing from a first point O to a second point D within a first time interval. Block 402 comprises obtaining, by a detector (e.g., the detector 105), a traffic volume between O and D for a second time interval that is temporally after the first time interval. Block 403 comprises training, by the processor, one or more weights of a neural network model by inputting the first trajectory data and the traffic volume to the neural network model and using the obtained traffic volume as ground truth to obtain a trained neural network model. Block 404 comprises inputting, by the processor, second trajectory data between O and D to the trained neural network model to predict a future traffic volume between O and D for the a future time interval.)
Fink, however, does teach generate one or more network graphs based on the plurality of historical traffic values, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of edges having corresponding weight values; ([0052] One product of such a data collection and aggregation process is a "historical traffic model". In one example, a historical traffic model includes a list of traffic segments and associated time-of-day, day-of-week (and given enough time, week-of-year) time slots that contain expected traffic flow speeds (potentially with error estimates) during that time slot on that segment. Gaps can be filled with default "static" speeds. The model can be constructed as a large matrix, with rows representing traffic segments and columns representing time slots.
determine a modal route based on the one or more desired routes and the travel frequency data. ([0130] Rather, in an example method (FIG. 11), a current location of a device can be estimated (2403), such as by using GPS signal information, or an identity of a cell phone tower, triangulation of tower signals and so on. A comparison/determination (2405) between the current location and first and second pre-defined destination is made. If the current location is proximate a first pre-defined destination (e.g., work), such as by being within 100 meters, 1 km, or 50 m of a GPS coordinate (or otherwise used in defining such location), then the second pre-defined destination (e.g., home) is selected (2406) automatically as a destination for a route from the current location, for which an ETA will be calculated. An override can be accepted (2407) through an interface, which would override the automatic selection. An ETA is then calculated (2408), and subsequently outputted using those parameters. Traffic congestion information (2413) can be used in selecting (2412) a route to be taken, on which the ETA calculated will be based. A plurality of locations can each be associated with a pre-defined destination, for which an ETA can be calculated upon proximity to the location to which that pre-defined destination is associated.
Therefore, it would be obvious to one of ordinary skill in the art prior to the effective filing date to modify Yang in light of Huang and Fink so that generate one or more network graphs based on the plurality of historical traffic values of the OD matrix, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of edges having corresponding weight values;
determine a modal route based on the one or more desired routes and the travel frequency data.
It would be obvious to one of ordinary skill in the art prior to the effective filing date to modify Yang in this way because a model such as a random forest regression model would be expected to be accurate at predicting the flow between OD pairs during particular times of day. This information would then effectively be traffic flow or density information, which previous references have used to assist in route determination. It would also be expected to be useful in this situation at allowing a system to determine which route is optimal.
For Claim 2, Yang teaches The system of claim 1, wherein the one or more predefined time slots correspond to one or more historical occurrences of a predefined time period of a day. ([0074] Specifically, the computer device may first perform trajectory segmentation on the target vehicle trajectory data to obtain candidate travel paths respectively corresponding to multiple candidate vehicles, each candidate travel path including a candidate origin and a candidate destination. For example, one vehicle trajectory corresponds to one candidate vehicle. If the historical time period includes travel time corresponding to a vehicle trajectory, the vehicle trajectory is determined as a candidate travel path, whose origin is determined as a candidate origin while destination is determined as a candidate destination. If a length of travel time corresponding to a vehicle trajectory is greater than that of the historical time period, and a starting moment is within the historical time period, the vehicle trajectory is segmented with the trajectory beyond the historical time period discarded to obtain a target vehicle trajectory, and the target vehicle trajectory is determined as a candidate travel path, whose origin is determined as a candidate origin while destination is determined as a candidate destination. If a length of travel time corresponding to a vehicle trajectory is greater than that of the historical time period, and an ending moment is within the historical time period, the vehicle trajectory is segmented with the trajectory before the historical time period discarded to obtain a target vehicle trajectory, and the target vehicle trajectory is determined as a candidate travel path, whose origin is determined as a candidate origin while destination is determined as a candidate destination. During trajectory segmentation, segmentation may be performed with reference to an actual trajectory and intention of the user. For example, a trajectory with a strong purpose is generated when an on-line hailed vehicle travels to pick up a passenger, a trajectory with a strong purpose is generated when the on-line hailed vehicle takes a passenger somewhere, and a trajectory with a strong purpose is generated when the vehicle contends for and is designated with an order in an empty state. After a trajectory is segmented, starting and ending positions in the trajectory are an origin and a destination.)
For Claim 3, Yang teaches The system of claim 1, wherein each of the plurality of edges of each of the one or more network graphs is associated with one of the one or more routes, and wherein the weight value of each of the plurality of edges is associated with historical traffic volume of a corresponding route from the one or more routes. ([0081] Specifically, the computer device may obtain a historical traffic flow corresponding to each target trip combination and a historical traffic flow corresponding to each segment based on the target traffic flow data. The computer device may perform an expansion process on the initial traffic flow corresponding to each target trip combination based on the target traffic flow data to roughly increase OD pairs passing through a specific segment in a certain ratio according to a historical section traffic flow to obtain an intermediate traffic flow corresponding to each target trip combination. For example, if an initial traffic flow corresponding to an OD pair in an initial trip matrix is 80, and it is determined according to the target traffic flow data that a historical traffic flow corresponding to the OD pair is 100, the initial traffic flow may be preliminarily expanded to 100. It can be understood that expansion ratios of different OD pairs may be the same or different. For example, a corresponding expansion ratio may be determined according to the corresponding initial traffic flow and historical traffic flow.)
For Claim 4, Yang teaches The system of claim 1, wherein the one or more routes lie between a source location and a destination location. ([0083] Urban traffic requirement mining refers to analyzing a trip requirement by a big data technology. Referring to FIG. 4, the computer device may mine traffic flows between different OD pairs in a city by combining historical vehicle trajectories of a private vehicle, a taxi, a bus, a truck, and an on-line hailed vehicle, mobile signaling, mobile APP positioning, a bus trip code, a geomagnetic coil, a checkpoint, and other data, to generate an OD matrix. Specifically, the computer device first segments a trip trajectory of a user from collected multi-source data to obtain a candidate travel path including a candidate origin and destination. Then, the computer device performs traffic cell absorption on the candidate origin/candidate destination. Traffic cell absorption is performed by searching for a closest reference point of interest according to the origin/destination. That is, origin clustering and destination clustering are performed. In this manner, the computer device may obtain a most primitive initial OD matrix statistically, i.e., a traffic OD matrix and candidate travel paths sampled from the reality. The initial OD matrix may include initial traffic flows corresponding to different OD pairs respectively. Further, the initial OD matrix may also include travel heat of different transportation means on paths between different OD pairs, i.e., the initial traffic flows corresponding to different transportation means between different OD pairs. Anomaly filtering is mainly for abnormal trajectories. For example, abnormal trajectories may be determined based on abnormal driving behaviors of a driver, such as abnormal stopping, waiting for an order by the road, staying for a long time in a region, and positioning trajectory drifting.)
For Claim 5, Yang teaches The system of claim 1, wherein the one or more processors are configured to:
generate a navigation recommendation based on the modal route.
[0131] Specifically, the computer device may generate auxiliary navigation data based on the simulated traffic condition in the current time period, and transmit the auxiliary navigation data to the navigation server. After receiving the auxiliary navigation data, the navigation server may learn a traffic condition corresponding to traffic reproduction in the current time period based on the auxiliary navigation data, and further perform navigation path planning for the terminal. For example, if a current moment is 8:00, and the current time period is 8:15 to 8:30, the simulated traffic condition in the current time period is a predicted future traffic condition. The user may initiate a navigation request with the terminal. The terminal transmits the navigation request containing a navigation origin and a navigation destination to the navigation server. The navigation server 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. After receiving the candidate navigation path, the terminal may display it to the user. Alternatively, the navigation server may learn a traffic condition corresponding to each simulation requirement in the current time period based on the auxiliary navigation data, and further perform navigation path planning for the terminal. For example, the navigation server may learn traffic conditions respectively corresponding to traffic reproduction and system optimization based on the auxiliary navigation data, and further perform navigation path planning based on a difference between the traffic conditions respectively corresponding to traffic reproduction and system optimization. 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.
For Claim 6, Yang teaches The system of claim 5,
Yang does not teach wherein the navigation recommendation is generated in an offline manner.
Coleman, however, does teach wherein the navigation recommendation is generated in an offline manner. ([0028] In some implementations, server device 102 can include map service 104. For example, map service 104 can be executed by a software server that provides backend processing for a map service provider. Map service 104 can, for example, obtain map data (e.g., map images, points of interest, etc.) from map data database 106 and send the map data to various client devices (e.g., user device 130) so that the client devices can present maps to the users of the client devices. Map service 104 can determine navigation and/or routing information using map data in map data database 106 and other data (e.g., real-time traffic data) and send the navigation and/or routing information to the client devices (e.g., user device 130) so that the client devices can present navigation information to the users of the client devices. Map service 104 can also send offline map data from map data database 106 to allow user device 130 to provide some map functions when user device 130 is offline in some implementations. For example, map service 104 can send map data to a client device while the client device is connected to server device 102 through network 150 (e.g., the Internet). The client device can present the map and/or navigation data to the user using a map or navigation application on the client device. The data can be presented through a graphical user interface (UI) of the application and/or through notifications that can pop up on a home screen of the client device and/or during operation of other applications.)
Therefore, it would be obvious to one of ordinary skill in the art to modify modified Yang so that the navigation recommendations can be generated offline because it would allow the system to provide instructions even if the vehicle is in a location in which an internet service cannot be found, or there is no connection. Navigations may be particularly valuable in remote areas, and this would allow them to be provided in that situation.
For Claim 9, Yang teaches The system of claim 1, wherein the one or more processors are further configured to:
predict, using a server, the modal route from the one or more desired routes for a future time slot associated with the one or more predefined time slots, wherein the server is based based on a plurality of traffic data and trip frequency data. ([0131] Specifically, the computer device may generate auxiliary navigation data based on the simulated traffic condition in the current time period, and transmit the auxiliary navigation data to the navigation server. After receiving the auxiliary navigation data, the navigation server may learn a traffic condition corresponding to traffic reproduction in the current time period based on the auxiliary navigation data, and further perform navigation path planning for the terminal. For example, if a current moment is 8:00, and the current time period is 8:15 to 8:30, the simulated traffic condition in the current time period is a predicted future traffic condition. The user may initiate a navigation request with the terminal. The terminal transmits the navigation request containing a navigation origin and a navigation destination to the navigation server. The navigation server 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. After receiving the candidate navigation path, the terminal may display it to the user. Alternatively, the navigation server may learn a traffic condition corresponding to each simulation requirement in the current time period based on the auxiliary navigation data, and further perform navigation path planning for the terminal. For example, the navigation server may learn traffic conditions respectively corresponding to traffic reproduction and system optimization based on the auxiliary navigation data, and further perform navigation path planning based on a difference between the traffic conditions respectively corresponding to traffic reproduction and system optimization. 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.)
Yang does not teach wherein the one or more processors are further configured to: predict, using a machine learning (ML) model, the modal route from the one or more desired routes for a future time slot associated with the one or more predefined time slots, wherein the ML model is trained based on a plurality of training network graphs and training trip frequency data.
Huang, however, does teach the use of training a machine learning (ML) model based on a plurality of training network graphs and training trip frequency data. ([0045] For illustration of this figure, in each OD pair (e.g., O1D1, O2D2), the traffic flows from the O point to the D point. In one example, locations O1 and D1 are respectively installed with the detectors 105 for capturing AVI data (first traffic volume data) for O1D1. In addition, the system 102 also obtains first trajectory data that passes through O1 and then D1. The system 102 may train the algorithm by supervised learning based on the first trajectory data and the first traffic volume data. For example, the first trajectory data may be at an earlier time and the first traffic volume data may be at a later time. For training, the algorithm may use the first traffic volume data as a ground truth to update weights of a model that predicts a later-time traffic volume based on an earlier-time trajectory data input. The trained algorithm can be used to predict a future traffic volume from O1 to D1 based on second trajectory data (e.g., more recent trajectory data between O1 and D1 than the first trajectory data) as input. The system 102 may control a traffic signal (not shown) based on the prediction. For example, the system 102 may control a traffic light at D1 to stay in green longer for a future time period, if a larger traffic flow is predicted for the future time period.)
Therefore, it would be obvious to one of ordinary skill in the art prior to the effective filing date to modify Yang in light of Huang such that wherein the one or more processors are further configured to: predict, using a machine learning (ML) model, the modal route from the one or more desired routes for a future time slot associated with the one or more predefined time slots, wherein the ML model is trained based on a plurality of training network graphs and training trip frequency data.
It would be obvious to one of ordinary skill in the art prior to the effective filing date to modify Yang in light of Huang in this way because machine learning models are expected to be successful at performing tasks such as finding optimal routes. Training the model to consider information such as traffic data (the network graph) and trip frequency data would be expected to be useful at helping it know which locations are likely to be heavily trafficked at what times. This would assist it in determining what the optimal path is from an origin to a destination.
For Claim 10, Yang teaches The system of claim 1,
wherein a travel time associated with each of the one or more desired routes is shortest among one or more travel times associated with the one or more routes other than the one or more desired routes in a corresponding mesoscopic traffic simulation. ([0096] Specifically, the computer device may finally assign different candidate travel paths to the target vehicle for different simulation requirements. Therefore, the computer device needs to first determine the simulation requirement, i.e., the simulation target, and then determine reference travel data corresponding to each target vehicle based on the simulation requirement. During mesoscopic traffic simulation, the computer device assigns the initial travel path to the target vehicle first, and the target vehicle travels in the simulated road network according to the initial travel path, and generates simulated travel data. If the simulated travel data differs not so greatly from the reference travel data, it indicates that the assigned initial travel path is reasonable and capable of meeting the simulation requirement, and the computer device may determine the initial travel path as a target travel path. If the simulated travel data differs greatly from the reference travel data, it indicates that the assigned initial travel path is unreasonable and incapable of meeting the simulation requirement. In such case, the computer device needs to assign a new initial travel path to the target vehicle, and the target vehicle travels in the simulated road network according to the new initial travel path, and generates new simulated travel data. If the simulated travel data still differs greatly from the reference travel data, a new initial travel path continues to be assigned to the target vehicle until the simulated travel data differs not so greatly from the reference travel data, and a latest initial travel path is determined as the target travel path. Therefore, the computer device may generate a travel loss based on a difference between simulated travel data of each target vehicle generated during simulated traveling and the corresponding reference travel data, adjust the initial travel path corresponding to each target vehicle based on the travel loss, and perform the operation of adding each target vehicle to the simulated road network according to departure time and initial travel path corresponding to each target vehicle until the travel loss satisfies a convergence condition to obtain a target travel path corresponding to each target vehicle. The convergence condition may be that the travel loss is less than a preset threshold, a number of iterations reaches a preset threshold, etc. Moreover, different simulation requirements may correspond to different preset thresholds.
Yang does not teach wherein a travel time associated with each of the one or more desired routes is shortest among one or more travel times associated with the one or more routes other than the one or more desired routes in a corresponding one or more network graphs.
Huang, however, does teach the use of network graphs; ([0068] In some embodiments, a random forest regression model may be used to predict {circumflex over (R)}.sub.i,j, the ratio of the maximum volume between OD pairs i and j:
[00006]R^i,j=f(ximax,xjmax,disi,j,ximaxxjmax,loci,locj)≈Yscale:iYscale:j
[0069] where the function f(⋅) stands for a random forest regression function. Random forests can be viewed as an ensemble learning method for regression that operates by constructing a multitude of regression trees for training and outputting the mean prediction of the individual trees. x.sub.i.sup.max is the maximum volume of the trajectory data for point pair i within one day, is the 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. For example, a toy size tree with only 5 leaf nodes is shown in FIG. 3E. This random forest model makes prediction for the maximum volume over certain OD pair based on this OD pair's geographical information and its neighboring information. In FIG. 3F, a standard factor importance analysis shows that the most important factor, x_ratio, is the ratio of the trajectory counts between pair i and j. The next two most important factors are x_max_i and x_max_j, the maximum trajectory volume on pair i and pair j, respectively. x_max_i is the maximum trajectory volume on pair i. dist_ij is the averaged distance between OD pair i and j. st_i_x and st_i_y stands for the longitude and latitude of the starting node of pair i. Similarly, end_i_x and end_i_y stands for the longitude and latitude of the destination node of pair i. This factor importance analysis shows that the random forest model is mostly based on the information from the trajectory data.
[0088] Block 401 comprises obtaining, by a processor (e.g., the processor 104) and from a plurality of computing devices (e.g., the computing devices 110, 111), time-series locations of a plurality of vehicles respectively associated with the computing devices, wherein: the time-series locations form first trajectory data comprising corresponding trajectories at least passing from a first point O to a second point D within a first time interval. Block 402 comprises obtaining, by a detector (e.g., the detector 105), a traffic volume between O and D for a second time interval that is temporally after the first time interval. Block 403 comprises training, by the processor, one or more weights of a neural network model by inputting the first trajectory data and the traffic volume to the neural network model and using the obtained traffic volume as ground truth to obtain a trained neural network model. Block 404 comprises inputting, by the processor, second trajectory data between O and D to the trained neural network model to predict a future traffic volume between O and D for the a future time interval.)
Therefore, it would be obvious to one of ordinary skill in the art prior to the effective filing date to modify Yang in light of Huang such that wherein a travel time associated with each of the one or more desired routes is shortest among one or more travel times associated with the one or more routes other than the one or more desired routes in a corresponding one or more network graphs. It would be obvious to one of ordinary skill in the art prior to the effective filing date to modify Yang in this way because it would allow modified Yang to select among already optimized paths before doing a final traffic analysis and seeing which one is likely to be the best during the current time period or situation. By allowing the shortest of paths to be considered, paths that are unlikely to be optimal are already weeded out of the analysis, and time and computing power can be saved.
For Claim 11, Yang teaches The system of claim 1, wherein the historical traffic values comprise traffic volume distribution for each of the one or more routes during the one or more predefined time slots. ([0102] obtaining a historical path traffic flow distribution probability corresponding to each target trip combination; performing, based on the historical path traffic flow distribution probability corresponding to the same target trip combination, traffic flow assignment on each corresponding candidate travel path to obtain an assigned traffic flow corresponding to each candidate travel path; and obtaining the initial travel path corresponding to each target vehicle based on each candidate travel path and the corresponding assigned traffic flow.
[0103] The historical path traffic flow distribution probability refers to a distribution probability of vehicles on each candidate travel path corresponding to the same OD pair. For example, an OD pair corresponds to three candidate travel paths, and a historical path traffic flow distribution probability is 1:1:1, it indicates that the target vehicles may be equally assigned to the three candidate travel paths. Different OD pairs may correspond to different historical path traffic flow distribution probabilities.
[0104] Specifically, the computer device may perform statistical analysis on a historical path traffic flow distribution corresponding to each target trip combination to obtain a historical path traffic flow distribution probability corresponding to each target trip combination. When travel paths are assigned to the vehicles for the first time, the computer device may perform, based on the historical path traffic flow distribution probability corresponding to the same target trip combination, traffic flow assignment on each corresponding candidate travel path to obtain an assigned traffic flow corresponding to each candidate travel path, and assign the target vehicles corresponding to the same assigned traffic flow to the corresponding candidate travel path, so as to obtain the initial travel path corresponding to each target vehicle. For example, an OD pair corresponds to a target traffic flow of 90 and three candidate travel paths, and a historical path traffic flow distribution probability is 1:1:1. In such case, an assigned traffic flow corresponding to candidate travel path 1 is 30, and initial travel paths corresponding to 30 target vehicles are candidate travel path 1; an assigned traffic flow corresponding to candidate travel path 2 is 30, and initial candidate travel paths corresponding to 30 target vehicles are candidate travel path 2; and an assigned traffic flow corresponding to candidate travel path 3 is 30, and initial travel paths corresponding to 30 target vehicles are candidate travel path 3.
[0105] In this embodiment, the initial travel path assigned to the target vehicle for the first time is determined based on the historical path traffic flow distribution probability, so that the reliability of the initial travel path may be improved, and iterative convergence is accelerated.
[0007] A traffic simulation apparatus is provided, including: a target trip matrix obtaining module, configured to obtain a target trip matrix corresponding to a current time period, the target trip matrix describing trip information in the current time period; a mesoscopic traffic simulation module, configured to perform mesoscopic traffic simulation on a target vehicle corresponding to the target trip matrix based on starting mesoscopic simulated traffic condition data corresponding to the current time period and a simulation requirement to obtain target travel data of the target vehicle in the current time period, the starting mesoscopic simulated traffic condition data being determined according to real-time microscopic simulated traffic condition data in a previous time period corresponding to the current time period, mesoscopic traffic simulation being traffic simulation directed to vehicle groups, and mesoscopic traffic simulation being used for assigning a target travel path corresponding to the simulation requirement to the target vehicle; and a microscopic traffic simulation module, configured to perform microscopic traffic simulation on a traveling vehicle in a simulated road network corresponding to the starting mesoscopic simulated traffic condition data based on the target travel data to obtain real-time microscopic simulated traffic condition data corresponding to the current time period, the real-time microscopic simulated traffic condition data being used for obtaining a simulated traffic condition corresponding to the simulation requirement in the current time period, and microscopic traffic simulation being traffic simulation directed to vehicle individuals.)
For Claim 12, Yang teaches A method comprising:
obtaining an origin-destination (OD) matrix associated with one or more routes, the OD matrix comprising a plurality of historical traffic values for one or more predefined time slots for each of the one or more routes; ([0083] Urban traffic requirement mining refers to analyzing a trip requirement by a big data technology. Referring to FIG. 4, the computer device may mine traffic flows between different OD pairs in a city by combining historical vehicle trajectories of a private vehicle, a taxi, a bus, a truck, and an on-line hailed vehicle, mobile signaling, mobile APP positioning, a bus trip code, a geomagnetic coil, a checkpoint, and other data, to generate an OD matrix. Specifically, the computer device first segments a trip trajectory of a user from collected multi-source data to obtain a candidate travel path including a candidate origin and destination. Then, the computer device performs traffic cell absorption on the candidate origin/candidate destination. Traffic cell absorption is performed by searching for a closest reference point of interest according to the origin/destination. That is, origin clustering and destination clustering are performed. In this manner, the computer device may obtain a most primitive initial OD matrix statistically, i.e., a traffic OD matrix and candidate travel paths sampled from the reality. The initial OD matrix may include initial traffic flows corresponding to different OD pairs respectively. Further, the initial OD matrix may also include travel heat of different transportation means on paths between different OD pairs, i.e., the initial traffic flows corresponding to different transportation means between different OD pairs. Anomaly filtering is mainly for abnormal trajectories. For example, abnormal trajectories may be determined based on abnormal driving behaviors of a driver, such as abnormal stopping, waiting for an order by the road, staying for a long time in a region, and positioning trajectory drifting.
[0084] Then, the computer device checks and expands the initial OD matrix by combining a traffic section flow such as a geomagnetic coil and a checkpoint, and complete data such as mobile signaling, to estimate a traffic OD matrix closest to the reality and used for describing complete trip information, so as to complete OD matrix estimation to obtain a historical OD matrix. The computer device may generate a target OD matrix based on the historical OD matrix, the target OD matrix describing a trip requirement in the current time period. Further, the computer device may perform traffic simulation based on the target OD matrix. The target OD matrix provides the trip requirement for traffic simulation. The target OD matrix or the initial OD matrix provides a candidate travel path for traffic simulation. In addition, parameter calibration may be performed on a traffic flow model in mesoscopic traffic simulation and an autonomous driving model in microscopic traffic simulation based on traffic data collected from the reality. The computer device may extract a traffic flow sample from a basic road network (i.e., the real road network), and perform data analysis on the traffic flow sample, so as to perform parameter calibration on the traffic flow model and the autonomous driving model. The traffic flow sample include massive statistical data of speeds, densities, flows, etc., of segments and sensor data returned in a real vehicle road test.)
wherein each of the one or more Matrices corresponds to one of the one or more predefined time slots, and wherein each of the one or more Matrices comprises a plurality of edges having corresponding weight values; ([0090] Step S504: Add each target vehicle to the simulated road network according to departure time and initial travel path corresponding to each target vehicle.
[0091] Step S506: Adjust a travel speed of each target vehicle dynamically during simulated traveling of each target vehicle based on the real-time mesoscopic simulated traffic condition data of the simulated road network until each target vehicle stops traveling.
[0092] Specifically, after determining the initial travel path corresponding to each target vehicle, the computer device may add each target vehicle to the simulated road network according to departure time and initial travel path corresponding to each target vehicle such that each target vehicle travels in the simulated road network. The computer device may adjust a travel speed of each target vehicle dynamically during simulated traveling of each target vehicle based on the real-time mesoscopic simulated traffic condition data of the simulated road network until each target vehicle travels to the corresponding destination, namely each target vehicle stops traveling. The departure time corresponding to each target vehicle may be determined according to historical path departure time distribution information. The historical path departure time distribution information refers to a distribution of departure time of vehicles on each candidate travel path corresponding to the same OD pair. Different OD pairs may correspond to different historical path departure time distribution information. For example, historical path departure time distribution information corresponding to an OD pair is that 20% of vehicles depart every 5 minutes on candidate travel path 1, 30% of vehicles depart every 3 minutes on candidate travel path 2, and 40% of vehicles depart every 7 minutes on candidate travel path 3.
[0069] Specifically, the computer device may obtain the target trip matrix based on the historical trip matrix, namely predicting the target trip matrix according to the historical trip matrix. The computer device may merge multiple historical trip matrices to obtain the target trip matrix. For example, it is assumed that a current moment in a real road network is 8:00 on Monday, actual traffic data after 8:00 is yet not generated, and the current time period is 8:00 to 8:15 on Monday. In such case, the computer device may obtain target vehicle trajectory data and target traffic flow data from 7:45 to 8:00 on Monday to generate a historical trip matrix A from 7:45 to 8:00 on Monday, obtain target vehicle trajectory data and target traffic flow data from 8:00 to 8:15 last week to generate a historical trip matrix B in 8:00 to 8:15 last week, and generate a target trip matrix corresponding to the current time period based on the historical trip matrix A and the historical trip matrix B. 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.)
determining one or more desired routes from the one or more routes based on the weight values, wherein each of the one or more desired routes is associated with one of the one or more OD Networks; ([0097] Step S512: Obtain target travel data of each target vehicle in the current time period based on the target travel path and departure time corresponding to each target vehicle.
[0098] Specifically, after determining the target travel path corresponding to each target vehicle, the computer device may obtain target travel data of each target vehicle in the current time period based on the target travel path and departure time corresponding to each target vehicle.
[0081] Specifically, the computer device may obtain a historical traffic flow corresponding to each target trip combination and a historical traffic flow corresponding to each segment based on the target traffic flow data. The computer device may perform an expansion process on the initial traffic flow corresponding to each target trip combination based on the target traffic flow data to roughly increase OD pairs passing through a specific segment in a certain ratio according to a historical section traffic flow to obtain an intermediate traffic flow corresponding to each target trip combination. For example, if an initial traffic flow corresponding to an OD pair in an initial trip matrix is 80, and it is determined according to the target traffic flow data that a historical traffic flow corresponding to the OD pair is 100, the initial traffic flow may be preliminarily expanded to 100. It can be understood that expansion ratios of different OD pairs may be the same or different. For example, a corresponding expansion ratio may be determined according to the corresponding initial traffic flow and historical traffic flow.
It should be noted that the weight can be representative of Traffic flow, which Yang does provide for each segment.)
determining travel frequency data for each of the one or more desired routes at least in the one or more predefined time slots based on the one or more OD Matrix; and ([0076] Further, the computer device may cluster the candidate travel paths corresponding to the same intermediate origin and intermediate destination to obtain multiple target trip combinations, the target trip combination including at least one candidate travel path corresponding to the same intermediate origin and intermediate destination. That is, the candidate travel paths corresponding to the same OD pair are clustered to obtain multiple different OD pairs and at least one candidate travel path corresponding to each OD pair. The computer device may obtain a number of the candidate vehicles corresponding to the same target trip combination statistically to obtain an initial traffic flow corresponding to each target trip combination, and further generate the initial trip matrix based on each target trip combination and the corresponding initial traffic flow and candidate travel path. The initial trip matrix includes multiple OD pairs, an initial traffic flow corresponding to each OD pair, and at least one candidate travel path corresponding to each OD pair. It can be understood that there may be at least one travel path from point A to point B, and thus an OD pair may correspond to at least one candidate travel path.
[0077] In this embodiment, trajectory segmentation is performed on the target vehicle trajectory data to obtain the candidate travel paths respectively corresponding to the multiple candidate vehicles, the candidate travel path including the candidate origin and the candidate destination, and origin clustering and destination clustering are performed on each candidate travel path based on the reference point of interest to obtain the intermediate origin and intermediate destination corresponding to each candidate travel path. In this manner, scattered origins and destinations may be clustered to landmark geographic positions to obtain candidate travel paths capable of reflecting a real traffic requirement more accurately. Then, the candidate travel paths corresponding to the same intermediate origin and intermediate destination are clustered to obtain the multiple target trip combinations. The number of the candidate vehicles corresponding to the same target trip combination is obtained statistically to obtain the initial traffic flow corresponding to each target trip combination, the target trip combination including the at least one candidate travel path corresponding to the same intermediate origin and intermediate destination. The initial trip matrix may be generated rapidly based on each target trip combination and the corresponding initial traffic flow and candidate travel path.
[0078] In an embodiment, the initial trip matrix includes multiple target trip combinations and an initial traffic flow corresponding to each target trip combination. The operation of adjusting the initial trip matrix based on the target traffic flow data to obtain a historical trip matrix corresponding to the historical time period includes:
[0079] performing an expansion process on the initial traffic flow corresponding to each target trip combination based on the target traffic flow data to obtain an intermediate traffic flow corresponding to each target trip combination; performing a check process on each intermediate traffic flow based on the target traffic flow data to obtain an estimated traffic flow corresponding to each target trip combination; and adjusting, based on the estimated traffic flow corresponding to each target trip combination, the corresponding initial traffic flow to obtain the historical trip matrix.)
determining a modal route based on the one or more desired routes and the travel frequency data. [0131] Specifically, the computer device may generate auxiliary navigation data based on the simulated traffic condition in the current time period, and transmit the auxiliary navigation data to the navigation server. After receiving the auxiliary navigation data, the navigation server may learn a traffic condition corresponding to traffic reproduction in the current time period based on the auxiliary navigation data, and further perform navigation path planning for the terminal. For example, if a current moment is 8:00, and the current time period is 8:15 to 8:30, the simulated traffic condition in the current time period is a predicted future traffic condition. The user may initiate a navigation request with the terminal. The terminal transmits the navigation request containing a navigation origin and a navigation destination to the navigation server. The navigation server 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. After receiving the candidate navigation path, the terminal may display it to the user. Alternatively, the navigation server may learn a traffic condition corresponding to each simulation requirement in the current time period based on the auxiliary navigation data, and further perform navigation path planning for the terminal. For example, the navigation server may learn traffic conditions respectively corresponding to traffic reproduction and system optimization based on the auxiliary navigation data, and further perform navigation path planning based on a difference between the traffic conditions respectively corresponding to traffic reproduction and system optimization. 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.
Yang does not teach generating one or more network graphs based on the plurality of historical traffic values of the OD matrix, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of edges having corresponding weight values;
Huang, however, does teach generating one or more network graphs based on the plurality of historical traffic values of the OD matrix, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of edges having corresponding weight values; ([0068] In some embodiments, a random forest regression model may be used to predict {circumflex over (R)}.sub.i,j, the ratio of the maximum volume between OD pairs i and j:
[00006]R^i,j=f(ximax,xjmax,disi,j,ximaxxjmax,loci,locj)≈Yscale:iYscale:j
[0069] where the function f(⋅) stands for a random forest regression function. Random forests can be viewed as an ensemble learning method for regression that operates by constructing a multitude of regression trees for training and outputting the mean prediction of the individual trees. x.sub.i.sup.max is the maximum volume of the trajectory data for point pair i within one day, is the 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. For example, a toy size tree with only 5 leaf nodes is shown in FIG. 3E. This random forest model makes prediction for the maximum volume over certain OD pair based on this OD pair's geographical information and its neighboring information. In FIG. 3F, a standard factor importance analysis shows that the most important factor, x_ratio, is the ratio of the trajectory counts between pair i and j. The next two most important factors are x_max_i and x_max_j, the maximum trajectory volume on pair i and pair j, respectively. x_max_i is the maximum trajectory volume on pair i. dist_ij is the averaged distance between OD pair i and j. st_i_x and st_i_y stands for the longitude and latitude of the starting node of pair i. Similarly, end_i_x and end_i_y stands for the longitude and latitude of the destination node of pair i. This factor importance analysis shows that the random forest model is mostly based on the information from the trajectory data.
[0088] Block 401 comprises obtaining, by a processor (e.g., the processor 104) and from a plurality of computing devices (e.g., the computing devices 110, 111), time-series locations of a plurality of vehicles respectively associated with the computing devices, wherein: the time-series locations form first trajectory data comprising corresponding trajectories at least passing from a first point O to a second point D within a first time interval. Block 402 comprises obtaining, by a detector (e.g., the detector 105), a traffic volume between O and D for a second time interval that is temporally after the first time interval. Block 403 comprises training, by the processor, one or more weights of a neural network model by inputting the first trajectory data and the traffic volume to the neural network model and using the obtained traffic volume as ground truth to obtain a trained neural network model. Block 404 comprises inputting, by the processor, second trajectory data between O and D to the trained neural network model to predict a future traffic volume between O and D for the a future time interval.)
Fink, however, does teach generating one or more network graphs based on the plurality of historical traffic values, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of edges having corresponding weight values; ([0052] One product of such a data collection and aggregation process is a "historical traffic model". In one example, a historical traffic model includes a list of traffic segments and associated time-of-day, day-of-week (and given enough time, week-of-year) time slots that contain expected traffic flow speeds (potentially with error estimates) during that time slot on that segment. Gaps can be filled with default "static" speeds. The model can be constructed as a large matrix, with rows representing traffic segments and columns representing time slots.
determining a modal route based on the one or more desired routes and the travel frequency data. ([0130] Rather, in an example method (FIG. 11), a current location of a device can be estimated (2403), such as by using GPS signal information, or an identity of a cell phone tower, triangulation of tower signals and so on. A comparison/determination (2405) between the current location and first and second pre-defined destination is made. If the current location is proximate a first pre-defined destination (e.g., work), such as by being within 100 meters, 1 km, or 50 m of a GPS coordinate (or otherwise used in defining such location), then the second pre-defined destination (e.g., home) is selected (2406) automatically as a destination for a route from the current location, for which an ETA will be calculated. An override can be accepted (2407) through an interface, which would override the automatic selection. An ETA is then calculated (2408), and subsequently outputted using those parameters. Traffic congestion information (2413) can be used in selecting (2412) a route to be taken, on which the ETA calculated will be based. A plurality of locations can each be associated with a pre-defined destination, for which an ETA can be calculated upon proximity to the location to which that pre-defined destination is associated.
Therefore, it would be obvious to one of ordinary skill in the art prior to the effective filing date to modify Yang in light of Huang and Fink so that generating one or more network graphs based on the plurality of historical traffic values of the OD matrix, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of edges having corresponding weight values;
determining a modal route based on the one or more desired routes and the travel frequency data.
It would be obvious to one of ordinary skill in the art prior to the effective filing date to modify Yang in this way because a model such as a random forest regression model would be expected to be accurate at predicting the flow between OD pairs during particular times of day. This information would then effectively be traffic flow or density information, which previous references have used to assist in route determination. It would also be expected to be useful in this situation at allowing a system to determine which route is optimal.
For Claim 13, Yang teaches The method of claim 12, further comprising:
generating a navigation recommendation based on the modal route. ([0131] Specifically, the computer device may generate auxiliary navigation data based on the simulated traffic condition in the current time period, and transmit the auxiliary navigation data to the navigation server. After receiving the auxiliary navigation data, the navigation server may learn a traffic condition corresponding to traffic reproduction in the current time period based on the auxiliary navigation data, and further perform navigation path planning for the terminal. For example, if a current moment is 8:00, and the current time period is 8:15 to 8:30, the simulated traffic condition in the current time period is a predicted future traffic condition. The user may initiate a navigation request with the terminal. The terminal transmits the navigation request containing a navigation origin and a navigation destination to the navigation server. The navigation server 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. After receiving the candidate navigation path, the terminal may display it to the user. Alternatively, the navigation server may learn a traffic condition corresponding to each simulation requirement in the current time period based on the auxiliary navigation data, and further perform navigation path planning for the terminal. For example, the navigation server may learn traffic conditions respectively corresponding to traffic reproduction and system optimization based on the auxiliary navigation data, and further perform navigation path planning based on a difference between the traffic conditions respectively corresponding to traffic reproduction and system optimization. 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.)
For Claim 16, Yang teaches The method of claim 12, further comprising:
predicting, using a server, the modal route from the one or more desired routes for a future time slot associated with the one or more predefined time slots, wherein the server is based on a plurality of traffic data and trip frequency data. ([0131] Specifically, the computer device may generate auxiliary navigation data based on the simulated traffic condition in the current time period, and transmit the auxiliary navigation data to the navigation server. After receiving the auxiliary navigation data, the navigation server may learn a traffic condition corresponding to traffic reproduction in the current time period based on the auxiliary navigation data, and further perform navigation path planning for the terminal. For example, if a current moment is 8:00, and the current time period is 8:15 to 8:30, the simulated traffic condition in the current time period is a predicted future traffic condition. The user may initiate a navigation request with the terminal. The terminal transmits the navigation request containing a navigation origin and a navigation destination to the navigation server. The navigation server 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. After receiving the candidate navigation path, the terminal may display it to the user. Alternatively, the navigation server may learn a traffic condition corresponding to each simulation requirement in the current time period based on the auxiliary navigation data, and further perform navigation path planning for the terminal. For example, the navigation server may learn traffic conditions respectively corresponding to traffic reproduction and system optimization based on the auxiliary navigation data, and further perform navigation path planning based on a difference between the traffic conditions respectively corresponding to traffic reproduction and system optimization. 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.)
Yang does not teach predicting, using a machine learning (ML) model, the modal route from the one or more desired routes for a future time slot associated with the one or more predefined time slots, wherein the ML model is trained based on a plurality of training network graphs and training trip frequency data.
Huang, however, does teach the use of training a machine learning (ML) model based on a plurality of training network graphs and training trip frequency data. ([0045] For illustration of this figure, in each OD pair (e.g., O1D1, O2D2), the traffic flows from the O point to the D point. In one example, locations O1 and D1 are respectively installed with the detectors 105 for capturing AVI data (first traffic volume data) for O1D1. In addition, the system 102 also obtains first trajectory data that passes through O1 and then D1. The system 102 may train the algorithm by supervised learning based on the first trajectory data and the first traffic volume data. For example, the first trajectory data may be at an earlier time and the first traffic volume data may be at a later time. For training, the algorithm may use the first traffic volume data as a ground truth to update weights of a model that predicts a later-time traffic volume based on an earlier-time trajectory data input. The trained algorithm can be used to predict a future traffic volume from O1 to D1 based on second trajectory data (e.g., more recent trajectory data between O1 and D1 than the first trajectory data) as input. The system 102 may control a traffic signal (not shown) based on the prediction. For example, the system 102 may control a traffic light at D1 to stay in green longer for a future time period, if a larger traffic flow is predicted for the future time period.)
Therefore, it would be obvious to one of ordinary skill in the art prior to the effective filing date to modify Yang in light of Huang such that predicting, using a machine learning (ML) model, the modal route from the one or more desired routes for a future time slot associated with the one or more predefined time slots, wherein the ML model is trained based on a plurality of training network graphs and training trip frequency data.
It would be obvious to one of ordinary skill in the art prior to the effective filing date to modify Yang in light of Huang in this way because machine learning models are expected to be successful at performing tasks such as finding optimal routes. Training the model to consider information such as traffic data (the network graph) and trip frequency data would be expected to be useful at helping it know which locations are likely to be heavily trafficked at what times. This would assist it in determining what the optimal path is from an origin to a destination.
For Claim 17, Yang teaches The method of claim 12, wherein the one or more predefined time slots correspond to one or more historical occurrences of a predefined time period of a day. (([0074] Specifically, the computer device may first perform trajectory segmentation on the target vehicle trajectory data to obtain candidate travel paths respectively corresponding to multiple candidate vehicles, each candidate travel path including a candidate origin and a candidate destination. For example, one vehicle trajectory corresponds to one candidate vehicle. If the historical time period includes travel time corresponding to a vehicle trajectory, the vehicle trajectory is determined as a candidate travel path, whose origin is determined as a candidate origin while destination is determined as a candidate destination. If a length of travel time corresponding to a vehicle trajectory is greater than that of the historical time period, and a starting moment is within the historical time period, the vehicle trajectory is segmented with the trajectory beyond the historical time period discarded to obtain a target vehicle trajectory, and the target vehicle trajectory is determined as a candidate travel path, whose origin is determined as a candidate origin while destination is determined as a candidate destination. If a length of travel time corresponding to a vehicle trajectory is greater than that of the historical time period, and an ending moment is within the historical time period, the vehicle trajectory is segmented with the trajectory before the historical time period discarded to obtain a target vehicle trajectory, and the target vehicle trajectory is determined as a candidate travel path, whose origin is determined as a candidate origin while destination is determined as a candidate destination. During trajectory segmentation, segmentation may be performed with reference to an actual trajectory and intention of the user. For example, a trajectory with a strong purpose is generated when an on-line hailed vehicle travels to pick up a passenger, a trajectory with a strong purpose is generated when the on-line hailed vehicle takes a passenger somewhere, and a trajectory with a strong purpose is generated when the vehicle contends for and is designated with an order in an empty state. After a trajectory is segmented, starting and ending positions in the trajectory are an origin and a destination.))
For Claim 18, Yang teaches The method of claim 12, wherein each of the plurality of edges of each of the one or more network graphs is associated with one of the one or more routes, and wherein the weight value of each of the plurality of edges is associated with historical traffic volume of a corresponding route from the one or more routes. (([0081] Specifically, the computer device may obtain a historical traffic flow corresponding to each target trip combination and a historical traffic flow corresponding to each segment based on the target traffic flow data. The computer device may perform an expansion process on the initial traffic flow corresponding to each target trip combination based on the target traffic flow data to roughly increase OD pairs passing through a specific segment in a certain ratio according to a historical section traffic flow to obtain an intermediate traffic flow corresponding to each target trip combination. For example, if an initial traffic flow corresponding to an OD pair in an initial trip matrix is 80, and it is determined according to the target traffic flow data that a historical traffic flow corresponding to the OD pair is 100, the initial traffic flow may be preliminarily expanded to 100. It can be understood that expansion ratios of different OD pairs may be the same or different. For example, a corresponding expansion ratio may be determined according to the corresponding initial traffic flow and historical traffic flow.))
For Claim 19, Yang teaches The method of claim 12, wherein the one or more routes lie between a source location and a destination location. (([0083] Urban traffic requirement mining refers to analyzing a trip requirement by a big data technology. Referring to FIG. 4, the computer device may mine traffic flows between different OD pairs in a city by combining historical vehicle trajectories of a private vehicle, a taxi, a bus, a truck, and an on-line hailed vehicle, mobile signaling, mobile APP positioning, a bus trip code, a geomagnetic coil, a checkpoint, and other data, to generate an OD matrix. Specifically, the computer device first segments a trip trajectory of a user from collected multi-source data to obtain a candidate travel path including a candidate origin and destination. Then, the computer device performs traffic cell absorption on the candidate origin/candidate destination. Traffic cell absorption is performed by searching for a closest reference point of interest according to the origin/destination. That is, origin clustering and destination clustering are performed. In this manner, the computer device may obtain a most primitive initial OD matrix statistically, i.e., a traffic OD matrix and candidate travel paths sampled from the reality. The initial OD matrix may include initial traffic flows corresponding to different OD pairs respectively. Further, the initial OD matrix may also include travel heat of different transportation means on paths between different OD pairs, i.e., the initial traffic flows corresponding to different transportation means between different OD pairs. Anomaly filtering is mainly for abnormal trajectories. For example, abnormal trajectories may be determined based on abnormal driving behaviors of a driver, such as abnormal stopping, waiting for an order by the road, staying for a long time in a region, and positioning trajectory drifting.))
For Claim 20, 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: ([0009] A computer device is provided, including a memory and one or more processors, the memory storing computer-readable instructions, and 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.)
obtaining an origin-destination (OD) matrix associated with one or more routes, the OD matrix comprising a plurality of historical traffic values for one or more predefined time slots for each of the one or more routes; ([0083] Urban traffic requirement mining refers to analyzing a trip requirement by a big data technology. Referring to FIG. 4, the computer device may mine traffic flows between different OD pairs in a city by combining historical vehicle trajectories of a private vehicle, a taxi, a bus, a truck, and an on-line hailed vehicle, mobile signaling, mobile APP positioning, a bus trip code, a geomagnetic coil, a checkpoint, and other data, to generate an OD matrix. Specifically, the computer device first segments a trip trajectory of a user from collected multi-source data to obtain a candidate travel path including a candidate origin and destination. Then, the computer device performs traffic cell absorption on the candidate origin/candidate destination. Traffic cell absorption is performed by searching for a closest reference point of interest according to the origin/destination. That is, origin clustering and destination clustering are performed. In this manner, the computer device may obtain a most primitive initial OD matrix statistically, i.e., a traffic OD matrix and candidate travel paths sampled from the reality. The initial OD matrix may include initial traffic flows corresponding to different OD pairs respectively. Further, the initial OD matrix may also include travel heat of different transportation means on paths between different OD pairs, i.e., the initial traffic flows corresponding to different transportation means between different OD pairs. Anomaly filtering is mainly for abnormal trajectories. For example, abnormal trajectories may be determined based on abnormal driving behaviors of a driver, such as abnormal stopping, waiting for an order by the road, staying for a long time in a region, and positioning trajectory drifting.
[0084] Then, the computer device checks and expands the initial OD matrix by combining a traffic section flow such as a geomagnetic coil and a checkpoint, and complete data such as mobile signaling, to estimate a traffic OD matrix closest to the reality and used for describing complete trip information, so as to complete OD matrix estimation to obtain a historical OD matrix. The computer device may generate a target OD matrix based on the historical OD matrix, the target OD matrix describing a trip requirement in the current time period. Further, the computer device may perform traffic simulation based on the target OD matrix. The target OD matrix provides the trip requirement for traffic simulation. The target OD matrix or the initial OD matrix provides a candidate travel path for traffic simulation. In addition, parameter calibration may be performed on a traffic flow model in mesoscopic traffic simulation and an autonomous driving model in microscopic traffic simulation based on traffic data collected from the reality. The computer device may extract a traffic flow sample from a basic road network (i.e., the real road network), and perform data analysis on the traffic flow sample, so as to perform parameter calibration on the traffic flow model and the autonomous driving model. The traffic flow sample include massive statistical data of speeds, densities, flows, etc., of segments and sensor data returned in a real vehicle road test.)
wherein each of the one or more Matrices corresponds to one of the one or more predefined time slots, and wherein each of the one or more Matrices comprises a plurality of edges having corresponding weight values; ([0090] Step S504: Add each target vehicle to the simulated road network according to departure time and initial travel path corresponding to each target vehicle.
[0091] Step S506: Adjust a travel speed of each target vehicle dynamically during simulated traveling of each target vehicle based on the real-time mesoscopic simulated traffic condition data of the simulated road network until each target vehicle stops traveling.
[0092] Specifically, after determining the initial travel path corresponding to each target vehicle, the computer device may add each target vehicle to the simulated road network according to departure time and initial travel path corresponding to each target vehicle such that each target vehicle travels in the simulated road network. The computer device may adjust a travel speed of each target vehicle dynamically during simulated traveling of each target vehicle based on the real-time mesoscopic simulated traffic condition data of the simulated road network until each target vehicle travels to the corresponding destination, namely each target vehicle stops traveling. The departure time corresponding to each target vehicle may be determined according to historical path departure time distribution information. The historical path departure time distribution information refers to a distribution of departure time of vehicles on each candidate travel path corresponding to the same OD pair. Different OD pairs may correspond to different historical path departure time distribution information. For example, historical path departure time distribution information corresponding to an OD pair is that 20% of vehicles depart every 5 minutes on candidate travel path 1, 30% of vehicles depart every 3 minutes on candidate travel path 2, and 40% of vehicles depart every 7 minutes on candidate travel path 3.
[0069] Specifically, the computer device may obtain the target trip matrix based on the historical trip matrix, namely predicting the target trip matrix according to the historical trip matrix. The computer device may merge multiple historical trip matrices to obtain the target trip matrix. For example, it is assumed that a current moment in a real road network is 8:00 on Monday, actual traffic data after 8:00 is yet not generated, and the current time period is 8:00 to 8:15 on Monday. In such case, the computer device may obtain target vehicle trajectory data and target traffic flow data from 7:45 to 8:00 on Monday to generate a historical trip matrix A from 7:45 to 8:00 on Monday, obtain target vehicle trajectory data and target traffic flow data from 8:00 to 8:15 last week to generate a historical trip matrix B in 8:00 to 8:15 last week, and generate a target trip matrix corresponding to the current time period based on the historical trip matrix A and the historical trip matrix B. 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.)
determining one or more desired routes from the one or more routes based on the weight values, wherein each of the one or more desired routes is associated with one of the one or more OD Networks; ([0097] Step S512: Obtain target travel data of each target vehicle in the current time period based on the target travel path and departure time corresponding to each target vehicle.
[0098] Specifically, after determining the target travel path corresponding to each target vehicle, the computer device may obtain target travel data of each target vehicle in the current time period based on the target travel path and departure time corresponding to each target vehicle.
[0081] Specifically, the computer device may obtain a historical traffic flow corresponding to each target trip combination and a historical traffic flow corresponding to each segment based on the target traffic flow data. The computer device may perform an expansion process on the initial traffic flow corresponding to each target trip combination based on the target traffic flow data to roughly increase OD pairs passing through a specific segment in a certain ratio according to a historical section traffic flow to obtain an intermediate traffic flow corresponding to each target trip combination. For example, if an initial traffic flow corresponding to an OD pair in an initial trip matrix is 80, and it is determined according to the target traffic flow data that a historical traffic flow corresponding to the OD pair is 100, the initial traffic flow may be preliminarily expanded to 100. It can be understood that expansion ratios of different OD pairs may be the same or different. For example, a corresponding expansion ratio may be determined according to the corresponding initial traffic flow and historical traffic flow.
It should be noted that the weight can be representative of Traffic flow, which Yang does provide for each segment.)
determining travel frequency data for each of the one or more desired routes at least in the one or more predefined time slots based on the one or more OD Matrix; and ([0076] Further, the computer device may cluster the candidate travel paths corresponding to the same intermediate origin and intermediate destination to obtain multiple target trip combinations, the target trip combination including at least one candidate travel path corresponding to the same intermediate origin and intermediate destination. That is, the candidate travel paths corresponding to the same OD pair are clustered to obtain multiple different OD pairs and at least one candidate travel path corresponding to each OD pair. The computer device may obtain a number of the candidate vehicles corresponding to the same target trip combination statistically to obtain an initial traffic flow corresponding to each target trip combination, and further generate the initial trip matrix based on each target trip combination and the corresponding initial traffic flow and candidate travel path. The initial trip matrix includes multiple OD pairs, an initial traffic flow corresponding to each OD pair, and at least one candidate travel path corresponding to each OD pair. It can be understood that there may be at least one travel path from point A to point B, and thus an OD pair may correspond to at least one candidate travel path.
[0077] In this embodiment, trajectory segmentation is performed on the target vehicle trajectory data to obtain the candidate travel paths respectively corresponding to the multiple candidate vehicles, the candidate travel path including the candidate origin and the candidate destination, and origin clustering and destination clustering are performed on each candidate travel path based on the reference point of interest to obtain the intermediate origin and intermediate destination corresponding to each candidate travel path. In this manner, scattered origins and destinations may be clustered to landmark geographic positions to obtain candidate travel paths capable of reflecting a real traffic requirement more accurately. Then, the candidate travel paths corresponding to the same intermediate origin and intermediate destination are clustered to obtain the multiple target trip combinations. The number of the candidate vehicles corresponding to the same target trip combination is obtained statistically to obtain the initial traffic flow corresponding to each target trip combination, the target trip combination including the at least one candidate travel path corresponding to the same intermediate origin and intermediate destination. The initial trip matrix may be generated rapidly based on each target trip combination and the corresponding initial traffic flow and candidate travel path.
[0078] In an embodiment, the initial trip matrix includes multiple target trip combinations and an initial traffic flow corresponding to each target trip combination. The operation of adjusting the initial trip matrix based on the target traffic flow data to obtain a historical trip matrix corresponding to the historical time period includes:
[0079] performing an expansion process on the initial traffic flow corresponding to each target trip combination based on the target traffic flow data to obtain an intermediate traffic flow corresponding to each target trip combination; performing a check process on each intermediate traffic flow based on the target traffic flow data to obtain an estimated traffic flow corresponding to each target trip combination; and adjusting, based on the estimated traffic flow corresponding to each target trip combination, the corresponding initial traffic flow to obtain the historical trip matrix.)
determining a modal route based on the one or more desired routes and the travel frequency data. [0131] Specifically, the computer device may generate auxiliary navigation data based on the simulated traffic condition in the current time period, and transmit the auxiliary navigation data to the navigation server. After receiving the auxiliary navigation data, the navigation server may learn a traffic condition corresponding to traffic reproduction in the current time period based on the auxiliary navigation data, and further perform navigation path planning for the terminal. For example, if a current moment is 8:00, and the current time period is 8:15 to 8:30, the simulated traffic condition in the current time period is a predicted future traffic condition. The user may initiate a navigation request with the terminal. The terminal transmits the navigation request containing a navigation origin and a navigation destination to the navigation server. The navigation server 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. After receiving the candidate navigation path, the terminal may display it to the user. Alternatively, the navigation server may learn a traffic condition corresponding to each simulation requirement in the current time period based on the auxiliary navigation data, and further perform navigation path planning for the terminal. For example, the navigation server may learn traffic conditions respectively corresponding to traffic reproduction and system optimization based on the auxiliary navigation data, and further perform navigation path planning based on a difference between the traffic conditions respectively corresponding to traffic reproduction and system optimization. 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.
Yang does not teach generating one or more network graphs based on the plurality of historical traffic values of the OD matrix, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of edges having corresponding weight values;
Huang, however, does teach generating one or more network graphs based on the plurality of historical traffic values of the OD matrix, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of edges having corresponding weight values; ([0068] In some embodiments, a random forest regression model may be used to predict {circumflex over (R)}.sub.i,j, the ratio of the maximum volume between OD pairs i and j:
[00006]R^i,j=f(ximax,xjmax,disi,j,ximaxxjmax,loci,locj)≈Yscale:iYscale:j
[0069] where the function f(⋅) stands for a random forest regression function. Random forests can be viewed as an ensemble learning method for regression that operates by constructing a multitude of regression trees for training and outputting the mean prediction of the individual trees. x.sub.i.sup.max is the maximum volume of the trajectory data for point pair i within one day, is the 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. For example, a toy size tree with only 5 leaf nodes is shown in FIG. 3E. This random forest model makes prediction for the maximum volume over certain OD pair based on this OD pair's geographical information and its neighboring information. In FIG. 3F, a standard factor importance analysis shows that the most important factor, x_ratio, is the ratio of the trajectory counts between pair i and j. The next two most important factors are x_max_i and x_max_j, the maximum trajectory volume on pair i and pair j, respectively. x_max_i is the maximum trajectory volume on pair i. dist_ij is the averaged distance between OD pair i and j. st_i_x and st_i_y stands for the longitude and latitude of the starting node of pair i. Similarly, end_i_x and end_i_y stands for the longitude and latitude of the destination node of pair i. This factor importance analysis shows that the random forest model is mostly based on the information from the trajectory data.
[0088] Block 401 comprises obtaining, by a processor (e.g., the processor 104) and from a plurality of computing devices (e.g., the computing devices 110, 111), time-series locations of a plurality of vehicles respectively associated with the computing devices, wherein: the time-series locations form first trajectory data comprising corresponding trajectories at least passing from a first point O to a second point D within a first time interval. Block 402 comprises obtaining, by a detector (e.g., the detector 105), a traffic volume between O and D for a second time interval that is temporally after the first time interval. Block 403 comprises training, by the processor, one or more weights of a neural network model by inputting the first trajectory data and the traffic volume to the neural network model and using the obtained traffic volume as ground truth to obtain a trained neural network model. Block 404 comprises inputting, by the processor, second trajectory data between O and D to the trained neural network model to predict a future traffic volume between O and D for the a future time interval.)
Fink, however, does teach generating one or more network graphs based on the plurality of historical traffic values, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of edges having corresponding weight values; ([0052] One product of such a data collection and aggregation process is a "historical traffic model". In one example, a historical traffic model includes a list of traffic segments and associated time-of-day, day-of-week (and given enough time, week-of-year) time slots that contain expected traffic flow speeds (potentially with error estimates) during that time slot on that segment. Gaps can be filled with default "static" speeds. The model can be constructed as a large matrix, with rows representing traffic segments and columns representing time slots.
determining a modal route based on the one or more desired routes and the travel frequency data. ([0130] Rather, in an example method (FIG. 11), a current location of a device can be estimated (2403), such as by using GPS signal information, or an identity of a cell phone tower, triangulation of tower signals and so on. A comparison/determination (2405) between the current location and first and second pre-defined destination is made. If the current location is proximate a first pre-defined destination (e.g., work), such as by being within 100 meters, 1 km, or 50 m of a GPS coordinate (or otherwise used in defining such location), then the second pre-defined destination (e.g., home) is selected (2406) automatically as a destination for a route from the current location, for which an ETA will be calculated. An override can be accepted (2407) through an interface, which would override the automatic selection. An ETA is then calculated (2408), and subsequently outputted using those parameters. Traffic congestion information (2413) can be used in selecting (2412) a route to be taken, on which the ETA calculated will be based. A plurality of locations can each be associated with a pre-defined destination, for which an ETA can be calculated upon proximity to the location to which that pre-defined destination is associated.
Therefore, it would be obvious to one of ordinary skill in the art prior to the effective filing date to modify Yang in light of Huang and Fink so that generating one or more network graphs based on the plurality of historical traffic values of the OD matrix, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of edges having corresponding weight values;
determining a modal route based on the one or more desired routes and the travel frequency data.
It would be obvious to one of ordinary skill in the art prior to the effective filing date to modify Yang in this way because a model such as a random forest regression model would be expected to be accurate at predicting the flow between OD pairs during particular times of day. This information would then effectively be traffic flow or density information, which previous references have used to assist in route determination. It would also be expected to be useful in this situation at allowing a system to determine which route is optimal.
Claim 6 is rejected under 35 U.S.C. 103 as being unpatentable over Yang in light of Huang in light of Fink in light of Coleman et al (US Pub 2021/0063189 A1), hereafter known as Coleman..
For Claim 6, Yang teaches The system of claim 5,
Yang does not teach wherein the navigation recommendation is generated in an offline manner.
Coleman, however, does teach wherein the navigation recommendation is generated in an offline manner. ([0028] In some implementations, server device 102 can include map service 104. For example, map service 104 can be executed by a software server that provides backend processing for a map service provider. Map service 104 can, for example, obtain map data (e.g., map images, points of interest, etc.) from map data database 106 and send the map data to various client devices (e.g., user device 130) so that the client devices can present maps to the users of the client devices. Map service 104 can determine navigation and/or routing information using map data in map data database 106 and other data (e.g., real-time traffic data) and send the navigation and/or routing information to the client devices (e.g., user device 130) so that the client devices can present navigation information to the users of the client devices. Map service 104 can also send offline map data from map data database 106 to allow user device 130 to provide some map functions when user device 130 is offline in some implementations. For example, map service 104 can send map data to a client device while the client device is connected to server device 102 through network 150 (e.g., the Internet). The client device can present the map and/or navigation data to the user using a map or navigation application on the client device. The data can be presented through a graphical user interface (UI) of the application and/or through notifications that can pop up on a home screen of the client device and/or during operation of other applications.)
Therefore, it would be obvious to one of ordinary skill in the art to modify modified Yang so that the navigation recommendations can be generated offline because it would allow the system to provide instructions even if the vehicle is in a location in which an internet service cannot be found, or there is no connection. Navigations may be particularly valuable in remote areas, and this would allow them to be provided in that situation.
Claims 7 and 14 are rejected under 35 U.S.C. 103 as being unpatentable over Yang in light of Huang in light of Fink in light of Schunder et al (US Pub 2011/0166774 A1), hereafter known as Schunder.
For Claim 7, Yang teaches The system of claim 1, wherein the one or more processors are configured to:
determine the one or more desired routes based on the one or more OD Matrix associated with the one or more predefined time slots; ([0097] Step S512: Obtain target travel data of each target vehicle in the current time period based on the target travel path and departure time corresponding to each target vehicle.
[0098] Specifically, after determining the target travel path corresponding to each target vehicle, the computer device may obtain target travel data of each target vehicle in the current time period based on the target travel path and departure time corresponding to each target vehicle.
[0081] Specifically, the computer device may obtain a historical traffic flow corresponding to each target trip combination and a historical traffic flow corresponding to each segment based on the target traffic flow data. The computer device may perform an expansion process on the initial traffic flow corresponding to each target trip combination based on the target traffic flow data to roughly increase OD pairs passing through a specific segment in a certain ratio according to a historical section traffic flow to obtain an intermediate traffic flow corresponding to each target trip combination. For example, if an initial traffic flow corresponding to an OD pair in an initial trip matrix is 80, and it is determined according to the target traffic flow data that a historical traffic flow corresponding to the OD pair is 100, the initial traffic flow may be preliminarily expanded to 100. It can be understood that expansion ratios of different OD pairs may be the same or different. For example, a corresponding expansion ratio may be determined according to the corresponding initial traffic flow and historical traffic flow.
It should be noted that the weight can be representative of Traffic flow, which Yang does provide for each segment.)
determine the travel frequency data for each of the one or more desired routes; and ([0076] Further, the computer device may cluster the candidate travel paths corresponding to the same intermediate origin and intermediate destination to obtain multiple target trip combinations, the target trip combination including at least one candidate travel path corresponding to the same intermediate origin and intermediate destination. That is, the candidate travel paths corresponding to the same OD pair are clustered to obtain multiple different OD pairs and at least one candidate travel path corresponding to each OD pair. The computer device may obtain a number of the candidate vehicles corresponding to the same target trip combination statistically to obtain an initial traffic flow corresponding to each target trip combination, and further generate the initial trip matrix based on each target trip combination and the corresponding initial traffic flow and candidate travel path. The initial trip matrix includes multiple OD pairs, an initial traffic flow corresponding to each OD pair, and at least one candidate travel path corresponding to each OD pair. It can be understood that there may be at least one travel path from point A to point B, and thus an OD pair may correspond to at least one candidate travel path.
[0077] In this embodiment, trajectory segmentation is performed on the target vehicle trajectory data to obtain the candidate travel paths respectively corresponding to the multiple candidate vehicles, the candidate travel path including the candidate origin and the candidate destination, and origin clustering and destination clustering are performed on each candidate travel path based on the reference point of interest to obtain the intermediate origin and intermediate destination corresponding to each candidate travel path. In this manner, scattered origins and destinations may be clustered to landmark geographic positions to obtain candidate travel paths capable of reflecting a real traffic requirement more accurately. Then, the candidate travel paths corresponding to the same intermediate origin and intermediate destination are clustered to obtain the multiple target trip combinations. The number of the candidate vehicles corresponding to the same target trip combination is obtained statistically to obtain the initial traffic flow corresponding to each target trip combination, the target trip combination including the at least one candidate travel path corresponding to the same intermediate origin and intermediate destination. The initial trip matrix may be generated rapidly based on each target trip combination and the corresponding initial traffic flow and candidate travel path.
[0078] In an embodiment, the initial trip matrix includes multiple target trip combinations and an initial traffic flow corresponding to each target trip combination. The operation of adjusting the initial trip matrix based on the target traffic flow data to obtain a historical trip matrix corresponding to the historical time period includes:
[0079] performing an expansion process on the initial traffic flow corresponding to each target trip combination based on the target traffic flow data to obtain an intermediate traffic flow corresponding to each target trip combination; performing a check process on each intermediate traffic flow based on the target traffic flow data to obtain an estimated traffic flow corresponding to each target trip combination; and adjusting, based on the estimated traffic flow corresponding to each target trip combination, the corresponding initial traffic flow to obtain the historical trip matrix.)
Yang does not teach determine the one or more desired routes based on the one or more network graphs associated with the one or more predefined time slots;
determine the travel frequency data for each of the one or more desired routes; and
determine the modal route from the one or more desired routes based on an aggregation of the one or more desired routes and the corresponding travel frequency data.
Huang, however, does teach using network graphs. Huang, however, does teach generate one or more network graphs based on the plurality of historical traffic values of the OD matrix, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of edges having corresponding weight values; ([0068] In some embodiments, a random forest regression model may be used to predict {circumflex over (R)}.sub.i,j, the ratio of the maximum volume between OD pairs i and j:
[00006]R^i,j=f(ximax,xjmax,disi,j,ximaxxjmax,loci,locj)≈Yscale:iYscale:j
[0069] where the function f(⋅) stands for a random forest regression function. Random forests can be viewed as an ensemble learning method for regression that operates by constructing a multitude of regression trees for training and outputting the mean prediction of the individual trees. x.sub.i.sup.max is the maximum volume of the trajectory data for point pair i within one day, is the 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. For example, a toy size tree with only 5 leaf nodes is shown in FIG. 3E. This random forest model makes prediction for the maximum volume over certain OD pair based on this OD pair's geographical information and its neighboring information. In FIG. 3F, a standard factor importance analysis shows that the most important factor, x_ratio, is the ratio of the trajectory counts between pair i and j. The next two most important factors are x_max_i and x_max_j, the maximum trajectory volume on pair i and pair j, respectively. x_max_i is the maximum trajectory volume on pair i. dist_ij is the averaged distance between OD pair i and j. st_i_x and st_i_y stands for the longitude and latitude of the starting node of pair i. Similarly, end_i_x and end_i_y stands for the longitude and latitude of the destination node of pair i. This factor importance analysis shows that the random forest model is mostly based on the information from the trajectory data.
[0088] Block 401 comprises obtaining, by a processor (e.g., the processor 104) and from a plurality of computing devices (e.g., the computing devices 110, 111), time-series locations of a plurality of vehicles respectively associated with the computing devices, wherein: the time-series locations form first trajectory data comprising corresponding trajectories at least passing from a first point O to a second point D within a first time interval. Block 402 comprises obtaining, by a detector (e.g., the detector 105), a traffic volume between O and D for a second time interval that is temporally after the first time interval. Block 403 comprises training, by the processor, one or more weights of a neural network model by inputting the first trajectory data and the traffic volume to the neural network model and using the obtained traffic volume as ground truth to obtain a trained neural network model. Block 404 comprises inputting, by the processor, second trajectory data between O and D to the trained neural network model to predict a future traffic volume between O and D for the a future time interval.)
Schunder, however, does teach determine the modal route from the one or more desired routes based on an aggregation of the one or more desired routes and the corresponding travel frequency data. ([0004] Alternatively, the system may wish to calculate the shortest route, or one that avoids certain roads, such as highways or unpaved roads. Using data associated with roads, such as classifications, the system can avoid roads of certain types. Also, using pure distances to be traveled, the system can calculate the shortest route to a location, even if it isn't the fastest route.
[0061] The calculations can be predictive in nature. For example, if the present time is 6:00 P.M. and a particular area along a route is twenty five minutes away, the GPS may predictively consider historic traffic patterns at 6:25 P.M., the projected time of arrival. Traffic lights, presumably, will not move, although system data may include information on when the lights are functioning and when the lights are flashing yellows, for example, allowing traffic to flow through. Real-time traffic patterns may also be considered, although they may have less value at initial route calculation the further along the route they are (i.e., the more time there is for them to change before the user arrives at that point).
[0048] The final results of the calculation are then output as the route most likely to use the least amount of fuel in the aggregate 217. This may vary from a route that simply consumes the least amount of fuel, as a route which consumes slightly more fuel may use the least amount of fuel in the aggregate due to regeneration over that route.)
Therefore, it would be obvious to one of ordinary skill in the art prior to the effective filing date to modify Yang in light of Schunder such that a modal route is determined from the other desired routes and corresponding traffic data because considering a number of potential routes and selecting the best one is a common and effective method of providing an optimal route from a series. The decision to incorporate traffic data into the decision would allow the system to bypass heavy trafficked areas that may slow down the route and make it take longer.
For Claim 14, Yang teaches The method of claim 12, further comprising:
determining the one or more desired routes based on the one or more OD Matrix associated with the one or more predefined time slots; ([0097] Step S512: Obtain target travel data of each target vehicle in the current time period based on the target travel path and departure time corresponding to each target vehicle.
[0098] Specifically, after determining the target travel path corresponding to each target vehicle, the computer device may obtain target travel data of each target vehicle in the current time period based on the target travel path and departure time corresponding to each target vehicle.
[0081] Specifically, the computer device may obtain a historical traffic flow corresponding to each target trip combination and a historical traffic flow corresponding to each segment based on the target traffic flow data. The computer device may perform an expansion process on the initial traffic flow corresponding to each target trip combination based on the target traffic flow data to roughly increase OD pairs passing through a specific segment in a certain ratio according to a historical section traffic flow to obtain an intermediate traffic flow corresponding to each target trip combination. For example, if an initial traffic flow corresponding to an OD pair in an initial trip matrix is 80, and it is determined according to the target traffic flow data that a historical traffic flow corresponding to the OD pair is 100, the initial traffic flow may be preliminarily expanded to 100. It can be understood that expansion ratios of different OD pairs may be the same or different. For example, a corresponding expansion ratio may be determined according to the corresponding initial traffic flow and historical traffic flow.
It should be noted that the weight can be representative of Traffic flow, which Yang does provide for each segment.)
determining the travel frequency data for each of the one or more desired routes; and ([0076] Further, the computer device may cluster the candidate travel paths corresponding to the same intermediate origin and intermediate destination to obtain multiple target trip combinations, the target trip combination including at least one candidate travel path corresponding to the same intermediate origin and intermediate destination. That is, the candidate travel paths corresponding to the same OD pair are clustered to obtain multiple different OD pairs and at least one candidate travel path corresponding to each OD pair. The computer device may obtain a number of the candidate vehicles corresponding to the same target trip combination statistically to obtain an initial traffic flow corresponding to each target trip combination, and further generate the initial trip matrix based on each target trip combination and the corresponding initial traffic flow and candidate travel path. The initial trip matrix includes multiple OD pairs, an initial traffic flow corresponding to each OD pair, and at least one candidate travel path corresponding to each OD pair. It can be understood that there may be at least one travel path from point A to point B, and thus an OD pair may correspond to at least one candidate travel path.
[0077] In this embodiment, trajectory segmentation is performed on the target vehicle trajectory data to obtain the candidate travel paths respectively corresponding to the multiple candidate vehicles, the candidate travel path including the candidate origin and the candidate destination, and origin clustering and destination clustering are performed on each candidate travel path based on the reference point of interest to obtain the intermediate origin and intermediate destination corresponding to each candidate travel path. In this manner, scattered origins and destinations may be clustered to landmark geographic positions to obtain candidate travel paths capable of reflecting a real traffic requirement more accurately. Then, the candidate travel paths corresponding to the same intermediate origin and intermediate destination are clustered to obtain the multiple target trip combinations. The number of the candidate vehicles corresponding to the same target trip combination is obtained statistically to obtain the initial traffic flow corresponding to each target trip combination, the target trip combination including the at least one candidate travel path corresponding to the same intermediate origin and intermediate destination. The initial trip matrix may be generated rapidly based on each target trip combination and the corresponding initial traffic flow and candidate travel path.
[0078] In an embodiment, the initial trip matrix includes multiple target trip combinations and an initial traffic flow corresponding to each target trip combination. The operation of adjusting the initial trip matrix based on the target traffic flow data to obtain a historical trip matrix corresponding to the historical time period includes:
[0079] performing an expansion process on the initial traffic flow corresponding to each target trip combination based on the target traffic flow data to obtain an intermediate traffic flow corresponding to each target trip combination; performing a check process on each intermediate traffic flow based on the target traffic flow data to obtain an estimated traffic flow corresponding to each target trip combination; and adjusting, based on the estimated traffic flow corresponding to each target trip combination, the corresponding initial traffic flow to obtain the historical trip matrix.)
Yang does not teach determine the one or more desired routes based on the one or more network graphs associated with the one or more predefined time slots;
determine the travel frequency data for each of the one or more desired routes; and
determining the modal route from the one or more desired routes based on an aggregation of the one or more desired routes and the corresponding travel frequency data.
Huang, however, does teach using network graphs. Huang, however, does teach generating one or more network graphs based on the plurality of historical traffic values of the OD matrix, wherein each of the one or more network graphs corresponds to one of the one or more predefined time slots, and wherein each of the one or more network graphs comprises a plurality of edges having corresponding weight values; ([0068] In some embodiments, a random forest regression model may be used to predict {circumflex over (R)}.sub.i,j, the ratio of the maximum volume between OD pairs i and j:
[00006]R^i,j=f(ximax,xjmax,disi,j,ximaxxjmax,loci,locj)≈Yscale:iYscale:j
[0069] where the function f(⋅) stands for a random forest regression function. Random forests can be viewed as an ensemble learning method for regression that operates by constructing a multitude of regression trees for training and outputting the mean prediction of the individual trees. x.sub.i.sup.max is the maximum volume of the trajectory data for point pair i within one day, is the 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. For example, a toy size tree with only 5 leaf nodes is shown in FIG. 3E. This random forest model makes prediction for the maximum volume over certain OD pair based on this OD pair's geographical information and its neighboring information. In FIG. 3F, a standard factor importance analysis shows that the most important factor, x_ratio, is the ratio of the trajectory counts between pair i and j. The next two most important factors are x_max_i and x_max_j, the maximum trajectory volume on pair i and pair j, respectively. x_max_i is the maximum trajectory volume on pair i. dist_ij is the averaged distance between OD pair i and j. st_i_x and st_i_y stands for the longitude and latitude of the starting node of pair i. Similarly, end_i_x and end_i_y stands for the longitude and latitude of the destination node of pair i. This factor importance analysis shows that the random forest model is mostly based on the information from the trajectory data.
[0088] Block 401 comprises obtaining, by a processor (e.g., the processor 104) and from a plurality of computing devices (e.g., the computing devices 110, 111), time-series locations of a plurality of vehicles respectively associated with the computing devices, wherein: the time-series locations form first trajectory data comprising corresponding trajectories at least passing from a first point O to a second point D within a first time interval. Block 402 comprises obtaining, by a detector (e.g., the detector 105), a traffic volume between O and D for a second time interval that is temporally after the first time interval. Block 403 comprises training, by the processor, one or more weights of a neural network model by inputting the first trajectory data and the traffic volume to the neural network model and using the obtained traffic volume as ground truth to obtain a trained neural network model. Block 404 comprises inputting, by the processor, second trajectory data between O and D to the trained neural network model to predict a future traffic volume between O and D for the a future time interval.)
Schunder, however, does teach determining the modal route from the one or more desired routes based on an aggregation of the one or more desired routes and the corresponding travel frequency data. ([0004] Alternatively, the system may wish to calculate the shortest route, or one that avoids certain roads, such as highways or unpaved roads. Using data associated with roads, such as classifications, the system can avoid roads of certain types. Also, using pure distances to be traveled, the system can calculate the shortest route to a location, even if it isn't the fastest route.
[0061] The calculations can be predictive in nature. For example, if the present time is 6:00 P.M. and a particular area along a route is twenty five minutes away, the GPS may predictively consider historic traffic patterns at 6:25 P.M., the projected time of arrival. Traffic lights, presumably, will not move, although system data may include information on when the lights are functioning and when the lights are flashing yellows, for example, allowing traffic to flow through. Real-time traffic patterns may also be considered, although they may have less value at initial route calculation the further along the route they are (i.e., the more time there is for them to change before the user arrives at that point).
[0048] The final results of the calculation are then output as the route most likely to use the least amount of fuel in the aggregate 217. This may vary from a route that simply consumes the least amount of fuel, as a route which consumes slightly more fuel may use the least amount of fuel in the aggregate due to regeneration over that route.)
Therefore, it would be obvious to one of ordinary skill in the art prior to the effective filing date to modify Yang in light of Schunder such that a modal route is determined from the other desired routes and corresponding traffic data because considering a number of potential routes and selecting the best one is a common and effective method of providing an optimal route from a series. The decision to incorporate traffic data into the decision would allow the system to bypass heavy trafficked areas that may slow down the route and make it take longer.
Claims 8 and 15 are rejected under 35 U.S.C. 103 as being unpatentable over Yang in light of Huang in light of Fink in light of Becker et al (US Pub 2020/0011690 A1), hereafter known as Becker.
For Claim 8, Yang teaches The system of claim 1, wherein the one or more processors are configured to:
Yang does not teach determine the one or more desired routes based on applying a shortest path function on each of the one or more network graphs.
Becker, however, does teach determine the one or more desired routes based on applying a shortest path function on each of the one or more network graphs. ([0041] Conventional algorithms for establishing a route reaching a plurality of waypoints computes the time and distances between pairs of waypoints as described above with respect to the matrix of FIG. 3. An initial sequence of waypoints may be determined according to algorithms such as “nearest neighbor” which chooses the shortest path between waypoints to reach each waypoint, or “shortest time” which chooses the shortest trip time between waypoints as established when the matrix is created.)
Therefore it would be obvious to one of ordinary skill in the art prior to the effective filing date to modify modified Yang in light of Becker so that a shortest path function is applied on the network graph because a shortest path function is expected to be an effective method to take a network graph and determine what may be optimal paths.
For Claim 15, Yang teaches The method of claim 12, further comprising:
Yang does not teach determining the one or more desired routes based on applying a shortest path function on each of the one or more network graphs.
Becker, however, does teach determining the one or more desired routes based on applying a shortest path function on each of the one or more network graphs. ([0041] Conventional algorithms for establishing a route reaching a plurality of waypoints computes the time and distances between pairs of waypoints as described above with respect to the matrix of FIG. 3. An initial sequence of waypoints may be determined according to algorithms such as “nearest neighbor” which chooses the shortest path between waypoints to reach each waypoint, or “shortest time” which chooses the shortest trip time between waypoints as established when the matrix is created.)
Therefore it would be obvious to one of ordinary skill in the art prior to the effective filing date to modify modified Yang in light of Becker so that a shortest path function is applied on the network graph because a shortest path function is expected to be an effective method to take a network graph and determine what may be optimal paths.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Patil et al (US Pub 2015/0168164 A1), relates to navigation using shortest path algorithms.
Lim et al (US Pub 2018/0252540 A1), relates to determining optimal paths using traffic and shortest paths.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to TRISTAN J GREINER whose telephone number is (571)272-1382. The examiner can normally be reached Mon - Fri 7:30-4:30.
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, Khoi Tran can be reached at Monday-Thursday. 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.
/T.J.G./Examiner, Art Unit 3656
/KHOI H TRAN/Supervisory Patent Examiner, Art Unit 3656
Prosecution Insights