DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claims 1-20 have been presented for examination based on the application filed on
06/27/2023.
Claim(s) 1, 10-20 is/are rejected under 35 U.S.C. 102 (a)(2) as being anticipated by US PGPUB No. US20140278052A1 by Slavin et al.
Claim(s) 2-9 is/are rejected under 35 U.S.C. 103 as being unpatentable over US Patent No. US20140278052A1 by Slavin et al. in further view of US Patent No. CN110570660A by ZHANG XIAOCHUN.
This action is made Non-Final.
---- This page is left blank after this line ----
The lengthy specification has not been checked to the extent necessary to determine the presence of all possible minor errors. Applicant’s cooperation is requested in correcting any errors of which applicant may become aware in the specification.
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.
The text of those sections of Title 35, U.S. Code not included in this action can be found in a prior Office action.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an
abstract idea without significantly more. The claim recites "performing conversion according to the first vehicle traffic data to obtain second vehicle traffic data," which is an abstract idea falling within the "mathematical concepts" grouping. The specification describes this conversion through mathematical relationships and formulas used to calculate distances and orientations.
This abstract idea is not integrated into a practical application. The additional elements of "obtaining data," "running a simulation," and the use of a "computer device" merely link the abstract idea to the technological environment of traffic simulation. The claim recites a desired outcome (conversion) without reciting the specific technical mechanism for achieving it, which amounts to a mere instruction to "apply" the exception on a computer.
The additional elements do not amount to significantly more. The "computer device" is a generic tool performing conventional functions such as data gathering and record keeping. These elements, taken individually and in combination, consist of well-understood, routine, conventional activity in the art and insignificant extra-solution activity that fail to transform the abstract idea into a patent-eligible invention.
Claims [ 1 ]:
Step 1: the claims are drawn to a method and system respectively, falling under one of the four statutory categories of invention.
Step 2A, Prong 1: This part of the eligibility analysis evaluates whether the claim recites a judicial exception. As explained in MPEP 2106.04, subsection II, a claim “recites” a judicial exception when the judicial exception is “set forth” or “described” in the claim. The limitations are bolded for abstract idea/judicial exception identification.
Claim 1
Mapping Under Step 2A Prong 1
A traffic simulation conversion method, the method being performed by a computer device, and the method comprising:
obtaining first vehicle traffic data of a vehicle in a first traffic simulation;
performing conversion according to the first vehicle traffic data to obtain second vehicle traffic data of the vehicle in a second traffic simulation;
and running the second traffic simulation according to the second vehicle traffic data of the vehicle,
wherein the first traffic simulation and the second traffic simulation comprises one of a microscopic traffic simulation and a mesoscopic traffic simulation, and the first traffic simulation is different from the second traffic simulation.
See Step 2A Prong 2
See Step 2A Prong 2
Mental Processes: The act of performing a conversion calculation can be performed in the human mind or by a human using a pen and paper. While the scale of traffic simulation may be complex, the individual steps of data manipulation and coordinate conversion are "human cognitive actions" performed via a computer tool. (see MPEP § 2106.04(a)(2), subsection III)
Mathematical Concepts: The core of the claim is "performing conversion1" between traffic simulations. The specification describes this conversion through mathematical relationships, formulas, and calculations related to road section serial numbers, distances from road origins, and vehicle orientations. Under MPEP § 2106.04(a)(2), "mathematical concepts" such as formulas, equations, and mathematical calculations are identified as a grouping of abstract ideas. (as in 2106.04(a)(2) Abstract Idea Groupings)
Mental Processes: The act of using the results to run a simulation describe concepts that can be performed in the human mind or by a human using a pen and paper. While the scale of traffic simulation may be complex, the individual steps of data manipulation and coordinate conversion are "human cognitive actions" performed via a computer tool. (see MPEP § 2106.04(a)(2), subsection III)
See Step 2A Prong 2
Step 2A, Prong 2: This part of the eligibility analysis evaluates whether the claim as a whole integrates the recited judicial exception into a practical application of the exception. This evaluation is performed by (1) identifying whether there are any additional elements recited in the claim beyond the judicial exception, and (2) evaluating those additional elements individually and in combination to determine whether the claim as a whole integrates the exception into a practical application. See MPEP 2106.04(d). As per (1) the additional elements are identified as bolded parts of the limitations in column 1 of the table below, and as per (2) the evaluation is shown in the mapping section of the table.
In accordance with this step, the judicial exception is not integrated into a practical application.
Claim 1
Mapping Under Step 2A Prong 2
A traffic simulation conversion method, the method being performed by a computer device, and the method comprising:
obtaining first vehicle traffic data of a vehicle in a first traffic simulation;
performing conversion according to the first vehicle traffic data to obtain second vehicle traffic data of the vehicle in a second traffic simulation;
and running the second traffic simulation according to the second vehicle traffic data of the vehicle,
wherein the first traffic simulation and the second traffic simulation comprises one of a microscopic traffic simulation and a mesoscopic traffic simulation, and the first traffic simulation is different from the second traffic simulation
Additional Elements: The additional elements include a "computer device2” (mere data gathering) (MPEP § 2106.05(g))
Insignificant Extra-Solution Activity: "Obtaining" data is recognized by the courts as mere data-gathering, and "running" a simulation is a generic use of the converted data; both are insignificant extra-solution activities (See Bilski, 561 U.S. at 610, 95 USPQ2d at 1009 (citing Parker v. Flook, 437 U.S. 584, 590, 198 USPQ 193, 197 (1978)), and CyberSource v. Retail Decisions, 654 F.3d 1366, 1370, 99 USPQ2d 1690 (Fed. Cir. 2011) (citations omitted))( See MPEP § 2106.05(g) & (h))
See Step 2A Prong 1
See Step 2A Prong 1
Field of Use: Generally linking the mathematical conversion to the "traffic simulation" environment constitutes a "field of use" or "technological environment" limitation, which does not integrate the exception into a practical application. (2106.04(d)(1)) (See MPEP § 2106.05(f))( See, e.g., Rapid Litigation Management v. CellzDirect, Inc., 827 F.3d 1042, 119 USPQ2d 1370 (Fed. Cir. 2016)) ( See Internet Patents Corporation v. Active Network, Inc., 790 F.3d 1343, 1348, 115 USPQ2d 1414, 1418 (Fed. Cir. 2015))
Step 2B: This part of the eligibility analysis evaluates whether the claim as a whole amounts 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. See MPEP 2106.05. This step determines whether the additional elements amount to "significantly more" than the exception by providing an unconventional technological solution. (see MPEP § 2106.05(g) and see MPEP § 2106.05(h))
"Obtaining first data" is characterized as "mere data gathering," which is considered insignificant extra-solution activity. Executing the transformations and predictive model on a "computer" requires only well-understood, routine, and conventional computer functions (storing/retrieving data, performing calculations).
Conclusion: The additional elements do not amount to significantly more.
Claim 2 recites, “The method according to claim 1, (See Claim 1) wherein the first traffic simulation comprises the mesoscopic traffic simulation, and the second traffic simulation comprises the microscopic traffic simulation; obtaining first vehicle traffic data of a vehicle in a first traffic simulation comprises: obtaining the first vehicle traffic data of the vehicle in the mesoscopic traffic simulation, the first vehicle traffic data comprising a serial number of a road section that the vehicle is on and a distance from a current position of the vehicle to an origin of the road section that the vehicle is on; and performing conversion according to the first vehicle traffic data to obtain second vehicle traffic data of the vehicle in a second traffic simulation comprises: performing conversion according to the serial number of the road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the road section that the vehicle is on to obtain the second vehicle traffic data of the vehicle in the microscopic traffic simulation, the second vehicle traffic data comprising a longitude and a latitude of the vehicle and a front orientation of the vehicle.”
Insignificant Extra-Solution Activity: "Obtaining" data is recognized by the courts as mere data-gathering, and "running" a simulation is a generic use of the converted data; both are insignificant extra-solution activities (See Bilski, 561 U.S. at 610, 95 USPQ2d at 1009 (citing Parker v. Flook, 437 U.S. 584, 590, 198 USPQ 193, 197 (1978)), and CyberSource v. Retail Decisions, 654 F.3d 1366, 1370, 99 USPQ2d 1690 (Fed. Cir. 2011) (citations omitted))( See MPEP § 2106.05(g) & (h))
Claim 3 recites, “The method according to claim 2, (See Claim 2) wherein performing conversion according to the serial number of the road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the road section that the vehicle is on to obtain the second vehicle traffic data of the vehicle in the microscopic traffic simulation comprises:
determining, when a type of the road section that the vehicle is on is a road, the longitude and the latitude of the vehicle according to a serial number of a road that the vehicle is on and a distance from the current position of the vehicle to an origin of the road that the vehicle is on; or determining, when a type of the road section that the vehicle is on is a connecting road section, the longitude and the latitude of the vehicle according to a serial number of a connecting road section that the vehicle is on and a distance from the current position of the vehicle to an origin of the connecting road section that the vehicle is on.” (Mental Processes)(see MPEP § 2106.04(a)(2), subsection III) (Mathematical Concepts) (as in 2106.04(a)(2) Abstract Idea Groupings)
Claim 4 recites, “The method according to claim 3, (See Claim 3) wherein the road that the vehicle is on in the microscopic traffic simulation comprises N discrete points arranged in order, N being a positive integer; and determining the longitude and the latitude of the vehicle according to the serial number of the road that the vehicle is on and the distance from the current position of the vehicle to an origin of the road that the vehicle is on comprises: determining, when the type of the road section that the vehicle is on is a road, a longitude and a latitude of an ith discrete point closest to the current position of the vehicle in the N discrete points in the road that the vehicle is on as the longitude and the latitude of the vehicle according to the serial number of the road that the vehicle is on and the distance from the current position of the vehicle to the origin of the road that the vehicle is on, i being a positive integer less than N.” (Mental Processes)(see MPEP § 2106.04(a)(2), subsection III) (Mathematical Concepts) (as in 2106.04(a)(2) Abstract Idea Groupings)
Claim 5 recites, “The method according to claim 4, (See Claim 4) wherein determining a longitude and a latitude of an ith discrete point closest to the current position of the vehicle in the N discrete points in the road that the vehicle is on as the longitude and the latitude of the vehicle according to the serial number of the road that the vehicle is on and the distance from the current position of the vehicle to the origin of the road that the vehicle is on comprises: obtaining a distance between adjacent discrete points in the N discrete points according to the serial number of the road that the vehicle is on;
determining a distance from each of the N discrete points in the road that the vehicle is on to the origin of the road that the vehicle is on by accumulating the distance between the adjacent discrete points; calculating a difference between the distance from each of the N discrete points to the origin of the road that the vehicle is on and the distance from the current position of the vehicle to the origin of the road that the vehicle is on; and determining the longitude and the latitude of the ith discrete point corresponding to a minimum difference as the longitude and the latitude of the vehicle, i being a positive integer less than or equal to N.” (Mental Processes)(see MPEP § 2106.04(a)(2), subsection III) (Mathematical Concepts) (as in 2106.04(a)(2) Abstract Idea Groupings)
Claim 6 recites, “The method according to claim 3, (See claim 3) wherein connecting road section that the vehicle is on in the microscopic traffic simulation comprises M discrete points arranged in order, M being a positive integer; and determining the longitude and the latitude of the vehicle according to a serial number of the connecting road section that the vehicle is on and a distance from the current position of the vehicle to an origin of the connecting road section that the vehicle is on comprises: determining a longitude and a latitude of an ith discrete point closest to the current position of the vehicle in the M discrete points in the connecting road section that the vehicle is on as the longitude and the latitude of the vehicle according to the serial number of the connecting road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the connecting road section that the vehicle is on, i being a positive integer less than M.” (Mental Processes)(see MPEP § 2106.04(a)(2), subsection III) (Mathematical Concepts) (as in 2106.04(a)(2) Abstract Idea Groupings)
Claim 7 recites, “The method according to claim 6, (See claim 6) wherein determining a longitude and a latitude of an ith discrete point closest to the current position of the vehicle in the M discrete points in the connecting road section that the vehicle is on as the longitude and the latitude of the vehicle according to the serial number of the connecting road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the connecting road section that the vehicle is on comprises: obtaining a distance between adjacent discrete points in the M discrete points according to the serial number of the connecting road section that the vehicle is on; determining a distance from each of the M discrete points in the connecting road section that the vehicle is on to the origin of the connecting road section that the vehicle is on by accumulating the distance between the adjacent discrete points; calculating a difference between the distance from each of the M discrete points to the origin of the connecting road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the connecting road section that the vehicle is on; and determining the longitude and the latitude of the ith discrete point corresponding to a minimum difference as the longitude and the latitude of the vehicle, i being a positive integer less than or equal to M.” (Mental Processes)(see MPEP § 2106.04(a)(2), subsection III) (Mathematical Concepts) (as in 2106.04(a)(2) Abstract Idea Groupings)
Claim 8 recites, “The method according to claim 2, (See Claim 2) wherein performing conversion according to the serial number of the road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the road section that the vehicle is on to obtain the second vehicle traffic data of the vehicle in the microscopic traffic simulation comprises: determining the front orientation of the vehicle according to a serial number of a road that the vehicle is on and a distance from the current position of the vehicle to an origin of the road that the vehicle is on.” (Mental Processes)(see MPEP § 2106.04(a)(2), subsection III) (Mathematical Concepts) (as in 2106.04(a)(2) Abstract Idea Groupings)
Claim 9 recites, “The method according to claim 8, (See claim 8) wherein determining the front orientation of the vehicle according to a serial number of a road that the vehicle is on and a distance from the current position of the vehicle to an origin of the road that the vehicle is on comprises:
determining an ith discrete point closest to the current position of the vehicle according to the serial number of the road that the vehicle is on and the distance from the current position of the vehicle to the origin of the road that the vehicle is on; and determining the front orientation of the vehicle according to the ith discrete point and an (i−1)th discrete point, i being an integer less than N+1 and greater than 1.” (Mental Processes)(see MPEP § 2106.04(a)(2), subsection III) (Mathematical Concepts) (as in 2106.04(a)(2) Abstract Idea Groupings)
Claim 10 recites, “The method according to claim 1, (See claim 1) wherein the first traffic simulation comprises the microscopic traffic simulation, and the second traffic simulation comprises the mesoscopic traffic simulation; obtaining first vehicle traffic data of a vehicle in a first traffic simulation comprises: obtaining the first vehicle traffic data of the vehicle in the microscopic traffic simulation, the first vehicle traffic data comprising a serial number of a road section that the vehicle is on, a longitude and a latitude of the vehicle, and a speed of the vehicle; and performing conversion according to the first vehicle traffic data to obtain second vehicle traffic data of the vehicle in a second traffic simulation comprises at least one of the following operations: performing conversion according to the serial number of the road section that the vehicle is on and the longitude and the latitude of the vehicle to obtain a distance from a current position of the vehicle to an origin of the road section that the vehicle is on in the mesoscopic traffic simulation; and performing conversion according to the serial number of the road section that the vehicle is on, the longitude and the latitude of the vehicle, and the speed of the vehicle to obtain landing time of the vehicle on a next road in the mesoscopic traffic simulation.” (Mental Processes)(see MPEP § 2106.04(a)(2), subsection III) (Mathematical Concepts) (as in 2106.04(a)(2) Abstract Idea Groupings)
Claim 11 recites, “The method according to claim 10, (See claim 10) wherein the road that the vehicle is on comprises N discrete points, N being a positive integer; and determining a distance from the current position of the vehicle to an origin of the road that the vehicle is on according to a serial number of the road that the vehicle is on and the longitude and the latitude of the vehicle comprises:
determining an ith discrete point closest to the current position of the vehicle according to longitudes and latitudes of the N discrete points and the longitude and the latitude of the vehicle, i being a positive integer less than N; and determining the distance from the current position of the vehicle to the origin of the road that the vehicle is on according to a distance from the ith discrete point to the origin of the road that the vehicle is on and a distance from the ith discrete point to the current position of the vehicle.” (Mental Processes)(see MPEP § 2106.04(a)(2), subsection III) (Mathematical Concepts) (as in 2106.04(a)(2) Abstract Idea Groupings)
Claim 12 recites, “The method according to claim 10, (See Claim 10) wherein a connecting road section that the vehicle is on comprises M discrete points arranged in order, M being a positive integer; and
determining of the landing time of the vehicle on the next road according to a serial number of the connecting road section that the vehicle is on, the longitude and the latitude of the vehicle, and the speed of the vehicle comprises: determining an ith discrete point closest to the current position of the vehicle according to longitudes and latitudes of the M discrete points and the longitude and the latitude of the vehicle, i being a positive integer less than M; and determining, according to a distance from the ith discrete point to an origin of the connecting road section that the vehicle is on, a distance from the ith discrete point to the current position of the vehicle, the speed of the vehicle, and a total length of the connecting road section that the vehicle is on, the landing time of the vehicle on the next road.” (Mental Processes)(see MPEP § 2106.04(a)(2), subsection III) (Mathematical Concepts) (as in 2106.04(a)(2) Abstract Idea Groupings)
Claim 13 recites, “The method according to claim 1, (See Claim 1) wherein the method further comprises: obtaining a microscopic traffic simulation region; displaying the microscopic traffic simulation in the microscopic traffic simulation region, and displaying the mesoscopic traffic simulation in a mesoscopic traffic simulation region other than the microscopic traffic simulation region; and displaying microscopic vehicle traffic data in the microscopic traffic simulation region, and displaying mesoscopic vehicle traffic data in the mesoscopic traffic simulation region, the microscopic vehicle traffic data being vehicle traffic data of a microscopic vehicle, and the mesoscopic vehicle traffic data being vehicle traffic data of a mesoscopic vehicle.” (Mental Processes)(see MPEP § 2106.04(a)(2), subsection III)
Claim 14 recites, “The method according to claim 1, (See claim 1) wherein the method further comprises: determining, in response to a traffic prediction operation, mesoscopic vehicle traffic data in the mesoscopic traffic simulation based on microscopic vehicle traffic data in the microscopic traffic simulation; converting, for a vehicle in a prediction region, the microscopic traffic simulation to the mesoscopic traffic simulation according to the microscopic vehicle traffic data and the mesoscopic vehicle traffic data; and displaying a predicted traffic status according to the mesoscopic traffic simulation.” (Mental Processes)(see MPEP § 2106.04(a)(2), subsection III) (Mathematical Concepts) (as in 2106.04(a)(2) Abstract Idea Groupings)
Claim 15Step 1: Machine
Step 2A Prong 1: similar to claim 1
Step 2A Prong 2: similar to claim 1
Step 2B: similar to claim 1
Claim 16Step 1: Machine
Step 2A Prong 1: similar to claim 2
Step 2A Prong 2: similar to claim 2
Step 2B: similar to claim 2
Claim 17Step 1: Machine
Step 2A Prong 1: similar to claim 10
Step 2A Prong 2: similar to claim 10
Step 2B: similar to claim 10
Claim 18Step 1: Article of Manufacturer
Step 2A Prong 1: similar to claim 1
Step 2A Prong 2: similar to claim 1
Step 2B: similar to claim 1Claim 19Step 1: Article of Manufacturer
Step 2A Prong 1: similar to claim 2
Step 2A Prong 2: similar to claim 2
Step 2B: similar to claim 2
Claim 20Step 1: Article of Manufacturer
Step 2A Prong 1: similar to claim 10
Step 2A Prong 2: similar to claim 10
Step 2B: similar to claim 10
Claim Rejections - 35 USC § 102
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 the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
The text of those sections of Title 35, U.S. Code not included in this action can be found in a prior Office action.
Claim(s) 1, 10-20is/are rejected under 35 U.S.C. 102 (a)(2) as being anticipated by US PGPUB No. US20140278052A1 by Slavin et al.
Regarding Claim 1
Slavin teaches A traffic simulation conversion method, the method being performed by a computer device, and the method comprising: (Abstract: “A lane-level vehicle routing and navigation apparatus includes a simulation module that performs microsimulation of individual vehicles in a traffic stream, and a lane-level optimizer that evaluates conditions along the candidate paths from an origin to a destination as determined by the simulation module, and determines recommended lane-level maneuvers along the candidate paths. A link-level optimizer may determines the candidate paths based on link travel times determined by the simulation module. The simulation may be based on real-time traffic condition data. Recommended candidate paths may be provided to delivery or service or emergency response vehicles, or used for evacuation planning, or to route vehicles such as garbage or postal trucks, or snowplows. Corresponding methods also may be used for traffic planning and management, including determining, based on microsimulation, at least one of (a) altered road geometry, (b) altered traffic signal settings, such as traffic signal timing, or (c) road pricing.” [0046]: “FIG. 2 illustrates the context in which systems according to embodiments of the invention may operate. Hardware commonly found in the field—for example, magnetic loop detectors 201 embedded in pavement and traffic cameras 202—can provide real-time traffic data, which can be transmitted over electrical or optical cable, or wirelessly, to a centralized computing environment 203, where historical traffic data are also stored. Traffic signal controllers 204 also provide real-time state information for remote performance monitoring. Satellite and terrestrial wireless communication devices 205 support the transmission of traffic data to the computing environment 203, where simulations are run and routing strategies are tested before guidance is sent back to travelers through those same communication devices. Drivers yet to depart, and en route, may receive guidance on personal computers 206 at home or work, or on on-board systems 207, or on mobile devices 208 (including hand-held navigation devices as well as mobile telephones). Instructions 209 can also be returned to the traffic signal control devices 204 to better manage traffic. As a result, various users of the system (e.g., drivers of commercial vehicles, passenger automobiles, etc.) may receive lane-level route guidance 210 that is tailored to their particular need or objective.”
[FIG.2]:
PNG
media_image1.png
1102
1060
media_image1.png
Greyscale
[[0008]: “Methods in accordance with the invention are also provided. The methods also may be used for traffic planning or management, including determining, based on microsimulation, at least one of (a) improvements to road geometry, or (b) traffic signal settings and improvements to traffic signal timing.”) obtaining first vehicle traffic data of a vehicle in a first traffic simulation; ([0004] : “A lane-level vehicle routing and navigation apparatus according to embodiments of the invention includes a simulation module that performs microsimulation of individual vehicles in a traffic stream, and a lane-level route optimizer that evaluates predicted conditions along candidate paths from an origin to a destination as determined by the simulation module, and determines recommended lanes to use and the associated lane-level maneuvers along the candidate paths. A link-level optimizer may be used to determine the candidate paths based on link travel times determined by the simulation module which then may be further refined with the lane-level optimizer. The simulation may be based on real-time traffic condition data.” [0057]: “One element of the lane-level navigation system is the inclusion of a lane-level route optimizer which can be used in addition to or instead of a link-level optimizer. Given the origin, destination and vehicle type and preference (e.g., high occupancy vehicle (HOV), car vs. truck, value of time, etc.), the link-level optimizer computes candidate paths represented by a sub-network or a veritable “hammock” of link sequences connecting an origin and a destination. A hammock can be thought of as a network of links and nodes emanating from a single link at the origin, or the vehicle's current position, and converging at a single link at the destination. According to a predefined look-ahead threshold (preference), the lane-level optimizer evaluates the travel time, delay and driving experience on path candidates using either historical measurements of lane-level traffic density and speed, or microsimulation. The result of this evaluation is then used to derive the lane-level route guidance, and in some cases (e.g., none of the lane change maneuvers are possible or desirable) may also invoke the link-level optimizer to recompute the path candidates according to the revised criteria. In the microsimulation employed by the lane-level optimizer, traffic signals (which may be adaptive traffic signals) at downstream intersections (and other traffic controls, including, e.g., message signs and other driver information systems) are simulated to determine intersection delay realistically as are vehicle trajectories and conflicts inside of intersections. It should be noted that in some embodiments, the origin, destination and vehicle type and preference, and any other inputs, can be entered directly into the lane-level optimizer, without using a link-level optimizer at all.” The examiner interprets this link-level path (a "hammock" of link sequences) as shown as vehicle traffic data within a first, coarser scale of simulation/optimization.) performing conversion according to the first vehicle traffic data to obtain second vehicle traffic data of the vehicle in a second traffic simulation; ([0081]: “Link-level optimizer 709 generates link-level alternative routes. It can provide multiple alternative routes from a driver's current position to the desired destination. These alternative routes can be formulated as a sub-network or “hammock” of a directional sequence of links. For the chosen route, as the guided vehicle move from one road segment to next or changes lane, the downstream portion of the links along the route within a look-ahead range is then expanded to a lane-level network or graph 711 as presented earlier. Lane-level optimizer 712 is used to generate possible lane-level trajectories. These lane-level alternative paths are then evaluated to determine the optimal one based on preset rules and criteria.”) The examiner interprets the transformation of a link-level path into detailed lane-level trajectories as shown in a conversion between data types of different simulation scales.) and running the second traffic simulation according to the second vehicle traffic data of the vehicle, ([0081]: “Link-level optimizer 709 generates link-level alternative routes. It can provide multiple alternative routes from a driver's current position to the desired destination. These alternative routes can be formulated as a sub-network or “hammock” of a directional sequence of links. For the chosen route, as the guided vehicle move from one road segment to next or changes lane, the downstream portion of the links along the route within a look-ahead range is then expanded to a lane-level network or graph 711 as presented earlier. Lane-level optimizer 712 is used to generate possible lane-level trajectories. These lane-level alternative paths are then evaluated to determine the optimal one based on preset rules and criteria.” [0047-0048]]: “Microsimulation can be used to generate or supplement the data if the data are not available from other sources or cannot be cost-effectively gathered. A navigation engine that simulates regional traffic flow at very short time intervals ranging from 0.1 seconds to 1 second can be used to evaluate alternative lane-level routes.”) wherein the first traffic simulation and the second traffic simulation comprises one of a microscopic traffic simulation and a mesoscopic traffic simulation, and the first traffic simulation is different from the second traffic simulation. ([0024]: “The prevailing view has been that mesoscopic traffic simulation, which lacks lane-level modeling detail, is the only feasible method of providing real-time route guidance because microscopic simulation models have not yet been built at a large enough geographic scale and would be too expensive to build and validate or too computationally demanding to be useful. Obstacles to region-wide traffic microsimulation have traditionally included lack of detailed data on trip patterns by time of day and network performance by road segment and the lanes therein, difficulties in modeling driver route choice, problems in accurate simulation of large numbers of vehicles especially under heavily congested traffic conditions, as well as the computational burden of performing the simulation within a short enough time for the results to be useful. However, microsimulation at the regional scale can be implemented using methods described in commonly-assigned U.S. Pat. No. 7,155,376, which is hereby incorporated by reference herein in its entirety.” [0093]: “While microscopic simulation is used to provide lane-level performance and routing, some portions of the network could be simulated by coarser macroscopic or mesoscopic or a hybrid combination with microscopic means. Due to the computational burden involved, the simulation would typically be multi-threaded and also distributed. The multi-threading of the simulation of vehicle movement and network state update can be improved by using a node adjacency matrix to assign tasks to each thread such that all the active threads are processing nodes that are not adjacent to one another and the maximum number of threads is put to work. This method avoids the certain locking of threads needed for write-access of shared data items. As shown in the diagram in FIG. 10, if the white nodes 1001 are the ones actively processed by eight threads, then the vehicle movements managed by these threads can be safely performed without locking the update of location-specific variables. This method also helps to balance the workload among the threads because any free thread is immediately put to work (unless the network is too small compared to the number of threads available and no non-adjacent nodes exist that are ready for processing).” The examiner interprets where the conversion from the link-level sequence (mesoscopic-like) to lane-level trajectories (microscopic) as shown in two difference simulations of different scales.)
Regarding Claim 10
Slavin teaches The method according to claim 1, (See claim 1) wherein the first traffic simulation comprises the microscopic traffic simulation, and the second traffic simulation comprises the mesoscopic traffic simulation; ([0061]: “When it is detected at 716 that the traveler has moved to a new road segment, engine 700 determines at 717 whether the traveler is on a road segment on the current advised link path, and if so the lane graph 711 is updated to reflect the new position in the network. Otherwise, the engine returns to the link-level optimizer 709. In this way, the traveler's location in relation to the region-wide network is continually tracked by engine 700, which uses simulation coupled with link-level optimizer 709 and lane-level optimizer 712 to guide the traveler.” [0093]: “While microscopic simulation is used to provide lane-level performance and routing, some portions of the network could be simulated by coarser macroscopic or mesoscopic or a hybrid combination with microscopic means. Due to the computational burden involved, the simulation would typically be multi-threaded and also distributed. The multi-threading of the simulation of vehicle movement and network state update can be improved by using a node adjacency matrix to assign tasks to each thread such that all the active threads are processing nodes that are not adjacent to one another and the maximum number of threads is put to work. This method avoids the certain locking of threads needed for write-access of shared data items. As shown in the diagram in FIG. 10, if the white nodes 1001 are the ones actively processed by eight threads, then the vehicle movements managed by these threads can be safely performed without locking the update of location-specific variables. This method also helps to balance the workload among the threads because any free thread is immediately put to work (unless the network is too small compared to the number of threads available and no non-adjacent nodes exist that are ready for processing).” The examiner interprets where Conversion from Micro-to-Mesoscopic in a hybrid system is shown in tracking vehicles from "microsimulation" relative to a "mesoscopic" or "region-wide network".) obtaining first vehicle traffic data of a vehicle in a first traffic simulation comprises: obtaining the first vehicle traffic data of the vehicle in the microscopic traffic simulation, the first vehicle traffic data comprising a serial number of a road section that the vehicle is on, a longitude and a latitude of the vehicle, and a speed of the vehicle; (See [0072] & [0036]: “These improved processes are based on the ability to store, manage, and utilize time-dependent, lane-level information on traffic and geometric conditions on highways and between and within intersections on streets. Between intersections, a road may be divided into segments based on traffic characteristics (e.g., curvature, grade, number of lanes), and each segment may be divided into lanes. Alignments between upstream and downstream lanes at adjacent segments and intersections are described by lane connectors. Travel demand, either as individual trips, or as aggregated trip counts by entities, are associated geographically and temporally to the network using origins, destinations, and desired departure or arrival time. Vehicle locations and trajectories, lane-segment-specific vehicle lane-occupancies/densities, vehicle gap distributions, and speeds can be recorded for short time intervals from observations and measurements and also from detailed microsimulation. These data can be used to analyze the likely travel times and other characteristics of potential vehicle trajectories at the lane-level from an origin to a destination. Similarly, these data items can be gathered for the components of trajectories that take place inside of intersections where delays are often experienced due to conflicting movements of vehicles and even pedestrians. If not all of the necessary data can be observed or measured in the field, detailed simulation can be used to supplement the available measurements for the needed locations and/or time intervals.” The examiner interprets where Microscopic data: ID, Lat/Long, and Speed are shown in Recorded trajectories using "unique road segment identifier," "geographic coordinates," and "speeds".) and performing conversion according to the first vehicle traffic data to obtain second vehicle traffic data of the vehicle in a second traffic simulation comprises at least one of the following operations: performing conversion according to the serial number of the road section that the vehicle is on and the longitude and the latitude of the vehicle to obtain a distance from a current position of the vehicle to an origin of the road section that the vehicle is on in the mesoscopic traffic simulation; (See [0061] & [0072]: The examiner interprets where Conversion to linear distance to origin is shown in "continually tracking" location relative to links requires converting Lat/Long back to "relative distance".) and performing conversion according to the serial number of the road section that the vehicle is on, the longitude and the latitude of the vehicle, and the speed of the vehicle to obtain landing time of the vehicle on a next road in the mesoscopic traffic simulation. ([0059]: “With lane-level model 702 of the region-wide network using the historical and real-time information, accurate dynamic traffic assignments and simulations are run at 707 to produce predictions of travel times and turning movement delays 708 that in turn drive a link-level route optimizer 709. A set of alternative link paths represented by a hammock 710 connecting a traveler's origin to his/her destination is produced by optimizer 709. In one embodiment, a set of lane graphs 711 is developed for the traveler. Ideally, the lane graphs encompass the entirety of the optimal link route, but if computational resources are not sufficient, the lane graph may be limited to a look-ahead range, as shown.” The examiner interprets where Conversion to "landing time" on next road is shown in the Uses of microsimulation results to update "travel times" and "delays" for the next links in the network)
Under MPEP § 2112, a limitation is inherent if it is "necessarily present" in the prior art. Slavin’s apparatus must map a vehicle's geographic coordinates back to a link-relative offset to "continually track" the traveler in the mesoscopic "region-wide network". This map-matching process is a mandatory functional step in any navigation system that reconciles high-fidelity trajectory data with a link-node graph. Furthermore, because Slavin uses Microscopic-level trajectories to update the "travel times" and "delays" of the coarser network links, the system necessarily determines the time at which a vehicle exits its current segment and "lands" on the next one. A computer-implemented hybrid simulation cannot function without these conversion steps; thus, they are inherently disclosed.
Regarding Claim 11
Slavin teaches The method according to claim 10, (See claim 10) wherein the road that the vehicle is on comprises N discrete points, N being a positive integer; (See [0066]: The examiner interprets where Road comprises N discrete points is shown in "Lane graph" using "vertices" [points] to represent roads.) and determining a distance from the current position of the vehicle to an origin of the road that the vehicle is on according to a serial number of the road that the vehicle is on and the longitude and the latitude of the vehicle comprises: determining an ith discrete point closest to the current position of the vehicle according to longitudes and latitudes of the N discrete points and the longitude and the latitude of the vehicle, i being a positive integer less than N; (See [0061]: The examiner interprets where Map-matching vehicle to closest ith point using Lat/Long is shown in "Continually tracking" vehicle relative to the graph requires finding the nearest node to the coordinate.) and determining the distance from the current position of the vehicle to the origin of the road that the vehicle is on according to a distance from the ith discrete point to the origin of the road that the vehicle is on and a distance from the ith discrete point to the current position of the vehicle. (See [0072]: The examiner interprets where Linear distance = Vertex distance + displacement distance is shown in Resolving "relative distance" on a discrete graph requires summing vertex weights and local offsets.)
Under MPEP § 2112, a limitation is inherent if it is "necessarily present" in the prior art. Slavin’s apparatus performs "microsimulation" and "continually track[s]" vehicle trajectories on a discrete "lane graph" while coordinating with "geographic coordinates". A computer-implemented navigation engine using a discrete vertex-based model has no geometric information between vertices unless it performs interpolation. To "track" a coordinate (Lat/Long) in such a graph, the system necessarily identifies which vertex (ith point) is the closest match to anchor the vehicle. Furthermore, to determine the "relative distance" (linear offset) of that vehicle in the Mesoscopic-level network, the computer necessarily performs the math of taking the vertex's known distance-to-origin and adding the local displacement. A computer cannot resolve a network-relative linear position from a geographic coordinate in a discrete graph without these steps. Thus, the algorithm recited in Claim 11 is inherently disclosed.
Regarding Claim 12
Slavin teaches The method according to claim 10, (See Claim 10) wherein a connecting road section that the vehicle is on comprises M discrete points arranged in order, M being a positive integer; (See [0064], [0066], [0055], [FIG. 9]: The examiner interprets where Connecting section with M discrete points in order is shown in a "lane-level network (otherwise known as a lane graph)" containing "vertices" and "edges;” where Slavin explicitly defines "lane connectors" within intersections (connecting road sections) as part of this network; where FIG. 9 of Slavin represents these connectors as a sequence of discrete vertices (points).) and determining of the landing time of the vehicle on the next road according to a serial number of the connecting road section that the vehicle is on, the longitude and the latitude of the vehicle, and the speed of the vehicle comprises: (See [Abstract], [0081], [0096], [0061]: The examiner interprets where Landing time calculation parameters is shown in Slavin's simulation module performs "microsimulation of individual vehicles" and evaluates "lane-level trajectories" to "estimate the travel time and delay;" where Slavin records trajectories using a "unique road segment identifier" (serial number), "geographic coordinates" (Lat/Long), and "speeds;" where the arrival time at the next segment (landing time) is the functional output of this microsimulation process used to update the "region-wide network".) determining an ith discrete point closest to the current position of the vehicle according to longitudes and latitudes of the M discrete points and the longitude and the latitude of the vehicle, i being a positive integer less than M; (See [0061], [0036], [0066]: The examiner interprets where Determining the closest ith point is shown in a navigation engine that "continually tracked" a traveler's location in relation to the network based on geographic coordinates from "microsimulation;" where in a computer simulation; where infrastructure is modeled as a "lane graph" of discrete "vertices," map-matching a coordinate to that graph requires identifying which vertex (ith point) is the nearest match to anchor the vehicle.) and determining, according to a distance from the ith discrete point to an origin of the connecting road section that the vehicle is on, a distance from the ith discrete point to the current position of the vehicle, (See [0072], [0070]: The examiner interprets where Distances is shown in tracking "relative distance from either end" and using the "predecessor of each vertex" to calculate distances along the path; where Resolving a Lat/Long to this graph requires summing the vertex's offset and the vehicle's displacement from that vertex.) the speed of the vehicle, and a total length of the connecting road section that the vehicle is on, the landing time of the vehicle ], on the next road. (See [0071 & [0055]: The examiner interprets where Speed and Total Length is shown in recording vehicle "travel speed" and the "geometric alignments" of the lane graph; where the "total length" of a path/connector is a standard attribute of the lane graph edge.)
Under MPEP § 2112, a limitation is inherent if it is "necessarily present" in the prior art. Slavin’s apparatus performs a hybrid microsimulation that must predict "travel times" and "turning movement delays" for vehicles moving through intersection connectors to update a mesoscopic network.
In a computer-implemented simulation using a discrete vertex-based graph, the only available data to predict a vehicle's exit time is the vehicle's current position (defined by a vertex and displacement), its speed, and the known distance to the end of the segment (defined by its total length). A computer cannot "predict travel time" or determine an exit point without performing the specific kinematic math recited in limitation “and determining, according to a distance from the ith discrete point to an origin of the connecting road section that the vehicle is on, a distance from the ith discrete point to the current position of the vehicle the speed of the vehicle, and a total length of the connecting road section that the vehicle is on, the landing time of the vehicle ], on the next road”. Because Slavin’s simulation is "based on the ability to store... and utilize... lane-level information" in a graph to generate "predictions," it inherently performs the steps of finding the closest vertex and calculating the landing time using that vertex's offset, the vehicle's speed, and the segment's total length. Therefore, the algorithm of Claim 12 is inherently disclosed.
Regarding Claim 13
Slavin teaches The method according to claim 1, (See claim 1) wherein the method further comprises:
obtaining a microscopic traffic simulation region; (See [0096]: The examiner interprets where Obtaining a microscopic simulation region is shown in a "smaller and selected area of the network" for microsimulation.) displaying the microscopic traffic simulation in the microscopic traffic simulation region, and displaying the mesoscopic traffic simulation in a mesoscopic traffic simulation region other than the microscopic traffic simulation region; (See [FIG 1]: The examiner interprets where Displaying Micro in one region and Mesoscopic in another is shown in FIG. 1 showing a high-detail "Box 1" (Micro) within a wider network (Mesoscopic/Macro).) and displaying microscopic vehicle traffic data in the microscopic traffic simulation region and displaying mesoscopic vehicle traffic data in the mesoscopic traffic simulation region, the microscopic vehicle traffic data being vehicle traffic data of a microscopic vehicle, and the mesoscopic vehicle traffic data being vehicle traffic data of a mesoscopic vehicle. (See [FIG 1 & 10] & [0093]: The examiner interprets where Displaying Micro vehicle data in the Micro region & Displaying Mesoscopic vehicle data in the Mesoscopic region are shown in FIG. 1 depicting individual vehicles and trajectories within Box 1 & a "hybrid combination" where the surrounding network is simulated/shown via mesoscopic means.)
Under MPEP § 2112, a limitation is inherent if it is "necessarily present" in the prior art. Slavin discloses a computer-implemented simulation that uses a "hybrid combination" of mesoscopic and microscopic means and provides a "visual representation" showing a high-detail microscopic inset (Box 1) within a region-wide network. A computer screen that visualizes a hybrid simulation (where one area is micro and another is Mesoscopic) necessarily displays the vehicle data corresponding to those respective scales. To show the "near-ground-truth level of detail" [0037], the system must display the microscopic data (individual vehicle units) in that region. Simultaneously, to show the traveler's location relative to the "region-wide network" (Mesoscopic scale) [0061], the system must display the coarser flow data for the links in the surrounding regions. A hybrid visualization cannot function or provide the described "visual representation" without displaying these distinct data types in their respective regions. Thus, the partitioned data display is inherently disclosed.
Regarding Claim 14
Slavin teaches The method according to claim 1, (See claim 1) wherein the method further comprises:
determining, in response to a traffic prediction operation, mesoscopic vehicle traffic data in the mesoscopic traffic simulation based on microscopic vehicle traffic data in the microscopic traffic simulation; (See [Abstract] & [0059]: The examiner interprets where Mesoscopic data derived from Microscopic data for prediction is shown in Describes using "microsimulation" of trajectories to update "predictions" in a "region-wide network.") converting, for a vehicle in a prediction region, the microscopic traffic simulation to the mesoscopic traffic simulation according to the microscopic vehicle traffic data and the mesoscopic vehicle traffic data; ([0053]: “Anticipatory, route-strategic, planned lane changes can improve upon travelers travel times and routes in a significant way. FIG. 3 shows two of candidate paths 301, 302 from location 311 to location 313. In this case, a driver has chosen the hatched path and is approaching location 312. The distance or number of links (i.e., road segments) downstream on the chosen path for which a driver must plan near-term lane changing decisions is called the look-ahead range. The immediate downstream road segments connecting the next two intersections are highlighted at 303 and shown in greater detail in FIG. 4.” [0094]: “The simulation can also be distributed to a cluster of multiple computers based on network decomposition, which minimizes the number of boundary links between sub-networks and balances the load among the computers in the cluster. By minimizing the thread-locking on each computer responsible for a sub-network and limiting the amount of required communication between the computers that jointly perform the region-wide simulation, on-time computational performance of the network state estimation and prediction can be achieved. Because the traffic measurement and network events occur in real time, the system operates in a rolling horizon style. For every 5, 10, 15, or 30 minutes, as the new measurements and events data become available, a new cluster of computers is activated to perform network state estimation and traffic prediction for the next time period. The diagram in FIG. 11 illustrates how three clusters 1101, 1102, 1103 of computers take turns in rotation to perform distributed travel time estimation and traffic prediction for different time periods. Each computer in a class simulates part of the network based on network decomposition.”
[FIG. 3 & 4]:
PNG
media_image2.png
1037
691
media_image2.png
Greyscale
[FIG. 11]:
PNG
media_image3.png
653
882
media_image3.png
Greyscale
and displaying a predicted traffic status according to the mesoscopic traffic simulation. (See [0004] & [0059]: The examiner interprets where Displaying predicted Mesoscopic traffic status is shown in displaying "predicted conditions" and "travel time predictions" on mobile and computing devices.)
Under MPEP § 2112, a feature is inherent if it is "necessarily present" in the prior art. Slavin’s apparatus must aggregate individual vehicle data into link-level data to perform its disclosed function of using "microsimulation" to "produce predictions of travel times ... in the region-wide network". In a computer-implemented hybrid simulation, a link-level (mesoscopic) travel time cannot be "estimated" or "predicted" from individual units without performing the mathematical summation or averaging of those units' speeds and positions over the link's length. This aggregation/conversion is a mandatory functional requirement for the "reconciliation" and "tracking" Slavin describes. Thus, the conversion logic is inherently disclosed.
Regarding Claim 15
Slavin teaches A traffic simulation conversion apparatus, the apparatus comprising: (See [Abstract]: The examiner interprets where Conversion apparatus is shown in a lane-level vehicle routing and navigation apparatus.) a processor; (See [0094, [FIG. 11], [0046], [FIG.2]: The examiner interprets where Processor is shown in a "centralized computing environment 203" and "cluster of multiple computers".) and a non-transitory computer readable memory in communication with the processor and storing a plurality of instructions, the plurality of instructions, when executed by the processor, configure the processor to: (See [0058] & [FIG. 7]: The examiner interprets where Memory with instructions is shown in a "geographic database" and "storing" of traffic/geometric data for simulation.) obtain first vehicle traffic data of a vehicle in a first traffic simulation; (See [0004]: The examiner interprets where Obtain first data in 1st simulation is shown in producing "link-level" route candidates based on simulation data.) perform conversion according to the first vehicle traffic data to obtain second vehicle traffic data of the vehicle in a second traffic simulation; (See [0081]: The examiner interprets Conversion to second data in 2nd simulation is shown in link routes "expand[ing]" to generate detailed "lane-level trajectories".) and run the second traffic simulation according to the second vehicle traffic data of the vehicle, the first traffic simulation and the second traffic simulation comprising one of a microscopic traffic simulation and a mesoscopic traffic simulation, (See [0009]: The examiner interprets where Run second simulation is shown in evaluating the generated trajectories via "microsimulation".) and the first traffic simulation being different from the second traffic simulation. (See [0024]: The examiner interprets where Different (Microscopic/Mesoscopic) simulations is shown in distinguishment between "microsimulation" and "mesoscopic traffic simulation".)
Under MPEP § 2112, structural hardware components like "processor" and "memory" are inherently disclosed by Slavin’s description of a "centralized computing environment," "cluster of multiple computers," and a "database" used to "store, manage, and utilize" simulation data and "execute" dynamic traffic assignments. A computer-implemented simulation and optimization engine, by its very nature, must run on a processor utilizing memory.
Regarding Claim 16
Slavin teaches The apparatus according to claim 15, (See claim 15) wherein the first traffic simulation comprises the mesoscopic traffic simulation, and the second traffic simulation comprises the microscopic traffic simulation; (See [0061]: The examiner interprets where First = Mesoscopic; Second = Microscopic is shown in hybrid simulation with "mesoscopic" portions and "microsimulation.") wherein the plurality of instructions further configure the processor to: obtain the first vehicle traffic data of the vehicle in the mesoscopic traffic simulation, the first vehicle traffic data comprising a serial number of a road section that the vehicle is on and a distance from a current position of the vehicle to an origin of the road section that the vehicle is on; (See [0072]: The examiner interprets where Mesoscopic data: Serial Number + Distance to origin is shown in "data triplets" containing a "unique road segment identifier" and "relative distance from either end.") and perform conversion according to the serial number of the road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the road section that the vehicle is on to obtain the second vehicle traffic data of the vehicle in the microscopic traffic simulation, (See [0081] & [0072]: The examiner interprets where Perform conversion based on ID and Distance is shown in link routes that are "expanded" to Microscopic-level and data triplets are "converted" to geographic coordinates.) the second vehicle traffic data comprising a longitude and a latitude of the vehicle and a front orientation of the vehicle. (See [0072]: The examiner interprets where Microscopic data: Lat/Long + Front Orientation is shown in "geographic coordinates" (Lat/Long); where front orientation is required for movement and trajectory simulation.)
Under MPEP § 2112, a limitation is inherent if it is "necessarily present" in the prior art. While Slavin does not use the verbatim phrase "front orientation," it performs "microsimulation of vehicle movements" along "lane-level trajectories" following "lane alignment". As a matter of computational physics and simulation logic, a vehicle cannot possess a "trajectory" or follow a "lane alignment" in a computer-implemented simulation without the system resolving its heading or "front orientation". Because Slavin converts the unique segment ID and linear offset (Mesoscopic data) into these Microscopic-level trajectories, the determination of the vehicle’s orientation based on the underlying road geometry at that specific point is a mandatory and necessary functional step in Slavin's disclosed apparatus. Therefore, "front orientation" is inherently disclosed.
Regarding Claim 17
Slavin teaches The apparatus according to claim 15, (See claim 15) wherein the first traffic simulation comprises the microscopic traffic simulation, and the second traffic simulation comprises the mesoscopic traffic simulation; (See [0093] & [FIG. 10]: The examiner interprets where First = Microscopic; Second = Mesoscopic is shown in hybrid simulation with "mesoscopic" portions and "microsimulation.") and wherein the plurality of instructions further configure the processor to: obtain the first vehicle traffic data of the vehicle in the microscopic traffic simulation, the first vehicle traffic data comprising a serial number of a road section that the vehicle is on, a longitude and a latitude of the vehicle, and a speed of the vehicle; (See [0036] & [0072]: The examiner interprets where Microscopic data: ID, Lat/Long, and Speed is shown in trajectories using "unique road segment identifier," "geographic coordinates," and "speeds.") and perform at least one of the following operations: performing conversion according to the serial number of the road section that the vehicle is on and the longitude and the latitude of the vehicle to obtain a distance from a current position of the vehicle to an origin of the road section that the vehicle is on in the mesoscopic traffic simulation, (See [0061] & [0072]: The examiner interprets where Conversion to distance to origin is shown in "Continually tracking" location relative to links requires converting Lat/Long back to "relative distance.") and performing conversion according to the serial number of the road section that the vehicle is on, the longitude and the latitude of the vehicle, and the speed of the vehicle to obtain landing time of the vehicle on a next road in the mesoscopic traffic simulation. (See [0059]: The examiner interprets where Conversion to landing time is shown in Using microsimulation results to produce "predictions of travel times" for next links.)
Under MPEP § 2112, a limitation is inherent if it is "necessarily present" in the prior art. Slavin’s apparatus must map a vehicle's geographic coordinates back to a link-relative offset to "continually track" the traveler in the mesoscopic "region-wide network". This map-matching process is a mandatory functional step in any navigation system that reconciles high-fidelity trajectory data with a link-node graph. Furthermore, because Slavin uses Microscopic-level trajectories to update the state of the coarser network links, the system necessarily determines the time at which a vehicle exits its current segment and "lands" on the next one to resolve future link travel times. These conversion steps are inherent to the operation of Slavin’s disclosed hybrid simulation.
Regarding Claim 18
Slavin teaches A non-transitory computer readable memory in communication with a processor and storing a plurality of instructions, the plurality of instructions, when executed by the processor, configure the processor to: (See [0058], [0046]: The examiner interprets where Non-transitory memory storing instructions for a processor is shown in a "geographic database" and "centralized computing environment" used to execute simulation/routing.) obtain first vehicle traffic data of a vehicle in a first traffic simulation; (See [0004]: The examiner interprets where Obtain first vehicle data in 1st simulation is shown in link-level route candidates produced by an optimizer based on simulation results.) perform conversion according to the first vehicle traffic data to obtain second vehicle traffic data of the vehicle in a second traffic simulation; (See [0081]: The examiner interprets where Perform conversion to obtain second data in 2nd simulation is shown in link routes are "expand[ing]" to generate detailed "lane-level trajectories".) and run the second traffic simulation according to the second vehicle traffic data of the vehicle, the first traffic simulation and the second traffic simulation comprising one of a microscopic traffic simulation and a mesoscopic traffic simulation, (See [0009]: The examiner interprets where Run 2nd simulation according to 2nd data is shown in evaluating the generated lane-level trajectories using "microsimulation".) and the first traffic simulation being different from the second traffic simulation. (See [0093]: The examiner interprets where Simulations are different (Microscopic vs. Mesoscopic) is shown in the distinguishment between "microsimulation" and "mesoscopic traffic simulation" and teaches their hybrid use.)
Under MPEP § 2112, structural hardware components such as a "processor" and "memory" are inherently disclosed by Slavin’s description of a "centralized computing environment," "cluster of multiple computers," and a "database" used to "store, manage, and utilize" simulation data. A computer-implemented simulation and optimization engine, by its very nature, must run on a processor utilizing non-transitory memory. Furthermore, the functional "expansion" of a link-relative path into a lane-level trajectory inherently requires the mathematical conversion of the data attributes to reconcile them with the higher-fidelity microsimulation model.
Regarding Claim 19
Slavin teaches The non-transitory computer readable memory according to claim 18, (See claim 18) wherein the first traffic simulation comprises the mesoscopic traffic simulation, and the second traffic simulation comprises the microscopic traffic simulation; (See [0093] & [FIG. 10]: The examiner interprets where First = Mesoscopic; Second = Microscopic is shown in a hybrid simulation with "mesoscopic" portions and "microsimulation".) wherein the plurality of instructions further configure the processor to: obtain the first vehicle traffic data of the vehicle in the mesoscopic traffic simulation, the first vehicle traffic data comprising a serial number of a road section that the vehicle is on and a distance from a current position of the vehicle to an origin of the road section that the vehicle is on; (See [0072]: The examiner interprets where Mesoscopic data: Serial Number + Distance to origin is shown in "data triplets" containing a "unique road segment identifier" and "relative distance from either end".) and perform conversion according to the serial number of the road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the road section that the vehicle is on to obtain the second vehicle traffic data of the vehicle in the microscopic traffic simulation, (See [0072 & [0081]: The examiner interprets where Perform conversion based on ID and Distance is shown in link routes are "expand[ing]" and data triplets are "convert[ing]" to geographic coordinates.) the second vehicle traffic data comprising a longitude and a latitude of the vehicle and a front orientation of the vehicle. (See [0072]: The examiner interprets where Microscopic data: Lat/Long + Front Orientation is shown in geographic coordinates" (Lat/Long); where front orientation is a necessary attribute for movements on a lane alignment.)
Under MPEP § 2112, a limitation is inherent if it is "necessarily present" in the prior art. While Slavin does not use the verbatim term "front orientation," it performs a "microsimulation of vehicle movements" along "lane-level trajectories" following "lane alignment". In a computer-implemented simulation of individual units moving along a geometric "alignment," a vehicle's heading or "front orientation" is a mandatory derivative of the underlying geometry at its calculated position. The system cannot resolve "movement" or "trajectories" without establishing the vehicle's orientation vector relative to the lane graph. Therefore, the determination of "front orientation" as part of the Microscopic-level vehicle data is inherently disclosed.
Regarding Claim 20
Slavin teaches The non-transitory computer readable memory according to claim 18, (See claim 18) wherein the first traffic simulation comprises the microscopic traffic simulation, and the second traffic simulation comprises the mesoscopic traffic simulation; (See 0093], [FIG. 10], [0061]: The examiner interprets where Conversion from Microscopic-to-Mesoscopic is shown in a "hybrid combination" tracking high-fidelity vehicles relative to a coarser "region-wide network".) and wherein the plurality of instructions further configure the processor to: obtain the first vehicle traffic data of the vehicle in the microscopic traffic simulation, the first vehicle traffic data comprising a serial number of a road section that the vehicle is on, a longitude and a latitude of the vehicle, and a speed of the vehicle; (See [0036] & [0072]: The examiner interprets where Microscopic data: ID, Lat/Long, and Speed is shown in trajectories using "unique road segment identifier," "geographic coordinates," and "speeds".) and perform at least one of the following operations: performing conversion according to the serial number of the road section that the vehicle is on and the longitude and the latitude of the vehicle to obtain a distance from a current position of the vehicle to an origin of the road section that the vehicle is on in the mesoscopic traffic simulation, (See [0061] & [0072]: The examiner interprets where Conversion to distance to origin is shown in "continually tracking" location relative to links requires map-matching Lat/Long to "relative distance".) and performing conversion according to the serial number of the road section that the vehicle is on, the longitude and the latitude of the vehicle, and the speed of the vehicle to obtain landing time of the vehicle on a next road in the mesoscopic traffic simulation. (See [0059]:The examiner interprets where Conversion to landing time is shown in using microsimulation results to produce "predictions of travel times" for next links in the network.)
Under MPEP § 2112, a limitation is inherent if it is "necessarily present" in the prior art. Slavin’s apparatus must map a vehicle's geographic coordinates back to a link-relative offset to "continually track" the traveler in the mesoscopic "region-wide network". This map-matching process is a mandatory functional step in any system that reconciles high-fidelity trajectory data with a link-node graph. Furthermore, because Slavin uses Microscopic-level trajectories to update the "travel times" and "delays" of the coarser network links, the system necessarily determines the time at which a vehicle exits its current segment and "lands" on the next one to resolve the future link state. A computer-implemented hybrid simulation cannot function without these conversion steps; thus, they are inherently disclosed.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The text of those sections of Title 35, U.S. Code not included in this action can be found in a prior Office action.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claim(s) 2-9 is/are rejected under 35 U.S.C. 103 as being unpatentable over US Patent No. US20140278052A1 by Slavin et al. in further view of US Patent No. CN110570660A by ZHANG XIAOCHUN.
Regarding Claim 2
Slavin teaches The method according to claim 1 (See claim 1) wherein the first traffic simulation comprises the mesoscopic traffic simulation, and the second traffic simulation comprises the microscopic traffic simulation; (See [0081] & [0093], [0024]: “The prevailing view has been that mesoscopic traffic simulation, which lacks lane-level modeling detail, is the only feasible method of providing real-time route guidance because microscopic simulation models have not yet been built at a large enough geographic scale, and would be too expensive to build and validate or too computationally demanding to be useful. Obstacles to region-wide traffic microsimulation have traditionally included lack of detailed data on trip patterns by time of day and network performance by road segment and the lanes therein, difficulties in modeling driver route choice, problems in accurate simulation of large numbers of vehicles especially under heavily congested traffic conditions, as well as the computational burden of performing the simulation within a short enough time for the results to be useful. However, microsimulation at the regional scale can be implemented using methods described in commonly-assigned U.S. Pat. No. 7,155,376, which is hereby incorporated by reference herein in its entirety.” [0034]: “In one known system that uses a mesoscopic simulation method, the supply side traffic performance is treated at the link level and not at the lane level. Generally speaking, the research literature has taught that microsimulation cannot be feasible for entire regions and cannot be computed quickly enough to provide navigation guidance.” [0025]: “In traffic simulation, and particularly in microscopic traffic simulation in which vehicles are simulated with lane-level detail, route guidance can be provided to vehicles while at the same time considering other traffic on the network. Yet existing simulation-based systems attempt to model actual driver behavior and discretionary lane changing without regard to normative strategies for lane use from an origin to a destination or a portion of a route. Consequently, these systems cannot properly determine the best lanes to use for an entire trip or a portion of a trip or the locations within road links at which to attempt or make lane changes based upon historical, measured, simulated, or forecasted lane-level densities and possible speeds” The examiner interprets where first traffic simulation comprises the mesoscopic traffic simulation, and the second traffic simulation comprises the microscopic traffic simulation is shown in expanding a coarser link-level route into a "microsimulation" environment.) obtaining first vehicle traffic data of a vehicle in a first traffic simulation comprises: obtaining the first vehicle traffic data of the vehicle in the mesoscopic traffic simulation, the first vehicle traffic data comprising a serial number of a road section that the vehicle is on and ([0072]: “In this framework, a lane path, either that representing a vehicle's travel diary up to the current position or that representing lane-level guidance derived from the foregoing techniques, can be represented by geographic coordinates and events or by a sequence of data triplets. Each data triplet could contain a (1) unique road segment identifier (i.e., a column of vertices in the lane graph)…”) a distance from a current position of the vehicle to an origin of the road section that the vehicle is on; ([0072]: “… (3) the position of a lane change expressed in terms of relative distance from either end of the lane. When formulating a lane path for recommendation to the driver, the distance reflects the location at which a lane change is advised, allowing for a comfortable interval before which the lane change should be completed. Advisory lane change positions can be derived from current or historical speed data, which are used to characterize the degree of difficulty of a lane change at a given position. When providing guidance, the data triplets could be converted to geographic coordinates and event notices and be coordinated with real-time GPS information on the vehicle's current location.” The examiner interprets where The "relative distance from [the] end" that serves as the entry point is synonymous with the distance to the origin of that section.) and performing conversion according to the first vehicle traffic data to obtain second vehicle traffic data of the vehicle in a second traffic simulation comprises: performing conversion according to the serial number of the road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the road section that the vehicle is on to obtain the second vehicle traffic data of the vehicle in the microscopic traffic simulation, (See [0072]: The examiner interprets where path representations (comprising segment ID and relative distance) "could be converted to geographic coordinates... and be coordinated with real-time GPS information" is shown as transforming the link-level/mesoscopic data into the microscopic simulation space.) the second vehicle traffic data comprising a longitude and a latitude of the vehicle (See [0072]:The examiner interprets where geographic coordinates is shown as longitude and latitude) and a front orientation of the vehicle. (See [0004], [0009]: “The invention includes improvements to traffic microsimulation methods by taking account of more realistic lane level trajectory selections made by drivers. Within the context of a single simulation run, a look ahead mechanism is used to identify better lane-level guidance and ensure that the guidance is feasible in light of other traffic in later time intervals. The look ahead mechanism also improves other aspects of traffic microsimulation.” [0064]:
“A lane-level network (otherwise known as a lane graph) is a model to represent the detailed information on the lane use regulation, lane change and lane alignment in the road network. It is specifically designed to support lane-level navigation and microsimulation of vehicle movements. The design of the lane graph can be best shown by a simplified example as shown in FIG. 8.”
[FIG. 8]:
PNG
media_image4.png
1144
944
media_image4.png
Greyscale
[0081]: “Link-level optimizer 709 generates link-level alternative routes. It can provide multiple alternative routes from a driver's current position to the desired destination. These alternative routes can be formulated as a sub-network or “hammock” of a directional sequence of links. For the chosen route, as the guided vehicle move from one road segment to next or changes lane, the downstream portion of the links along the route within a look-ahead range is then expanded to a lane-level network or graph 711 as presented earlier. Lane-level optimizer 712 is used to generate possible lane-level trajectories. These lane-level alternative paths are then evaluated to determine the optimal one based on preset rules and criteria.”
The examiner interprets in the context of a "microsimulation of individual vehicles", a vehicle's orientation is a necessary functional attribute of its "trajectory" and its position on a specific arc within the "lane graph". Directional nature of the links (meso) from which lane (micro) level details of position (lat/long mapped to geographical coordinates) indicate that front of vehicle would be traveling in the direction of the link.
Slavin fails to explicitly use the term "front orientation" in its conversion description. However; Zhang teaches a front orientation of the vehicle. [0106-0108]: “Furthermore, addressing the limitation of traditional mesoscopic simulation models where simulated vehicles can only operate within a single road segment link within a simulation time step ts, this application enables vehicles to simulate across multiple road segments links within the same simulation time step ts. This allows for adaptation to different road segment division methods in the road network and demonstrates strong versatility. The specific implementation process is as follows: Based on the original simulation, a vehicle state variable a (a=0~ts) is added to each vehicle to represent the actual driving situation of the vehicle within each simulation step ts.
a=ts indicates that the vehicle has not yet moved; a=0 indicates that the vehicle has completed the simulation within this simulation step; add a time variable t to each node on the vehicle's path to record the free flow running time required from that node to the next node; add a node state variable z (0 or 1) to each node on the vehicle's path to record whether the vehicle has completed the node, z=0 indicates that the vehicle has not completed the node; z=1 indicates that the vehicle has completed the node. The new simulation process will maintain the original simulation while adding cross-link simulation steps. The specific simulation flow can be seen in Figure 6. Within a simulation step ts, after completing the road segment movement and node transfer, it is necessary to traverse all vehicles, find the vehicles that have not completed the simulation step, and continue to repeat the road segment movement and node transfer process until all vehicles complete their own simulation step and the state variable a of all vehicles becomes 0.” The examiner interprets where a front orientation of the vehicle is shown in mapping of vehicle states during mesoscopic-to-microscopic transfers.)
It would have been obvious to a POSITA before the effective filing date of the invention to include "front orientation" as a converted data element because microscopic simulation of individual vehicle trajectories inherently requires orientation (e.g., heading) to accurately position the vehicle on lane connectors and within intersections as taught by Slavin. The combination of these known simulation techniques yields the predictable result of high-fidelity local traffic modeling integrated with regional-scale performance monitoring.
Regarding Claim 3
Slavin in combination with Zhang teaches The method according to claim 2. (See claim 2) Slavin teaches wherein performing conversion according to the serial number of the road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the road section that the vehicle is on to obtain the second vehicle traffic data of the vehicle in the microscopic traffic simulation comprises: (See [0072]: The examiner interprets where performing conversion is shown in a lane path represented by "geographic coordinates" or by a "sequence of data triplets"; these triplets including a "(1) unique road segment identifier" and "(3) the position... expressed in terms of relative distance from either end of the lane", and that these data triplets "could be converted to geographic coordinates" (Longitude and Latitude)) determining, when a type of the road section that the vehicle is on is a road, the longitude and the latitude of the vehicle according to a serial number of a road that the vehicle is on and a distance from the current position of the vehicle to an origin of the road that the vehicle is on; ([0037]: “FIG. 1 depicts the aforementioned microsimulation of traffic in Phoenix, Ariz., in which box 1 represents an intersection, including vehicles and lane-level geometry, with a near-ground-truth level of detail, as shown in box 2. The model also includes detailed traffic signal timing and other traffic management data, as shown in box 3, enabling the accurate simulation of signal operations and drivers' behavioral responses to them. For example, box 4 illustrates the operational state of a traffic signal controller at an arbitrary time t, and box 5 represents the operational state of that controller at time t+10 seconds. This allows with high-fidelity simulation of both the demand (i.e., vehicles) and supply (i.e., lane-level geometries and traffic signal operations) elements of the environment in which a navigation system operates.”
[FIG.1]:
PNG
media_image5.png
1278
940
media_image5.png
Greyscale
See [0072]: The examiner interprets where the use of the unique ID and relative distance (data triplets) to determine the vehicle's position on these road segments is shown as Road Type Conversion.) or determining, when a type of the road section that the vehicle is on is a connecting road section, the longitude and the latitude of the vehicle according to a serial number of a connecting road section that the vehicle is on and a distance from the current position of the vehicle to an origin of the connecting road section that the vehicle is on. (See [FIG. 8], [0037], [0072], [0081] [0055]: “Based on the road type, number of lanes, geography of the road, and existence of traffic signals and signs, embodiments of the invention can automatically generate the lane connectivity in typical urban intersection and freeway interchange configurations. The result of the automatically generated lane connections can be validated and further revised if necessary using survey data, aerial imagery, and vehicle trajectory data. As an example, FIG. 5 illustrates the lane connection at intersection 403 in more detail. The curved lines with arrowheads inside the intersection are called lane connectors. Lane connectors indicate the geometric alignments and permitted movements between lanes. As features in the lane-level database described, the lane connectors support the storage of data indicating the tendency, or probability, of drivers to use the particular connector. As shown, solid lane connectors 501 are more commonly used than dashed lane connectors 502.”
[FIG.5]:
PNG
media_image6.png
1160
1288
media_image6.png
Greyscale
[0023]: “Existing navigation systems provide route guidance primarily by choosing routes based upon expected link travel times and turn penalties, and occasionally preferences for use of certain types or classes of roads. These systems can readily identify the locations where mandatory lane changes are required to traverse a particular recommended or chosen path, but are not sensitive to the best lanes to use in various traffic situations and in different locations. They also fail to represent barriers and restrictions on lane use and lane changes explicitly. None considers traffic congestion at the lane level explicitly, or recognizes the differences in driver behavior for choosing lanes or even alternative paths when certain lanes are congested or inaccessible. With lane-level data, more effective routes and lane choices can be determined. Processes that exploit lane-level detail in route guidance navigation can be further evaluated and also refined through appropriate traffic simulation.” [0055]: “Based on the road type, number of lanes, geography of the road, and existence of traffic signals and signs, embodiments of the invention can automatically generate the lane connectivity in typical urban intersection and freeway interchange configurations. The result of the automatically generated lane connections can be validated and further revised if necessary using survey data, aerial imagery, and vehicle trajectory data. As an example, FIG. 5 illustrates the lane connection at intersection 403 in more detail. The curved lines with arrowheads inside the intersection are called lane connectors. Lane connectors indicate the geometric alignments and permitted movements between lanes. As features in the lane-level database described, the lane connectors support the storage of data indicating the tendency, or probability, of drivers to use the particular connector. As shown, solid lane connectors 501 are more commonly used than dashed lane connectors 502.”
The examiner interprets where the determination of Lat/Long based on IDs and offsets for both infrastructure types is shown as Connecting Road Section Type Conversion.)
Slavin fails to explicitly recite separate logic for standard "roads" versus "connecting road sections" in a dual-simulation conversion context. However; Zhang teaches determining, when a type of the road section that the vehicle is on is a connecting road section, the longitude and the latitude of the vehicle according to a serial number of a connecting road section that the vehicle is on and a distance from the current position of the vehicle to an origin of the connecting road section that the vehicle is on. ([0020]: “The meso-micro region division unit is used to pre-divide the simulation area of the target traffic network into a meso-simulation area and a micro-simulation area, and to perform spatial matching of the regional boundaries of the meso-simulation area and the micro-simulation area. The characterization accuracy of the micro-simulation area is higher than that of the meso-simulation area.” The examiner interprets where Determining Longitude/Latitude for "connecting road section" types is shown in partitioning a network into different precision zones (meso vs. micro) and completing "spatial matching" of boundary segments to allow vehicle transfer between levels.)
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the invention to modify the conversion logic of Slavin to include the specific road-type distinctions (road vs. connecting road section) taught by Zhang. A POSITA would have recognized that different network segment types require specific mapping parameters to maintain spatial consistency during the "spatial matching" and inter-simulation transfers described by Zhang, thereby yielding the predictable result of an accurate fused simulation. No unexpected results are found, as these conversion steps represent a routine application of known coordinate transformation methods to classified network segments.
Regarding Claim 4
Slavin in combination with Zhang teaches The method according to claim 3. (See claim 3) Slavin teaches wherein the road that the vehicle is on in the microscopic traffic simulation comprises N discrete points arranged in order, N being a positive integer;
(See [0064], [0072], [FIG. 9]:
PNG
media_image7.png
882
1262
media_image7.png
Greyscale
The examiner interprets where a "lane-level network (otherwise known as a lane graph)" designed to "support lane-level navigation and microsimulation of vehicle movements"; containing vertices (representing lanes)" and "edges (representing relations between lanes)"; where in the lane graph 900 of FIG. 9, each vertex represents a lane within a specific road segment,; where these vertices are arranged sequentially to form a path; where the "unique road segment identifier" is represented as a "column of vertices in the lane graph" is shown as road links as ordered sets of discrete points (vertices).) and determining the longitude and the latitude of the vehicle according to the serial number of the road that the vehicle is on and the distance from the current position of the vehicle to an origin of the road that the vehicle is on comprises: (See [0067]: The examine interprets where Determining Lat/Long from ID and Distance is shown in r a vehicle's path using "data triplets" which include a "(1) unique road segment identifier" and "(3) the position... expressed in terms of relative distance from either end of the lane;” where these triplets "could be converted to geographic coordinates" (longitude and latitude). determining, when the type of the road section that the vehicle is on is a road, a longitude and a latitude of an ith discrete point closest to the current position of the vehicle in the N discrete points in the road that the vehicle is on as the longitude and the latitude of the vehicle according to the serial number of the road that the vehicle is on and the distance from the current position of the vehicle to the origin of the road that the vehicle is on, i being a positive integer less than N. (See [0081] & [0067]: The examiner interprets where Selecting the closest point's Lat/Long is shown in a microscopic simulation using the vertices of the lane graph to define vehicle trajectories; where the "road segment identifier" refers to the vertices in the graph; where the "relative distance" is used to locate the vehicle within that segment; where the conversion of a triplet to a Lat/Long coordinate necessarily resolves to the coordinates of the vertices (discrete points) that define the vehicle's current state in the graph. (In a discrete vertex-based simulation, a vehicle's geographic position is defined by the coordinates of the vertex that is "closest" to its calculated linear progression along the link.))
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the invention to combine the discretized road model and relative-positioning logic of Slavin with the hybrid simulation framework of Zhang. Specifically, in the conversion process taught by Zhang, a POSITA would find it routine and predictable to map a vehicle's mesoscopic relative position to the coordinates of the nearest existing point in the microscopic road model (as taught by the vertices in Slavin) to ensure computational efficiency and geometric consistency during data conversion. The resulting conversion process yields no more than the expected benefit of localized data precision within a hybrid simulation environment.
Regarding Claim 5
Slavin in combination with Zhang teaches The method according to claim 4. (See claim 4) Slavin teaches wherein determining a longitude and a latitude of an ith discrete point closest to the current position of the vehicle in the N discrete points in the road that the vehicle is on as the longitude and the latitude of the vehicle according to the serial number of the road that the vehicle is on and the distance from the current position of the vehicle to the origin of the road that the vehicle is on comprises:
obtaining a distance between adjacent discrete points in the N discrete points according to the serial number of the road that the vehicle is on; (See [0064] & [0071]: “Similarly, travel speed, delay, traffic density, and gaps between vehicles for the lanes in the graph can be recorded as the attributes for lane vertices in the graph. The possibilities and difficulties of lane change maneuver can be represented by the attributes of edges that connect neighbor lanes in the graph. Searching techniques, therefore, can be performed on the lane graph to evaluate the cost and driving experience along a candidate lane path and select the optimal location to start the required lane changes.” The examiner interprets where Obtaining distance between adjacent points is shown as a "lane-level network (otherwise known as a lane graph)" where roads are represented by vertices and edges; where attributes for these components, including "travel speed, delay," and "attributes of edges that connect neighbor lanes." (The lengths of these edges are the distances between adjacent discrete points (vertices).) determining a distance from each of the N discrete points in the road that the vehicle is on to the origin of the road that the vehicle is on by accumulating the distance between the adjacent discrete points; (See [0072], [0070]: “The numbers (1 or 0) on each line 904 represent the cost assigned to the lane change maneuver. With these costs assigned, computing a lane-level path from driver's current position to any downstream link can be performed by well-established shortest path algorithms. The minimum cost of the path gives the minimum number of lane changes required for the driver to stay on his/her current path. By tracking the predecessor of each vertex along the shortest path, it can be determined where a lane change should take place and its distance from the current position. By applying techniques such as depth-first or breadth-first search on lane graph 900, alternative lane paths from the current position (i.e., origin) to a chosen downstream destination can be enumerated.” The examiner interprets where Determining distance to origin by accumulating is shown in vehicle location using "data triplets" which include a "unique road segment identifier" and a "position... expressed in terms of relative distance from either end;" and tracking the predecessor of each vertex along the shortest path" to determine a "distance from the current position." (In a graph-based simulation, distance along a path is calculated by the summation (accumulation) of the lengths of the edges connecting sequential vertices.)) calculating a difference between the distance from each of the N discrete points to the origin of the road that the vehicle is on and the distance from the current position of the vehicle to the origin of the road that the vehicle is on; (See [0070] &[0072]: The examine interprets where Calculating difference between distances is shown in "data triplets" (which use linear distance) " being able to be converted to geographic coordinates.” (To perform this conversion in a computer-implemented simulation using a discrete vertex-based lane graph, the system must resolve the "relative distance" against the known geometry of the graph vertices.)) and determining the longitude and the latitude of the ith discrete point corresponding to a minimum difference as the longitude and the latitude of the vehicle, i being a positive integer less than or equal to N. (See [0072], [0070], 0063]: “In navigation engine 700, possible lane-level trajectories are evaluated by looking ahead at the traffic in lanes downstream on alternative routes by constructing a lane-level network or graph of variable size for only the part of routes within a predefined look-ahead range, but it can also potentially consider all lane-level paths from a location to the vehicle's destination if available” The examiner interprets where Minimum difference (Snapping) is shown in the microscopic simulation evaluating individual vehicles along "lane-level trajectories." (Because Slavin utilizes a discrete graph, a vehicle’s geographic Lat/Long must be determined by selecting the vertex that best represents its linear offset.))
Under MPEP § 2112, a limitation is inherent if it is "necessarily present" in the prior art. Slavin’s apparatus performs a "microsimulation of individual vehicles" on a "lane graph" and converts linear referencing data (relative distance) into "geographic coordinates." In a discrete computer model, there are only two ways to resolve a 1D offset into a 2D/3D coordinate: interpolation or snapping. Slavin claims snapping (selecting the "closest point"). Because Slavin's simulation is "based on the ability to store... and utilize... lane-level information" in a discrete graph to represent vehicle trajectories, the system necessarily identifies which vertex coordinates to use for the vehicle based on which vertex is the closest match to the calculated linear progression. A computer cannot "convert" a linear offset to a geographic coordinate within a discrete vertex-based model without performing the logic of finding the vertex that minimizes the spatial error (minimum difference). Thus, the steps of accumulation and selection of the point with the minimum difference are inherently disclosed.
It would have been obvious to a POSITA before the effective filing date of the invention to implement the coordinate conversion of Slavin using the distance accumulation and minimum difference algorithm of Claim 5 because finding the closest point in a discrete set of vertices is a routine optimization and a predictable method for mapping linear distances to spatial coordinates. The combination of these known simulation components according to known mathematical methods yields nothing more than the predictable result of spatial consistency in a multi-scale simulation environment.
Regarding Claim 6
Slavin in combination with Zhang teaches The method according to claim 3. (See Claim 3) Slavin teaches wherein connecting road section that the vehicle is on in the microscopic traffic simulation comprises M discrete points arranged in order, M being a positive integer; (See [FIG 9], [0064], [0058]: “The navigation engine 700 can be illustrated in the diagram in FIG. 7. In navigation engine 700, historical speed data 701 are used to populate a geographic database and model 702 representing the region-wide network (4). Records in the database represent road segments, lanes, and lane connectors as described. Together with historical speed data 701, the network is used to establish temporal and spatial patterns of traffic flow and congestion. Known traffic signal timing and management data 703 and estimates of travel demand 704, either measured or calibrated using historical data (e.g., traffic counts), also are stored with the network model and used to run simulations. Additionally, real-time data 705, including speed measurements from mobile telephones, detectors, and cameras, and incident reports and timing data 706, for example from a traffic management center, are used to feed current information to the network.”
[FIG 7]:
PNG
media_image8.png
870
794
media_image8.png
Greyscale
The examiner interprets where connecting road section with M discrete points in order is shown in a "lane-level network (otherwise known as a lane graph)" which is a model used for "microsimulation of vehicle movements;” where the lane graph contains "vertices" and "edges;” where "lane connectors" within intersections (connecting road sections) as part of this network; where In FIG. 9, the lane graph 900 represents these connectors using ordered "vertices" (discrete points).) and determining the longitude and the latitude of the vehicle according to a serial number of the connecting road section that the vehicle is on and a distance from the current position of the vehicle to an origin of the connecting road section that the vehicle is on comprises: (See [0072]: The examiner interprets where Determination using serial number and distance is shown in representing lane paths as a "sequence of data triplets" comprising (1) a "unique road segment identifier" (serial number) and (3) a "position... expressed in terms of relative distance from either end" (distance from origin); where these triplets "could be converted to geographic coordinates".) determining a longitude and a latitude of an ith discrete point closest to the current position of the vehicle in the M discrete points in the connecting road section that the vehicle is on as the longitude and the latitude of the vehicle according to the serial number of the connecting road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the connecting road section that the vehicle is on, i being a positive integer less than M. (See [0064], [FIG 8 & 9], [0081] & [0096]: “Given a desired route or a set of alternative routes, a lane graph may be constructed for the portion of route within a look-ahead range. This allows more detailed microsimulation to be performed and data to be assembled only for a much smaller and selected area of the network. The task of the lane-level path optimizer, therefore, is to evaluate the alternative trajectories or lane paths to estimate the travel time and delay and compute an index of driving experience. The best alternative is then recommended as navigation guidance.” [0066]: “As an example, FIG. 9 is part of lane graph 900 for a driver traveling in upstream segment 1. The graph contains vertices (representing lanes) and edges (representing relations between lanes). Depending whether a driver is going to exit 1 (808), exit 2 (809), or further downstream through the mainline, some of the vertices that represent the lanes can be trimmed (e.g., removed from the driver's intended route) or more vertices can be added.” The examiner interprets where Selecting coordinates of the closest (ith) point is shown in evaluating "lane-level alternative paths" and trajectories using these vertices; where in a computer-implemented "microsimulation" using a "lane graph" of discrete "vertices," the only available geographic coordinates for a vehicle are those assigned to the vertices themselves; where to "convert" a linear offset to a coordinate within such a discrete model, the system must necessarily resolve the vehicle's position to the coordinates of the vertex that most closely matches the calculated linear progress (the "closest point").
Under MPEP § 2112, a limitation is inherent if it is "necessarily present" in the prior art. Slavin discloses a computer-implemented "microsimulation of individual vehicles" on a "lane graph" and teaches converting linear referencing data (relative distance) into "geographic coordinates".
In a discrete computer model (a graph of vertices), there are two standard ways to resolve a 1D offset into a 2D coordinate: linear interpolation along an edge or snapping to a vertex. Claim 6 specifies snapping to the "closest point." Because Slavin's simulation is "based on the ability to store... and utilize... lane-level information" in a discrete graph of vertices, the system necessarily identifies which vertex coordinates to use for the vehicle representation based on which vertex is the closest match to the calculated linear progression along that path. A computer cannot perform a conversion from a linear identifier to a geographic coordinate within a discrete vertex-based model without performing the logic of identifying the vertex that approximates that location. Therefore, selecting the coordinates of the closest discrete point is inherently disclosed.
Zhang further teaches determining a longitude and a latitude of an ith discrete point closest to the current position of the vehicle in the M discrete points in the connecting road section that the vehicle is on as the longitude and the latitude of the vehicle according to the serial number of the connecting road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the connecting road section that the vehicle is on, i being a positive integer less than M. (See [0020]: The examiner interprets where Using (i)th discrete point closest to current position is shown in Spatial matching of boundaries.)
It would have been obvious to a POSITA before the effective filing date of the invention to implement the conversion step of Slavin by representing the road as (M) discrete points (as suggested by Slavin vertices) and determining the vehicle's coordinate by selecting the closest (i)th point. This combination represents the application of a known technique (discrete point mapping) to a known device ready for improvement (the conversion module of Slavin) to yield predictable results (accurate spatial placement of vehicles in a higher-fidelity simulation). The specific algorithmic step of choosing the "closest point" is a routine optimization within the ordinary capabilities of a programmer in the field of simulation conversion.
Regarding Claim 7
Slavin in combination with Zhang teaches The method according to claim 6. (See claim 6) Slavin teaches wherein determining a longitude and a latitude of an ith discrete point closest to the current position of the vehicle in the M discrete points in the connecting road section that the vehicle is on as the longitude and the latitude of the vehicle according to the serial number of the connecting road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the connecting road section that the vehicle is on comprises: obtaining a distance between adjacent discrete points in the M discrete points according to the serial number of the connecting road section that the vehicle is on; (See [0064], [0066], [0055]: The examiner interprets where Obtaining distance between adjacent points is shown in a "lane-level network (otherwise known as a lane graph)" where infrastructure is represented by a sequence of "vertices" and "edges;” where Slavin explicitly defines "lane connectors" within intersections (connecting road sections) as part of this network; where the edges in this graph possess attributes, such as distance or travel time, representing the distance between adjacent discrete points (vertices).) determining a distance from each of the M discrete points in the connecting road section that the vehicle is on to the origin of the connecting road section that the vehicle is on by accumulating the distance between the adjacent discrete points; (See [0072] & [0070]: The examiner interprets where Determining distance by accumulating is shown in representing vehicle position using "data triplets" which include a "(1) unique road segment identifier" and a "(3) position... expressed in terms of relative distance from either end" and "tracking the predecessor of each vertex along the shortest path" to determine a "distance from the current position". (In any graph-based model, the distance along a path is calculated by the summation (accumulation) of edge lengths connecting sequential vertices.)) calculating a difference between the distance from each of the M discrete points to the origin of the connecting road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the connecting road section that the vehicle is on; See [0072] & [0070]: The examiner interprets where Calculating difference is shown in "data triplets" (which rely on linear distance) "could be converted to geographic coordinates". (To resolve a continuous linear offset to a coordinate within a discrete vertex-based graph, the computer must necessarily compare the target offset to the known cumulative distances of the vertices in the connector.) and determining the longitude and the latitude of the ith discrete point corresponding to a minimum difference as the longitude and the latitude of the vehicle, i being a positive integer less than or equal to M. (See [0063], [0064]: The examiner interprets where Minimum difference (Snapping) is shown in Slavin’s microscopic simulation uses these vertices to define vehicle "trajectories" and "lane alignment". In a discrete computer model, a vehicle's geographic Lat/Long is determined by selecting the coordinates of the vertex that most closely matches (minimum difference) the vehicle's calculated linear progress.
Under MPEP § 2112, a feature is inherent if it is "necessarily present" in the prior art. Slavin discloses a "microsimulation of individual vehicles" on a "lane graph" and teaches converting linear referencing data (triplets) into "geographic coordinates".
A computer-implemented simulation using a discrete graph of vertices has no geometric information between vertices unless it performs interpolation. Slavin specifically claims the alternative: snapping to the "closest point." Because Slavin's simulation is "based on the ability to store... and utilize... lane-level information" in a discrete graph to represent vehicle trajectories, the system necessarily identifies which vertex coordinates to use for the vehicle based on which vertex is the closest match to the calculated linear progression along the path. A computer cannot "convert" a linear offset to a geographic coordinate within a discrete vertex-based model without performing the logic of finding the vertex that minimizes the spatial error (minimum difference). Thus, the steps of accumulation and selection of the point with the minimum difference are inherently disclosed.
It would have been obvious to a POSITA before the effective filing date of the invention to implement the coordinate conversion of Slavin using the claimed mathematical sequence because this is a standard technique for "snapping" linear-referenced data to a vertex-based geographic model. Specifically, to determine which vertex in a lane graph (Slavin) corresponds to a vehicle's mesoscopic offset, a POSITA would predictably accumulate the lengths of the graph edges to find vertex distances from the origin and then select the vertex that minimizes the error relative to the vehicle's position. This represents a routine application of known spatial mapping logic to the fused simulation environment of Zhang to achieve the predictable result of accurate vehicle rendering in a high-precision microscopic zone.
Regarding Claim 8
Slavin in combination with Zhang teaches The method according to claim 2. (See claim 2) Slavin teaches wherein performing conversion according to the serial number of the road section that the vehicle is on and the distance from the current position of the vehicle to the origin of the road section that the vehicle is on to obtain the second vehicle traffic data of the vehicle in the microscopic traffic simulation comprises: (See [0081] & [0072]: The examiner interprets where Conversion to Micro data using serial number and distance is shown in converting "data triplets" (Unique ID + Relative Distance) into Micro-level coordinates and trajectories.) determining the front orientation of the vehicle (See [Abstract] & [0081]: The examiner interprets where Determining the front orientation is shown in "microsimulation of vehicle movements" and "lane-level trajectories," which functionally require and define vehicle heading.) according to a serial number of a road that the vehicle is on and a distance from the current position of the vehicle to an origin of the road that the vehicle is on. (See [0064] & [0067]: The examiner interprets where Orientation determined according to serial number and distance is shown in a "lane graph" representing "lane alignment" where ID and distance are used to locate the vehicle's state on that alignment.)
Under MPEP § 2112, a limitation is inherent if it is "necessarily present" in the prior art. Slavin discloses a "microsimulation of individual vehicles" that follows "lane-level trajectories" along a "lane graph" that represents "lane alignment". A "microsimulation" of a vehicle "movement" or "trajectory" along a "lane alignment" is physically and mathematically impossible without the vehicle having a heading or "front orientation." Because Slavin converts linear referencing data (ID and Distance) to locate a vehicle on these lane alignments, the determination of the vehicle’s orientation based on those inputs is a mandatory functional requirement of Slavin’s disclosed apparatus. A computer cannot resolve a vehicle's motion vector at a specific linear offset on a specific road segment without deriving that vector from the road's geometry at that point. Thus, the determination of front orientation according to the serial number and distance is inherently disclosed.
Slavin fails to explicitly name "front orientation" in the context of the conversion, However, Yang further teaches determining the front orientation of the vehicle (See [0045]: Ther examiner interprets where Determining front orientation is shown in microscopic, simulated data including the "position and state of the vehicle".)
While Slavin does not explicitly recite the specific step of "determining the front orientation" from the road ID and distance, Zhang teaches determining the front orientation of the vehicle (See [0020]]: The examiner interprets where the requirement for state transfer/orientation is shown in spatial matching" of boundaries and the input of vehicle paths during mesoscopic-to-microscopic transfers to maintain simulation continuity.
It would have been obvious to a POSITA before the effective filing date of the invention to derive the vehicle's "front orientation" from the road serial number and distance because such information is a predictable and necessary requirement for modeling "individual vehicle trajectories" in the microscopic environment taught by Slavin. Specifically, in a microscopic simulation that models lane-level behavior, a vehicle's heading is inherently fixed by the geometry of the lane at its given longitudinal offset (distance from origin). Deriving this heading from known GIS road geometry is a routine technique for achieving the "spatial matching" described in Zhang, yielding the predictable result of accurate vehicle rendering at the simulation boundary.
Regarding Claim 9
Slavin in combination with Zhang teaches The method according to claim 8. (See claim 8) Slavin teaches wherein determining the front orientation of the vehicle according to a serial number of a road that the vehicle is on and a distance from the current position of the vehicle to an origin of the road that the vehicle is on comprises: (See [0072]: The exaxime interprets where Determination from ID and Distance is shown in "data triplets" (ID + Offset) to establish simulation state.) determining an ith discrete point closest to the current position of the vehicle according to the serial number of the road that the vehicle is on and the distance from the current position of the vehicle to the origin of the road that the vehicle is on; (See [0066] & [0071]: The examiner interprets where Determining closest ith point (vertex) is shown in "lane graph" with "vertices" and "edges" to locate vehicles.) and determining the front orientation of the vehicle according to the ith discrete point and an (i−1)th discrete point, i being an integer less than N+1 and greater than 1. (See [0064] & [0081]: The examiner interprets where Orientation from ith and (i-1)th point is shown in Graph representing "lane alignment" and "trajectories" via edge connections.)
Under MPEP § 2112, a limitation is inherent if it is "necessarily present" in the prior art. Slavin’s apparatus performs a "microsimulation of individual vehicles" that follows "lane alignment" and "lane-level trajectories" along a "lane graph" composed of vertices and edges. In a computer-implemented simulation using a discrete graph, a vehicle’s heading or "front orientation" along an "alignment" is not an independent variable but is a derivative of the graph's geometry. To represent a vehicle moving through a "trajectory" defined by vertices i−1 and i, the simulation engine must calculate the vehicle's orientation based on the segment connecting those two points. There is no other way to resolve "alignment" in a discrete graph model. Therefore, the determination of orientation based on the relationship between the current discrete point and its predecessor is inherently disclosed as a necessary functional requirement of Slavin’s lane graph navigation engine.
While Slavin does not explicitly name the trigonometric calculation of orientation using the “(i)th and (i-1)th discrete points," Zhang teaches determining the front orientation of the vehicle according to the ith discrete point and an (i−1)th discrete point, i being an integer less than N+1 and greater than 1. (See [0020]: The examiner interprets where Orientation from (i)th and (i-1)th points is shown in the necessity of "spatial matching" for vehicle states during mesoscopic-to-microscopic transfers.)
It would have been obvious to a POSITA before the effective filing date of the invention to calculate the "front orientation" (heading) of the vehicle by determining the closest vertex (the (i)th point) and using the segment between it and the previous vertex (the (i-1) point) to define the orientation angle. This represents a routine application of basic geometric principles to the "lane graph" and "trajectories" taught by Slavin to satisfy the continuity and "spatial matching" requirements of Zhang, yielding the predictable result of a vehicle correctly oriented along its high-fidelity lane path.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to AARIC RAYJEE MARKS whose telephone number is (571)467-6372. The examiner can normally be reached Monday-Friday 8am-5pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Ryan Pitaro can be reached at (571) 272-4071. 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.
/AARIC R MARKS/Examiner, Art Unit 2188
/RYAN F PITARO/Supervisory Patent Examiner, Art Unit 2188
1 See Spec [0073]: “That is, step 340 includes at least one of the following sub-steps: performing conversion according to the serial number of the road section that the vehicle is on and the longitude and the latitude of the vehicle to obtain the distance from the current position of the vehicle to the origin of the road section in the mesoscopic traffic simulation; and performing conversion according to the serial number of the road section that the vehicle is on, the longitude and the latitude of the vehicle, and the speed of the vehicle to obtain the landing time of the vehicle on the next road in the mesoscopic traffic simulation.”
2 See Spec [0231]: “FIG. 13 is a schematic diagram of a structure of a computer device according to an embodiment. The computer device 1300 includes a central processing unit (CPU) 1301, a system memory 1304 including a random access memory (RAM) 1302 and a read-only memory (ROM) 1303, and a system bus 1305 that connects the system memory 1304 to the CPU 1301. The computer device 1300 further includes a basic input/output (I/O) system 1306 that helps information transmission between devices in the computer device, and a mass storage device 1307 configured to store an operating system 1313, an application program 1314, and another program module 1315.”
Prosecution Insights