Notice of Pre-AIA or AIA Status
1. The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
2. Claim 1 is rejected under 35 U.S.C. 101 because the claimed invention is directed to abstract idea without significantly more.
The determination of whether a claim recites patent ineligible subject matter is a 2 step inquiry.
STEP 1: the claim does not fall within one of the four statutory categories of invention (process, machine, manufacture or composition of matter), see MPEP 2106.03, or
STEP 2: the claim recites a judicial exception, e.g. an abstract idea, without reciting additional elements that amount to significantly more than the judicial exception, as determined using the following analysis: see MPEP 2106.04
STEP 2A (PRONG 1): Does the claim recite an abstract idea, law of nature, or natural phenomenon? see MPEP 2106.04(II)(A)(1)
STEP 2A (PRONG 2): Does the claim recite additional elements that integrate the judicial exception into a practical application? see MPEP 2106.04(II)(A)(2) and 2106.05(a) thru (d) for explanations.
STEP 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception? see MPEP 2106.05
101 Analysis – Step 1
Claim 1 is directed to a method (i.e., a process). Therefore, claim 1 is within at least one of the four statutory categories.
101 Analysis – Step 2A, Prong I
Regarding Prong I of the Step 2A analysis, the claims are to be analyzed to determine whether they recite subject matter that falls within one of the follow groups of abstract ideas: a) mathematical concepts, b) certain methods of organizing human activity, and/or c) mental processes. see MPEP 2106(A)(II)(1) and MPEP 2106.04(a)-(c)
Independent claim 1 includes limitations that recite an abstract idea (emphasized below [with the category of abstract idea in brackets]) and will be used as a representative claim for the remainder of the 101 rejection. Claim 1 recites:
A computer-implemented method for generating lane data for use in a digital map, wherein the digital map comprises data representative of longitudinal portions of navigable elements of a network of navigable elements in a geographic region, and wherein each longitudinal portion is defined, in the digital map, at least in part by an edge between two nodes; the method comprising:
receiving probe data for a longitudinal portion of a navigable element, wherein the probe data comprises a set of a plurality of positions of a plurality of devices that have traversed along the longitudinal portion of the navigable element;
determining, based at least in part on the probe data, a subset of the probe data for each of a plurality of segments of the longitudinal portion of the navigable element of the network [mental process/step];
determining, based at least in part on the subset of probe data for each segment, lane layout information for each segment, wherein the lane layout information for each segment comprises information indicative of: a number, usage and/or geometry of lanes in the respective segment [mental process/step];
determining, based at least in part on the lane layout information for each segment, at least first and second sections of the navigable element, wherein the first section of the navigable element comprises a first set of consecutive segments having a first lane layout, and wherein the second section of the navigable element comprises a second set of consecutive segments having a second lane layout different to the first lane layout [mental process/step]; and
generating, based at least in part on the first and second sections of the navigable element, lane data for the navigable element wherein the lane data is indicative of a change of lane layout.
The examiner submits that the foregoing bolded limitation(s) constitute a “certain method of organizing human activity” and a “mental process” because under its broadest reasonable interpretation, the claim covers performance of the limitation in the human mind. For example, “determining...a subset of probe data…” in the context of the claim encompasses a person evaluating the received data to determine a set of data from plurality of vehicles relevant to a road segment of a navigable element. Also, “determining...lane layout information…” in the context of the claim encompasses a person evaluating the determined subset of probe data to determine how a lane is laid out in terms of number of lanes, uses, and/or geometric shape. Further, “determining... at least first and second sections of the navigable element…” in the context of the claim encompasses a person evaluating the determined lane layout information to determine that there are two lane sections that indicates a change or a difference of lane layout between two sections. Accordingly, the claim recites at least one abstract idea.
101 Analysis – Step 2A, Prong II
Regarding Prong II of the Step 2A analysis, the claims are to be analyzed to determine whether the claim, as a whole, integrates the abstract into a practical application. see MPEP 2106.04(II)(A)(2) and MPEP 2106.04(d)(2). It must be determined whether any additional elements in the claim beyond the abstract idea integrate the exception into a practical application in a manner that imposes a meaningful limit on the judicial exception. The courts have indicated that additional elements merely using a computer to implement an abstract idea, adding insignificant extra solution activity, or generally linking use of a judicial exception to a particular technological environment or field of use do not integrate a judicial exception into a “practical application.”
In the present case, the additional limitations beyond the above-noted abstract idea are as follows (where the underlined portions are the “additional limitations” [with a description of the additional limitations in brackets], while the bolded portions continue to represent the “abstract idea”.):
A computer-implemented method for generating lane data for use in a digital map, wherein the digital map comprises data representative of longitudinal portions of navigable elements of a network of navigable elements in a geographic region, and wherein each longitudinal portion is defined, in the digital map, at least in part by an edge between two nodes [generic linking to technical field, 2106.05(h)]; the method comprising:
receiving probe data for a longitudinal portion of a navigable element, wherein the probe data comprises a set of a plurality of positions of a plurality of devices that have traversed along the longitudinal portion of the navigable element [insignificant pre-solution activity (data gathering) 2106.05(g)];
determining, based at least in part on the probe data, a subset of the probe data for each of a plurality of segments of the longitudinal portion of the navigable element of the network [mental process/step];
determining, based at least in part on the subset of probe data for each segment, lane layout information for each segment, wherein the lane layout information for each segment comprises information indicative of: a number, usage and/or geometry of lanes in the respective segment [mental process/step];
determining, based at least in part on the lane layout information for each segment, at least first and second sections of the navigable element, wherein the first section of the navigable element comprises a first set of consecutive segments having a first lane layout, and wherein the second section of the navigable element comprises a second set of consecutive segments having a second lane layout different to the first lane layout [mental process/step]; and
generating, based at least in part on the first and second sections of the navigable element, lane data for the navigable element wherein the lane data is indicative of a change of lane layout [insignificant post solution activity of merely outputting the result of the mental process 2106.05(g)].
For the following reason(s), the examiner submits that the above identified additional limitations do not integrate the above-noted abstract idea into a practical application.
Regarding the additional limitation of “a computer implemented method…”, the examiner submits that this is recited at a high level of generality and serves only to link the particular abstract concept to a broad technical field. Regarding the limitations of “receiving…” and “generating…”, these limitations amount to no more than mere instruction to apply the exception using a generic computer. Regarding the “receive…”, specifically, this merely comprises gathering data from sensors and network and it can be done through a generic computer and processor. Regarding the “generating…”, specifically, this merely comprises outputting the result of the mental process and it does not specify if it outputs to any source.
Thus, taken alone, the additional elements do not integrate the abstract idea into a practical application. Further, looking at the additional limitation(s) as an ordered combination or as a whole, the limitation(s) add nothing that is not already present when looking at the elements taken individually. For instance, there is no indication that the additional elements, when considered as a whole, reflect an improvement in the functioning of a computer or an improvement to another technology or technical field, apply or use the above-noted judicial exception to effect a particular treatment or prophylaxis for a disease or medical condition, implement/use the above-noted judicial exception with a particular machine or manufacture that is integral to the claim, effect a transformation or reduction of a particular article to a different state or thing, or apply or use the judicial exception in some other meaningful way beyond generally linking the use of the judicial exception to a particular technological environment, such that the claim as a whole is not more than a drafting effort designed to monopolize the exception. see MPEP § 2106.05. Accordingly, the additional limitation(s) do/does not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea.
101 Analysis – Step 2B
Regarding Step 2B of the Revised Guidance, representative independent claim 1 does not include additional elements (considered both individually and as an ordered combination) that are sufficient to amount to significantly more than the judicial exception for the same reasons to those discussed above with respect to determining that the claim does not integrate the abstract idea into a practical application. As discussed above with respect to the integration of the abstract idea into a practical application, the additional element of “generating” to perform the generating an output data of lane layout change amounts to nothing more than mere instructions to apply the exception using a generic computer. Mere instructions to apply an exception using a generic computer cannot provide an inventive concept. And, as discussed above, the additional limitations related to acquiring and transmitting data, the examiner submits that these limitations are insignificant extra-solution activity.
Independent claims 13 and 17 recites similar limitations to independent claim 1 through an apparatus and a non-transitory computer readable storage medium, which further indicates a mental process, and therefore requires a similar rejection.
Dependent claim(s) 2-12, 14-16, and 18-20 do not recite any further limitations that cause the claim(s) to be patent eligible. Rather, the limitations of dependent claims are directed toward additional aspects of the judicial exception and/or well-understood, routine and conventional additional elements that do not integrate the judicial exception into a practical application. Dependent claims 2-4, 14-15, and 18-19 only recite additional output data relating to lane layout changes. Dependent claims 5-6, 9-11, 16, and 20 only recite further determining data in relation to lane layouts, navigable element, and different segments and sections of the navigable element based on received and other determined data. Dependent claims 7-8 and 12 only recite additional information of probe data, lane layout, and navigable element. Therefore, dependent claims 2-11 and 14-20 are not patent eligible under the same rationale as provided for in the rejection of claim 1.
Claim Rejections - 35 USC § 102
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.
3. Claim 1-4, 6-8, 12-15, and 17-19 are rejected under 35 U.S.C 102(a)(1) as being anticipated by Shapira et al. (US 20220082403A1).
Regarding claim 1, Shapira teaches a computer-implemented method for generating lane data for use in a digital map (see [0284] where a server 1230, through a processor, generates a road navigation model for a common road segment and store as a portion of a sparse map.), wherein the digital map comprises data representative of longitudinal portions of navigable elements of a network of navigable elements in a geographic region (see [0214] where a sparse map includes local maps for vehicles traveling along roadways, i.e. map data representing navigable elements in a geographic region.), and wherein each longitudinal portion is defined, in the digital map, at least in part by an edge between two nodes (see [0275], [0293]-[0294, and [0324] where it describes a path between A and B and a segment A to B within a map skeleton which is formed from nodes and links, with segments connecting junctions, i.e. longitudinal portion defined by an edge between two nodes.); the method comprising:
receiving probe data for a longitudinal portion of a navigable element, wherein the probe data comprises a set of a plurality of positions of a plurality of devices that have traversed along the longitudinal portion of the navigable element (see [0256] where crowdsourcing of various vehicles are used to receive data of vehicles that have travelled on a road segment at different times, which are used to generate or update a road model, i.e. receiving probe data for a navigable element from plurality of devices that have traversed the same navigable element; note also in [0293] and Fig. 14 where there are raw data from multiple drives of separate vehicles at the same time, same vehicle at different times, and/or separate vehicles at separate times to generate a map skeleton.);
determining, based at least in part on the probe data, a subset of the probe data for each of a plurality of segments of the longitudinal portion of the navigable element of the network (see [0284] where a server 1230 receives and stores crowdsource navigation information from multiple vehicles traveled on lanes of road segments at different times and, based on that information, determine trajectories associated with each lane. Further, then, in [0477]-[0478] shows clustering of the trajectories along a road segment by defining a segment normal at a given location and identifying all trajectories that intersect that segment, which is for each longitudinal portion of a navigable element, a server determines a relevant subset of probe data, or crowdsourced trajectory, corresponding to the segment.);
determining, based at least in part on the subset of probe data for each segment, lane layout information for each segment, wherein the lane layout information for each segment comprises information indicative of: a number, usage and/or geometry of lanes in the respective segment (see [0478] where a server 1230 obtains a segment specific subset of crowdsourced trajectory data, i.e. probe data, by defining a segment at a given longitudinal location and identifying the trajectories that intersect the segment. Further, [0502] shows a land layout of the segment specific comparison indicating that the trajectories are clustered together at one or more locations before the lane split feature and clustered separately at one or more locations after the lane split feature, which are different lane layouts at the respective segment locations, i.e. a lane layout information of increase in number of lanes, usage of the lanes and geometry of lanes in the respective segment.);
determining, based at least in part on the lane layout information for each segment, at least first and second sections of the navigable element, wherein the first section of the navigable element comprises a first set of consecutive segments having a first lane layout, and wherein the second section of the navigable element comprises a second set of consecutive segments having a second lane layout different to the first lane layout (see [0502] where first and second trajectories of road segments may be clustered together in at least one first location, which is first section, before a lane split feature and clustered separately in at least one second location, which is second section, after the lane split feature, with locations separated by predetermined longitudinal distance, i.e. lane layout information of first and second segments having different lane layouts.); and
generating, based at least in part on the first and second sections of the navigable element, lane data for the navigable element wherein the lane data is indicative of a change of lane layout (see [0503] where updating a vehicle road navigation model includes a first target trajectory corresponding to a pre-split land and extending along one post-split lane and a second target trajectory branching from the first target trajectory and extending along the other post-split lane, i.e. first and second sections of single lane to two lane layout change.).
Regarding claim 2, Shapira teaches the computer-implemented method of claim 1, wherein the change of lane layout comprises at least one of:
a lane closure (see [0485] and [0486] where a road obstacle, such as a stalled vehicle, an animal, an emergency or service vehicle, a road construction, a lane closure, etc., is present and a server 1230 detects a lane merges, i.e. a lane closure);
a lane re-opening;
a contraflow lane;
a change of lane usage (see [0508]-[0510] where a first or second trajectory that are split is determined to be associated with a turn lane, an exit ramp, a passing lane, or the like, i.e. change of lane layout to indicate that lane usage changes to one of a turn lane, an exit ramp, a passing lane, or the like.);
a change of lane number (see [0485] and [0486 where a road obstacle, such as a stalled vehicle, an animal, an emergency or service vehicle, a road construction, a lane closure, etc., is present and a server 1230 detects a lane convergence, i.e. a number of lane changing due to reduction of lanes from merging.); and
a change of lane geometry (see [0478] as shown in claim 1 where lane layout has a split lane section, which is a change of lane geometry from a single lane to two lanes that diverges to two different directions.).
Regarding claim 3, Shapira teaches the computer-implemented method of claim 1, wherein the digital map provides an indication of a reference lane layout for the navigable element (see [0224]-[0229] where sparse map provides a road segment with lane boundaries and describe lanes network information through geometric descriptors and meta-data, i.e. digital map that provides reference lane layout of a navigable element.), and wherein the lane data for the navigable element layout comprises information indicative of at least one of:
a different lane layout to the reference lane layout (see [0503] where there is an update of road navigation model that includes an added branch target trajectories corresponding to a different lane layout of split layout to a reference lane layout of pre-split layout.);
a modification to the reference lane layout (see [0277] where a server 1230 identifies road model changes, i.e. reference lane layout modification, such as constructions, detours, new signs, removal of signs, etc., and update the model upon receiving new data from vehicles. Note also in [0336] where a refinement of vehicle trajectory based on image data from onboard camera will update the server for updating sparse data map. Further, [0504]-[0505] and 37A-38B shows updating and adjusting trajectory branch positions based on actual trajectory that has navigated along a road segment and removing anomalies, i.e. adjusting reference lane layout based on actual traveled trajectory.); and
a temporary adjustment to the reference lane layout (see [0277] where a server identifies road model changes, i.e. reference lane layout adjustment, such as constructions, detours, new signs, removal of signs, etc., and update the model upon receiving new data from vehicles. Note that it is temporary due to the fact that changes such as constructions and detours are not permanent changes.).
Regarding claim 4, Shapira teaches the computer-implemented method of claim 1, wherein the lane layout data for the navigable element comprises information indicative of at least one of:
which particular one or more lanes of the navigable element has undergone a change of lane layout (see [0471]-[0472] and Fig. 36 where a road segment initially two lanes and a number of lanes increases along a direction of travel and there is a split of a lane, i.e. one or more lanes of a navigable element changes its layout from two to three lanes, which includes being an exit lane or a turn lane. Note also in [0485]-[0486] where there is an indication of convergence, or merging, of lanes based on obstacles, lane closure, or construction.); and
a position of the change of lane layout (see [0480]-[0481] where a server 1230 samples trajectories at a plurality of longitudinal distances before and/or after a cluster point and determines where groups begin to diverge, which then determine a branch point, i.e. a position of a change of lane layout.).
Regarding claim 6, Shapira teaches the computer-implemented method of claim 1, wherein generating the lane data for the navigable element comprises generating a position associated with the change of lane layout (see [0479] where target trajectories are determined and a target trajectory begins at a branch point or divergence point corresponding with clustering of data, i.e. generating position at a point of change of lane layout.), and wherein the position is based at least in part on a position:
where the first and second sections of the navigable element abut (see [0479] and [0503]-[0504] where a target trajectory begins at a branch point or divergence point that is adjacent or contiguous to a first target trajectory, and where second target trajectory begins at a branch point adjacent to or contiguous to the first trajectory, i.e. a position where the first and second sections abut, or connected.); or
between the first and second sections of the navigable element (see [0479] where a target position, or point, is at a branch or divergence point, and note [0480]-[0481] where a server samples positions before and after a coarse cluster point and refines a branch point where trajectories begins to diverge, i.e. a refined position between a pre-split first section and post-split second section).
Regarding claim 7, Shapira teaches the computer-implemented method of claim 1, further comprising at least one or more of:
associating at least a portion of the probe data to the navigable element (see [0284] where a server 1230 receives and stores crowdsource navigation information from multiple vehicles traveled on lanes of road segments at different times and, based on that information, determine trajectories associated with each lane. Further, then, in [0477]-[0478] shows clustering of the trajectories along a road segment by defining a segment normal at a given location and identifying all trajectories that intersect that segment, which is for each longitudinal portion of a navigable element, a server determines a relevant subset of probe data, or crowdsourced trajectory, corresponding to the segment.);
associating at least a portion of the probe data to the longitudinal portion of the navigable element (see [0248] and [0477]-[0478] as indicated above where clustering of the trajectories along a road segment is shown by defining a segment normal at a given location and identifying all trajectories that intersect that segment, which is for each longitudinal portion of a navigable element, a server determines a relevant subset of probe data, or crowdsourced trajectory, corresponding to the segment.); and
associating at least a portion of the probe data to each of the plurality of segments of the longitudinal portion of the navigable element (see [0477]-[0478] where it shows that a server 1230, at a given local segment along a road, identifies trajectories that intersect the segment, i.e. associating overall relevant portion of probe data to each of plurality of segments.).
Regarding claim 8, Shapira teaches the computer-implemented method of claim 1, wherein each of the plurality of segments of the navigable element is associated with a length of the navigable element (see [0477] where clustering determined along road segment have predetermined intervals, i.e. segments associated with a length of navigable element as clustering are part of the navigable element.), and wherein the length is:
less than 100 metres; less than 75 metres; less than 50 metres; or less than 25 metres (see [0477] where predetermined intervals of clusters are 1 m, 2 m, 5 m, 10 m, 20 m, 50 m, etc., which clearly includes lengths less than 100 m, 75 m, 50 m, and 25 m. Note that having road analyzed at longitudinal intervals are reasonably interpreted as local portions that are plurality of segments of a navigable element, in which intervals lengths of clusters within navigable element are in association with a length of the navigable element itself.).
Regarding claim 12, Shapira teaches the computer-implemented method of claim 1, wherein the probe data comprises:
historical probe data (see [0256] where crowdsourcing of various vehicles are used to receive data of vehicles that have travelled on a road segment at different times, which are used to generate or update a road model, i.e. receiving historical probe data for a navigable element from plurality of devices that have traversed the same navigable element; note also in [0293] and Fig. 14 where there are raw data from multiple drives of separate vehicles at the same time, same vehicle at different times, and/or separate vehicles at separate times to generate a map skeleton which clearly includes historical probe data of different vehicles at different times and same vehicle at different times.) ;
substantially current probe data (see [0272]-[0273] where a server continuously and periodically update road model when receiving new data from vehicles, i.e. substantially current probe data that is received continuously or in frequent periodic manner to update road model when there is a lane closing or some other changes.); and/or
real-time probe data (see [0272]-[0273] where a server continuously an update road model when receiving new data from vehicles, i.e. real-time probe data that are received continuously to update road model when there is a lane closing or some other changes. Note also [0368]-[0369] where a navigation information from a vehicle is transmitted to a server 1230 and information from various sensors and components are transmitted to the server, i.e. real-time data being transmitted to a server.).
Regarding claim 13, Shapira teaches an apparatus that generates lane data for use in a digital map (see [0284] where a server 1230, through a processor, generates a road navigation model for a common road segment and store as a portion of a sparse map.), wherein the digital map comprises data representative of longitudinal portions of navigable elements of a network of navigable elements in a geographic region (see [0214] where a sparse map includes local maps for vehicles traveling along roadways, i.e. map data representing navigable elements in a geographic region.), and wherein each longitudinal portion is defined, in the digital map, at least in part by an edge between two nodes (see [0275], [0293]-[0294, and [0324] where it describes a path between A and B and a segment A to B within a map skeleton which is formed from nodes and links, with segments connecting junctions, i.e. longitudinal portion defined by an edge between two nodes.), the apparatus comprising:
processing circuity (see [0284] where a server 1230 uses a processor) configured to:
receive probe data for a longitudinal portion of a navigable element, wherein the probe data comprises a set of a plurality of positions of a plurality of devices that have traversed along the longitudinal portion of the navigable element (see [0256] where crowdsourcing of various vehicles are used to receive data of vehicles that have travelled on a road segment at different times, which are used to generate or update a road model, i.e. receiving probe data for a navigable element from plurality of devices that have traversed the same navigable element; note also in [0293] and Fig. 14 where there are raw data from multiple drives of separate vehicles at the same time, same vehicle at different times, and/or separate vehicles at separate times to generate a map skeleton.);
determine, based at least in part on the probe data, a subset of the probe data for each of a plurality of segments of the longitudinal portion of the navigable element of the network (see [0284] where a server 1230 receives and stores crowdsource navigation information from multiple vehicles traveled on lanes of road segments at different times and, based on that information, determine trajectories associated with each lane. Further, then, in [0477]-[0478] shows clustering of the trajectories along a road segment by defining a segment normal at a given location and identifying all trajectories that intersect that segment, which is for each longitudinal portion of a navigable element, a server determines a relevant subset of probe data, or crowdsourced trajectory, corresponding to the segment.);
determine, based at least in part on the subset of probe data for each segment, lane layout information for each segment, wherein the lane layout information for each segment comprises information indicative of: a number, usage and/or geometry of lanes in the respective segment (see [0478] where a server 1230 obtains a segment specific subset of crowdsourced trajectory data, i.e. probe data, by defining a segment at a given longitudinal location and identifying the trajectories that intersect the segment. Further, [0502] shows a land layout of the segment specific comparison indicating that the trajectories are clustered together at one or more locations before the lane split feature and clustered separately at one or more locations after the lane split feature, which are different lane layouts at the respective segment locations, i.e. a lane layout information of increase in number of lanes, usage of the lanes and geometry of lanes in the respective segment.);
determine, based at least in part on the lane layout information for each segment, at least first and second sections of the navigable element, wherein the first section of the navigable element comprises a first set of consecutive segments having a first lane layout, and wherein the second section of the navigable element comprises a second set of consecutive segments having a second lane layout different to the first lane layout (see [0502] where first and second trajectories of road segments may be clustered together in at least one first location, which is first section, before a lane split feature and clustered separately in at least one second location, which is second section, after the lane split feature, with locations separated by predetermined longitudinal distance, i.e. lane layout information of first and second segments having different lane layouts.); and
generate, based at least in part on the first and second sections of the navigable element, lane data for the navigable element wherein the lane data is indicative of a change of lane layout (see [0503] where updating a vehicle road navigation model includes a first target trajectory corresponding to a pre-split land and extending along one post-split lane and a second target trajectory branching from the first target trajectory and extending along the other post-split lane, i.e. first and second sections of single lane to two lane layout change.).
Regarding claim 14, Shapira teaches the apparatus of claim 13, wherein the digital map provides an indication of a reference lane layout for the navigable element (see [0224]-[0229] where sparse map provides a road segment with lane boundaries and describe lanes network information through geometric descriptors and meta-data, i.e. digital map that provides reference lane layout of a navigable element.), and wherein the lane data for the navigable element layout comprises information indicative of at least one of:
a different lane layout to the reference lane layout (see [0503] where there is an update of road navigation model that includes an added branch target trajectories corresponding to a different lane layout of split layout to a reference lane layout of pre-split layout.);
a modification to the reference lane layout (see [0277] where a server 1230 identifies road model changes, i.e. reference lane layout modification, such as constructions, detours, new signs, removal of signs, etc., and update the model upon receiving new data from vehicles. Note also in [0336] where a refinement of vehicle trajectory based on image data from onboard camera will update the server for updating sparse data map. Further, [0504]-[0505] and 37A-38B shows updating and adjusting trajectory branch positions based on actual trajectory that has navigated along a road segment and removing anomalies, i.e. adjusting reference lane layout based on actual traveled trajectory.); and
a temporary adjustment to the reference lane layout (see [0277] where a server identifies road model changes, i.e. reference lane layout adjustment, such as constructions, detours, new signs, removal of signs, etc., and update the model upon receiving new data from vehicles. Note that it is temporary due to the fact that changes such as constructions and detours are not permanent changes.).
Regarding claim 15 Shapira teaches the apparatus of claim 13, wherein the lane layout data for the navigable element comprises information indicative of at least one of:
which particular one or more lanes of the navigable element has undergone a change of lane layout (see [0471]-[0472] and Fig. 36 where a road segment initially two lanes and a number of lanes increases along a direction of travel and there is a split of a lane, i.e. one or more lanes of a navigable element changes its layout from two to three lanes, which includes being an exit lane or a turn lane. Note also in [0485]-[0486] where there is an indication of convergence, or merging, of lanes based on obstacles, lane closure, or construction.); and
a position of the change of lane layout (see [0480]-[0481] where a server 1230 samples trajectories at a plurality of longitudinal distances before and/or after a cluster point and determines where groups begin to diverge, which then determine a branch point, i.e. a position of a change of lane layout.).
Regarding claim 17, Shapira teaches a non-transitory computer readable storage medium storing instructions which, when executed by processing circuitry, cause the processing circuitry to perform a method for generating lane data for use in a digital map (see [0284] where a server 1230, through a processor, generates a road navigation model for a common road segment and store as a portion of a sparse map.), wherein the digital map comprises data representative of longitudinal portions of navigable elements of a network of navigable elements in a geographic region (see [0214] where a sparse map includes local maps for vehicles traveling along roadways, i.e. map data representing navigable elements in a geographic region.), and wherein each longitudinal portion is defined, in the digital map, at least in part by an edge between two nodes (see [0275], [0293]-[0294, and [0324] where it describes a path between A and B and a segment A to B within a map skeleton which is formed from nodes and links, with segments connecting junctions, i.e. longitudinal portion defined by an edge between two nodes.), the method comprising:
receiving probe data for a longitudinal portion of a navigable element, wherein the probe data comprises a set of a plurality of positions of a plurality of devices that have traversed along the longitudinal portion of the navigable element (see [0256] where crowdsourcing of various vehicles are used to receive data of vehicles that have travelled on a road segment at different times, which are used to generate or update a road model, i.e. receiving probe data for a navigable element from plurality of devices that have traversed the same navigable element; note also in [0293] and Fig. 14 where there are raw data from multiple drives of separate vehicles at the same time, same vehicle at different times, and/or separate vehicles at separate times to generate a map skeleton.);
determining, based at least in part on the probe data, a subset of the probe data for each of a plurality of segments of the longitudinal portion of the navigable element of the network (see [0284] where a server 1230 receives and stores crowdsource navigation information from multiple vehicles traveled on lanes of road segments at different times and, based on that information, determine trajectories associated with each lane. Further, then, in [0477]-[0478] shows clustering of the trajectories along a road segment by defining a segment normal at a given location and identifying all trajectories that intersect that segment, which is for each longitudinal portion of a navigable element, a server determines a relevant subset of probe data, or crowdsourced trajectory, corresponding to the segment.);
determining, based at least in part on the subset of probe data for each segment, lane layout information for each segment, wherein the lane layout information for each segment comprises information indicative of: a number, usage and/or geometry of lanes in the respective segment (see [0478] where a server 1230 obtains a segment specific subset of crowdsourced trajectory data, i.e. probe data, by defining a segment at a given longitudinal location and identifying the trajectories that intersect the segment. Further, [0502] shows a land layout of the segment specific comparison indicating that the trajectories are clustered together at one or more locations before the lane split feature and clustered separately at one or more locations after the lane split feature, which are different lane layouts at the respective segment locations, i.e. a lane layout information of increase in number of lanes, usage of the lanes and geometry of lanes in the respective segment.);
determining, based at least in part on the lane layout information for each segment, at least first and second sections of the navigable element, wherein the first section of the navigable element comprises a first set of consecutive segments having a first lane layout, and wherein the second section of the navigable element comprises a second set of consecutive segments having a second lane layout different to the first lane layout (see [0502] where first and second trajectories of road segments may be clustered together in at least one first location, which is first section, before a lane split feature and clustered separately in at least one second location, which is second section, after the lane split feature, with locations separated by predetermined longitudinal distance, i.e. lane layout information of first and second segments having different lane layouts.); and
generating, based at least in part on the first and second sections of the navigable element, lane data for the navigable element wherein the lane data is indicative of a change of lane layout (see [0503] where updating a vehicle road navigation model includes a first target trajectory corresponding to a pre-split land and extending along one post-split lane and a second target trajectory branching from the first target trajectory and extending along the other post-split lane, i.e. first and second sections of single lane to two lane layout change.).
Regarding claim 18, Shapira teaches the non-transitory computer readable storage medium of claim 17, wherein the digital map provides an indication of a reference lane layout for the navigable element (see [0224]-[0229] where sparse map provides a road segment with lane boundaries and describe lanes network information through geometric descriptors and meta-data, i.e. digital map that provides reference lane layout of a navigable element.), and wherein the lane data for the navigable element layout comprises information indicative of at least one of:
a different lane layout to the reference lane layout (see [0503] where there is an update of road navigation model that includes an added branch target trajectories corresponding to a different lane layout of split layout to a reference lane layout of pre-split layout.);
a modification to the reference lane layout (see [0277] where a server 1230 identifies road model changes, i.e. reference lane layout modification, such as constructions, detours, new signs, removal of signs, etc., and update the model upon receiving new data from vehicles. Note also in [0336] where a refinement of vehicle trajectory based on image data from onboard camera will update the server for updating sparse data map. Further, [0504]-[0505] and 37A-38B shows updating and adjusting trajectory branch positions based on actual trajectory that has navigated along a road segment and removing anomalies, i.e. adjusting reference lane layout based on actual traveled trajectory.); and
a temporary adjustment to the reference lane layout (see [0277] where a server identifies road model changes, i.e. reference lane layout adjustment, such as constructions, detours, new signs, removal of signs, etc., and update the model upon receiving new data from vehicles. Note that it is temporary due to the fact that changes such as constructions and detours are not permanent changes.).
Regarding claim 19, Shapira teaches the non-transitory computer readable storage medium of claim 17, wherein the lane layout data for the navigable element comprises information indicative of at least one of:
which particular one or more lanes of the navigable element has undergone a change of lane layout (see [0471]-[0472] and Fig. 36 where a road segment initially two lanes and a number of lanes increases along a direction of travel and there is a split of a lane, i.e. one or more lanes of a navigable element changes its layout from two to three lanes, which includes being an exit lane or a turn lane. Note also in [0485]-[0486] where there is an indication of convergence, or merging, of lanes based on obstacles, lane closure, or construction.); and
a position of the change of lane layout (see [0480]-[0481] where a server 1230 samples trajectories at a plurality of longitudinal distances before and/or after a cluster point and determines where groups begin to diverge, which then determine a branch point, i.e. a position of a change of lane layout.).
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
4. Claim 5, 16, and 20 are rejected under pre-35 U.S.C. 103 as being unpatentable over Shapira in view of Motomura et al. (US 20180105186A1).
Regarding claim 5, Shapira teaches the computer-implemented method of claim 1, wherein determining the at least first and second sections of the navigable element (see [0502] where first and second trajectories of road segments may be clustered together in at least one first location, which is first section, before a lane split feature and clustered separately in at least one second location, which is second section, after the lane split feature, with locations separated by predetermined longitudinal distance, i.e. lane layout information of first and second segments having different lane layouts.) comprises determining, for each section:
the lane layout of the respective section (see [0502] where there is a distinction of clustering together, or converging, before a split, and clustering separately, or diverging, after the split, which gives a lane layout of each section where one is two lanes together and one separate into another lane.).
Shapira also teaches first location before splitting into different lanes and second location after splitting into different lanes in [0502]. This would indicate that there are start and end of one section to another.
Shapira does not explicitly teach: a start position of the respective section;
and an end position of the respective section.
However, Motomura teaches distance until start/end of merging section, a distance until start/end of divergence, and distance until start/end of construction section, which are clear indication of pointing to a start position of a respective section and an end position of the respective section (see [0512]-[0514]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the application to modify distinct location of clustering together before a split of lane in a road segment and clustering separately after the split of Shapira by incorporating teaching of Motomura such that a start and end of first section before a split of lane and a start and end of second section after the split are defined.
The motivation to indicate start and end position of road segments before and after a split in lanes is that, as indicated by Motomura, this would allow for appropriate selection of behavior estimation of vehicle in different scenes to improve precision and drive conduct and perform full or partial autonomous driving with minimal conflict between a vehicle and driver (see [0016]-[0029]).
Regarding claim 16, Shapira teaches the apparatus of claim 13, wherein determining the at least first and second sections of the navigable element (see [0502] where first and second trajectories of road segments may be clustered together in at least one first location, which is first section, before a lane split feature and clustered separately in at least one second location, which is second section, after the lane split feature, with locations separated by predetermined longitudinal distance, i.e. lane layout information of first and second segments having different lane layouts.) comprises determining, for each section:
the lane layout of the respective section (see [0502] where there is a distinction of clustering together, or converging, before a split, and clustering separately, or diverging, after the split, which gives a lane layout of each section where one is two lanes together and one separate into another lane.).
Shapira also teaches first location before splitting into different lanes and second location after splitting into different lanes in [0502]. This would indicate that there are start and end of one section to another.
Shapira does not explicitly teach: a start position of the respective section; and
an end position of the respective section.
However, Motomura teaches distance until start/end of merging section, a distance until start/end of divergence, and distance until start/end of construction section, which are clear indication of pointing to a start position of a respective section and an end position of the respective section (see [0512]-[0514]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the application to modify distinct location of clustering together before a split of lane in a road segment and clustering separately after the split of Shapira by incorporating teaching of Motomura such that a start and end of first section before a split of lane and a start and end of second section after the split are defined.
The motivation to indicate start and end position of road segments before and after a split in lanes is that, as indicated by Motomura, this would allow for appropriate selection of behavior estimation of vehicle in different scenes to improve precision and drive conduct and perform full or partial autonomous driving with minimal conflict between a vehicle and driver (see [0016]-[0029]).
Regarding claim 20, Shapira teaches the non-transitory computer readable storage medium of claim 17, wherein determining the at least first and second sections of the navigable element (see [0502] where first and second trajectories of road segments may be clustered together in at least one first location, which is first section, before a lane split feature and clustered separately in at least one second location, which is second section, after the lane split feature, with locations separated by predetermined longitudinal distance, i.e. lane layout information of first and second segments having different lane layouts.) comprises determining, for each section:
the lane layout of the respective section (see [0502] where there is a distinction of clustering together, or converging, before a split, and clustering separately, or diverging, after the split, which gives a lane layout of each section where one is two lanes together and one separate into another lane.).
Shapira also teaches first location before splitting into different lanes and second location after splitting into different lanes in [0502]. This would indicate that there are start and end of one section to another.
Shapira does not explicitly teach: a start position of the respective section; and
an end position of the respective section.
However, Motomura teaches distance until start/end of merging section, a distance until start/end of divergence, and distance until start/end of construction section, which are clear indication of pointing to a start position of a respective section and an end position of the respective section (see [0512]-[0514]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the application to modify distinct location of clustering together before a split of lane in a road segment and clustering separately after the split of Shapira by incorporating teaching of Motomura such that a start and end of first section before a split of lane and a start and end of second section after the split are defined.
The motivation to indicate start and end position of road segments before and after a split in lanes is that, as indicated by Motomura, this would allow for appropriate selection of behavior estimation of vehicle in different scenes to improve precision and drive conduct and perform full or partial autonomous driving with minimal conflict between a vehicle and driver (see [0016]-[0029]).
5. Claim 9-11 are rejected under pre-35 U.S.C. 103 as being unpatentable over Shapira in view of Fowe et al. (US 20190026591A1).
Regarding claim 9, Shapira teaches the computer-implemented method of claim 1,
Shapira does not teach: wherein a geometry of the navigable element is defined, in the digital map, via a reference line, and wherein determining lane layout information for each segment comprises:
determining, for each segment, a plurality of lateral offsets of the plurality of positions with respect to the reference line.
However, Fowe teaches probe data points that form a multi-modal distribution relative to a pre-defined reference position on a road segment (e.g., a centerline) to approximate road lanes of the road segment, i.e. geometry of a navigable element defined by reference line (see [0056]). Further, Fowe teaches lane distance defined as the closest perpendicular distance from the probe data point raw position to a sub-segment of the road segment and indicates that the lane distance represents the distance of the probe data point from a predefined reference of the road segment, such as the centerline of the road segment, i.e. a lateral offset that is a sideways, perpendicular distance from each probe position to the reference line (see [0058]). Note also that in [0059], it states that road segment is sub-divided into sub-segments and an algorithm is used to calculate the lane distance for the probe for each sub-segment, i.e. lateral offset calculated for each segment.
It would have been obvious to one of ordinary skill in the art before the effective filing date of the application to modify crowdsourced trajectory data with clustering of data points of Shapira by incorporating teaching of Fowe such that a pre-defined centerline is used with probe data, or clustering of the crowdsourced trajectory data, to define road lanes of a road segment by finding perpendicular distance from each probe position to the centerline, i.e. reference line.
The motivation to use perpendicular distance between probe data and centerline to determine lane layout is that, as indicated by Fowe, this would allow for most current maps as well as having dynamic information that are not known to a map database where each road segment is provided with number of lanes and traffic for detailed analysis of traffic per lane basis (see [0002]-[0003]).
Regarding claim 10, modified Shapira in view of Fowe teaches the computer-implemented method of claim 9, wherein determining lane layout information for each segment comprises:
aggregating the plurality of lateral offsets for the respective segment (see Fowe [0061]-[0062] where each probe data point map-matched to a road segment is assigned a sign of positive or negative lane distance based on a side of the road segment, which then the probe data points spatial distribution are analyzed to the road segment to produce a multi-modal distribution, i.e. multiple lateral offsets aggregated to be analyzed. Note also in [0065] where the probe data points associated with the road segment are divided according to the sub-segments to which they are associated and the sub-segments are also analyzed, i.e. aggregation for respective segment.);
determining a distribution of the plurality of lateral offsets for the respective segment (see Fowe [0062] where spatial distribution of probe data points on a road produces multi-modal distribution and an algorithm is used to find multiple and consistent peaks in the distribution of the probe data points based on their lane distances from predetermined reference point, which is a centerline, of a road segment, i.e. a distribution of plurality of lateral offsets for respective segment.); and/or
determining a histogram of the plurality of lateral offsets of the respective segment (see Fowe [0056] where a spatial distribution of a large population of probes on a road segment produces a histogram with multiple peaks (multi-modality). Note also [0061]-[0062] that probe data points, with assigned signs of negative or positive signs based on a side of the road segment, are analyzed for spatial distribution relative to the road segment to form multi-modal distribution with peaks, i.e. histogram of plurality of lateral offsets.).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the application to modify crowdsourced trajectory data with clustering of probe data points of Shapira by incorporating teaching of Fowe such that the probe data points, with assigned signs of negative or positive signs based on a side of the road segment, are analyzed for spatial distribution relative to the road segment to form multi-modal distribution with peaks, i.e. histogram of aggregated lateral offsets of respective segment.
The motivation to use perpendicular distance between probe data and centerline to determine lane layout is that, as indicated by Fowe, this would allow for most current maps as well as having dynamic information that are not known to a map database where each road segment is provided with number of lanes and traffic for detailed analysis of traffic per lane basis (see [0002]-[0003]).
Regarding claim 11, modified Shapira in view of Fowe teaches the computer-implemented method of claim 10, wherein determining lane layout information for each segment comprises determining, based at least in part on the distribution of the plurality of lateral offsets (see Fowe [0061]-[0062] as shown in claim 10 with regards to analyzing spatial distribution of probe data points with assigned signs and lane distance, and producing a multi-modal distribution with peaks.), at least one of:
a number of lanes of the respective segment (see Fowe [0063] where ordered clusters of probes representing lane-level spatial differences are representation of number of lanes on a road segment.);
a usage of one or more lanes of the respective segment (see Shapira [0508]-[0509] where first or second trajectory determined from split of cluster probe data points is associated with a turn lane, an exit ramp, a passing lane, or the like, i.e. a usage of one or more lanes.); and
a geometry of one or more lanes of the respective segment (see Shapira [0475] and [0478] where a server 1230 determines a shape of a lane boundary to indicate if there has been a new lane formed, determine an increase in overall width, detect dashed lane marks, and a structure of a road. Note also [0478] shows server 1230 configured to cluster trajectories based on a lateral spacing between trajectories to determine whether trajectories are merged together or diverged into different lanes, i.e. spatial arrangement of lanes which is a lane geometry.).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the application to modify crowdsourced trajectory data with clustering of probe data points associated with a turn lane, an exit ramp, a passing lane, or the like which are used to determine whether trajectories are merged together or diverged into different lanes of Shapira by incorporating teaching of Fowe such that the probe data points, with assigned signs of negative or positive signs based on a side of the road segment, are analyzed for spatial distribution relative to the road segment to form multi-modal distribution with peaks to determine a number of lanes in a road segment.
The motivation to use perpendicular distance between probe data and centerline to determine lane layout is that, as indicated by Fowe, this would allow for most current maps as well as having dynamic information that are not known to a map database where each road segment is provided with number of lanes and traffic for detailed analysis of traffic per lane basis (see [0002]-[0003]).
Conclusion
6. The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
a. Pack et al. (US 8718932B1), teaches a road segment that is 50 meters long that includes ten positions which are equally spaced within the road segment.
b. Fowe (US 11348453B2), teaches aggregation of probe data that determines a line that is parallel to a road segment and divides the road segment along a longitudinal axis. There is also clustering of probe data into first lane and second lane of a road segment.
c. Gate et al. (US 11560154B1), teaches assessing of geographical location with regards to whether a lane closure is still active, and if not, reopen the lane.
d. Mubarek (US 20220170761A1), teaches a system capable of detecting and verifying contraflow lane shift incidents using bidirectional lateral distance measurements.
7. Any inquiry concerning this communication or earlier communications from the examiner should be directed to HYANG AHN whose telephone number is (571)272-4162. The examiner can normally be reached M-F 9-5.
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, Ramya Burgess can be reached at 571-272-6011. 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.
/H.A./Examiner, Art Unit 3661
/MATTHIAS S WEISFELD/Examiner, Art Unit 3661
Prosecution Insights