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 Claims
This Office Action is in response to the Applicant’s amendments and remarks filed on January 22, 2026.
Claims 1, 9, 11, 15, and 17 are currently amended.
Claims 5-6, 12-13, and 19-20 are currently canceled.
Claims 1-4, 7-11, and 14-18 are pending and have been examined.
Response to Arguments
Regarding the outstanding Claim Objections:
Regarding claim 8, the outstanding claim objection is maintained because the term in line 2, “constrains” appears to be a typographical error. Further, it was not addressed in Applicant’s Remarks.
Regarding claim 17, the outstanding claim objection is withdrawn in view of the newest set of claims reflecting the correction. The current line 23, the term “acceleration” appears to correct the prior set of claims that included the term “acclerationa”. The Examiner notes that amendments to claims should be properly indicated in the listing of claims.
Regarding the outstanding 35 U.S.C. § 112(b) Rejections:
The outstanding 35 USC 112(b) rejections of claims 5, 6, 11, 13, 17, and 19 are withdrawn in view of Applicants deleting claims 5, 6, 13, and 19 and amending claims 11 and 17 to delete the indefinite limitations.
Regarding the outstanding 35 U.S.C. § 101 Rejections:
Applicant’s arguments filed on January 22, 2026 have been fully considered but they are not persuasive.
The claims are considered to be an abstract idea involving mental processes. The additional limitation of, “the ST graph dynamically updated based on sensor readings of the autonomous driving vehicle” is considered to be an additional element involving data gathering. This type of data gathering is considered to be insignificant extra-solution activity and, therefore, does not integrate the judicial exception into a practical application. Further, the claim does not recite an additional element that amounts to significantly more than the judicial exception. Gathering data from sensors of autonomous vehicles is well-known.
The Examiner notes that if the claims were amended to explicitly add a limitation that an autonomous vehicle is controlled using the passage way that is calculated based on all of the claim limitations, that would be considered a practical application and would render the claim eligible. There appears to be support for such an amendment in paragraph [0031] of the originally filed specification.
Regarding the outstanding 35 U.S.C. § 103 Rejections:
Applicant’s arguments filed on January 22, 2026 have been fully considered but they are not persuasive.
The Examiner respectfully disagrees. Applicant’s arguments with respect to the claims have been considered but are moot because the new ground of rejection does not rely on any reference applied in the prior rejection of record for any teaching or matter specifically challenged in the argument. A new ground of rejection is made in view Applicant’s amendments.
The outstanding 35 USC 103 rejections are maintained, however, they are modified in view of newly found references found based on the updated search in view of Applicant’s amendments.
Claim Objections
Claims 8 and 14 are objected to because of the following informalities: the term “constrains” within the claim language appears to be a typographical error. For purposes of compact prosecution, this term was interpreted by the Examiner to be “constraints.” Appropriate action is required.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-4, 7-11, and 14-18 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
A claim that recites an abstract idea, a law of nature, or a natural phenomenon is directed to a judicial exception. Abstract ideas include the following groupings of subject matter, when recited as such in a claim limitation: (a) Mathematical concepts – mathematical relationships, mathematical formulas or equations, mathematical calculations; (b) Certain methods of organizing human activity – fundamental economic principles or practices (including hedging, insurance, mitigating risk); commercial or legal interactions (including agreements in the form of contracts; legal obligations; advertising, marketing or sales activities or behaviors; business relations); managing personal behavior or relationships or interactions between people (including social activities, teaching, and following rules or instructions); and (c) Mental processes – concepts performed in the human mind (including an observation, evaluation, judgment, opinion). See the 2019 Revised Patent Subject Matter Eligibility Guidance.
Even when a judicial element is recited in the claim, an additional claim element(s) that integrates the judicial exception into a practical application of that exception renders the claim eligible under §101. A claim that integrates a judicial exception into a practical application will apply, rely on, or use the judicial exception 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 following examples are indicative that an additional element or combination of elements may integrate the judicial exception into a practical application:
the additional element(s) reflects an improvement in the functioning of a computer, or an improvement to other technology or technical field;
the additional element(s) that applies or uses a judicial exception to effect a particular treatment or prophylaxis for a disease or medical condition;
the additional element(s) implements a judicial exception with, or uses a judicial exception in conjunction with, a particular machine or manufacture that is integral to the claim;
the additional element(s) effects a transformation or reduction of a particular article to a different state or thing; and
the additional element(s) applies or uses 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 more than a drafting effort designed to monopolize the exception.
Examples in which the judicial exception has not been integrated into a practical application include:
the additional element(s) merely recites the words “apply it” (or an equivalent) with the judicial exception, or merely includes instructions to implement an abstract idea on a computer, or merely uses a computer as a tool to perform an abstract idea;
the additional element(s) adds insignificant extra-solution activity to the judicial exception; and
the additional element does no more than generally
link the use of a judicial exception to a particular technological environment or field of use.
See the 2019 Revised Patent Subject Matter Eligibility Guidance and the 2024 Patent Subject Matter Eligibility Guidance Update Including on Artificial Intelligence.
101 Analysis – Step 1
Claim 1 is directed to a method (i.e., a process).
Claim 11 is directed to a method (i.e., a process).
Claim 17 is directed to a method (i.e., a process).
Therefore, claims 1, 11, and 17 are each within at least one of the four statutory categories.
101 Analysis – Step 2A, Prong 1
Regarding Prong I of the Step 2A analysis in the 2019 PEG, the claims are to be analyzed to determine whether they recite subject matter that falls within one of the following groups of abstract ideas: a) mathematical concepts, b) certain methods of organizing human activity, and/or c) mental processes.
Independent claim 17 includes limitations that recite an abstract idea (emphasized below) and will be used as a representative claim (representing claims 1 and 11) for the remainder of the 101 rejection. Claim 17 recites:
A method for generating operable driving areas for an autonomous driving vehicle based on a path trajectory of the autonomous driving vehicle, comprising:
forming a space time (ST) graph indicating a distance of travel along the path trajectory with respect to time of the autonomous driving vehicle and path trajectories of devices intersecting with the path trajectory of the autonomous driving vehicle, the ST graph dynamically updated based on sensor readings of the autonomous driving vehicle;
segmenting the ST graph into cells, wherein viable cells represent discretized viable unoccupied spaces in the ST graph, wherein segmenting the ST graph comprises;
identifying occupied cells associated with each device at each time segment, wherein occupied cells are dynamically updated based on sensor readings of the autonomous driving vehicle at each time segment;
combining overlapping occupied cells; and
forming a complimentary set of the occupied cells, the complimentary set of the occupied cells forming the viable cells;
finding passage ways for the autonomous driving vehicle based on the viable cells; and
selecting a desired passage way using quadratic programming (QP) optimization when multiple passage ways are found at each time segment, wherein the QP optimization uses soft constraints so inequality constraints when constructing the ST graph remain within bounds to select the desired passage way to minimize time travel and undesirable movement of the autonomous driving vehicle, wherein distance, speed and acceleration are used as state variables and jerk as a control variable in a symmetric matrix of the QP optimization, wherein the soft constraints comprises adding a slack variable for each upper and lower bound and penalize non-zero slack variables in an objective function of the QP optimization.
The Examiner submits that the foregoing bolded limitations constitute a “mental process” because under its broadest reasonable interpretation, the claim covers performance of the limitation in the human mind. For example, “forming a space time (ST) graph indicating a distance of travel along the path trajectory with respect to time of the autonomous driving vehicle and path trajectories of devices intersecting with the path trajectory of the autonomous driving vehicle, …; segmenting the ST graph into cells, wherein viable cells represent discretized viable unoccupied spaces in the ST graph, wherein segmenting the ST graph comprises: identifying occupied cells associated with each device at each time segment, wherein occupied cells are dynamically updated based on sensor readings of the autonomous driving vehicle at each time segment; combining overlapping occupied cells; and forming a complimentary set of the occupied cells, the complimentary set of the occupied cells forming the viable cells; finding passage ways for the autonomous driving vehicle based on the viable cells; and selecting a desired passage way using quadratic programming (QP) optimization when multiple passage ways are found at each time segment, wherein the QP optimization uses soft constraints so inequality constraints when constructing the ST graph remain within bounds to select the desired passage way to minimize time travel and undesirable movement of the autonomous driving vehicle, wherein distance, speed and acceleration are used as state variables and jerk as a control variable in a symmetric matrix of the QP optimization, wherein the soft constraints comprises adding a slack variable for each upper and lower bound and penalize non-zero slack variables in an objective function of the QP optimization” in the context of this claim encompasses a person performing these limitations in the human mind, or by a human using a pen and paper. Accordingly, the claim recites at least one abstract idea.
101 Analysis – Step 2A, Prong II
Regarding Prong II of the Step 2A analysis in the 2019 PEG, the claims are to be analyzed to determine whether the claim, as a whole, integrates the abstract idea into a practical application. As noted in the 2019 PEG, it must be determined whether any additional elements in the claim beyond the abstract idea integrate the exception into a practical application in a manner that imposes a meaningful limit on the judicial exception. The courts have indicated that additional elements merely using a computer to implement an abstract idea, 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” while the bolded portions continue to represent the “abstract idea”):
A method for generating operable driving areas for an autonomous driving vehicle based on a path trajectory of the autonomous driving vehicle, comprising:
forming a space time (ST) graph indicating a distance of travel along the path trajectory with respect to time of the autonomous driving vehicle and path trajectories of devices intersecting with the path trajectory of the autonomous driving vehicle, the ST graph dynamically updated based on sensor readings of the autonomous driving vehicle;
segmenting the ST graph into cells, wherein viable cells represent discretized viable unoccupied spaces in the ST graph, wherein segmenting the ST graph comprises;
identifying occupied cells associated with each device at each time segment, wherein occupied cells are dynamically updated based on sensor readings of the autonomous driving vehicle at each time segment;
combining overlapping occupied cells; and
forming a complimentary set of the occupied cells, the complimentary set of the occupied cells forming the viable cells;
finding passage ways for the autonomous driving vehicle based on the viable cells; and
selecting a desired passage way using quadratic programming (QP) optimization when multiple passage ways are found at each time segment, wherein the QP optimization uses soft constraints so inequality constraints when constructing the ST graph remain within bounds to select the desired passage way to minimize time travel and undesirable movement of the autonomous driving vehicle, wherein distance, speed and acceleration are used as state variables and jerk as a control variable in a symmetric matrix of the QP optimization, wherein the soft constraints comprises adding a slack variable for each upper and lower bound and penalize non-zero slack variables in an objective function of the QP optimization.
For the following reasons, 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 “the ST graph dynamically updated based on sensor readings of the autonomous driving vehicle”, , the Examiner submits that this limitation is insignificant extra-solution activity that merely gathers data to perform updating a map. In particular, the limitation is recited at a high level of generality (i.e. as a general means of gathering information) and amounts to mere data gathering, which is a form of insignificant extra-solution activity.
Thus, taken alone, the additional elements do not integrate the abstract idea into a practical application. Further, looking at the additional limitations as an ordered combination or as a whole, the limitations 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 (MPEP § 2106.05). Accordingly, the additional limitation 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 2019 PEG, representative independent claim 17 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 as 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 integration of the abstract idea into a practical application, the additional element of “the ST graph dynamically updated based on sensor readings of the autonomous driving machine”, the Examiner submits that this limitation is insignificant extra-solution activity.
Further, a conclusion that an additional element is insignificant extra-solution activity in Step 2A should be re-evaluated in Step 2B to determine if they are more than what is well-understood, routine, conventional activity in the field. The additional limitations of “the ST graph dynamically updated based on sensor readings of the autonomous driving vehicle”, is well-understood, routine, and conventional activity. 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. Hence, the claim is not patent eligible.
Dependent claims 2-4, 7-10, 14-16, and 18 do not recite any further limitations that cause the claims 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. Therefore, independent claims 1 and 11 and dependent claims 2-4, 7-10, 14-16, and 18 are not patent eligible under the same rationale as provided for in the rejection of independent claim 17.
Therefore, claims 1-4, 7-11, and 14-18 are ineligible under 35 USC §101.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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.
Claim 1 is rejected under 35 U.S.C. 103 as being unpatentable over Afshar, et al. (Publication US 2024/0132112 A1), in view of Advani, et al. (Publication US 2021/0132213 A1), and Fan, et al. (Publication US 2019/0086932 A1) (hereinafter referred to as “Afshar”, “Advani”, and “Fan”.)
As per claim 1, Afshar discloses a method for generating operable driving areas for an autonomous driving vehicle based on a path trajectory of the autonomous driving vehicle, comprising:
forming a space time (ST) graph indicating a distance of travel along the path trajectory with respect to time of the autonomous driving vehicle and path trajectories of devices intersecting with the path trajectory of the autonomous driving vehicle, the ST graph dynamically updated based on sensor readings of the autonomous driving vehicle [see at least Afshar Figs. 5-8; [0029] "...The techniques described herein perform path-based prediction of potential future trajectories of agents (e.g., surrounding vehicles, bicycles, and/or pedestrians) in a field of view of an AV. Particularly, the techniques predict not only future targets (e.g., intermediate destinations) of the agents but also reference paths (e.g., ones with highest probabilities) which each agent is likely to follow. After predicting a reference path, a future trajectory of each agent is completed with respect to its predicted reference path, which enhances a map compliance of the prediction,"; [0030] "...2) sampling the vectorized map for candidate reference paths (e.g., in 8 seconds) with reachable lane segments or reachable targets (e.g., end points) of the candidate reference paths; [0070] "planning system 404 receives data associated with an updated position of a vehicle (e.g., vehicles 102 of FIG. 1 or vehicle 200 of FIG. 2) from localization system 406 and planning system 404 updates the at least one trajectory or generates at least one different trajectory based on the data generated by localization system 406."; [0071] "the map is generated in real-time based on the data received by the perception system."];
segmenting the ST graph into cells, … wherein viable cells represent discretized viable unoccupied spaces in the ST graph … [see at least Afshar Fig 8 [0119] "The scene encoder 810 creates agent feature vectors from the scene for each agent. The agent feature vectors include information about the map (e.g., lanes, cross sections, stop signs, turns, and/or the like), agent history 804 (e.g., past trajectories of agents), as well as agent-map interactions (e.g., location data, traffic data, expected routes, and/or the like) and agent-agent interactions (e.g., neighboring agent's routes, velocity data,..."; [0120] "...First, rotational invariant local feature vectors are encoded for each agent with a transformer module to aggregate neighboring agents' information (e.g., location data, expected routes, and/or the like) as well as local map structure (e.g., lanes, cross sections, stop signs, turns, and/or the like)."];
…finding passage ways for the autonomous driving vehicle based on the viable cells [see at least Afshar Fig 8 [0123] "An objective of the candidate path sampler 820 is to create a set of candidate reference paths for each agent by traversing the lane graph (e.g., the vectorized map 802)."; [0124] "In some embodiments, to select the candidate reference path for an agent a, a set of seed lane segments to be considered as the path starting points are selected".; [0125] "From the seed lane segments, a breadth-first search is performed to find the candidate paths, ... The output of the candidate path sampler 820 is a set of candidate reference paths for each agent, .... The choice of this parameter depends on the prediction horizon and lane segment resolution."]; and
selecting a desired passage way using … optimization when multiple passage ways are found, … to select the desired passage way to minimize time travel and undesirable movement of the autonomous driving vehicle [see at least Afshar Fig 8; [0123] "An objective of the candidate path sampler 820 is to create a set of candidate reference paths for each agent by traversing the lane graph (e.g., the vectorized map 802)."; [0124] "In some embodiments, to select the candidate reference path for an agent a, a set of seed lane segments to be considered as the path starting points are selected."; [0125] "From the seed lane segments, a breadth-first search is performed to find the candidate paths... ."]
Afshar fails to disclose … segmenting the ST graph into cells at each time segment, … wherein segmenting the ST graph comprises: identifying occupied cells associated with each device at each time segment wherein occupied cells are dynamically updated based on sensor readings of the autonomous driving vehicle at each time segment; combining overlapping occupied cells; and forming a complimentary set of the occupied cells, the complimentary set of the occupied cells forming the viable cells. However, Advani teaches these limitations:
… segmenting the ST graph into cells at each time segment [see at least Advani [0107] "...the architecture 420a includes a Lidar SLAM component 471 and a radar mapping component 475...The Lidar SLAM component 471 generates a Lidar map 478 and a Lidar pose 477...the Lidar map is a grid map with predetermined size (number of grids) and resolution (size of each grid). Each map grid stores one of the three states: occupied, un-occupied and unknown. The occupied and unoccupied states imply whether the grid is filled with obstacles or not, while the unknown state means that it is undecided whether the grid is occupied or not. For example, an occupied state indicates that the grid includes an obstacle, while an unoccupied state indicates that the grid does not include an obstacle."], … wherein segmenting the ST graph comprises:
identifying occupied cells associated with each device at each time segment wherein occupied cells are dynamically updated based on sensor readings of the autonomous driving vehicle at each time segment [see at least Advani [0107] "...the architecture 420a includes a Lidar SLAM component 471 and a radar mapping component 475...The Lidar SLAM component 471 generates a Lidar map 478 and a Lidar pose 477...the Lidar map is a grid map with predetermined size (number of grids) and resolution (size of each grid). Each map grid stores one of the three states: occupied, un-occupied and unknown. The occupied and unoccupied states imply whether the grid is filled with obstacles or not, while the unknown state means that it is undecided whether the grid is occupied or not. For example, an occupied state indicates that the grid includes an obstacle, while an unoccupied state indicates that the grid does not include an obstacle."; [0066] “previously generated maps within the information repository 340 can be updated as the drive system 320 maneuvers the electronic device 300 within an area, based on the information from the sensors 310, the SLAM engine 330, and previously generated maps.”];
combining overlapping occupied cells [see at least Advani [0109] "The radar map is a grid map that shares the same size and resolution as those of the Lidar map 478. Each grid stores an integer. In certain embodiments, the integer can range from 0 to 100, that represents the occupancy probability. The occupancy probability is the probability that the grid is occupied. In step 476b, the radar map and the Lidar map are then combined into one fusion map as the fusion map 479. The fusion map 479 is output top the navigation layer 430 of FIG. 4A."]; and
forming a complimentary set of the occupied cells, the complimentary set of the occupied cells forming the viable cells [see at least Advani [0109] "The radar map is a grid map that shares the same size and resolution as those of the Lidar map 478. Each grid stores an integer. In certain embodiments, the integer can range from 0 to 100, that represents the occupancy probability. The occupancy probability is the probability that the grid is occupied. In step 476b, the radar map and the Lidar map are then combined into one fusion map as the fusion map 479. The fusion map 479 is output top the navigation layer 430 of FIG. 4A."; [0205] " In step 710, the electronic device 300 modifies the first map, that is based on the Lidar scans, with the missed object of the second map, that was based on the radar scans, based on the determination that the second map includes an object that was missed by the first map. In certain embodiments, the electronic device 300 generates a fusion map by merging a state (occupied or unoccupied) of each cell of the first map with the value of the first cell of the second map, where the value indicates a probability that the cell is occupied."]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in Afshar to use … segmenting the ST graph into cells at each time segment, … wherein segmenting the ST graph comprises: identifying occupied cells associated with each device at each time segment wherein occupied cells are dynamically updated based on sensor readings of the autonomous driving vehicle at each time segment; combining overlapping occupied cells; and forming a complimentary set of the occupied cells, the complimentary set of the occupied cells forming the viable cells as disclosed in Advani with a reasonable expectation of success for the benefit of improved generation of a map and navigation. [See at least Advani [0037].]
The combination of Afshar and Advani fails to disclose … selecting a desired passage way using quadratic programming (QP) optimization ... at each time segment, wherein the QP optimization uses soft constraints so inequality constraints when constructing the ST graph remain within bounds … . However, Fan teaches this limitation [see at least Fan [0026] "...a system selects a number of polynomials representing a number of time segments of a time duration to complete the path trajectory...The system defines a set of constraints to the polynomials to at least ensure the polynomials are smoothly joined together. The system performs a quadratic programming (QP) optimization on the objective function in view of the added constraints, such that a cost associated with the objective function reaches a minimum while the set of constraints are satisfied. The system generates a smooth speed for the time duration based on the optimized objective function to control the ADV autonomously."; FIG. 5B; [0080] "...a QP solver, such as QP optimization performed by optimization module 540 of FIG. 5B, can solve the target function to generate a smooth reference line. In one embodiment, a QP optimization is performed on the target function such that the target function reaches a predetermined threshold (e.g., minimum), while the set of constraints are satisfied. Once the target function has been optimized in view of the constraints, the coefficients of the polynomial functions can be determined. Then the location of the path points (e.g., control points) along the path can be determined using the polynomial function with the optimized coefficients, which represents a smooth reference line. As described above, the smoothing function is incorporated into the target function to be solved... .]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar and Advani to use … selecting a desired passage way using quadratic programming (QP) optimization ... at each time segment, wherein the QP optimization uses soft constraints so inequality constraints when constructing the ST graph remain within bounds … as disclosed in Fan with a reasonable expectation of success for the benefit of improved system responsiveness. [See at least Fan [0108].]
Claims 2-4, 7, and 11 are rejected under 35 U.S.C. 103 as being unpatentable over Afshar, in view of Advani, Fan, and Liu, et al. (Changliu Liu, Wei Zhan, and Masayoshi Tomizuka, Speed Profile Planning in Dynamic Environments via Temporal Optimization, in 2017 IEEE Intelligent Vehicles Symposium (IV), pages 154-159, 2017) (hereinafter referred to as “Liu”.)
As per claim 2, the combination of Afshar, Advani, and Fan, as shown in the rejection above, discloses all of the limitations of claim 1.
Afshar discloses … comprising using distance, speed and acceleration as state variables in a symmetric matrix of the … optimization [see at least Afshar [0124] , [0130] , [0070] "…planning system 404 receives data associated with a destination and generates data associated with at least one route (e.g., routes 106) along which a vehicle (e.g., vehicles 102) can travel along toward a destination… selecting an appropriate speed, acceleration, deceleration..."]
Afshar fails to disclose … QP optimization. However, Liu teaches this limitation [see at least Liu p. 155 "B. Computing Speed, Acceleration and Jerk"; p. 155 "Section III formulates the temporal optimization problem for speed profile planning; Section IV discusses the quadratic approximation of the temporal optimization problem."]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar, Advani, and Fan to use … QP optimization as disclosed in Liu with a reasonable expectation of success for the benefit of safety during interactions with other road participants. [See at least Liu, p. 159 Conclusion.]
As per claim 3, the combination of Afshar, Advani, and Fan, as shown in the rejection above, discloses all of the limitations of claim 1.
Afshar discloses … using distance, speed and acceleration as state variables … in a symmetric matrix of the … optimization [see at least Afshar [0124] , [0130] , [0070] "…planning system 404 receives data associated with a destination and generates data associated with at least one route (e.g., routes 106) along which a vehicle (e.g., vehicles 102) can travel along toward a destination… selecting an appropriate speed, acceleration, deceleration..."]
The combination of Afshar, Advani, and Fan fails to disclose … jerk as a control variable … in a … QP optimization. However, Liu teaches this limitation [see at least Liu p. 155 "B. Computing Speed, Acceleration and Jerk"; p. 155 "Section III formulates the temporal optimization problem for speed profile planning; Section IV discusses the quadratic approximation of the temporal optimization problem."]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar, Advani, and Fan to use … jerk as a control variable … in a … QP optimization as disclosed in Liu with a reasonable expectation of success for the benefit of safety during interactions with other road participants. [See at least Liu, p. 159 Conclusion.]
As per claim 4, the combination of Afshar, Advani, and Fan, as shown in the rejection above, discloses all of the limitations of claim 1.
Afshar discloses … using distance, speed and acceleration as state variables … in a symmetric matric {Examiner is interpreting this as matrix} of the QP optimization … [see at least Afshar [0124] , [0130] , [0070] "…planning system 404 receives data associated with a destination and generates data associated with at least one route (e.g., routes 106) along which a vehicle (e.g., vehicles 102) can travel along toward a destination… selecting an appropriate speed, acceleration, deceleration... ."]
The combination of Afshar, Advani, and Fan fails to disclose … using … jerk as a control variable in a … QP optimization, wherein a weight wa is imposed on accelerations for displacements t E [0, .. . ,N - 2]) and a weight wj is imposed on jerks for displacements t E [0, ...,N - 3]). However, Liu teaches these limitations [see at least Liu p. 155 "B. Computing Speed, Acceleration and Jerk"; p. 155 "Section III formulates the temporal optimization problem for speed profile planning; Section IV discusses the quadratic approximation of the temporal optimization problem"; p. 156 Problem 1, "w(1), w(2), w(3), w(4), w(5) are positive weights" for acceleration (a) and jerk (j) in equation (2a).]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar, Advani, and Fan to use … using … jerk as a control variable in a … QP optimization, wherein a weight wa is imposed on accelerations for displacements t E [0, .. . ,N - 2]) and a weight wj is imposed on jerks for displacements t E [0, ...,N - 3]) as disclosed in Liu with a reasonable expectation of success for the benefit of safety during interactions with other road participants. [See at least Liu, p. 159 Conclusion.]
As per claim 7, the combination of Afshar, Advani, and Fan, as shown in the rejection above, discloses all of the limitations of claim 1.
Afshar discloses … using an initial distance and an initial speed as constraints in the … optimization [see at least Afshar [0022] "As used herein, “trajectory” refers to a path or route to navigate an AV from a first spatiotemporal location to second spatiotemporal location. In an embodiment, the first spatiotemporal location is referred to as the initial or starting location and the second spatiotemporal location is referred to as the destination, final location, goal, goal position, or goal location."; [0035] "... routes 106 may include more precise actions or states such as, for example, specific target lanes or precise locations within the lane areas and targeted speed at those positions."]
The combination of Afshar, Advani, and Fan fails to disclose … using an initial distance and an initial speed as constraints in the QP optimization. However, Liu teaches these limitations "IV. Quadratic Approximation of the Temporal Optimization" p. 156.; "p. 158 "A. Case 0: Speed Profile for a Curvy Road"]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar, Advani, and Fan to use … using an initial distance and an initial speed as constraints in the QP optimization as disclosed in Liu with a reasonable expectation of success for the benefit of safety during interactions with other road participants. [See at least Liu, p. 159 Conclusion.]
As per claim 11, Afshar discloses a method of controlling an autonomous vehicle, the method implemented using a vehicle control system including a processor communicatively coupled to a memory device, the method comprising:
forming a space time (ST) graph indicating a distance of travel along the path trajectory with respect to time of the autonomous driving vehicle and path trajectories of devices intersecting with the path trajectory of the autonomous driving vehicle, the ST graph dynamically updated based on sensor readings of the autonomous driving vehicle [see at least Afshar Figs. 5-8; [0029] "...The techniques described herein perform path-based prediction of potential future trajectories of agents (e.g., surrounding vehicles, bicycles, and/or pedestrians) in a field of view of an AV. Particularly, the techniques predict not only future targets (e.g., intermediate destinations) of the agents but also reference paths (e.g., ones with highest probabilities) which each agent is likely to follow. After predicting a reference path, a future trajectory of each agent is completed with respect to its predicted reference path, which enhances a map compliance of the prediction,"; [0030] "...2) sampling the vectorized map for candidate reference paths (e.g., in 8 seconds) with reachable lane segments or reachable targets (e.g., end points) of the candidate reference paths; [0070] "planning system 404 receives data associated with an updated position of a vehicle (e.g., vehicles 102 of FIG. 1 or vehicle 200 of FIG. 2) from localization system 406 and planning system 404 updates the at least one trajectory or generates at least one different trajectory based on the data generated by localization system 406."; [0071] "the map is generated in real-time based on the data received by the perception system."];
segmenting the ST graph into cells, wherein viable cells represent discretized viable unoccupied spaces in the ST graph … [see at least Afshar Fig 8 [0119] "The scene encoder 810 creates agent feature vectors from the scene for each agent. The agent feature vectors include information about the map (e.g., lanes, cross sections, stop signs, turns, and/or the like), agent history 804 (e.g., past trajectories of agents), as well as agent-map interactions (e.g., location data, traffic data, expected routes, and/or the like) and agent-agent interactions (e.g., neighboring agent's routes, velocity data,..."; [0120] "...First, rotational invariant local feature vectors are encoded for each agent with a transformer module to aggregate neighboring agents' information (e.g., location data, expected routes, and/or the like) as well as local map structure (e.g., lanes, cross sections, stop signs, turns, and/or the like)."];
…finding passage ways for the autonomous driving vehicle based on the viable cells [see at least Afshar Fig 8 [0123] "An objective of the candidate path sampler 820 is to create a set of candidate reference paths for each agent by traversing the lane graph (e.g., the vectorized map 802)."; [0124] "In some embodiments, to select the candidate reference path for an agent a, a set of seed lane segments to be considered as the path starting points are selected".; [0125] "From the seed lane segments, a breadth-first search is performed to find the candidate paths, ... The output of the candidate path sampler 820 is a set of candidate reference paths for each agent, .... The choice of this parameter depends on the prediction horizon and lane segment resolution."]; and
selecting a desired passage way using … optimization when multiple passage ways are found, … to select the desired passage way to minimize time travel and undesirable movement of the autonomous driving vehicle, wherein distance, speed and acceleration are state variables … in a symmetric matrix of the … optimization … [see at least Afshar Fig 8; [0123] "An objective of the candidate path sampler 820 is to create a set of candidate reference paths for each agent by traversing the lane graph (e.g., the vectorized map 802)."; [0124] "In some embodiments, to select the candidate reference path for an agent a, a set of seed lane segments to be considered as the path starting points are selected."; [0125] "From the seed lane segments, a breadth-first search is performed to find the candidate paths... ."; [0124] , [0130] , [0070] "…planning system 404 receives data associated with a destination and generates data associated with at least one route (e.g., routes 106) along which a vehicle (e.g., vehicles 102) can travel along toward a destination… selecting an appropriate speed, acceleration, deceleration... ."]
Afshar fails to disclose … wherein segmenting the ST graph comprises: identifying occupied cells associated with each device at each time segment wherein occupied cells are dynamically updated based on sensor readings of the autonomous driving vehicle at each time segment; combining overlapping occupied cells; and forming a complimentary set of the occupied cells, the complimentary set of the occupied cells forming the viable cells. However, Advani teaches these limitations:
… wherein segmenting the ST graph comprises:
identifying occupied cells associated with each device at each time segment wherein occupied cells are dynamically updated based on sensor readings of the autonomous driving vehicle at each time segment [see at least Advani [0107] "...the architecture 420a includes a Lidar SLAM component 471 and a radar mapping component 475...The Lidar SLAM component 471 generates a Lidar map 478 and a Lidar pose 477...the Lidar map is a grid map with predetermined size (number of grids) and resolution (size of each grid). Each map grid stores one of the three states: occupied, un-occupied and unknown. The occupied and unoccupied states imply whether the grid is filled with obstacles or not, while the unknown state means that it is undecided whether the grid is occupied or not. For example, an occupied state indicates that the grid includes an obstacle, while an unoccupied state indicates that the grid does not include an obstacle."; [0066] “previously generated maps within the information repository 340 can be updated as the drive system 320 maneuvers the electronic device 300 within an area, based on the information from the sensors 310, the SLAM engine 330, and previously generated maps.”];
combining overlapping occupied cells [see at least Advani [0109] "The radar map is a grid map that shares the same size and resolution as those of the Lidar map 478. Each grid stores an integer. In certain embodiments, the integer can range from 0 to 100, that represents the occupancy probability. The occupancy probability is the probability that the grid is occupied. In step 476b, the radar map and the Lidar map are then combined into one fusion map as the fusion map 479. The fusion map 479 is output top the navigation layer 430 of FIG. 4A."]; and
forming a complimentary set of the occupied cells, the complimentary set of the occupied cells forming the viable cells [see at least Advani [0109] "The radar map is a grid map that shares the same size and resolution as those of the Lidar map 478. Each grid stores an integer. In certain embodiments, the integer can range from 0 to 100, that represents the occupancy probability. The occupancy probability is the probability that the grid is occupied. In step 476b, the radar map and the Lidar map are then combined into one fusion map as the fusion map 479. The fusion map 479 is output top the navigation layer 430 of FIG. 4A."; [0205] " In step 710, the electronic device 300 modifies the first map, that is based on the Lidar scans, with the missed object of the second map, that was based on the radar scans, based on the determination that the second map includes an object that was missed by the first map. In certain embodiments, the electronic device 300 generates a fusion map by merging a state (occupied or unoccupied) of each cell of the first map with the value of the first cell of the second map, where the value indicates a probability that the cell is occupied."]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in Afshar to use … wherein segmenting the ST graph comprises: identifying occupied cells associated with each device at each time segment wherein occupied cells are dynamically updated based on sensor readings of the autonomous driving vehicle at each time segment; combining overlapping occupied cells; and forming a complimentary set of the occupied cells, the complimentary set of the occupied cells forming the viable cells as disclosed in Advani with a reasonable expectation of success for the benefit of improved generation of a map and navigation. [See at least Advani [0037].]
The combination of Afshar and Advani fails to disclose … selecting a desired passage way using quadratic programming (QP) optimization ... at each time segment, wherein the QP optimization uses soft constraints so inequality constraints when constructing the ST graph remain within bounds … . However, Fan teaches this limitation [see at least Fan [0026] "...a system selects a number of polynomials representing a number of time segments of a time duration to complete the path trajectory...The system defines a set of constraints to the polynomials to at least ensure the polynomials are smoothly joined together. The system performs a quadratic programming (QP) optimization on the objective function in view of the added constraints, such that a cost associated with the objective function reaches a minimum while the set of constraints are satisfied. The system generates a smooth speed for the time duration based on the optimized objective function to control the ADV autonomously."; FIG. 5B; [0080] "...a QP solver, such as QP optimization performed by optimization module 540 of FIG. 5B, can solve the target function to generate a smooth reference line. In one embodiment, a QP optimization is performed on the target function such that the target function reaches a predetermined threshold (e.g., minimum), while the set of constraints are satisfied. Once the target function has been optimized in view of the constraints, the coefficients of the polynomial functions can be determined. Then the location of the path points (e.g., control points) along the path can be determined using the polynomial function with the optimized coefficients, which represents a smooth reference line. As described above, the smoothing function is incorporated into the target function to be solved... .]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar and Advani to use … selecting a desired passage way using quadratic programming (QP) optimization ... at each time segment, wherein the QP optimization uses soft constraints so inequality constraints when constructing the ST graph remain within bounds … as disclosed in Fan with a reasonable expectation of success for the benefit of improved system responsiveness. [See at least Fan [0108].]
The combination of Afshar, Advani, and Fan fails to disclose … wherein … jerk is a control variable in a … QP optimization, wherein a weight wa is imposed on accelerations for displacements t E [0, .. . ,N - 2]) and a weight wj is imposed on jerks for displacements t E [0, ...,N - 3]). However, Liu teaches these limitations [see at least Liu p. 155 "B. Computing Speed, Acceleration and Jerk"; p. 155 "Section III formulates the temporal optimization problem for speed profile planning; Section IV discusses the quadratic approximation of the temporal optimization problem"; p. 156 Problem 1, "w(1), w(2), w(3), w(4), w(5) are positive weights" for acceleration (a) and jerk (j) in equation (2a).]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar, Advani, and Fan to use … wherein … jerk is a control variable in a … QP optimization, wherein a weight wa is imposed on accelerations for displacements t E [0, .. . ,N - 2]) and a weight wj is imposed on jerks for displacements t E [0, ...,N - 3]) as disclosed in Liu with a reasonable expectation of success for the benefit of safety during interactions with other road participants. [See at least Liu, p. 159 Conclusion.]
Claims 8, 10, and 16 are rejected under 35 U.S.C. 103 as being unpatentable over Afshar, in view of Advani, Fan, and Zhang, et al. (Publication US 2023/0242142 A1) (hereinafter referred to as “Zhang”.)
As per claim 8, the combination of Afshar, Advani, and Fan, as shown in the rejection above, discloses all of the limitations of claim 1.
Afshar discloses … using an initial distance, an initial speed, …as constrains in the … optimization [See at least Afshar [0022] "As used herein, “trajectory” refers to a path or route to navigate an AV from a first spatiotemporal location to second spatiotemporal location. In an embodiment, the first spatiotemporal location is referred to as the initial or starting location and the second spatiotemporal location is referred to as the destination, final location, goal, goal position, or goal location."; [0035] "... routes 106 may include more precise actions or states such as, for example, specific target lanes or precise locations within the lane areas and targeted speed at those positions."]
The combination of Afshar, Advani, and Fan fails to disclose … using a lower bound and an upper bound of each passage way as constrains in the QP optimization. However, Zhang teaches this limitation [see at Zhang FIG. 1; [0008] "The dotted area represents an occupied or non-drivable area 11 (for example out of road boundary area), and the outlined diamond pattern represents an open space or drivable area 13. The SL plane projection 16 of a planned vehicle trajectory is represented by a line that extends through the drivable area from a start position 15 (e.g., a current vehicle position) to a target position 17."]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar, Advani, and Fan to use … using a lower bound and an upper bound of each passage way as constrains in the QP optimization as disclosed in Zhang with a reasonable expectation of success for the benefit of improving the shape of the trajectory. [See at least Zhang [0011].]
As per claim 10, the combination of Afshar, Advani, and Fan, as shown in the rejection above, discloses all of the limitations of claim 1.
The combination of Afshar, Advani, and Fan fails to disclose … linearly decreasing an upper bound of a speed of the autonomous driving vehicle. However, Zhang teaches this limitation [see at least Zhang [0018] "... using one or more upper-bound cost terms that each approximate the upper-bound of a cost term for the trajectory for the spatial frame can advantageously allow an optimization problem solver, such as a quadratic programming optimization solver, to be used to optimize a motion planning trajectory in the spatial frame in addition to optimizing in the spatio-temporal frames such that planning objectives are also best optimized in the spatial frame ..."]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar, Advani, and Fan to use … linearly decreasing an upper bound of a speed of the autonomous driving vehicle as disclosed in Zhang with a reasonable expectation of success for the benefit of improving the shape of the trajectory. [See at least Zhang [0011].]
As per claim 16, the combination of Afshar, Advani, Fan, and Liu, as shown in the rejection above, discloses all of the limitations of claim 11.
The combination of Afshar, Advani, Fan, and Liu fails to disclose … linearly decreasing an upper bound of a speed of the autonomous driving vehicle. However, Zhang teaches this limitation [see at least Zhang [0018] "... using one or more upper-bound cost terms that each approximate the upper-bound of a cost term for the trajectory for the spatial frame can advantageously allow an optimization problem solver, such as a quadratic programming optimization solver, to be used to optimize a motion planning trajectory in the spatial frame in addition to optimizing in the spatio-temporal frames such that planning objectives are also best optimized in the spatial frame ..."]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar, Advani, Fan, and Liu to use … linearly decreasing an upper bound of a speed of the autonomous driving vehicle as disclosed in Zhang with a reasonable expectation of success for the benefit of improving the shape of the trajectory. [See at least Zhang [0011].]
Claim 9 is rejected under 35 U.S.C. 103 as being unpatentable over Afshar, in view of Advani, Fan, Zhang, and Woerner, et al. (Publication US 2021/0216897 A1) (hereinafter referred to as “Woerner”.)
As per claim 9, the combination of Afshar, Advani, Fan, and Zhang, as shown in the rejection above, discloses all of the limitations of claim 8.
The combination of Afshar, Advani, Fan, and Zhang fails to disclose … adding a slack variable for each lower and upper bound and penalize non-zero slack variables in an objective function of the QP optimization to prevent inequality constraint violations. However, Woerner teaches this limitation [see at least Woerner [0017] "...Today's algorithms for including inequality constraints into Quadratic Unconstrained Binary Optimization (QUBO) problems include non-negative slack variables to translate inequality to equality constraints which can be added as penalty terms to the QUBO objective. The slack variables are then handled in the classical optimizer together with the variational parameters dricving the ansatz that handles the binary variables."]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar, Advani, Fan, and Zhang to use … adding a slack variable for each lower and upper bound and penalize non-zero slack variables in an objective function of the QP optimization to prevent inequality constraint violations as disclosed in Woerner with a reasonable expectation of success for the benefit of solving optimization problems effectively and improving system performance. [See at least Woerner [0017].]
Claim 14 is rejected under 35 U.S.C. 103 as being unpatentable over Afshar, in view of Advani, Fan, Liu, and Zhang.
As per claim 14, the combination of Afshar, Advani, Fan, and Liu, as shown in the rejection above, discloses all of the limitations of claim 11.
Afshar discloses … using an initial distance, an initial speed, …as constrains in the … optimization [See at least Afshar [0022] "As used herein, “trajectory” refers to a path or route to navigate an AV from a first spatiotemporal location to second spatiotemporal location. In an embodiment, the first spatiotemporal location is referred to as the initial or starting location and the second spatiotemporal location is referred to as the destination, final location, goal, goal position, or goal location."; [0035] "... routes 106 may include more precise actions or states such as, for example, specific target lanes or precise locations within the lane areas and targeted speed at those positions."]
The combination of Afshar, Advani, Fan, and Liu fails to disclose … using a lower bound and an upper bound of each passage way as constrains in the QP optimization. However, Zhang teaches this limitation [see at Zhang FIG. 1; [0008] "The dotted area represents an occupied or non-drivable area 11 (for example out of road boundary area), and the outlined diamond pattern represents an open space or drivable area 13. The SL plane projection 16 of a planned vehicle trajectory is represented by a line that extends through the drivable area from a start position 15 (e.g., a current vehicle position) to a target position 17."]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar, Advani, Fan, and Liu to use … using a lower bound and an upper bound of each passage way as constrains in the QP optimization as disclosed in Zhang with a reasonable expectation of success for the benefit of improving the shape of the trajectory. [See at least Zhang [0011].]
Claim 15 is rejected under 35 U.S.C. 103 as being unpatentable over Afshar, in view of Advani, Fan, Liu, Zhang, and Woerner.
As per claim 15, the combination of Afshar, Advani, Fan, Liu, and Zhang, as shown in the rejection above, discloses all of the limitations of claim 14.
The combination of Afshar, Advani, Fan, Liu, and Zhang fails to disclose … adding a slack variable for each lower and upper bound and penalize non-zero slack variables in an objective function of the QP optimization to prevent inequality constraint violations. However, Woerner teaches this limitation [see at least Woerner [0017] "...Today's algorithms for including inequality constraints into Quadratic Unconstrained Binary Optimization (QUBO) problems include non-negative slack variables to translate inequality to equality constraints which can be added as penalty terms to the QUBO objective. The slack variables are then handled in the classical optimizer together with the variational parameters driving the ansatz that handles the binary variables."]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar, Advani, Fan, Liu, and Zhang to use … adding a slack variable for each lower and upper bound and penalize non-zero slack variables in an objective function of the QP optimization to prevent inequality constraint violations as disclosed in Woerner with a reasonable expectation of success for the benefit of solving optimization problems effectively and improving system performance. [See at least Woerner [0017].]
Claims 17-18 are rejected under 35 U.S.C. 103 as being unpatentable over Afshar, in view of Advani, Fan, Liu, and Woerner.
As per claim 17, Afshar discloses a method for generating operable driving areas for an autonomous driving vehicle based on a path trajectory of the autonomous driving vehicle, comprising:
forming a space time (ST) graph indicating a distance of travel along the path trajectory with respect to time of the autonomous driving vehicle and path trajectories of devices intersecting with the path trajectory of the autonomous driving vehicle, the ST graph dynamically updated based on sensor readings of the autonomous driving vehicle [see at least Afshar Figs. 5-8; [0029] "...The techniques described herein perform path-based prediction of potential future trajectories of agents (e.g., surrounding vehicles, bicycles, and/or pedestrians) in a field of view of an AV. Particularly, the techniques predict not only future targets (e.g., intermediate destinations) of the agents but also reference paths (e.g., ones with highest probabilities) which each agent is likely to follow. After predicting a reference path, a future trajectory of each agent is completed with respect to its predicted reference path, which enhances a map compliance of the prediction,"; [0030] "...2) sampling the vectorized map for candidate reference paths (e.g., in 8 seconds) with reachable lane segments or reachable targets (e.g., end points) of the candidate reference paths; [0070] "planning system 404 receives data associated with an updated position of a vehicle (e.g., vehicles 102 of FIG. 1 or vehicle 200 of FIG. 2) from localization system 406 and planning system 404 updates the at least one trajectory or generates at least one different trajectory based on the data generated by localization system 406."; [0071] "the map is generated in real-time based on the data received by the perception system."];
segmenting the ST graph into cells, wherein viable cells represent discretized viable unoccupied spaces in the ST graph … [see at least Afshar Fig 8 [0119] "The scene encoder 810 creates agent feature vectors from the scene for each agent. The agent feature vectors include information about the map (e.g., lanes, cross sections, stop signs, turns, and/or the like), agent history 804 (e.g., past trajectories of agents), as well as agent-map interactions (e.g., location data, traffic data, expected routes, and/or the like) and agent-agent interactions (e.g., neighboring agent's routes, velocity data,..."; [0120] "...First, rotational invariant local feature vectors are encoded for each agent with a transformer module to aggregate neighboring agents' information (e.g., location data, expected routes, and/or the like) as well as local map structure (e.g., lanes, cross sections, stop signs, turns, and/or the like)."];
…finding passage ways for the autonomous driving vehicle based on the viable cells [see at least Afshar Fig 8 [0123] "An objective of the candidate path sampler 820 is to create a set of candidate reference paths for each agent by traversing the lane graph (e.g., the vectorized map 802)."; [0124] "In some embodiments, to select the candidate reference path for an agent a, a set of seed lane segments to be considered as the path starting points are selected".; [0125] "From the seed lane segments, a breadth-first search is performed to find the candidate paths, ... The output of the candidate path sampler 820 is a set of candidate reference paths for each agent, .... The choice of this parameter depends on the prediction horizon and lane segment resolution."]; and
selecting a desired passage way using … optimization when multiple passage ways are found, … to select the desired passage way to minimize time travel and undesirable movement of the autonomous driving vehicle, wherein distance, speed and acceleration are state variables … in a symmetric matrix of the … optimization … [see at least Afshar Fig 8; [0123] "An objective of the candidate path sampler 820 is to create a set of candidate reference paths for each agent by traversing the lane graph (e.g., the vectorized map 802)."; [0124] "In some embodiments, to select the candidate reference path for an agent a, a set of seed lane segments to be considered as the path starting points are selected."; [0125] "From the seed lane segments, a breadth-first search is performed to find the candidate paths... ."; [0124] , [0130] , [0070] "…planning system 404 receives data associated with a destination and generates data associated with at least one route (e.g., routes 106) along which a vehicle (e.g., vehicles 102) can travel along toward a destination… selecting an appropriate speed, acceleration, deceleration... ."]
Afshar fails to disclose … wherein segmenting the ST graph comprises: identifying occupied cells associated with each device at each time segment, wherein occupied cells are dynamically updated based on sensor readings of the autonomous driving vehicle at each time segment; combining overlapping occupied cells; and forming a complimentary set of the occupied cells, the complimentary set of the occupied cells forming the viable cells. However, Advani teaches these limitations:
… wherein segmenting the ST graph comprises:
identifying occupied cells associated with each device at each time segment wherein occupied cells are dynamically updated based on sensor readings of the autonomous driving vehicle at each time segment [see at least Advani [0107] "...the architecture 420a includes a Lidar SLAM component 471 and a radar mapping component 475...The Lidar SLAM component 471 generates a Lidar map 478 and a Lidar pose 477...the Lidar map is a grid map with predetermined size (number of grids) and resolution (size of each grid). Each map grid stores one of the three states: occupied, un-occupied and unknown. The occupied and unoccupied states imply whether the grid is filled with obstacles or not, while the unknown state means that it is undecided whether the grid is occupied or not. For example, an occupied state indicates that the grid includes an obstacle, while an unoccupied state indicates that the grid does not include an obstacle."; [0066] “previously generated maps within the information repository 340 can be updated as the drive system 320 maneuvers the electronic device 300 within an area, based on the information from the sensors 310, the SLAM engine 330, and previously generated maps.”];
combining overlapping occupied cells [see at least Advani [0109] "The radar map is a grid map that shares the same size and resolution as those of the Lidar map 478. Each grid stores an integer. In certain embodiments, the integer can range from 0 to 100, that represents the occupancy probability. The occupancy probability is the probability that the grid is occupied. In step 476b, the radar map and the Lidar map are then combined into one fusion map as the fusion map 479. The fusion map 479 is output top the navigation layer 430 of FIG. 4A."]; and
forming a complimentary set of the occupied cells, the complimentary set of the occupied cells forming the viable cells [see at least Advani [0109] "The radar map is a grid map that shares the same size and resolution as those of the Lidar map 478. Each grid stores an integer. In certain embodiments, the integer can range from 0 to 100, that represents the occupancy probability. The occupancy probability is the probability that the grid is occupied. In step 476b, the radar map and the Lidar map are then combined into one fusion map as the fusion map 479. The fusion map 479 is output top the navigation layer 430 of FIG. 4A."; [0205] " In step 710, the electronic device 300 modifies the first map, that is based on the Lidar scans, with the missed object of the second map, that was based on the radar scans, based on the determination that the second map includes an object that was missed by the first map. In certain embodiments, the electronic device 300 generates a fusion map by merging a state (occupied or unoccupied) of each cell of the first map with the value of the first cell of the second map, where the value indicates a probability that the cell is occupied."]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in Afshar to use … wherein segmenting the ST graph comprises: identifying occupied cells associated with each device at each time segment wherein occupied cells are dynamically updated based on sensor readings of the autonomous driving vehicle at each time segment; combining overlapping occupied cells; and forming a complimentary set of the occupied cells, the complimentary set of the occupied cells forming the viable cells as disclosed in Advani with a reasonable expectation of success for the benefit of improved generation of a map and navigation. [See at least Advani [0037].]
The combination of Afshar and Advani fails to disclose … selecting a desired passage way using quadratic programming (QP) optimization ... at each time segment, wherein the QP optimization uses soft constraints so inequality constraints when constructing the ST graph remain within bounds … . However, Fan teaches this limitation [see at least Fan [0026] "...a system selects a number of polynomials representing a number of time segments of a time duration to complete the path trajectory...The system defines a set of constraints to the polynomials to at least ensure the polynomials are smoothly joined together. The system performs a quadratic programming (QP) optimization on the objective function in view of the added constraints, such that a cost associated with the objective function reaches a minimum while the set of constraints are satisfied. The system generates a smooth speed for the time duration based on the optimized objective function to control the ADV autonomously."; FIG. 5B; [0080] "...a QP solver, such as QP optimization performed by optimization module 540 of FIG. 5B, can solve the target function to generate a smooth reference line. In one embodiment, a QP optimization is performed on the target function such that the target function reaches a predetermined threshold (e.g., minimum), while the set of constraints are satisfied. Once the target function has been optimized in view of the constraints, the coefficients of the polynomial functions can be determined. Then the location of the path points (e.g., control points) along the path can be determined using the polynomial function with the optimized coefficients, which represents a smooth reference line. As described above, the smoothing function is incorporated into the target function to be solved... .]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar and Advani to use … selecting a desired passage way using quadratic programming (QP) optimization ... at each time segment, wherein the QP optimization uses soft constraints so inequality constraints when constructing the ST graph remain within bounds … as disclosed in Fan with a reasonable expectation of success for the benefit of improved system responsiveness. [See at least Fan [0108].]
The combination of Afshar, Advani, and Fan fails to disclose … wherein … jerk [is used] as a control variable in a … QP optimization … . However, Liu teaches these limitations [see at least Liu p. 155 "B. Computing Speed, Acceleration and Jerk"; p. 155 "Section III formulates the temporal optimization problem for speed profile planning; Section IV discusses the quadratic approximation of the temporal optimization problem"; p. 156 Problem 1, "w(1), w(2), w(3), w(4), w(5) are positive weights" for acceleration (a) and jerk (j) in equation (2a).]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar, Advani, and Fan to use … wherein … jerk [is used] as a control variable in a … QP optimization … as disclosed in Liu with a reasonable expectation of success for the benefit of safety during interactions with other road participants. [See at least Liu, p. 159 Conclusion.]
The combination of Afshar, Advani, Fan, and Liu fails to disclose … wherein the soft constraints comprises adding a slack variable for each upper and lower bound and penalize non-zero slack variables in an objective function of the QP optimization. However, Woerner teaches this limitation [see at least Woerner [0017] "...Today's algorithms for including inequality constraints into Quadratic Unconstrained Binary Optimization (QUBO) problems include non-negative slack variables to translate inequality to equality constraints which can be added as penalty terms to the QUBO objective. The slack variables are then handled in the classical optimizer together with the variational parameters driving the ansatz that handles the binary variables."]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar, Advani, Fan, and Liu to use … wherein the soft constraints comprises adding a slack variable for each upper and lower bound and penalize non-zero slack variables in an objective function of the QP optimization as disclosed in Woerner with a reasonable expectation of success for the benefit of solving optimization problems effectively and improving system performance. [See at least Woerner [0017].]
As per claim 18, the combination of Afshar, Advani, Fan, Liu, and Woerner, as shown in the rejection above, discloses all of the limitations of claim 17.
The combination of Afshar, Advani, and Fan fails to disclose … wherein a weight wa is imposed on accelerations for displacements t E [0, .. . ,N - 2]) and a weight wj is imposed on jerks for displacements t E [0, ...,N - 3]). However, Liu teaches these limitations [see at least Liu p. 155 "B. Computing Speed, Acceleration and Jerk"; p. 155 "Section III formulates the temporal optimization problem for speed profile planning; Section IV discusses the quadratic approximation of the temporal optimization problem"; p. 156 Problem 1, "w(1), w(2), w(3), w(4), w(5) are positive weights" for acceleration (a) and jerk (j) in equation (2a).]
It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify the method as disclosed in the combination of Afshar, Advani, and Fan to use … wherein a weight wa is imposed on accelerations for displacements t E [0, .. . ,N - 2]) and a weight wj is imposed on jerks for displacements t E [0, ...,N - 3]) as disclosed in Liu with a reasonable expectation of success for the benefit of safety during interactions with other road participants. [See at least Liu, p. 159 Conclusion.]
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 PAULA L SCHNEIDER whose telephone number is (703)756-4606. The examiner can normally be reached Monday - Friday 9:00 am - 5:00 pm 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, Fadey Jabr can be reached at 571-272-1516. 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.
/P.L.S/Examiner, Art Unit 3668
/Fadey S. Jabr/Supervisory Patent Examiner, Art Unit 3668
Prosecution Insights