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
The claims 1-20 are currently pending and have been examined. Applicant amended claims 1-3, 7-10, and 12-19.
Response to Arguments/Amendments
The amendment filed November 17, 2025 has been entered. Claims 1-20 are currently pending in the Application. Applicant’s amendments to the claims have overcome the claim objections and 35 U.S.C. 112 rejections previously set forth in the Non-Final Rejection mailed August 18, 2025.
Applicant’s arguments with respect to Claims 1-20 under 35 U.S.C. 103 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.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claim(s) 1-6, 10 and 11 is/are rejected under 35 U.S.C. 103 as being unpatentable over Caldwell (US 20230041975 A1) in view of Moffitt (US 20140365544 A1).
Regarding Claim 1, Caldwell teaches A system comprising: one or more processors (See at least paragraph [0049], “The vehicle computing device(s) 204 may include processor(s) 218 and memory 220 communicatively coupled with the one or more processors 218. Memory 220 may represent memory 108. Computing device(s) 214 may also include processor(s) 222, and/or memory 224. The processor(s) 218 and/or 222 may be any suitable processor capable of executing instructions to process data and perform operations as described herein. By way of example and not limitation, the processor(s) 218 and/or 222 may comprise one or more central processing units (CPUs), graphics processing units (GPUs), integrated circuits (e.g., application-specific integrated circuits (ASICs)), gate arrays (e.g., field-programmable gate arrays (FPGAs)), and/or any other device or portion of a device that processes electronic data to transform that electronic data into other electronic data that may be stored in registers and/or memory.”); and non-transitory memory storing processor-executable instructions that, when executed by the one or more processors, cause the system to perform operations comprising: receiving sensor data from a sensor (See at least paragraph [0025], “According to the techniques discussed herein and an example where scenario 100 is a real-world example, the vehicle 102 may receive sensor data from sensor(s) 104 of the vehicle 102. For example, the sensor(s) 104 may include a location sensor (e.g., a global positioning system (GPS) sensor), an inertia sensor (e.g., an accelerometer sensor, a gyroscope sensor, etc.), a magnetic field sensor (e.g., a compass), a position/velocity/acceleration sensor (e.g., a speedometer, a drive system sensor), a depth position sensor (e.g., a lidar sensor, a radar sensor, a sonar sensor, a time of flight (ToF) camera, a depth camera, and/or other depth-sensing sensor), an image sensor (e.g., a camera), an audio sensor (e.g., a microphone), and/or environmental sensor (e.g., a barometer, a hygrometer, etc.). In some examples, a simulated sensor may correspond with at least one of the sensor(s) 104 on the vehicle 102 and in a simulation, one or more of sensor(s) 104 may be simulated. In some examples, the position of a simulated sensor may correspond with a relative position of one of the sensor(s) 104 to the vehicle 102.”); determining, based at least in part on the sensor data, a first candidate action and a second candidate action for controlling motion of a vehicle (See at least paragraph [0080], “At operation 336, example process 300 may comprise determining a first candidate action for controlling motion of the vehicle (based at least in part on a previous prediction node), according to any of the techniques discussed herein. The candidate action determined at operation 336 may be determined based at least in part on a prediction node of a most recently determined layer of prediction nodes. For example, FIG. 3B depicts only the first layer of prediction nodes, which only includes the root node 330. FIG. 3C depicts a second layer of prediction nodes, which includes prediction nodes 350 and 352. Determining the first candidate action may include providing to the planning component environment state data associated with a prediction node upon which the candidate action is based. For example, first action node 338 may be indicate one or more candidate actions that are based on environment state data indicated by the root node 330. FIG. 3B depicts one such candidate action, candidate action 340, which comprises controlling the vehicle to move straight forward.”); generating a tree comprising a first action node associated with the first candidate action and a second action node associated with the second candidate action (See at least paragraph [0088], “Once the planning component generates a first candidate action, the guidance component may update the data structure 332 to include the first action node 338 that identifies the first candidate action. FIG. 3B also depicts two more action nodes, 342 and 344, which are illustrated with dashed lines, as they may not be generated in cases where the tree search algorithm finds a low cost path with minimal exploration. In other words, action nodes 342 and 344 may be as-of-yet unexplored but may be generated upon additionally iterating operation 336 to enumerate additional candidate actions.”); determining, based at least in part on the first candidate action and a first cost function associated with a first level objective for controlling the vehicle, a first lower bound cost and a first upper bound cost associated with the first level objective (See at least paragraph [0090], “At operation 346, example process 300 may comprise determining, using a lower bound cost, a first cost associated with the first candidate action, according to any of the techniques discussed herein. In some examples, determining the first cost may be part of determining the first candidate action at operation 336 and/or the cost determination may happen contemporaneously using different processing units or upon receiving the first candidate action. In some examples, the guidance system may determine the cost and the cost may be based at least in part on the environment state data. In particular, the cost be based at least in part on a variety of sub-costs such as proximity cost(s), safety cost(s), comfort cost(s), and/or progress cost(s). These sub-costs may be based at least in part on the environment state data indicated by the last prediction node (whether the last prediction node is the root node or another prediction node). The proximity cost(s) may be based at least in part on a minimum, average, or other distance that the candidate action take the vehicle from a static and/or dynamic object. The safety cost(s) may include a score indicating conformance to rules of the road, proximity to other object(s) and/or a velocity associated with the candidate action (e.g., the safety cost may penalize candidate actions that are close to (e.g., within a threshold distance of) an object and moving at a high speed and not penalize or only provide a small penalty to candidate actions that are close to an object but associated with a low speed—high speed candidate actions that are far from other objects may be unpenalized by this cost), and/or proximity to a non-drivable surface (e.g., sidewalk, building, closed lane). In an example where the safety cost(s) include a variable cost based on velocity and lateral distance to an object, the cost may be determined based at least in part a hinge function, such as an L1 or L2 hinge function. In some examples, the hinge point in the hinge function where a penalty starts being applied may be based on distance to the object, velocity associated with the candidate action, object track, and/or object type. For example, a penalty may start applying further away from a biker than from a vehicle and/or a penalty may be higher/more sever for bikers than for vehicles. Moreover, the penalty may be more severe the faster the velocity associated with the candidate action once the candidate action is within the threshold distance of the vehicle (e.g., the hinge point of the hinge function). In at least one example, the threshold distance for applying the penalty specified by the L1 or L2 hinge function may be based at least in part the velocity associated with the candidate action. In other words, fast candidate actions will have a penalty applied further from the object than slow candidate actions and the L1 or L2 penalty may become more severe (e.g., steeper slope in the case of L1, larger coefficient and/or squared value) the closer a fast candidate action comes to the object compared to the same distance from a slow candidate action to the object.”); determining, based at least in part on the first upper bound cost, a first subset of the tree associated with upper bound costs that are determined based at least in part on the first cost function and are not greater than the first upper bound cost by more than a threshold amount (See at least paragraph [0095], “In some instances, a ramping ratio may be used to change the ratio of the lower bound cost to upper bound cost used in successive layers. For example, the upper bound cost may be used more or exclusively in the lowest layers (e.g., the first two or three), before introducing the lower bound cost and increasing the frequency with which the lower bound cost is used for successive layers (or vice versa. In some examples where the tree is sufficiently deep, the ramping ratio may reach a steady state where the lower bound is exclusively used or where a particular ratio is used (e.g., leveling off at a 1:1 ratio). Purely using the lower bound cost guarantees that finding the optimal route since it causes the tree search algorithm to explore more of the tree. However, by incorporating the upper bound cost, the tree search algorithm is greedier and by balancing the ratio of use of the lower bound cost to use of the upper bound cost, the tree search algorithm may be tuned. In other words, tuning the tree search algorithm may comprise balancing the algorithm between completeness of the amount of the space explored/time and an amount of compute to find a path and finding the best path” and paragraph [0096], “In some examples, search parameters, such as the ratio at which lower bound cost to upper bound cost is used or whether a lower bound or an upper bound cost is used exclusively may be determined based at least in part on perception data using a machine-learned model. For example, training data may be generated by experimentally altering the ratio used or exclusively using one of the lower bound cost or the upper bound cost and storing the path generated; the time, computational cycles, and/or number of nodes and/or layers it took to compute the path; the cost associated with the path; and/or how the lower bound/upper bound parameters were set. The machine-learned model may be trained to output tree search parameters predicted to decrease the computational cycles used, number of nodes explored, and/or cost associated with the path based on the perception data available to the machine-learned model, such as the environment state data indicated by the root node. The parameters may additionally or alternatively include a depth of the tree search, a width of the tree search, sampling parameters (discussed in more detail with reference to FIGS. 8A and 8B, such as how to vary predictions, the number of predictions made), parameters for determining whether to group prediction nodes into a single prediction node (e.g., whether an exact match of dependent candidate actions is required, a threshold distance used for identifying what qualifies as “similar,” and/or k-means clustering parameters), whether or not dynamic objects may be reclassified during the tree search and/or how many layers the search may explore before reclassifying, etc.” The system determines which nodes of the tree to explore based on comparisons against an upper bound cost. The process results in a subset of the tree that includes only those nodes whose costs do not exceed the upper bound threshold, satisfying determining a subset of the tree based on the cost not being greater than a first upper bound cost by more than a threshold amount.); determining a second subset of the tree based at least in part on a second upper bound cost determined by a second cost function associated with a second level objective, wherein the second subset is a subset of the first subset and wherein the second upper bound cost is determined for the first candidate action or the second candidate action (See at least paragraph [0107], “At operation 354, example process 300 may comprise determining a second candidate action for controlling motion of a vehicle based at least in part on environment state data indicated by a preceding prediction node, according to any of the techniques discussed herein. For example, determining the second candidate action may be based at least in part on the environment state data indicated by prediction node 350. This relationship between the prediction node and the candidate action based thereon is indicated by an arrow. In some examples, determining the second candidate action based at least in part on the prediction node 350 may be based at least in part on determining that the simulation that resulted in the updated environment state data associated with prediction node 350 didn't result in a violation of an operating constraint, that a cost was not exceeded, or that there was not an impact” and paragraph [0109], “In some examples, a final cost associated with the first candidate action may be determined after and/or contemporaneously with generation of the prediction node 350. In some examples, determining to generate the second candidate action may be based at least in part on this final cost. For example, other final cost(s) may be determined in association with action nodes 342 and/or 344 and/or prediction nodes dependent therefrom. Determining to generate a second candidate action that branches from the first action node 338 (via prediction node 35) may be based at least in part on determining that the first action node 338 is associated with a sum cost of action that is less than the sum cost of taking another action. Sum cost refers to the cost of the candidate action in question and the total cost of any preceding actions in the branch leading to the candidate action in question. In the case of the second candidate action, the sum cost would be the final cost associated with the second candidate action plus the final cost associated with the first candidate action.” The system determines a second candidate action based on environment data. The system determines a final cost for the action and compares it to the cost of other actions to choose the one with the lower total cost. This results in selecting a second subset of the tree from the first subset based on the second level objective.), determining a trajectory based at least in part on the second subset of the tree (See at least paragraph [0123], “A second set of candidate actions 412 may be generated based at least in part on selecting a first candidate action of the first set of candidate actions 402 for exploration and based at least in part on a final position 414, orientation, velocity, steering rate, etc. that the first candidate action would cause the vehicle to accomplish upon concluding execution of the first candidate action and environment state data. The second set of candidate actions 412 may additionally or alternatively be determined based at least in part on environment state data indicated by prediction node determined based at least in part on the first candidate action.” The system determines a trajectory using candidate actions selected from a refined portion of the search tree, consistent with the second subset, based on earlier cost evaluations.); and controlling the vehicle based at least in part on the trajectory (See at least paragraph [0120], “In some examples, the path determined by the guidance system may be a coarse path. For example, the coarse path may identify a position, heading, velocity, and/or curvature of approach for the vehicle to track at a 1 second or 500 millisecond interval, but the components of the vehicle may require or be capable of control over a finer time interval (e.g., 10 milliseconds, 100 milliseconds). In other words, the coarse path may not be smooth enough for the vehicle to track without significant errors. In some examples, a processor of a first type (e.g., a graphics processing unit (GPU)) may determine the prediction nodes and action nodes and/or determine the path and a processor of a second type may smooth the path generated by the GPU and/or determine a trajectory for controlling the vehicle based at least in part on the smooth path” and paragraph [0122], “The guidance system discussed herein may identify a path as feasible and/or determine a confidence score associated with the path based at least in part on the costs discussed herein. The guidance system may output the path and/or confidence score, which the autonomous vehicle may use to control motion of the autonomous vehicle, e.g., by generating a trajectory based at least in part on the path. In some examples, the guidance system may output a primary path and/or a contingent path. For example, the guidance system may determine the contingent path based at least in part on generating a set of candidate paths, determining that the set comprises two groups of candidate paths based at least in part on a threshold distance (e.g., the two groups may be two distinct homotopic groups), and selecting a primary path from a first group and a contingent path from the second group. In some examples, the primary path may be selected as the primary path based at least in part on determining that the primary path is associated with a first total cost that is less than a second total cost associated with the contingent path. The primary path may be associated with a first total cost and/or the contingent path may be associated with a second total cost that is/are less than a cost threshold and/or may be minimum costs of the respective groups associated therewith.”).
Caldwell does not explicitly disclose, however, Moffitt, in the same field of endeavor, teaches and wherein the first level objective is associated with at least a first level of the tree, the second level objective is associated with at least a second level of the tree, and the second level objective is different from the first level objective (See at least paragraph [0007], “In order to explore the space of all possible arrangements, an inclusion-exclusion tree is searched. An internal node of this tree may be pruned if a partial subset cannot possibly extend to a better solution. The leaves of this tree correspond to coarse decompositions of numbers to subproblems, but not necessarily to assignments within each group. To construct solutions, optimal partitions are obtained for each subproblem, and combined if their concatenation results in an improved solution”, paragraph [0038], “In order to limit the search performed by child solvers for P.sub.2 and its descendants once recursion is under way, the parameters can be passed as <c.sub.min, c.sub.max>=<max(P.sub.1), c.sub.best>, where max(P.sub.j) is the maximum subset sum in partition P.sub.j, and c.sub.best is the cost of the best solution S.sub.best found so far. Partial assignments for the second partition are abandoned whenever any subset sum is greater than the upper cost bound (.SIGMA.S.sub.i.gtoreq.c.sub.max), or whenever the sum of the complement of a subset is greater than the upper cost bound times a multiple based on the number of assignments remaining (.SIGMA. S.sub.i.gtoreq.c.sub.max*(k-i)). More signifcantly, a complete solution S will be returned whenever all subset sums are less than the lower cost bound (.SIGMA.S.sub.i.ltoreq.c.sub.min), regardless of whether P.sub.2 is an optimal decomposition. These cost bounds are distinct from any self-imposed upper and lower bounds, since they are determined by criteria computed by parent solvers. The lower cost bound criterion extends directly from the weakest-link nature of the partitioning objective function: a decomposition cannot be redeemed if its cost exceeds that of solutions encountered at higher levels, yet it receives no extra credit for obtaining sums below its neighboring partitions”, paragraph [0039], “Accordingly, a global optimum solution may be found which is not semi-optimal, as seen FIG. 3”, and paragraph [0040], “Additionally, another form of pruning can be introduced in which dominated solutions (i.e., solutions that are cost-preserving transmutations of earlier assignments) are detected and eliminated from search…In other words, surprisingly, after considering the inclusion of a number S.sub.i in a set whose sum is less than the upper bound, any subsequent extension to the set must strictly exceed that sum to obtain an improved solution.” The system further associates a first objective with a first level of the tree and a different second objective with a second level of the tree, such that objective-based evaluation and pruning are performed at different levels of the tree during the hierarchical search.).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Caldwell with the teachings of Ferguson such that the vehicle system of Caldwell is further configured to utilize wherein the first level objective is associated with at least a first level of the tree, the second level objective is associated with at least a second level of the tree, and the second level objective is different from the first level objective, as taught by Moffitt (See paragraph [0007], [0038]-[0040].), with a reasonable expectation of success. The motivation for doing so would be to increase efficiency for optimal solutions for search, as taught by Moffitt (See paragraph [0004].).
Regarding Claim 2, Caldwell and Moffitt teach The system of claim 1, as set forth in the obviousness rejection above. Caldwell teaches wherein: the first candidate action and the second candidate action are two candidate actions from among a plurality of candidate actions associated with different nodes of the tree; and determining the first subset of the tree comprises determining a subset of candidate actions that are associated with second upper bound costs that are more than the first upper bound cost by no more than the threshold amount (See at least paragraph [0107], “At operation 354, example process 300 may comprise determining a second candidate action for controlling motion of a vehicle based at least in part on environment state data indicated by a preceding prediction node, according to any of the techniques discussed herein. For example, determining the second candidate action may be based at least in part on the environment state data indicated by prediction node 350. This relationship between the prediction node and the candidate action based thereon is indicated by an arrow. In some examples, determining the second candidate action based at least in part on the prediction node 350 may be based at least in part on determining that the simulation that resulted in the updated environment state data associated with prediction node 350 didn't result in a violation of an operating constraint, that a cost was not exceeded, or that there was not an impact.”).
Regarding Claim 3, Caldwell and Moffitt teach The system of claim 1, as set forth in the obviousness rejection above. Caldwell teaches wherein: the first level objective comprises at least one of an impact avoidance objective or a safety objective; and the second level objective comprises at least one of a safety objective, a progress objective, a passenger comfort objective, or a driving performance objective (See at least paragraph [0090], “At operation 346, example process 300 may comprise determining, using a lower bound cost, a first cost associated with the first candidate action, according to any of the techniques discussed herein. In some examples, determining the first cost may be part of determining the first candidate action at operation 336 and/or the cost determination may happen contemporaneously using different processing units or upon receiving the first candidate action. In some examples, the guidance system may determine the cost and the cost may be based at least in part on the environment state data. In particular, the cost be based at least in part on a variety of sub-costs such as proximity cost(s), safety cost(s), comfort cost(s), and/or progress cost(s). These sub-costs may be based at least in part on the environment state data indicated by the last prediction node (whether the last prediction node is the root node or another prediction node). The proximity cost(s) may be based at least in part on a minimum, average, or other distance that the candidate action take the vehicle from a static and/or dynamic object. The safety cost(s) may include a score indicating conformance to rules of the road, proximity to other object(s) and/or a velocity associated with the candidate action (e.g., the safety cost may penalize candidate actions that are close to (e.g., within a threshold distance of) an object and moving at a high speed and not penalize or only provide a small penalty to candidate actions that are close to an object but associated with a low speed—high speed candidate actions that are far from other objects may be unpenalized by this cost), and/or proximity to a non-drivable surface (e.g., sidewalk, building, closed lane). In an example where the safety cost(s) include a variable cost based on velocity and lateral distance to an object, the cost may be determined based at least in part a hinge function, such as an L1 or L2 hinge function. In some examples, the hinge point in the hinge function where a penalty starts being applied may be based on distance to the object, velocity associated with the candidate action, object track, and/or object type. For example, a penalty may start applying further away from a biker than from a vehicle and/or a penalty may be higher/more sever for bikers than for vehicles. Moreover, the penalty may be more severe the faster the velocity associated with the candidate action once the candidate action is within the threshold distance of the vehicle (e.g., the hinge point of the hinge function). In at least one example, the threshold distance for applying the penalty specified by the L1 or L2 hinge function may be based at least in part the velocity associated with the candidate action. In other words, fast candidate actions will have a penalty applied further from the object than slow candidate actions and the L1 or L2 penalty may become more severe (e.g., steeper slope in the case of L1, larger coefficient and/or squared value) the closer a fast candidate action comes to the object compared to the same distance from a slow candidate action to the object.”).
With respect to claim 10, please see the rejection above with respect to claim 3, which is commensurate in scope to claim 10, with claim 3 being drawn to a system for a vehicle and claim 10 being drawn to a corresponding method.
Regarding Claim 4, Caldwell and Moffitt teach The system of claim 1, as set forth in the obviousness rejection above. Caldwell teaches wherein: the operations further comprise determining a predicted state estimated to result from controlling the vehicle using the first candidate action; and determining the first lower bound cost and the first upper bound cost is based at least in part on the predicted state (See at least paragraph [0090], “At operation 346, example process 300 may comprise determining, using a lower bound cost, a first cost associated with the first candidate action, according to any of the techniques discussed herein. In some examples, determining the first cost may be part of determining the first candidate action at operation 336 and/or the cost determination may happen contemporaneously using different processing units or upon receiving the first candidate action. In some examples, the guidance system may determine the cost and the cost may be based at least in part on the environment state data. In particular, the cost be based at least in part on a variety of sub-costs such as proximity cost(s), safety cost(s), comfort cost(s), and/or progress cost(s). These sub-costs may be based at least in part on the environment state data indicated by the last prediction node (whether the last prediction node is the root node or another prediction node). The proximity cost(s) may be based at least in part on a minimum, average, or other distance that the candidate action take the vehicle from a static and/or dynamic object. The safety cost(s) may include a score indicating conformance to rules of the road, proximity to other object(s) and/or a velocity associated with the candidate action (e.g., the safety cost may penalize candidate actions that are close to (e.g., within a threshold distance of) an object and moving at a high speed and not penalize or only provide a small penalty to candidate actions that are close to an object but associated with a low speed—high speed candidate actions that are far from other objects may be unpenalized by this cost), and/or proximity to a non-drivable surface (e.g., sidewalk, building, closed lane). In an example where the safety cost(s) include a variable cost based on velocity and lateral distance to an object, the cost may be determined based at least in part a hinge function, such as an L1 or L2 hinge function. In some examples, the hinge point in the hinge function where a penalty starts being applied may be based on distance to the object, velocity associated with the candidate action, object track, and/or object type. For example, a penalty may start applying further away from a biker than from a vehicle and/or a penalty may be higher/more sever for bikers than for vehicles. Moreover, the penalty may be more severe the faster the velocity associated with the candidate action once the candidate action is within the threshold distance of the vehicle (e.g., the hinge point of the hinge function). In at least one example, the threshold distance for applying the penalty specified by the L1 or L2 hinge function may be based at least in part the velocity associated with the candidate action. In other words, fast candidate actions will have a penalty applied further from the object than slow candidate actions and the L1 or L2 penalty may become more severe (e.g., steeper slope in the case of L1, larger coefficient and/or squared value) the closer a fast candidate action comes to the object compared to the same distance from a slow candidate action to the object” and paragraph [0101], “Once the simulation is complete (e.g., upon completing the candidate action), the resulting predicted track(s) (e.g., position(s), orientation(s), etc. as discussed above) of the object(s) in the environment, including vehicle 306's resultant track from executing the first candidate action, may be used to determine updated environment state data. The data structure 332 may be updated to include a prediction node 350 that indicates this updated environment state data and the predicted state of the environment that may result from implementing the first candidate action. In some examples, the simulation may be re-executed using slightly different variables (e.g., changing a propensity of a dynamic object from “conservative” to “aggressive,” “submissive,” or “nominal) to determine second updated environment data associated with a different prediction node, prediction node 352. In some examples, the simulation component may output multiple potential scenarios, each of which may be associated with a likelihood. In such an example, the guidance component may create a prediction node for each potential (predicted) scenario that is associated with a likelihood that meets or exceeds a likelihood threshold.”).
Regarding Claim 5, Caldwell and Moffitt teach The system of claim 1, as set forth in the obviousness rejection above. Caldwell teaches wherein: the threshold amount is a first threshold amount associated with the first level objective; and the second level objective is associated with a second threshold amount different from the first threshold amount (See at least paragraph [0090], “At operation 346, example process 300 may comprise determining, using a lower bound cost, a first cost associated with the first candidate action, according to any of the techniques discussed herein. In some examples, determining the first cost may be part of determining the first candidate action at operation 336 and/or the cost determination may happen contemporaneously using different processing units or upon receiving the first candidate action. In some examples, the guidance system may determine the cost and the cost may be based at least in part on the environment state data. In particular, the cost be based at least in part on a variety of sub-costs such as proximity cost(s), safety cost(s), comfort cost(s), and/or progress cost(s). These sub-costs may be based at least in part on the environment state data indicated by the last prediction node (whether the last prediction node is the root node or another prediction node). The proximity cost(s) may be based at least in part on a minimum, average, or other distance that the candidate action take the vehicle from a static and/or dynamic object. The safety cost(s) may include a score indicating conformance to rules of the road, proximity to other object(s) and/or a velocity associated with the candidate action (e.g., the safety cost may penalize candidate actions that are close to (e.g., within a threshold distance of) an object and moving at a high speed and not penalize or only provide a small penalty to candidate actions that are close to an object but associated with a low speed—high speed candidate actions that are far from other objects may be unpenalized by this cost), and/or proximity to a non-drivable surface (e.g., sidewalk, building, closed lane). In an example where the safety cost(s) include a variable cost based on velocity and lateral distance to an object, the cost may be determined based at least in part a hinge function, such as an L1 or L2 hinge function. In some examples, the hinge point in the hinge function where a penalty starts being applied may be based on distance to the object, velocity associated with the candidate action, object track, and/or object type. For example, a penalty may start applying further away from a biker than from a vehicle and/or a penalty may be higher/more sever for bikers than for vehicles. Moreover, the penalty may be more severe the faster the velocity associated with the candidate action once the candidate action is within the threshold distance of the vehicle (e.g., the hinge point of the hinge function). In at least one example, the threshold distance for applying the penalty specified by the L1 or L2 hinge function may be based at least in part the velocity associated with the candidate action. In other words, fast candidate actions will have a penalty applied further from the object than slow candidate actions and the L1 or L2 penalty may become more severe (e.g., steeper slope in the case of L1, larger coefficient and/or squared value) the closer a fast candidate action comes to the object compared to the same distance from a slow candidate action to the object” and paragraph [0101], “Once the simulation is complete (e.g., upon completing the candidate action), the resulting predicted track(s) (e.g., position(s), orientation(s), etc. as discussed above) of the object(s) in the environment, including vehicle 306's resultant track from executing the first candidate action, may be used to determine updated environment state data. The data structure 332 may be updated to include a prediction node 350 that indicates this updated environment state data and the predicted state of the environment that may result from implementing the first candidate action. In some examples, the simulation may be re-executed using slightly different variables (e.g., changing a propensity of a dynamic object from “conservative” to “aggressive,” “submissive,” or “nominal) to determine second updated environment data associated with a different prediction node, prediction node 352. In some examples, the simulation component may output multiple potential scenarios, each of which may be associated with a likelihood. In such an example, the guidance component may create a prediction node for each potential (predicted) scenario that is associated with a likelihood that meets or exceeds a likelihood threshold.”).
With respect to claim 11, please see the rejection above with respect to claim 5, which is commensurate in scope to claim 11, with claim 5 being drawn to a system for a vehicle and claim 11 being drawn to a corresponding method.
Regarding Claim 6, Caldwell and Moffitt teach The system of claim 1, as set forth in the obviousness rejection above. Caldwell teaches wherein the first upper bound cost is a lowest upper bound cost from among multiple upper bound costs determined by the first cost function (See at least paragraph [0090], “At operation 346, example process 300 may comprise determining, using a lower bound cost, a first cost associated with the first candidate action, according to any of the techniques discussed herein. In some examples, determining the first cost may be part of determining the first candidate action at operation 336 and/or the cost determination may happen contemporaneously using different processing units or upon receiving the first candidate action. In some examples, the guidance system may determine the cost and the cost may be based at least in part on the environment state data. In particular, the cost be based at least in part on a variety of sub-costs such as proximity cost(s), safety cost(s), comfort cost(s), and/or progress cost(s). These sub-costs may be based at least in part on the environment state data indicated by the last prediction node (whether the last prediction node is the root node or another prediction node). The proximity cost(s) may be based at least in part on a minimum, average, or other distance that the candidate action take the vehicle from a static and/or dynamic object. The safety cost(s) may include a score indicating conformance to rules of the road, proximity to other object(s) and/or a velocity associated with the candidate action (e.g., the safety cost may penalize candidate actions that are close to (e.g., within a threshold distance of) an object and moving at a high speed and not penalize or only provide a small penalty to candidate actions that are close to an object but associated with a low speed—high speed candidate actions that are far from other objects may be unpenalized by this cost), and/or proximity to a non-drivable surface (e.g., sidewalk, building, closed lane). In an example where the safety cost(s) include a variable cost based on velocity and lateral distance to an object, the cost may be determined based at least in part a hinge function, such as an L1 or L2 hinge function. In some examples, the hinge point in the hinge function where a penalty starts being applied may be based on distance to the object, velocity associated with the candidate action, object track, and/or object type. For example, a penalty may start applying further away from a biker than from a vehicle and/or a penalty may be higher/more sever for bikers than for vehicles. Moreover, the penalty may be more severe the faster the velocity associated with the candidate action once the candidate action is within the threshold distance of the vehicle (e.g., the hinge point of the hinge function). In at least one example, the threshold distance for applying the penalty specified by the L1 or L2 hinge function may be based at least in part the velocity associated with the candidate action. In other words, fast candidate actions will have a penalty applied further from the object than slow candidate actions and the L1 or L2 penalty may become more severe (e.g., steeper slope in the case of L1, larger coefficient and/or squared value) the closer a fast candidate action comes to the object compared to the same distance from a slow candidate action to the object” and paragraph [0101], “Once the simulation is complete (e.g., upon completing the candidate action), the resulting predicted track(s) (e.g., position(s), orientation(s), etc. as discussed above) of the object(s) in the environment, including vehicle 306's resultant track from executing the first candidate action, may be used to determine updated environment state data. The data structure 332 may be updated to include a prediction node 350 that indicates this updated environment state data and the predicted state of the environment that may result from implementing the first candidate action. In some examples, the simulation may be re-executed using slightly different variables (e.g., changing a propensity of a dynamic object from “conservative” to “aggressive,” “submissive,” or “nominal) to determine second updated environment data associated with a different prediction node, prediction node 352. In some examples, the simulation component may output multiple potential scenarios, each of which may be associated with a likelihood. In such an example, the guidance component may create a prediction node for each potential (predicted) scenario that is associated with a likelihood that meets or exceeds a likelihood threshold.”).
Claim(s) 7-9, and 12-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Caldwell (US 20230041975 A1) in view of Ferguson (US 9248834 B1) and Moffitt (US 20140365544 A1).
Regarding Claim 7, Caldwell teaches A method comprising: determining, for a first candidate action for controlling a vehicle, a first lower bound cost and a first upper bound cost associated with a first level objective (See at least paragraph [0090], “At operation 346, example process 300 may comprise determining, using a lower bound cost, a first cost associated with the first candidate action, according to any of the techniques discussed herein. In some examples, determining the first cost may be part of determining the first candidate action at operation 336 and/or the cost determination may happen contemporaneously using different processing units or upon receiving the first candidate action. In some examples, the guidance system may determine the cost and the cost may be based at least in part on the environment state data. In particular, the cost be based at least in part on a variety of sub-costs such as proximity cost(s), safety cost(s), comfort cost(s), and/or progress cost(s). These sub-costs may be based at least in part on the environment state data indicated by the last prediction node (whether the last prediction node is the root node or another prediction node). The proximity cost(s) may be based at least in part on a minimum, average, or other distance that the candidate action take the vehicle from a static and/or dynamic object. The safety cost(s) may include a score indicating conformance to rules of the road, proximity to other object(s) and/or a velocity associated with the candidate action (e.g., the safety cost may penalize candidate actions that are close to (e.g., within a threshold distance of) an object and moving at a high speed and not penalize or only provide a small penalty to candidate actions that are close to an object but associated with a low speed—high speed candidate actions that are far from other objects may be unpenalized by this cost), and/or proximity to a non-drivable surface (e.g., sidewalk, building, closed lane). In an example where the safety cost(s) include a variable cost based on velocity and lateral distance to an object, the cost may be determined based at least in part a hinge function, such as an L1 or L2 hinge function. In some examples, the hinge point in the hinge function where a penalty starts being applied may be based on distance to the object, velocity associated with the candidate action, object track, and/or object type. For example, a penalty may start applying further away from a biker than from a vehicle and/or a penalty may be higher/more sever for bikers than for vehicles. Moreover, the penalty may be more severe the faster the velocity associated with the candidate action once the candidate action is within the threshold distance of the vehicle (e.g., the hinge point of the hinge function). In at least one example, the threshold distance for applying the penalty specified by the L1 or L2 hinge function may be based at least in part the velocity associated with the candidate action. In other words, fast candidate actions will have a penalty applied further from the object than slow candidate actions and the L1 or L2 penalty may become more severe (e.g., steeper slope in the case of L1, larger coefficient and/or squared value) the closer a fast candidate action comes to the object compared to the same distance from a slow candidate action to the object” and paragraph [0093], “In some examples, instead of determining all of the sub-costs, operation 346 may comprise using a lower bound cost or an upper bound cost to stand-in for determining at least a portion of the sub-costs, such as the cost-to-go. For example, the lower bound cost may be 0 and the upper bound cost may be the cost of using a default action. The lower bound cost may be a predefined heuristic although in an additional or alternate example, the lower bound may be determined by a machine-learned model trained based at least in part on simulating or operating the vehicle and determining a minimum cost of the action taken by the vehicle for similar scenarios. This machine-learned model may determine the lower bound cost based at least in part on the environment scenario data and/or a track associated with the vehicle (i.e., that data may be provided as input). In yet another example, the lower bound cost may be updated after all or most of the candidate actions have been determined that are based upon a prediction node. In such an instance, the lower bound cost may be updated to be the cost of the candidate action having the lowest cost.”); generating a tree comprising a first action node associated with the first candidate action and a second action node associated with a second candidate action (See at least paragraph [0103], “If any candidate actions are identified as being similar, the process may comprise associating the predictions that the two (or more) similar candidate actions were generated from/dependent upon with a same prediction node. In some examples, when multiple predictions are associated with a same prediction node, the process may include determining a weight in association with each different prediction. The weight may indicate a degree to which the prediction belongs with that prediction node. Determining this weight may be based at least in part on the similarity of a candidate action generated from a prediction to one or more actions associated with different candidate actions associated determined from the other prediction(s). Grouping the predictions into a single prediction node may be used by the process to determine a smaller subset of candidate actions to explore, such as one or the top p candidate actions, as ranked by cost, where p is a positive integer. For example, the top two candidate actions, ranked according to cost, may be associated with the prediction node that identifies multiple predictions. Future exploration may be based at least in part on these two candidate actions.”); determining a second lower bound cost and a second upper bound cost associated with a second level objective (See at least paragraph [0090], “At operation 346, example process 300 may comprise determining, using a lower bound cost, a first cost associated with the first candidate action, according to any of the techniques discussed herein. In some examples, determining the first cost may be part of determining the first candidate action at operation 336 and/or the cost determination may happen contemporaneously using different processing units or upon receiving the first candidate action. In some examples, the guidance system may determine the cost and the cost may be based at least in part on the environment state data. In particular, the cost be based at least in part on a variety of sub-costs such as proximity cost(s), safety cost(s), comfort cost(s), and/or progress cost(s). These sub-costs may be based at least in part on the environment state data indicated by the last prediction node (whether the last prediction node is the root node or another prediction node). The proximity cost(s) may be based at least in part on a minimum, average, or other distance that the candidate action take the vehicle from a static and/or dynamic object. The safety cost(s) may include a score indicating conformance to rules of the road, proximity to other object(s) and/or a velocity associated with the candidate action (e.g., the safety cost may penalize candidate actions that are close to (e.g., within a threshold distance of) an object and moving at a high speed and not penalize or only provide a small penalty to candidate actions that are close to an object but associated with a low speed—high speed candidate actions that are far from other objects may be unpenalized by this cost), and/or proximity to a non-drivable surface (e.g., sidewalk, building, closed lane). In an example where the safety cost(s) include a variable cost based on velocity and lateral distance to an object, the cost may be determined based at least in part a hinge function, such as an L1 or L2 hinge function. In some examples, the hinge point in the hinge function where a penalty starts being applied may be based on distance to the object, velocity associated with the candidate action, object track, and/or object type. For example, a penalty may start applying further away from a biker than from a vehicle and/or a penalty may be higher/more sever for bikers than for vehicles. Moreover, the penalty may be more severe the faster the velocity associated with the candidate action once the candidate action is within the threshold distance of the vehicle (e.g., the hinge point of the hinge function). In at least one example, the threshold distance for applying the penalty specified by the L1 or L2 hinge function may be based at least in part the velocity associated with the candidate action. In other words, fast candidate actions will have a penalty applied further from the object than slow candidate actions and the L1 or L2 penalty may become more severe (e.g., steeper slope in the case of L1, larger coefficient and/or squared value) the closer a fast candidate action comes to the object compared to the same distance from a slow candidate action to the object” and paragraph [0093], “In some examples, instead of determining all of the sub-costs, operation 346 may comprise using a lower bound cost or an upper bound cost to stand-in for determining at least a portion of the sub-costs, such as the cost-to-go. For example, the lower bound cost may be 0 and the upper bound cost may be the cost of using a default action. The lower bound cost may be a predefined heuristic although in an additional or alternate example, the lower bound may be determined by a machine-learned model trained based at least in part on simulating or operating the vehicle and determining a minimum cost of the action taken by the vehicle for similar scenarios. This machine-learned model may determine the lower bound cost based at least in part on the environment scenario data and/or a track associated with the vehicle (i.e., that data may be provided as input). In yet another example, the lower bound cost may be updated after all or most of the candidate actions have been determined that are based upon a prediction node. In such an instance, the lower bound cost may be updated to be the cost of the candidate action having the lowest cost.”), and controlling the vehicle based at least in part on the first candidate action (See at least paragraph [0120], “In some examples, the path determined by the guidance system may be a coarse path. For example, the coarse path may identify a position, heading, velocity, and/or curvature of approach for the vehicle to track at a 1 second or 500 millisecond interval, but the components of the vehicle may require or be capable of control over a finer time interval (e.g., 10 milliseconds, 100 milliseconds). In other words, the coarse path may not be smooth enough for the vehicle to track without significant errors. In some examples, a processor of a first type (e.g., a graphics processing unit (GPU)) may determine the prediction nodes and action nodes and/or determine the path and a processor of a second type may smooth the path generated by the GPU and/or determine a trajectory for controlling the vehicle based at least in part on the smooth path” and paragraph [0122], “The guidance system discussed herein may identify a path as feasible and/or determine a confidence score associated with the path based at least in part on the costs discussed herein. The guidance system may output the path and/or confidence score, which the autonomous vehicle may use to control motion of the autonomous vehicle, e.g., by generating a trajectory based at least in part on the path. In some examples, the guidance system may output a primary path and/or a contingent path. For example, the guidance system may determine the contingent path based at least in part on generating a set of candidate paths, determining that the set comprises two groups of candidate paths based at least in part on a threshold distance (e.g., the two groups may be two distinct homotopic groups), and selecting a primary path from a first group and a contingent path from the second group. In some examples, the primary path may be selected as the primary path based at least in part on determining that the primary path is associated with a first total cost that is less than a second total cost associated with the contingent path. The primary path may be associated with a first total cost and/or the contingent path may be associated with a second total cost that is/are less than a cost threshold and/or may be minimum costs of the respective groups associated therewith.”).
Caldwell does not explicitly disclose, however, Ferguson, in the same field of endeavor, teaches determining to use the first candidate action based at least in part on: determining that the second upper bound cost associated with the second level objective is less than a third upper bound cost associated with the second candidate action and determined for the second level objective (See at least Col. 5 lines 25-45, “The vehicle's computer may use the potential trajectories to identify a final future trajectory. The trajectory with the highest likelihood value may be identified as the final future trajectory. In other examples a second threshold may be used to identify a subset of the trajectories based on a relationship between the vehicle and other objects. The vehicle's computer may react to all the trajectories in the subset of trajectories in planning a route for the vehicle. In still other examples, where there are no trajectories with likelihood values above the predetermined threshold, all of the potential trajectories may be further analyzed. This analysis may include taking a number of points along each of the trajectories. If points from different trajectories are within a predetermined distance from each other at a predetermined time, the likelihood values of those trajectories may be added up and compared to the threshold value. If the sum of the likelihood values meets the threshold value, then all of the trajectories that had their likelihood values summed together may be considered a final future trajectory. The final future trajectory may be used by the vehicle's computer to plan a route for the vehicle that, for example, avoids the vehicle coming too close to the object.”); and determining that a difference between the first upper bound cost associated with the first level objective and a fourth upper bound cost associated with the second candidate action and determined for the first level objective is not greater than a threshold amount associated with the first level objective (See at least Col. 5 lines 25-45, “The vehicle's computer may use the potential trajectories to identify a final future trajectory. The trajectory with the highest likelihood value may be identified as the final future trajectory. In other examples a second threshold may be used to identify a subset of the trajectories based on a relationship between the vehicle and other objects. The vehicle's computer may react to all the trajectories in the subset of trajectories in planning a route for the vehicle. In still other examples, where there are no trajectories with likelihood values above the predetermined threshold, all of the potential trajectories may be further analyzed. This analysis may include taking a number of points along each of the trajectories. If points from different trajectories are within a predetermined distance from each other at a predetermined time, the likelihood values of those trajectories may be added up and compared to the threshold value. If the sum of the likelihood values meets the threshold value, then all of the trajectories that had their likelihood values summed together may be considered a final future trajectory. The final future trajectory may be used by the vehicle's computer to plan a route for the vehicle that, for example, avoids the vehicle coming too close to the object.”).
Caldwell and Ferguson do not explicitly disclose, however, Moffitt, in the same field of endeavor, teaches wherein the first level objective is associated with at least a first level of the tree, the second level objective is associated with at least a second level of the tree, and the second level objective is different from the first level objective (See at least paragraph [0007], “In order to explore the space of all possible arrangements, an inclusion-exclusion tree is searched. An internal node of this tree may be pruned if a partial subset cannot possibly extend to a better solution. The leaves of this tree correspond to coarse decompositions of numbers to subproblems, but not necessarily to assignments within each group. To construct solutions, optimal partitions are obtained for each subproblem, and combined if their concatenation results in an improved solution”, paragraph [0038], “In order to limit the search performed by child solvers for P.sub.2 and its descendants once recursion is under way, the parameters can be passed as <c.sub.min, c.sub.max>=<max(P.sub.1), c.sub.best>, where max(P.sub.j) is the maximum subset sum in partition P.sub.j, and c.sub.best is the cost of the best solution S.sub.best found so far. Partial assignments for the second partition are abandoned whenever any subset sum is greater than the upper cost bound (.SIGMA.S.sub.i.gtoreq.c.sub.max), or whenever the sum of the complement of a subset is greater than the upper cost bound times a multiple based on the number of assignments remaining (.SIGMA. S.sub.i.gtoreq.c.sub.max*(k-i)). More signifcantly, a complete solution S will be returned whenever all subset sums are less than the lower cost bound (.SIGMA.S.sub.i.ltoreq.c.sub.min), regardless of whether P.sub.2 is an optimal decomposition. These cost bounds are distinct from any self-imposed upper and lower bounds, since they are determined by criteria computed by parent solvers. The lower cost bound criterion extends directly from the weakest-link nature of the partitioning objective function: a decomposition cannot be redeemed if its cost exceeds that of solutions encountered at higher levels, yet it receives no extra credit for obtaining sums below its neighboring partitions”, paragraph [0039], “Accordingly, a global optimum solution may be found which is not semi-optimal, as seen FIG. 3”, and paragraph [0040], “Additionally, another form of pruning can be introduced in which dominated solutions (i.e., solutions that are cost-preserving transmutations of earlier assignments) are detected and eliminated from search…In other words, surprisingly, after considering the inclusion of a number S.sub.i in a set whose sum is less than the upper bound, any subsequent extension to the set must strictly exceed that sum to obtain an improved solution.” The system further associates a first objective with a first level of the tree and a different second objective with a second level of the tree, such that objective-based evaluation and pruning are performed at different levels of the tree during the hierarchical search.).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Caldwell with the teachings of Ferguson and Moffitt such that the vehicle system of Caldwell is further configured to determine to use the first candidate action based at least in part on: determining that the second upper bound cost associated with the second level objective is less than a third upper bound cost associated with the second candidate action and determined for the second level objective and determine that a difference between the first upper bound cost associated with the first level objective and a fourth upper bound cost associated with the second candidate action and determined for the first level objective is not greater than a threshold amount associated with the first level objective, as taught by Ferguson (See Col. 5 lines 25-45.), and utilize wherein the first level objective is associated with at least a first level of the tree, the second level objective is associated with at least a second level of the tree, and the second level objective is different from the first level objective, as taught by Moffitt (See paragraph [0007], [0038]-[0040].), with a reasonable expectation of success. The motivation for doing so would be to increase vehicle maneuverability and enhance driving decisions, as taught by Ferguson (See Col. 1 lines 15-30.). The motivation for doing so would be to increase efficiency for optimal solutions for search, as taught by Moffitt (See paragraph [0004].).
Regarding Claim 8, Caldwell, Ferguson, and Moffitt teach The method of claim 7, as set forth in the obviousness rejection above. Caldwell does not explicitly disclose, however, Ferguson, in the same field of endeavor, teaches further comprising: determining a subset of action nodes of the tree associated with upper bound costs determined for the first level objective, wherein determining the subset comprises determining that the upper bound costs associated therewith are not greater than the fourth upper bound cost by more than the threshold amount from the first upper bound cost, wherein the fourth upper bound cost is a lowest upper bound cost associated with the first level objective (See at least Col. 5 lines 25-45, “The vehicle's computer may use the potential trajectories to identify a final future trajectory. The trajectory with the highest likelihood value may be identified as the final future trajectory. In other examples a second threshold may be used to identify a subset of the trajectories based on a relationship between the vehicle and other objects. The vehicle's computer may react to all the trajectories in the subset of trajectories in planning a route for the vehicle. In still other examples, where there are no trajectories with likelihood values above the predetermined threshold, all of the potential trajectories may be further analyzed. This analysis may include taking a number of points along each of the trajectories. If points from different trajectories are within a predetermined distance from each other at a predetermined time, the likelihood values of those trajectories may be added up and compared to the threshold value. If the sum of the likelihood values meets the threshold value, then all of the trajectories that had their likelihood values summed together may be considered a final future trajectory. The final future trajectory may be used by the vehicle's computer to plan a route for the vehicle that, for example, avoids the vehicle coming too close to the object.” The system identifies a subset of trajectories based on a threshold relative to the optimal trajectory’s likelihood value (highest=lowest cost) which corresponds to determining action nodes whose upper bound costs are within a threshold of the lowest upper bound cost for the first level objective.).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Caldwell with the teachings of Ferguson and Moffitt such that the vehicle system of Caldwell is further configured to determine to use the first candidate action based at least in part on: determining that the second upper bound cost associated with the second level objective is less than a third upper bound cost associated with the second candidate action and determined for the second level objective and determine that a difference between the first upper bound cost associated with the first level objective and a fourth upper bound cost associated with the second candidate action and determined for the first level objective is not greater than a threshold amount associated with the first level objective, and determine a subset of action nodes of the tree associated with upper bound costs determined for the first level objective, wherein determining the subset comprises determining that the upper bound costs associated therewith are not greater than the fourth upper bound cost by more than the threshold amount from the first upper bound cost, wherein the fourth upper bound cost is a lowest upper bound cost associated with the first level objective, as taught by Ferguson (See Col. 5 lines 25-45.), and utilize wherein the first level objective is associated with at least a first level of the tree, the second level objective is associated with at least a second level of the tree, and the second level objective is different from the first level objective, as taught by Moffitt (See paragraph [0007], [0038]-[0040].), with a reasonable expectation of success. The motivation for doing so would be to increase vehicle maneuverability and enhance driving decisions, as taught by Ferguson (See Col. 1 lines 15-30.). The motivation for doing so would be to increase efficiency for optimal solutions for search, as taught by Moffitt (See paragraph [0004].).
Regarding Claim 9, Caldwell, Ferguson, and Moffitt teach The method of claim 8, as set forth in the obviousness rejection above. Caldwell teaches wherein: the first candidate action and the second candidate action are two candidate actions from among a plurality of candidate actions associated with different nodes of the tree; and determining the subset comprises determining a subset of candidate actions that are associated with second upper bound costs that are more than the fourth upper bound cost by no more than the threshold amount (See at least paragraph [0095], “In some instances, a ramping ratio may be used to change the ratio of the lower bound cost to upper bound cost used in successive layers. For example, the upper bound cost may be used more or exclusively in the lowest layers (e.g., the first two or three), before introducing the lower bound cost and increasing the frequency with which the lower bound cost is used for successive layers (or vice versa. In some examples where the tree is sufficiently deep, the ramping ratio may reach a steady state where the lower bound is exclusively used or where a particular ratio is used (e.g., leveling off at a 1:1 ratio). Purely using the lower bound cost guarantees that finding the optimal route since it causes the tree search algorithm to explore more of the tree. However, by incorporating the upper bound cost, the tree search algorithm is greedier and by balancing the ratio of use of the lower bound cost to use of the upper bound cost, the tree search algorithm may be tuned. In other words, tuning the tree search algorithm may comprise balancing the algorithm between completeness of the amount of the space explored/time and an amount of compute to find a path and finding the best path” and paragraph [0110], “The data structure 332 may be updated to include the second action node 356 and action node(s) associated with any other candidate actions determined based at least in part on prediction node 350. Note that FIGS. 3B and 3C illustrate a simplification of the process where only one branch of each layer is explored. Additional actions may be determined from a same prediction node, as depicted by action nodes 342 and 344, or from different prediction nodes; additional prediction nodes may be determined; and so on. Prediction nodes 350 and 352 may be considered to be in a second layer of prediction nodes, as the root node 330 may itself include predicted environment state data.”).
Regarding Claim 12, Caldwell, Ferguson, and Moffitt teach The method of claim 7, as set forth in the obviousness rejection above. Caldwell teaches wherein: the first upper bound cost is a lowest upper bound cost from among multiple upper bound costs determined by a first cost function; and the threshold amount is a first threshold amount and a second threshold amount is associated with the second level objective (See at least paragraph [0095], “In some instances, a ramping ratio may be used to change the ratio of the lower bound cost to upper bound cost used in successive layers. For example, the upper bound cost may be used more or exclusively in the lowest layers (e.g., the first two or three), before introducing the lower bound cost and increasing the frequency with which the lower bound cost is used for successive layers (or vice versa. In some examples where the tree is sufficiently deep, the ramping ratio may reach a steady state where the lower bound is exclusively used or where a particular ratio is used (e.g., leveling off at a 1:1 ratio). Purely using the lower bound cost guarantees that finding the optimal route since it causes the tree search algorithm to explore more of the tree. However, by incorporating the upper bound cost, the tree search algorithm is greedier and by balancing the ratio of use of the lower bound cost to use of the upper bound cost, the tree search algorithm may be tuned. In other words, tuning the tree search algorithm may comprise balancing the algorithm between completeness of the amount of the space explored/time and an amount of compute to find a path and finding the best path” and paragraph [0121], “The guidance system discussed herein may identify a path as feasible and/or determine a confidence score associated with the path based at least in part on the costs discussed herein. The guidance system may output the path and/or confidence score, which the autonomous vehicle may use to control motion of the autonomous vehicle, e.g., by generating a trajectory based at least in part on the path. In some examples, the guidance system may output a primary path and/or a contingent path. For example, the guidance system may determine the contingent path based at least in part on generating a set of candidate paths, determining that the set comprises two groups of candidate paths based at least in part on a threshold distance (e.g., the two groups may be two distinct homotopic groups), and selecting a primary path from a first group and a contingent path from the second group. In some examples, the primary path may be selected as the primary path based at least in part on determining that the primary path is associated with a first total cost that is less than a second total cost associated with the contingent path. The primary path may be associated with a first total cost and/or the contingent path may be associated with a second total cost that is/are less than a cost threshold and/or may be minimum costs of the respective groups associated therewith.”).
Regarding Claim 13, Caldwell, Ferguson, and Moffitt teach The method of claim 7, as set forth in the obviousness rejection above. Caldwell does not explicitly disclose, however, Ferguson, in the same field of endeavor, teaches wherein determining the first upper bound cost is based at least in part on a transition cost associated with taking the first candidate action from a first state to a second state, a an estimate of a total upper bound cost of reaching the second state from a beginning state associated with a root node of a tree search (See at least paragraph [0095], “In some instances, a ramping ratio may be used to change the ratio of the lower bound cost to upper bound cost used in successive layers. For example, the upper bound cost may be used more or exclusively in the lowest layers (e.g., the first two or three), before introducing the lower bound cost and increasing the frequency with which the lower bound cost is used for successive layers (or vice versa. In some examples where the tree is sufficiently deep, the ramping ratio may reach a steady state where the lower bound is exclusively used or where a particular ratio is used (e.g., leveling off at a 1:1 ratio). Purely using the lower bound cost guarantees that finding the optimal route since it causes the tree search algorithm to explore more of the tree. However, by incorporating the upper bound cost, the tree search algorithm is greedier and by balancing the ratio of use of the lower bound cost to use of the upper bound cost, the tree search algorithm may be tuned. In other words, tuning the tree search algorithm may comprise balancing the algorithm between completeness of the amount of the space explored/time and an amount of compute to find a path and finding the best path” and paragraph [0110], “The data structure 332 may be updated to include the second action node 356 and action node(s) associated with any other candidate actions determined based at least in part on prediction node 350. Note that FIGS. 3B and 3C illustrate a simplification of the process where only one branch of each layer is explored. Additional actions may be determined from a same prediction node, as depicted by action nodes 342 and 344, or from different prediction nodes; additional prediction nodes may be determined; and so on. Prediction nodes 350 and 352 may be considered to be in a second layer of prediction nodes, as the root node 330 may itself include predicted environment state data.”).
Caldwell does not explicitly disclose, however, Ferguson, in the same field of endeavor, teaches risk transition mapping (See at least Col. 5 lines 25-45, “The vehicle's computer may use the potential trajectories to identify a final future trajectory. The trajectory with the highest likelihood value may be identified as the final future trajectory. In other examples a second threshold may be used to identify a subset of the trajectories based on a relationship between the vehicle and other objects. The vehicle's computer may react to all the trajectories in the subset of trajectories in planning a route for the vehicle. In still other examples, where there are no trajectories with likelihood values above the predetermined threshold, all of the potential trajectories may be further analyzed. This analysis may include taking a number of points along each of the trajectories. If points from different trajectories are within a predetermined distance from each other at a predetermined time, the likelihood values of those trajectories may be added up and compared to the threshold value. If the sum of the likelihood values meets the threshold value, then all of the trajectories that had their likelihood values summed together may be considered a final future trajectory. The final future trajectory may be used by the vehicle's computer to plan a route for the vehicle that, for example, avoids the vehicle coming too close to the object.”).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Caldwell with the teachings of Ferguson and Moffitt such that the vehicle system of Caldwell is further configured to determine to use the first candidate action based at least in part on: determining that the second upper bound cost associated with the second level objective is less than a third upper bound cost associated with the second candidate action and determined for the second level objective and determine that a difference between the first upper bound cost associated with the first level objective and a fourth upper bound cost associated with the second candidate action and determined for the first level objective is not greater than a threshold amount associated with the first level objective, and utilize risk transition mapping, as taught by Ferguson (See Col. 5 lines 25-45.), and utilize wherein the first level objective is associated with at least a first level of the tree, the second level objective is associated with at least a second level of the tree, and the second level objective is different from the first level objective, as taught by Moffitt (See paragraph [0007], [0038]-[0040].), with a reasonable expectation of success. The motivation for doing so would be to increase vehicle maneuverability and enhance driving decisions, as taught by Ferguson (See Col. 1 lines 15-30.). The motivation for doing so would be to increase efficiency for optimal solutions for search, as taught by Moffitt (See paragraph [0004].).
With respect to claim 19, please see the rejection above with respect to claim 13, which is commensurate in scope to claim 19, with claim 13 being drawn to a method for controlling a vehicle and claim 19 being drawn to a corresponding non-transitory computer-readable media.
Regarding Claim 14, Caldwell teaches One or more non-transitory computer-readable media storing processor-executable instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising: determining, for a first candidate action associated with controlling a vehicle, a first lower bound cost and a first upper bound cost associated with a first level objective for controlling the vehicle (See at least paragraph [0066], “The memory 220 and/or 224 may additionally or alternatively store a mapping system, a planning system, a ride management system, etc. Although perception component 228, planning component 230, and/or simulation component 234 are illustrated as being stored in memory 220 and/or 224, perception component 228, planning component 230, guidance component 232, simulation component 234, and/or agent filter 236 may include processor-executable instructions, machine-learned model(s) (e.g., a neural network), and/or hardware”, paragraph [0090], “At operation 346, example process 300 may comprise determining, using a lower bound cost, a first cost associated with the first candidate action, according to any of the techniques discussed herein. In some examples, determining the first cost may be part of determining the first candidate action at operation 336 and/or the cost determination may happen contemporaneously using different processing units or upon receiving the first candidate action. In some examples, the guidance system may determine the cost and the cost may be based at least in part on the environment state data. In particular, the cost be based at least in part on a variety of sub-costs such as proximity cost(s), safety cost(s), comfort cost(s), and/or progress cost(s). These sub-costs may be based at least in part on the environment state data indicated by the last prediction node (whether the last prediction node is the root node or another prediction node). The proximity cost(s) may be based at least in part on a minimum, average, or other distance that the candidate action take the vehicle from a static and/or dynamic object. The safety cost(s) may include a score indicating conformance to rules of the road, proximity to other object(s) and/or a velocity associated with the candidate action (e.g., the safety cost may penalize candidate actions that are close to (e.g., within a threshold distance of) an object and moving at a high speed and not penalize or only provide a small penalty to candidate actions that are close to an object but associated with a low speed—high speed candidate actions that are far from other objects may be unpenalized by this cost), and/or proximity to a non-drivable surface (e.g., sidewalk, building, closed lane). In an example where the safety cost(s) include a variable cost based on velocity and lateral distance to an object, the cost may be determined based at least in part a hinge function, such as an L1 or L2 hinge function. In some examples, the hinge point in the hinge function where a penalty starts being applied may be based on distance to the object, velocity associated with the candidate action, object track, and/or object type. For example, a penalty may start applying further away from a biker than from a vehicle and/or a penalty may be higher/more sever for bikers than for vehicles. Moreover, the penalty may be more severe the faster the velocity associated with the candidate action once the candidate action is within the threshold distance of the vehicle (e.g., the hinge point of the hinge function). In at least one example, the threshold distance for applying the penalty specified by the L1 or L2 hinge function may be based at least in part the velocity associated with the candidate action. In other words, fast candidate actions will have a penalty applied further from the object than slow candidate actions and the L1 or L2 penalty may become more severe (e.g., steeper slope in the case of L1, larger coefficient and/or squared value) the closer a fast candidate action comes to the object compared to the same distance from a slow candidate action to the object”, and paragraph [0093], “In some examples, instead of determining all of the sub-costs, operation 346 may comprise using a lower bound cost or an upper bound cost to stand-in for determining at least a portion of the sub-costs, such as the cost-to-go. For example, the lower bound cost may be 0 and the upper bound cost may be the cost of using a default action. The lower bound cost may be a predefined heuristic although in an additional or alternate example, the lower bound may be determined by a machine-learned model trained based at least in part on simulating or operating the vehicle and determining a minimum cost of the action taken by the vehicle for similar scenarios. This machine-learned model may determine the lower bound cost based at least in part on the environment scenario data and/or a track associated with the vehicle (i.e., that data may be provided as input). In yet another example, the lower bound cost may be updated after all or most of the candidate actions have been determined that are based upon a prediction node. In such an instance, the lower bound cost may be updated to be the cost of the candidate action having the lowest cost.”); determining, based at least in part on the first candidate action or a second candidate action of the subset of the plurality of candidate actions, a second lower bound cost and a second upper bound cost associated with a second level objective for controlling the vehicle, wherein the second candidate action is part of the subset of the plurality of candidate actions and is associated with a third upper bound cost determined for the first level objective and that is greater than the first upper bound cost by less than the threshold amount (See at least paragraph [0090], “At operation 346, example process 300 may comprise determining, using a lower bound cost, a first cost associated with the first candidate action, according to any of the techniques discussed herein. In some examples, determining the first cost may be part of determining the first candidate action at operation 336 and/or the cost determination may happen contemporaneously using different processing units or upon receiving the first candidate action. In some examples, the guidance system may determine the cost and the cost may be based at least in part on the environment state data. In particular, the cost be based at least in part on a variety of sub-costs such as proximity cost(s), safety cost(s), comfort cost(s), and/or progress cost(s). These sub-costs may be based at least in part on the environment state data indicated by the last prediction node (whether the last prediction node is the root node or another prediction node). The proximity cost(s) may be based at least in part on a minimum, average, or other distance that the candidate action take the vehicle from a static and/or dynamic object. The safety cost(s) may include a score indicating conformance to rules of the road, proximity to other object(s) and/or a velocity associated with the candidate action (e.g., the safety cost may penalize candidate actions that are close to (e.g., within a threshold distance of) an object and moving at a high speed and not penalize or only provide a small penalty to candidate actions that are close to an object but associated with a low speed—high speed candidate actions that are far from other objects may be unpenalized by this cost), and/or proximity to a non-drivable surface (e.g., sidewalk, building, closed lane). In an example where the safety cost(s) include a variable cost based on velocity and lateral distance to an object, the cost may be determined based at least in part a hinge function, such as an L1 or L2 hinge function. In some examples, the hinge point in the hinge function where a penalty starts being applied may be based on distance to the object, velocity associated with the candidate action, object track, and/or object type. For example, a penalty may start applying further away from a biker than from a vehicle and/or a penalty may be higher/more sever for bikers than for vehicles. Moreover, the penalty may be more severe the faster the velocity associated with the candidate action once the candidate action is within the threshold distance of the vehicle (e.g., the hinge point of the hinge function). In at least one example, the threshold distance for applying the penalty specified by the L1 or L2 hinge function may be based at least in part the velocity associated with the candidate action. In other words, fast candidate actions will have a penalty applied further from the object than slow candidate actions and the L1 or L2 penalty may become more severe (e.g., steeper slope in the case of L1, larger coefficient and/or squared value) the closer a fast candidate action comes to the object compared to the same distance from a slow candidate action to the object” and paragraph [0093], “In some examples, instead of determining all of the sub-costs, operation 346 may comprise using a lower bound cost or an upper bound cost to stand-in for determining at least a portion of the sub-costs, such as the cost-to-go. For example, the lower bound cost may be 0 and the upper bound cost may be the cost of using a default action. The lower bound cost may be a predefined heuristic although in an additional or alternate example, the lower bound may be determined by a machine-learned model trained based at least in part on simulating or operating the vehicle and determining a minimum cost of the action taken by the vehicle for similar scenarios. This machine-learned model may determine the lower bound cost based at least in part on the environment scenario data and/or a track associated with the vehicle (i.e., that data may be provided as input). In yet another example, the lower bound cost may be updated after all or most of the candidate actions have been determined that are based upon a prediction node. In such an instance, the lower bound cost may be updated to be the cost of the candidate action having the lowest cost.”), and controlling the vehicle based at least in part on the second upper bound cost (See at least paragraph [0111], “Example process 300 may initiate operation(s) 358 and/or 360 based at least in part on determining the second candidate action although, in some examples, operation 358 may additionally or alternatively be determined based at least in part on operation 348.”).
Caldwell does not explicitly disclose, however, Ferguson, in the same field of endeavor, teaches determining, based at least in part on a threshold amount and at least one of the first lower bound cost or the first upper bound cost, a subset of a plurality of candidate actions comprising the first candidate action (See at least Col. 5 lines 25-45, “The vehicle's computer may use the potential trajectories to identify a final future trajectory. The trajectory with the highest likelihood value may be identified as the final future trajectory. In other examples a second threshold may be used to identify a subset of the trajectories based on a relationship between the vehicle and other objects. The vehicle's computer may react to all the trajectories in the subset of trajectories in planning a route for the vehicle. In still other examples, where there are no trajectories with likelihood values above the predetermined threshold, all of the potential trajectories may be further analyzed. This analysis may include taking a number of points along each of the trajectories. If points from different trajectories are within a predetermined distance from each other at a predetermined time, the likelihood values of those trajectories may be added up and compared to the threshold value. If the sum of the likelihood values meets the threshold value, then all of the trajectories that had their likelihood values summed together may be considered a final future trajectory. The final future trajectory may be used by the vehicle's computer to plan a route for the vehicle that, for example, avoids the vehicle coming too close to the object.”).
Caldwell and Ferguson do not explicitly disclose, however, Moffitt, in the same field of endeavor, teaches and wherein the first level objective is associated with at least a first level of a tree, the second level objective is associated with at least a second level of the tree, and the second level objective is different from the first level objective (See at least paragraph [0007], “In order to explore the space of all possible arrangements, an inclusion-exclusion tree is searched. An internal node of this tree may be pruned if a partial subset cannot possibly extend to a better solution. The leaves of this tree correspond to coarse decompositions of numbers to subproblems, but not necessarily to assignments within each group. To construct solutions, optimal partitions are obtained for each subproblem, and combined if their concatenation results in an improved solution”, paragraph [0038], “In order to limit the search performed by child solvers for P.sub.2 and its descendants once recursion is under way, the parameters can be passed as <c.sub.min, c.sub.max>=<max(P.sub.1), c.sub.best>, where max(P.sub.j) is the maximum subset sum in partition P.sub.j, and c.sub.best is the cost of the best solution S.sub.best found so far. Partial assignments for the second partition are abandoned whenever any subset sum is greater than the upper cost bound (.SIGMA.S.sub.i.gtoreq.c.sub.max), or whenever the sum of the complement of a subset is greater than the upper cost bound times a multiple based on the number of assignments remaining (.SIGMA. S.sub.i.gtoreq.c.sub.max*(k-i)). More signifcantly, a complete solution S will be returned whenever all subset sums are less than the lower cost bound (.SIGMA.S.sub.i.ltoreq.c.sub.min), regardless of whether P.sub.2 is an optimal decomposition. These cost bounds are distinct from any self-imposed upper and lower bounds, since they are determined by criteria computed by parent solvers. The lower cost bound criterion extends directly from the weakest-link nature of the partitioning objective function: a decomposition cannot be redeemed if its cost exceeds that of solutions encountered at higher levels, yet it receives no extra credit for obtaining sums below its neighboring partitions”, paragraph [0039], “Accordingly, a global optimum solution may be found which is not semi-optimal, as seen FIG. 3”, and paragraph [0040], “Additionally, another form of pruning can be introduced in which dominated solutions (i.e., solutions that are cost-preserving transmutations of earlier assignments) are detected and eliminated from search…In other words, surprisingly, after considering the inclusion of a number S.sub.i in a set whose sum is less than the upper bound, any subsequent extension to the set must strictly exceed that sum to obtain an improved solution.” The system further associates a first objective with a first level of the tree and a different second objective with a second level of the tree, such that objective-based evaluation and pruning are performed at different levels of the tree during the hierarchical search.).
Thus, it would have been obvious to one of ordinary skill in the art before the effective filing date to combine the invention of Caldwell with the teachings of Ferguson and Moffitt such that the vehicle system of Caldwell is further configured to determine, based at least in part on a threshold amount and at least one of the first lower bound cost or the first upper bound cost, a subset of a plurality of candidate actions comprising the first candidate action, as taught by Ferguson (See Col. 5 lines 25-45.), utilize wherein the first level objective is associated with at least a first level of the tree, the second level objective is associated with at least a second level of the tree, and the second level objective is different from the first level objective, as taught by Moffitt (See paragraph [0007], [0038]-[0040].), with a reasonable expectation of success. The motivation for doing so would be to increase vehicle maneuverability and enhance driving decisions, as taught by Ferguson (See Col. 1 lines 15-30.). The motivation for doing so would be to increase efficiency for optimal solutions for search, as taught by Moffitt (See paragraph [0004].).
Regarding Claim 15, Caldwell, Ferguson, and Moffitt teach The one or more non-transitory computer-readable media of claim 14, as set forth in the obviousness rejection above. Caldwell teaches wherein determining the subset of the plurality of candidate actions comprises determining that lower bound costs or upper bound costs associated with the subset of the plurality of candidate actions do not exceed the first upper bound cost by more than the threshold amount (See at least paragraph [0103], “If any candidate actions are identified as being similar, the process may comprise associating the predictions that the two (or more) similar candidate actions were generated from/dependent upon with a same prediction node. In some examples, when multiple predictions are associated with a same prediction node, the process may include determining a weight in association with each different prediction. The weight may indicate a degree to which the prediction belongs with that prediction node. Determining this weight may be based at least in part on the similarity of a candidate action generated from a prediction to one or more actions associated with different candidate actions associated determined from the other prediction(s). Grouping the predictions into a single prediction node may be used by the process to determine a smaller subset of candidate actions to explore, such as one or the top p candidate actions, as ranked by cost, where p is a positive integer. For example, the top two candidate actions, ranked according to cost, may be associated with the prediction node that identifies multiple predictions. Future exploration may be based at least in part on these two candidate actions.”).
Regarding Claim 16, Caldwell, Ferguson, and Moffitt teach The one or more non-transitory computer-readable media of claim 14, as set forth in the obviousness rejection above. Caldwell teaches wherein the operations further comprise updating a prediction node of a tree search, and the prediction node indicates a vehicle state that results in executing the first candidate action or the second candidate action (See at least paragraph [0078], “Predictions of how the object(s) will behave in the future, correspondingly how this data will change in the future, may be associated with the prediction node(s) discussed herein and, in some examples, the prediction data for a current time step may be associated with the root node. In other words, the root node may include the current state of the environment, including the object(s) therein, localization data related to the vehicle (e.g., determined by SLAM), and/or prediction data identifying one or more possible future states of the environment, which may include a position, orientation, velocity, acceleration, classification, etc. of an object associated with a future time” and paragraph [0088], “Once the planning component generates a first candidate action, the guidance component may update the data structure 332 to include the first action node 338 that identifies the first candidate action. FIG. 3B also depicts two more action nodes, 342 and 344, which are illustrated with dashed lines, as they may not be generated in cases where the tree search algorithm finds a low cost path with minimal exploration. In other words, action nodes 342 and 344 may be as-of-yet unexplored but may be generated upon additionally iterating operation 336 to enumerate additional candidate actions.” The prediction node stores prediction data indicating a possible future state of the vehicle (e.g. position, orientation, velocity and the tree search data structure is updated to include new nodes.).
Regarding Claim 17, Caldwell, Ferguson, and Moffitt teach The one or more non-transitory computer-readable media of claim 16, as set forth in the obviousness rejection above. Caldwell teaches wherein updating the prediction node is based at least in part on the first upper bound cost, the second upper bound cost, and one or more costs associated with a node that exists between the prediction node and a root node of the tree search (See at least paragraph [0109], “In some examples, a final cost associated with the first candidate action may be determined after and/or contemporaneously with generation of the prediction node 350. In some examples, determining to generate the second candidate action may be based at least in part on this final cost. For example, other final cost(s) may be determined in association with action nodes 342 and/or 344 and/or prediction nodes dependent therefrom. Determining to generate a second candidate action that branches from the first action node 338 (via prediction node 35) may be based at least in part on determining that the first action node 338 is associated with a sum cost of action that is less than the sum cost of taking another action. Sum cost refers to the cost of the candidate action in question and the total cost of any preceding actions in the branch leading to the candidate action in question. In the case of the second candidate action, the sum cost would be the final cost associated with the second candidate action plus the final cost associated with the first candidate action.”).
Regarding Claim 18, Caldwell, Ferguson, and Moffitt teach The one or more non-transitory computer-readable media of claim 16, as set forth in the obviousness rejection above. Caldwell teaches wherein the operations further comprise: storing the first lower bound cost and the first upper bound cost in association with the prediction node; and storing the second lower bound cost and the second upper bound cost in association with the prediction node, wherein the first candidate action is associated with a first action node of the tree search, the second candidate action is associated with a second action node of the tree search, and the prediction node is associated with the tree search (See at least paragraph [0115], “At operation 360, example process 300 may comprise determining, using an upper bound cost, a second cost associated with the second candidate action, according to any of the techniques discussed herein. As discussed above and purely for the sake of example, a lower bound cost was used at operation 346 and alternating use of the lower bound cost and upper bound cost according to a 1:1 ratio would dictate that an upper bound cost be used at operation 360. However, as discussed above, the upper bound cost may be used first and the ratio may be any other ratio other than 1:1. Regardless, determining the second cost may comprise using the upper bound cost, which may be a predetermined cost associated with a default action.”).
Regarding Claim 20, Caldwell, Ferguson, and Moffitt teach The one or more non-transitory computer-readable media of claim 19, as set forth in the obviousness rejection above. Caldwell teaches wherein the transition cost is based at least in part on one or more sub-costs associated with the first level objective (See at least paragraph [0090], “At operation 346, example process 300 may comprise determining, using a lower bound cost, a first cost associated with the first candidate action, according to any of the techniques discussed herein. In some examples, determining the first cost may be part of determining the first candidate action at operation 336 and/or the cost determination may happen contemporaneously using different processing units or upon receiving the first candidate action. In some examples, the guidance system may determine the cost and the cost may be based at least in part on the environment state data. In particular, the cost be based at least in part on a variety of sub-costs such as proximity cost(s), safety cost(s), comfort cost(s), and/or progress cost(s). These sub-costs may be based at least in part on the environment state data indicated by the last prediction node (whether the last prediction node is the root node or another prediction node). The proximity cost(s) may be based at least in part on a minimum, average, or other distance that the candidate action take the vehicle from a static and/or dynamic object. The safety cost(s) may include a score indicating conformance to rules of the road, proximity to other object(s) and/or a velocity associated with the candidate action (e.g., the safety cost may penalize candidate actions that are close to (e.g., within a threshold distance of) an object and moving at a high speed and not penalize or only provide a small penalty to candidate actions that are close to an object but associated with a low speed—high speed candidate actions that are far from other objects may be unpenalized by this cost), and/or proximity to a non-drivable surface (e.g., sidewalk, building, closed lane). In an example where the safety cost(s) include a variable cost based on velocity and lateral distance to an object, the cost may be determined based at least in part a hinge function, such as an L1 or L2 hinge function. In some examples, the hinge point in the hinge function where a penalty starts being applied may be based on distance to the object, velocity associated with the candidate action, object track, and/or object type. For example, a penalty may start applying further away from a biker than from a vehicle and/or a penalty may be higher/more sever for bikers than for vehicles. Moreover, the penalty may be more severe the faster the velocity associated with the candidate action once the candidate action is within the threshold distance of the vehicle (e.g., the hinge point of the hinge function). In at least one example, the threshold distance for applying the penalty specified by the L1 or L2 hinge function may be based at least in part the velocity associated with the candidate action. In other words, fast candidate actions will have a penalty applied further from the object than slow candidate actions and the L1 or L2 penalty may become more severe (e.g., steeper slope in the case of L1, larger coefficient and/or squared value) the closer a fast candidate action comes to the object compared to the same distance from a slow candidate action to the object.”).
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 JEWEL ASHLEY KUNTZ whose telephone number is (571)270-5542. The examiner can normally be reached M-F 8:30am-5:30pm.
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, Anne Antonucci can be reached at (313) 446-6519. 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.
/JEWEL A KUNTZ/Examiner, Art Unit 3666
/ANNE MARIE ANTONUCCI/Supervisory Patent Examiner, Art Unit 3666