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 .
Status of the Claims
This Office Action is in response to the claims filed on December 24, 2024.
Claims 1-20 have been presented for examination.
Claims 1-20 are currently rejected.
Claims 1-3, 5-7, 9-12, and 14-20 are rejected under 35 U.S.C. 103 as being unpatentable over Kurtz et al. (U.S. Patent Publication Number 2022/0242440) in view of Ebrahimi Afrouzi et al. (U.S. Patent Publication Number 2024/0310851 and hereinafter, “Afrouzi”).
Claims 4 and 8 are rejected under 35 U.S.C. 103 as being unpatentable over Kurtz et al. (U.S. Patent Publication Number 2022/0242440) in view of Ebrahimi Afrouzi et al. (U.S. Patent Publication Number 2024/0310851 and hereinafter, “Afrouzi”), further in view of Thibaux et al. (U.S. Patent Publication Number 2023/0099772).
Response to Arguments
Claim Objections
Applicant’s arguments, see Applicant Remarks, filed on 05/09/2026, with respect to the claim objections, have been fully considered and are persuasive. The claim objection has been withdrawn.
35 U.S.C. 101
Applicant's arguments filed on 05/09/2026 have been fully considered but they are not persuasive. The Applicant argues that operations such as "determining one or more edges having a pair of node identifiers," "inserting the one or more edges and the pair of node identifiers into a lane group routing graph, wherein the lane group routing graph is a directed graph," and "matching an input directed graph to the lane group routing graph" are data-structure manipulation operations that cannot be practically performed in the human mind (Applicant Remarks page 8). The Applicant further argues that the claimed invention is “anchored in sensor-derived real-world vehicle trajectory data” and that human mental activity “cannot acquire, store, or operate on raw vehicle trajectory data collected via sensors at scale” (Applicant Remarks page 9).
The Examiner has considered the arguments presented and respectfully disagrees. As defined in paragraph 54 of the instant specification, a node merely represents a connection among different trajectories. One having ordinary skill in the art would reasonably be able to mentally determine that one or more edges of a trajectory has a pair of node identifiers based on given geographic database information. For example, by visually viewing a map, one having ordinary skill in the art can practically identify one or more edges and a corresponding pair of nodes. Such determination may be made mentally or manually with the aid of pen and paper. The inserting of one or more edges and a pair of node identifiers merely amounts to one having ordinary skill in the art manually adding the appropriate trajectory information into a give routing graph or map, and mentally or manually performing a matching step to match corresponding graphs. The language provided in the claims does not preclude one having ordinary skill in the art from utilizing data and performing the mental process given the necessary information. Further, the claims do not recite or describe a “scale” of data collected via sensors. Therefore, the Applicant’s arguments are not persuasive.
The Applicant further argues that the final step of “providing a map matching result” outputs the result of the data processing and does not convert the claim into a mental process (Applicant Remarks page 9-10). The Examiner has considered the arguments presented and respectfully disagrees. The subject matter in this limitation is analyzed under 35 U.S.C. 101 Step 2A Prong II which investigates whether the additional elements integrate the judicial exception into practical application. The “providing” step is merely directed to data that is being generated or output, which is a form of insignificant extra-solution activity, and does not integrate the mental process steps into practical application.
The Applicant further argues that the reorganization of information and matching operation provides an improvement in the technical capability and functioning of the system, which improves how computer systems perform map matching (Applicant Remarks page 11-12). The Examiner has considered the arguments presented and respectfully disagrees. Assertions of improvement in a technological field must not be directed to an abstract idea (see MPEP 2106). In Berkheimer v. HP INC., 881 F. 3d 1360 (Fed. Cir. 2018), the federal circuit held that improvements are only considered “to the extent they are captured in the claims.” Berkheimer at 1369. See MPEP 2106.04(d)(1). The claim does not recite or describe such improvement; therefore, the Applicant’s arguments are not persuasive.
For these reasons, the Examiner maintains the 35 U.S.C. 101 rejection.
35 U.S.C. 103
The Applicant’s arguments, see Applicant Remarks filed on [X], appear to be primarily directed to the amended claim language. The Applicant’s arguments with respect to claim(s) [Y] have been considered but are moot because amendments shift the scope of claims and necessitate a new ground of rejection, which is made in view of Ebrahimi Afrouzi et al. (U.S. Patent Publication Number 2024/0310851 and hereinafter, “Afrouzi”).
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Claim 1
Claim 1. A method comprising:
determining a plurality of lane group centerlines respectively representing a plurality of lane groups of a road network in a geographic database;
for each lane group centerline of the plurality of lane group centerlines, determining one or more edges having a pair of node identifiers associated with said lane group centerline;
inserting the one or more edges and the pair of node identifiers into a lane group routing graph, wherein the lane group routing graph is a directed graph;
matching an input directed graph to the lane group routing graph, wherein the input directed graph represents an aggregated representation of a plurality of drive paths, and
wherein the plurality of drive paths represents a set of trajectories; and
providing a map matching result based on the matching.
101 Analysis - Step 1: Statutory category – Yes
The claim recites a method including at least one step. The claim falls within one of the four statutory categories. See MPEP 2106.03.
101 Analysis - Step 2A Prong one evaluation: Judicial Exception – Yes – Mental processes
In Step 2A, Prong one of the 2019 Patent Eligibility Guidance (PEG), a claim is to be analyzed to determine whether it recites subject matter that falls within one of the following groups of abstract ideas: a) mathematical concepts, b) mental processes, and/or c) certain methods of organizing human activity.
The Office submits that the foregoing bolded limitation(s) constitutes judicial exceptions in terms of “mental processes” because under its broadest reasonable interpretation, the limitations can be “performed in the human mind, or by a human using a pen and paper”. See MPEP 2106.04(a)(2)(III)
The claim recites the limitation of determining a plurality of lane group centerlines respectively representing a plurality of lane groups of a road network in a geographic database; for each lane group centerline of the plurality of lane group centerlines, determining one or more edges having a pair of node identifiers associated with said lane group centerline; inserting the one or more edges and the pair of node identifiers into a lane group routing graph, wherein the lane group routing graph is a directed graph; matching an input directed graph to the lane group routing graph, wherein the input directed graph represents an aggregated representation of a plurality of drive paths, and wherein the plurality of drive paths represents a set of trajectories.
These limitations, as drafted, are a simple process that, under its broadest reasonable interpretation, covers performance of the limitation in the mind. That is, nothing in the claim elements precludes the step from practically being performed in the mind. For example, the claim encompasses a person looking at data collected and forming a simple judgement. Specifically, the claim describes a person mentally performing, or with the aid of pen and paper, finding multiple lane group centerlines on a road network and identifying a pair of nodes. The person may use a pen to insert an edge and pair of node identifiers into the lane group routing graph, which may be a physical map, and matching a directed graph to the lane group routing graph. The graph may include an aggregated representation of a plurality of paths, showing multiple candidate paths. The person may then provide the map matching result.
Thus, the claim recites a mental process.
101 Analysis - Step 2A Prong two evaluation: Practical Application - No
In Step 2A, Prong two of the 2019 PEG, a claim is to be evaluated whether, as a whole, it integrates the recited judicial exception into a practical application. As noted in MPEP 2106.04(d), 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, such that the claim is more than a drafting effort designed to monopolize the judicial exception. The courts have indicated that additional elements such as: 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.”
The Office submits that the claim does not appear to include additional elements that would integrate the recited judicial exception into a practical application.
Accordingly, even in combination, these additional elements do not integrate the abstract idea into a practical application because they do not impose any meaningful limits on practicing the abstract idea.
101 Analysis - Step 2B evaluation: Inventive concept - No
In Step 2B of the 2019 PEG, a claim is to be evaluated as to 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.
As discussed with respect to Step 2A Prong Two, the additional elements in the claim amount to no more than mere instructions to apply the exception using a generic computer component. The same analysis applies here in 2B, i.e., mere instructions to apply an exception on a generic computer cannot integrate a judicial exception into a practical application at Step 2A or provide an inventive concept in Step 2B.
Under the 2019 PEG, a conclusion that an additional element is insignificant extra-solution activity in Step 2A should be re-evaluated in Step 2B. Here, the receiving steps and the displaying step were considered to be insignificant extra-solution activity in Step 2A, and thus they are re-evaluated in Step 2B to determine if they are more than what is well-understood, routine, conventional activity in the field. The background recites that the sensors are all conventional sensors mounted on the vehicle, and the specification does not provide any indication that the vehicle controller is anything other than a conventional computer within a vehicle. MPEP 2106.05(d)(II), and the cases cited therein, including Intellectual Ventures I, LLC v. Symantec Corp., 838 F.3d 1307, 1321 (Fed. Cir. 2016), TLI Communications LLC v. AV Auto. LLC, 823 F.3d 607, 610 (Fed. Cir. 2016), and OIP Techs., Inc., v. Amazon.com, Inc., 788 F.3d 1359, 1363 (Fed. Cir. 2015), indicate that mere collection or receipt of data over a network is a well‐understood, routine, and conventional function when it is claimed in a merely generic manner (as it is here). Further, the Federal Circuit in Trading Techs. Int’l v. IBG LLC, 921 F.3d 1084, 1093 (Fed. Cir. 2019), and Intellectual Ventures I LLC v. Erie Indemnity Co., 850 F.3d 1315, 1331 (Fed. Cir. 2017), for example, indicated that the mere displaying of data is a well understood, routine, and conventional function. Accordingly, a conclusion that the collecting step is well-understood, routine, conventional activity is supported under Berkheimer.
Thus, the claim is ineligible.
Claim 18
Independent claim 18 recites limitations that are parallel in scope to those provided in claim 1. The recited additional elements “at least one processor; and at least one memory including computer program code for one or more programs, the at least one memory and the computer program code configured to, with the at least one processor” are recited at a high level of generality and merely describe how to generally “apply” the otherwise mental judgements using a generic or general-purpose computing environment. Accordingly, claim 18 is rejected under 35 U.S.C. 101 under the same rationale.
Claim 20
Independent claim 20 recites limitations that are parallel in scope to those provided in claim 1. The recited additional elements “one or more processors” provided in the preamble of the claim are recited at a high level of generality and merely describe how to generally “apply” the otherwise mental judgements using a generic or general-purpose computing environment. Accordingly, claim 20 is rejected under 35 U.S.C. 101 under the same rationale.
Dependent Claims
Dependent claims 2-17 and 19 do not recite any further limitations that cause the claim(s) to be patent eligible. Rather, the limitations of the 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. Therefore, dependent claims 2-17 and 19 are not patent eligible under the same rationale as provided for in the rejection of independent claims 1 and 18.
Therefore, claims 1-20 are ineligible under 35 USC §101.
Allowable Subject Matter
Claim 13 is rejected under 35 U.S.C. 101 and is dependent upon a rejected base claim. However, claim 13 would be allowable if rewritten to overcome the 35 U.S.C. 101 rejection and rewritten in independent form including all of the limitations of the base claim and any intervening claims. As allowable subject matter has been indicated, applicant's reply must either comply with all formal requirements or specifically traverse each requirement not complied with. See 37 CFR 1.111(b) and MPEP § 707.07(a).
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.
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.
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.
Claims 1-3, 5-7, 9-12, and 14-20 are rejected under 35 U.S.C. 103 as being unpatentable over Kurtz et al. (U.S. Patent Publication Number 2022/0242440) in view of Ebrahimi Afrouzi et al. (U.S. Patent Publication Number 2024/0310851 and hereinafter, “Afrouzi”).
Regarding claim 1, Kurtz discloses a method comprising:
determining a plurality of lane group centerlines respectively representing a plurality of lane groups of a road network in a geographic database; (Kurtz in at least ¶ 4 discloses “a lane-level map that includes a plurality of lane segments corresponding to the map area,” wherein “the system may cluster the one or more lane segments selected for inclusion in the geonet into logical groupings,” see ¶ 7, and wherein the maps are received from a “map data store [i.e., a geographic database],” see ¶ 23)
for each lane group centerline of the plurality of lane group centerlines, determining one or more edges having a pair of node identifiers associated with said lane group centerline; (Kurtz ¶ 26 discloses that “the system may identify (106) a geo-coordinate corresponding to each lane segment in the lane-level map” such as identifying “the approximate middle point by, for example, computing a centerline (e.g., a line that is equidistant from and parallel to two opposing edges of a lane segment) that passes approximately through the middle of the lane segment,” wherein the lane segment information includes “an identifier associated with a lane segment.” The lane segments of Kurtz are nodes as according to ¶ 39 “using each lane segment as a node;” therefore, the identifier of the lane segment is an identifier of the node. Further, “For each of the plurality of lane segments, the system may identify a match geonet element” such as “geo-coordinate pairs that are each indicative of a start location and an end location,” see ¶ 4.)
inserting the one or more edges and the pair of node identifiers into a lane group routing graph, wherein the lane group routing graph is a directed graph; (Kurtz ¶ 39 discloses “The system may construct the routing graph by, for example, using each lane segment as a node and representing the option to proceed from one lane segment to its neighboring lane segment as a directed edge.”)
matching an input directed graph to the lane group routing graph, (Kurtz ¶ 27 discloses that “the system may identify a match geonet element [i.e., an input directed graph] within the geonet for each lane segment [i.e., lane group routing graph] within the lane-level map,” and “constructing a lane-level routing graph corresponding to the geonet using the lane segments determined to be included in the geonet,” see ¶ 39)
Kurtz does not expressly disclose:
wherein the input directed graph represents an aggregated representation of a plurality of drive paths, and
wherein the plurality of drive paths represents a set of sensor-derived vehicle trajectories; and
providing a map matching result based on the matching.
However, Afrouzi discloses:
wherein the input directed graph represents an aggregated representation of a plurality of drive paths, and (Afrouzi ¶ 701 discloses “a plurality of alternate candidate routes may be displayed (and various metrics thereof, like travel time or distance), and the user interface may include inputs (like event handlers mapped to regions of pixels) by which a user may select among these candidate routes by touching or otherwise selecting a segment of one of the candidate routes”)
wherein the plurality of drive paths represents a set of sensor-derived vehicle trajectories; and (Afrouzi ¶ 238 discloses using sensors to “determine movement paths”)
providing a map matching result based on the matching. (Afrouzi ¶ 324 discloses “a neural network may be used to adjudicate depth sensing, extract movement (e.g., angular and linear) of the robot, combine iterations of sensor readings into a map, adjudicate location (i.e., localization), extract dynamic obstacles and separate them from structural points, and actuate the robot such that the trajectory of the robot better matches the planned path.”)
While Kurtz does not expressly disclose inserting one or more edges and the pair of node identifiers into a lane group routing graph, it would have been obvious to a person having ordinary skill in the art before the effective filing date to have modified the construction of the lane routing graph with expressly disclosing that the construction of the graph includes inserting one or more edges and a pair of node identifiers, with reasonable expectation of success, to eliminate dead-end lane segments and to reduce the likelihood that an autonomous vehicle will become stranded, while traversing a trajectory (Kurtz ¶ 38).
Further, it would have been obvious to a person having ordinary skill in the art before the effective filing date to have combined the match geonet element, or directed graph, of Kurtz with an aggregated representation of a plurality of drive paths, as disclosed by Afrouzi, with reasonable expectation of success, because neural network may be advantageous for older, manually constructed features that are human understandable and, to some extent, in removing the human middleman from the process (Afrouzi ¶ 324), rendering the limitation to be an obvious modification.
Regarding claim 2, Kurtz in combination with Afrouzi discloses the method of claim 1, further comprising:
determining that at least one node identifier of the pair of node identifiers is shared by at least one connected lane group centerline that has been previously processed and inserted in the lane group routing graph; and (Kurtz ¶ 33 discloses clustering lane segments based on “successor-predecessor relationships within the lane segments of the lane-level map,” such that the system constructs a routing graph “representing the option to proceed from one lane segment to its neighboring lane segment as a directed edge [i.e., shared by a connected lane group],” wherein “the system may further select lane segments to be included [i.e., connected lane group] in the geonet using connectivity of lane segments to each other, and may only select a lane segment set that is strongly connected for inclusion in the geonet,” see ¶ 37, wherein the geonet includes a plurality of geocoordinate pairs, the geocoordinate pairs corresponding to a centerline, see ¶¶ 4 and 26)
reusing the at least one node identifier. (Kurtz Fig. 2 depicts the nodes being reused in the geonet)
Regarding claim 3, Kurtz in combination with Afrouzi discloses the method of claim 1, further comprising:
determining one or more edge directions of the one or more edges based on direction of travel data of each lane group centerline. (Kurtz ¶ 59 discloses the map data can provide, thereby having determined, “information regarding: the identity and location of different roadways, road segments, lane segments, ... the location, boundaries, and directions of traffic lanes (e.g., the location and direction of ... lanes within a particular roadway) [i.e., edge direction],” such that the map data includes reference paths that are pre-defined as the centerline of traffic lanes, see ¶ 60. Kurtz ¶ 60 further discloses that the reference path information of the map data includes information that corresponds to “common patterns of vehicle travel along one or more lanes.”)
Regarding claim 5, Kurtz in combination with Afrouzi discloses the method of claim 1, further comprising:
for each edge of the one or more edges, determining that said each edge exists in the lane group routing graph; and (Kurtz ¶ 37 discloses that “the system may further select lane segments to be included in the geonet” such that “A lane segment set is strongly connected if it is possible to find a route that leads from lane segment A to lane segment B for every pair (A, B) in the set of lane segments [i.e., each edge exists],” wherein the lane segments are used to construct the routing graph, see ¶ 39)
adding a virtual node and a virtual edge to said each edge in the lane group routing graph to distinguish routing from multiple edges. (Kurtz ¶ 46 discloses that “the system may assign a unique segment identifier each lane segment [i.e., node], and may add this unique lane segment identifier to the geonet data object,” and representing, on the routing graph, “the option to proceed from one lane segment to its neighboring lane segment as a directed edge,” see ¶ 39)
Regarding claim 6, Kurtz in combination with Afrouzi discloses the method of claim 1, wherein the plurality of lane group centerlines are represented in the geographic database as a plurality of respective lane group boundary polygons, the method further comprising:
for each lane group boundary polygon of the plurality of respective lane group polygons, determining a closing segment of said each lane group boundary polygon, (Kurtz ¶ 4 discloses that “each of the plurality of lane segments may be represented as a polygon within the lane-level map,” wherein “The lane-level map may include a plurality of lane segments as a collection of closed polygons that define sections of the mapped roadways within the environment,” see ¶ 24.” Also see Fig. 3.)
wherein the closing segment does not connect to another lane group boundary polygon; and (Kurtz Fig. 5 depicts groupings of lane segment 510 which depicts each polygon having closing segments in accordance with closings 803a and 803b of the instant specification, wherein each lane segment has “two opposing edges [i.e., closing segments],” see ¶ 26.)
an opening segment of said each lane group boundary, (Kurtz Fig. 5 depicts a road segment that starts or “opens” the lane group 510 from point A to point B, wherein each road segment has “a collection of geo-coordinate pairs that indicate approximate starting [i.e., opening] and ending locations,” see ¶ 22. Such a road segment constitutes an “opening segment” in accordance with the description provided in ¶ 67 of the instant specification defining the “opening segment” to be a connecting geometry to another polygon.)
wherein the opening segment is a connecting geometry with another lane group boundary polygon and allows traffic from one lane group to another lane group. (Kurtz Fig. 5 depicts “grouping lane segment 510 in the street 501(a) between points A and B,” wherein the one or more lane segments are connected to create a routing graph, see ¶¶ 8 and 37, which is in accordance with openings 801a and 801b of the instant specification, and wherein the lane segments generate a trajectory for navigating the autonomous vehicle, see ¶ 20.)
Regarding claim 7, Kurtz in combination with Afrouzi discloses the method of claim 6, further comprising:
for the opening segment, determining a start point and a direction of growth, (Kurtz ¶ 37 discloses “A lane segment set is strongly connected if it is possible to find a route that leads from lane segment A to lane segment B for every pair (A, B) in the set of lane segments.” One having ordinary skill in the art would recognize that determining a route from segment A to segment B is determining a start point and a direction of growth in the direction of segment B.)
wherein a center point of the opening segment is used as the start point, and (Kurtz ¶ 26 discloses “the system may identify the approximate middle point as an intersection of two centerlines within the polygon that forms [i.e., starts] the lane segment”)
wherein the growth direction is from the start point to an inner of said each lane group boundary polygon. (Kurtz Fig. 5 depicts that the lane grouping 510 extends as “a route that leads from lane segment A to lane segment B for every pair (A, B),” such that the growth direction would be to an inner of the lane group)
Regarding claim 9, Kurtz in combination with Afrouzi discloses the method of claim 1, wherein:
the matching comprises: matching a trajectory of the set of trajectories to the lane group routing graph to determine a sequence of lane group centerlines represented in the lane group routing corresponding to the trajectory; and (Kurtz ¶ 29 discloses that “The system may identify the match geonet element by analyzing various characteristics of each candidate geonet element” based on “an angle/angular distance between the lane segment centerline and each geonet element; (ii) a perpendicular distance between the geo-coordinate of the lane segment (e.g., centerline mid-point) and an infinite line defined by each geonet element [i.e., a sequence of lane group centerlines represented in the lane group routing corresponding to the trajectory]”)
applying one or more hard constraints to matching the trajectory. (Kurtz ¶ 60 discloses that the “map data may also include reference path information that correspond to common patterns of vehicle travel along one or more lanes such that the motion of the object is constrained to the reference path [i.e., applying one or more hard constraints],” wherein the reference path is “pre-defined such as the centerline of the traffic lanes”)
Regarding claim 10, Kurtz in combination with Afrouzi discloses the method of claim 9, wherein:
the one or more hard constraints include designating a transition in the sequence of lane group centerlines as infeasible if the sequence of lane group centerlines includes a sharp angle that is less than a threshold angle. (Kurtz ¶ 62 discloses “road segments that a vehicle can travel on to get from the start position to the destination position,” wherein the motion is constrained to the reference path, see ¶ 60, wherein the system may “discard lane segment clusters ... when, for example, a street is mostly straight but ends with a sharp turn, and the lane segment at the turn may not have the same match geonet element as the other lane segments in the street (because of its angular distance),” see ¶ 35. The Examiner notes that the claim appears to contain a contingent limitation (e.g., “if”) and is therefore not expressly required to be performed under the broadest reasonable interpretation of the claim. See MPEP 2111.04.)
Regarding claim 11, Kurtz in combination with Afrouzi discloses the method of claim 9, wherein:
the one or more hard constraints include eliminating a path in the sequence of lane group centerlines with a route distance that is greater than a direct distance by more than a threshold factor. (Kurtz ¶ 31 discloses that the system may “discard all the lane segments that form the undirected street,” wherein for each undirected street, determining that “all the lane segments that form that street should not be included in the geonet when the median match distance is greater than the second threshold distance”)
Regarding claim 12, Kurtz in combination with Afrouzi discloses the method of claim 9, wherein:
the one or more hard constraints include eliminating a path in the sequence of lane group centerlines with a route shape that deviates from a straight line of projected points by more than a threshold value. (Kurtz ¶ 41 discloses that “the system may use the selected lane segments determined to be included in the geonet” such as “aligning the selected lane segments and/or streets with the corresponding match geonet elements,” also see ¶ 38 disclosing delineating “strongly connected lane segments by, for example, discarding and/or otherwise distinctly identifying the lane segments that are not strongly connected” based on, for example, a “likelihood that an autonomous vehicle will become stranded, while traversing a trajectory, with no feasible route back to a destination/origination point [i.e., deviates from the straight line of projected points]”)
Regarding claim 14, Kurtz in combination with Afrouzi discloses the method of claim 1, wherein:
the matching comprises extending each edge of the directed graph, and (Kurtz ¶ 39 discloses “construct the routing graph by, for example, using each lane segment as a node and representing the option to proceed from one lane segment to its neighboring lane segment as a directed edge.”)
wherein the matching results are provided only for an unextend portion of said each edge. (Kurtz ¶ 60 discloses that the map data includes “reference path information that correspond to common patterns of vehicle travel along one or more lanes such that the motion of the object is constrained to the reference path.” One having ordinary skill in the art would recognize that a vehicle traveling along a constrained path is traveling forward in a given direction; therefore, the matched road segments would only extend forward for an unextended portion.)
Regarding claim 15, Kurtz in combination with Afrouzi discloses the method of claim 1, wherein:
the matching comprises storing multiple matches from the matching as a directed acyclic graph. (Kurtz ¶ 62 discloses a “map data store to identify possible routes and road segments that a vehicle can travel on to get from the start position to the destination position,” such that one having ordinary skill in the art would recognize that a start position to a destination position is acyclic. Also see the linear process depicted in Fig. 1. Additionally, the lane-level map, which contains matched geonet elements within the geonet for each lane segment, is received as a map data store, see ¶¶ 24 and 28.)
Regarding claim 16, Kurtz in combination with Afrouzi discloses the method of claim 15, wherein the providing comprises:
extracting a plurality of possible lane group sequences from the directed acyclic graph; (Kurtz in at least ¶ 7 discloses that “the system may cluster the one or more lane segments selected for inclusion in the geonet into logical groupings that form the plurality of undirected streets.” Also see Fig. 5.)
for each lane group sequence of the plurality of possible lane group sequences and for each lane group in the said each lane group sequence, determining one or more intersecting ranges and one or more non-intersecting ranges; (Kurtz in at least ¶ 7 discloses that the system may cluster the lane segments for inclusion by “merging one or more lane segments to create road segments, replacing one or more lane segments with a single lane required to span a street perpendicular to traffic, and/or merging merge road segments parallel with traffic.”)
for the one or more non-intersecting ranges that are shorter than a threshold length, merging the one or more non-intersecting ranges with a previous intersecting range; and (Kurtz ¶ 29 discloses selecting a matching geonet element for a given lane segment based on characteristics including “a lengthwise distance which is a minimum distance along a line computed as the projection of the geo-coordinate of lane segment”)
for each non-intersecting range of the one or more intersecting ranges, inferring its interpolated lane group sequences, orientations, possible lanes, or a combination thereof based on lane group matches; and (Kurtz ¶ 32 discloses “The system may refine the lane segment selection by clustering the lane segment into undirected streets to create logical groupings of lane segments such that the system may either include all the lane segments that form an undirected street into the geonet or discard all the lane segments that form the undirected street. Typically, lane segments clustered to form an undirected street should have the same match geonet element.”)
providing the map matching result including the one or more intersecting ranges, the one or more non-intersecting ranges, or a combination thereof. (Kurtz ¶ 41 discloses “The system may create the updated lane-level map by, for example, aligning the selected lane segments and/or streets with the corresponding match geonet elements”)
Regarding claim 17, Kurtz in combination with Afrouzi discloses the method of claim 15, wherein:
one or more virtual nodes for partial off-road matches are inserted into the directed acyclic graph to make a transition from empty matches to other matches or from other matches to empty matches feasible. (Kurtz ¶ 39 discloses “The system may identify lane segments that are not strongly connected [i.e., partial off-road matches] by constructing a lane-level routing graph corresponding to the geonet using the lane segments determined to be included in the geonet. The system may construct the routing graph by, for example, using each lane segment as a node and representing the option to proceed from one lane segment to its neighboring lane segment as a directed edge [i.e., inserting one or more virtual nodes].” Also see at least Fig. 5 and corresponding ¶ 42 depicting the lane segments that are not strongly connected, shown as a white color, being matched to [i.e., transitioning from] lane segments that are strongly connected, shown in grey.
Regarding claim 18, Kurtz in combination with Afrouzi discloses the parallel limitations contained in parent claim 1 for the reasons discussed above. Kurtz further discloses “at least one processor; and at least one memory including computer program code for one or more programs, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to” perform the limitations of claim 1. (Kurtz in at least ¶ 71)
Regarding claim 19, Kurtz in combination with Afrouzi discloses the parallel limitations contained in parent claim 2 for the reasons discussed above.
Regarding claim 20, Kurtz in combination with Afrouzi discloses the parallel limitations contained in parent claim 1 for the reasons discussed above.
Claims 4 and 8 are rejected under 35 U.S.C. 103 as being unpatentable over Kurtz et al. (U.S. Patent Publication Number 2022/0242440) in view of Ebrahimi Afrouzi et al. (U.S. Patent Publication Number 2024/0310851 and hereinafter, “Afrouzi”), further in view of Thibaux et al. (U.S. Patent Publication Number 2023/0099772).
Regarding claim 4, Kurtz in combination with Afrouzi does not expressly disclose the method of claim 1, further comprising:
for each edge of the one or more edges, determining that a lane group of the plurality of lane groups corresponding to said each edge has lanes in both directions; and
inserting two virtual nodes and two virtual edges in the lane group routing graph to distinguish routing from either direction of both directions based on determining that a start node identifier and an end node identifier of said each edge are the same.
However, Thibaux discloses:
for each edge of the one or more edges, determining that a lane group of the plurality of lane groups corresponding to said each edge has lanes in both directions; and (Thibaux ¶ 44 discloses that “A link between nodes on edges represents one or more drivable lanes that cross the two edges one after the other in the order specified by the direction of the link. Thus, nodes also have a corresponding associated direction of travel,” wherein the lanes may be “traveling through an edge in both directions,” see ¶ 97. Also see Fig. 9a.)
inserting two virtual nodes and two virtual edges in the lane group routing graph to distinguish routing from either direction of both directions based on determining that a start node identifier and an end node identifier of said each edge are the same. (Thibaux ¶ 79 discloses that “A link can be added ... with a new pair of nodes ... The new pair of nodes can include a newly added node or an existing node,” wherein the nodes “have an ordering ordered from left to right starting at the start node of the link and ending again at the same start node after going around the cell,” see ¶ 81, and wherein the “link will either start at a new node in an entrance edge, or it will be a new outgoing link from an existing [i.e., same] node,” see ¶ 87)
It would have been obvious to a person having ordinary skill in the art before the effective filing date to have combined the routing graph of Kurtz, of the combination of Kurtz and Afrouzi, with determining, for each edge of the one or more edges, that a lane group of the plurality of lane groups corresponding to said each edge has lanes in both directions, as disclosed by Thibaux, with reasonable expectation of success, to allow for fully autonomous navigation even on roads that have never been mapped (Thibaux ¶ 10), rendering the limitation to be an obvious modification.
Regarding claim 8, Kurtz in combination with Afrouzi discloses the method of claim 7, further comprising:
determining an extended point from the start point along the direction of growth with a stepwise tunable parameter; (Kurtz ¶ 22 discloses that the road network map 200 includes geonet 210 which is “a collection of geo-coordinate pairs that indicate approximate starting and ending locations [i.e., an extended point] of short road segments (typically less than 500 m) [i.e., a stepwise tunable parameter].” One having ordinary skill in the art would recognize that the distance for each road segment being 500 m or less is a stepwise tunable parameter in accordance with ¶ 69 of the instant specification describing the stepwise tunable parameter to be a designated step size that indicates the distance of the extended point from the start point or previous point.)
determining a line on the extended point perpendicular to the direction of growth; (Kurtz in at least ¶ 30 “The angular distance between the centerline of a lane segment and a geonet element is the largest when the lane segment is aligned perpendicular to a given geonet element.”)
determining a truncated segment of the line truncated by the closing segment and/or another closing segment; (Kurtz ¶ 24 discloses “a plurality of lane segments as a collection of closed [i.e., truncated] polygons that define sections of the mapped roadways”)
updating the start point as another center point of the truncated segment; (Kurtz ¶ 41 updating the lane-level map “by, for example, aligning the selected lane segments and/or streets with the corresponding match geonet elements”)
updating the direction of growth from a previous start point to a current start point; and (Kurtz ¶ 41 discloses using “the selected lane segments determined to be included in the geonet to create an updated lane-level map (corresponding to the received geonet) that includes the selected lane segments,” and creating the updated lane-level map by “aligning [i.e., from a previous start point] the selected lane segments and/or streets with the corresponding match geonet elements”)
Kurtz does not expressly disclose:
repeating until a last growth segment intersects another opening segment.
However, Thibaux discloses:
repeating until a last growth segment intersects another opening segment. (Thibaux ¶ 47 discloses that “a path is a sequence of connected [i.e., repeated] links having a direction that runs from an entrance edge to an exit edge through a sequence of nodes” wherein “the endpoint of a link can connect to the start of a link on the other side of the corresponding edge,” thereby repeating until it connects to a corresponding edge of a start of another link. One having ordinary skill in the art would recognize that the repeated occurrence may include only a single repetition.)
It would have been obvious to a person having ordinary skill in the art before the effective filing date to have modified the constructing the lane segment routing graph of Kurtz with expressly disclosing repeating until a last growth segment intersects another opening segment, as disclosed by Thibaux, with reasonable expectation of success, to enumerate all possible lane graph topologies, despite their potentially large number and great diversity to guarantee that the true lane graph is guaranteed to exist among the enumerated lane graph topologies (Thibaux ¶ 52), rendering the limitation to be an obvious modification.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to STEPHANIE T SU whose telephone number is (571)272-5326. The examiner can normally be reached Monday to Friday, 9:30AM - 5:00PM EST.
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, ANISS CHAD can be reached at (571)270-3832. 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.
/STEPHANIE T SU/Primary Examiner, Art Unit 3662
Prosecution Insights