DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first
inventor to file provisions of the AIA .
Status of Claims
This is the first Office action on the merits. Claims 1-20 are currently pending and addressed below.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea of a mental process without significantly more.
101 Analysis – Step 1
Claims 1, 13, and 20 are directed to a method (i.e., a process) and an electronic device (i.e., a machine). Therefore, claims 1, 13, and 20 are within at least one of the four statutory categories.
101 Analysis – Step 2A, Prong I
Regarding Prong I of the Step 2A analysis, the claims are to be analyzed to determine whether they recite subject matter that falls within one of the follow groups of abstract ideas: a) mathematical concepts, b) certain methods of organizing human activity, and/or c) mental processes.
Independent claims 1, 13, and 20 include limitations that recite an abstract idea and will be used as a representative claim for the remainder of the 101 rejection.
Independent claims 1, 13, and 20 recite the following information:
An electronic device/method, comprising:
memory storing instructions; and
at least one processor configured to execute the instructions,
wherein the instructions, when executed by the at least one processor individually or collectively, cause the electronic device to:
determine whether a moving object has reached a target node;
in response to the moving object not reaching the target node, determine a first optimal node and a first optimal edge through which the moving object passes to reach the target node from a current location of the moving object;
input obstacle information around the moving object, the target node, the first optimal node, and the first optimal edge to an artificial intelligence (AI) model;
determine a candidate node through which the moving object is likely to pass after reaching the first optimal node to reach the target node based on a confidence of an output of the Al model included in the output of the Al model, based on a selected one of a first distribution of the optimal path determined based on the first optimal node, a second distribution of the optimal path determined based on a target tree generated from the target node, and an area comprising the first distribution and the second distribution; and
determine an optimal path for the moving object to reach the target node based on one or more candidate nodes including the candidate node.
The examiner submits that the foregoing bolded limitation(s) constitute an abstract idea of a mental process that monitors the trajectory and an environment of a vehicle to determine if a vehicle has reached a target destination, determines an initial optimal path from the current location of the vehicle to the destination, evaluates, using a model, identified obstacle information, the target destination and initial optimal path to determine candidate points in the path to the destination based on a confidence of outputs of the model, and analyzes the candidate points to determine the most optimal path to the destination.
Each of the limitations can be performed in the mental realm or by using pen and paper to monitor the trajectory and an environment of a vehicle to determine if a vehicle has reached a target destination, determine an initial optimal path from the current location of the vehicle to the destination, evaluate, using a model, identified obstacle information, the target destination and initial optimal path to determine candidate points in the path to the destination based on a confidence of outputs of the model, and analyze the candidate points to determine the most optimal path to the destination.
101 Analysis – Step 2A, Prong II
Regarding Prong II of the Step 2A analysis, the claims are to be analyzed to determine whether the claim, as a whole, integrates the abstract into a practical application. It must be determined whether any additional elements in the claim beyond the abstract idea integrate the exception into a practical application in a manner that imposes a meaningful limit on the judicial exception. The courts have indicated that additional elements merely using a computer to implement an abstract idea, adding insignificant extra solution activity, or generally linking use of a judicial exception to a particular technological environment or field of use do not integrate a judicial exception into a “practical application.”
Claims 1, 13, and 20 do contain additional elements of an electronic device, memory storing instructions, at least one processor configured to execute the instructions, wherein the instructions, when executed by the at least one processor individually or collectively, cause the electronic device to perform functions, and an artificial intelligence (AI) model. However, these additional elements do not add to significantly more than the abstract idea of a mental process.
For the following reason(s), the examiner submits that the above identified additional limitations do not integrate the above-noted abstract idea into a practical application.
Regarding the additional elements of an electronic device, memory storing instructions, at least one processor configured to execute the instructions, wherein the instructions, when executed by the at least one processor individually or collectively, cause the electronic device to perform functions, and an artificial intelligence (AI) model, the examiner submits that these limitations merely describe how to generally apply the otherwise mental judgements in a generic or general-purpose vehicle path planning system environment. The an electronic device, memory storing instructions, at least one processor configured to execute the instructions, wherein the instructions, when executed by the at least one processor individually or collectively, cause the electronic device to perform functions, and an artificial intelligence (AI) model are recited at a high level of generality and merely automate the whether the moving object has reached a target node determining, first optimal node determining, artificial intelligence model information inputting, candidate node determining, and optimal path determining components of the system. The examiner submits that these limitations are recited at a high level of generality (i.e., describe general means of the whether the moving object has reached a target node determining, first optimal node determining, artificial intelligence model information inputting, candidate node determining, and optimal path determining steps) and therefore amount to mere transmission of data between computer processing components which is a form of insignificant extra-solution activity that merely uses computing components to perform the process.
Thus, taken alone, the additional elements do not integrate the abstract idea into a practical application. Further, looking at the additional limitation(s) as an ordered combination or as a whole, the limitation(s) add nothing that is not already present when looking at the elements taken individually. For instance, there is no indication that the additional elements, when considered as a whole, reflect an improvement in the functioning of a computer or an improvement to another technology or technical field, apply or use the above-noted judicial exception to effect a particular treatment or prophylaxis for a disease or medical condition, implement/use the above-noted judicial exception with a particular machine or manufacture that is integral to the claim, effect a transformation or reduction of a particular article to a different state or thing, or apply or use the judicial exception in some other meaningful way beyond generally linking the use of the judicial exception to a particular technological environment, such that the claim as a whole is not more than a drafting effort designed to monopolize the exception (MPEP § 2106.05). Accordingly, the additional limitation(s) do/does not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea.
101 Analysis – Step 2B
Regarding Step 2B, representative independent claims 1, 13, and 20 do not include additional elements (considered both individually and as an ordered combination) that are sufficient to amount to significantly more than the judicial exception for the same reasons to those discussed above with respect to determining that the claim does not integrate the abstract idea into a practical application. As discussed above with respect to integration of the abstract idea into a practical application, the additional elements of an electronic device, memory storing instructions, at least one processor configured to execute the instructions, wherein the instructions, when executed by the at least one processor individually or collectively, cause the electronic device to perform functions, and an artificial intelligence (AI) model amount to nothing more than applying the exception using a generic computer component. Generally applying an exception using a generic computer component cannot provide an inventive concept. And as discussed above, the additional limitations amount to mere transmission of data between computer processing components which is a form of insignificant extra-solution activity that merely uses computing components to perform the process.
Further, a conclusion that an additional element is insignificant extra-solution activity in Step 2A should be re-evaluated in Step 2B to determine if they are more than what is well-understood, routine, conventional activity in the field. The additional limitations of gathering/transmitting data are well-understood, routine, and conventional activities because the specification does not provide any indication that the computer is anything other than a conventional computer. MPEP 2106.05(d)(II), and the cases cited therein, including Intellectual Ventures I, LLC v. Symantec Corp., 838 F.3d 1307, 1321 (Fed. Cir. 2016), TLI Communications LLC v. AV Auto. LLC, 823 F.3d 607, 610 (Fed. Cir. 2016), and OIP Techs., Inc., v. Amazon.com, Inc., 788 F.3d 1359, 1363 (Fed. Cir. 2015), indicate that mere collection or receipt of data over a network is a well‐understood, routine, and conventional function when it is claimed in a merely generic manner. Hence, the claims are not patent eligible.
Dependent claims 2-12 and 14-19 do not recite and further limitations that cause the claims to be patent eligible. The limitations of the dependent claims are directed towards additional aspects of the judicial exception that do not integrate the judicial exception into a practical application. The dependent claims further narrow the scope of independent claims 1, 13, and 20, however, the identified additional limitations and elements still do not impose any meaningful limits on practicing the identified abstract ideas. Therefore, dependent claims 2-12 and 14-19 are not patent eligible under the same rationale as provided for in the rejection of claims 1, 13, and 20. Therefore, claims 1-20 are ineligible under 35 USC §101.
Examiner notes that amending claims 1, 13, and 20 to necessarily include the feature of controlling the moving object to follow the optimal path would render the claimed invention eligible.
Examiner note to help applicant overcome the art on record
Applicant may overcome the art on record by amending independent claims 1, 13, and 20 to include the limitations from dependent claim 8 with the following further clarification included:
“… wherein the determining of the candidate node comprises
determining the candidate node based on the first distribution, if a random value is less than a second parameter;
determining the candidate node based on the second distribution, if the random value is greater than or equal to the second parameter and less than a predetermined value; and
determining the candidate node based on the area comprising the first distribution and the second distribution, if the random value is greater than or equal to the predetermined value”
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1-7, 13-18, and 20 are rejected under 35 U.S.C. 102(a)(2) as being anticipated by Chang et al. US 12649462 B1 (“Chang”).
For claim 1, Chang discloses a processor-implemented method (See at least Col. 28 line 60 through Col. 29 lines 1-18 of Chang – “… FIG. 7 is a block diagram of an example system 700 for implementing the techniques described herein… vehicle computing device 704 may include one or more processors 716 and memory 718 communicatively coupled with the processor(s) 716…”) comprising:
determining whether a moving object has reached a target node (See at least Col. 10 lines 12-46 – “… As the autonomous vehicle operates to reach the end state 120… the planning component 112 may use the map data and/or perception data, and apply trajectory optimization techniques to determine a trajectory 126 for the autonomous vehicle 102 to follow … The trajectory 126 may continuously and feasibly connect the start state 118 … with the intended end state 120 of the driving route…” and Col. 18 lines 5-9 of Chang – “… the cost evaluator 310 may implement an assumption that the autonomous vehicle 102 may continue performing the same candidate action throughout the driving route (e.g., until an end state or end time step is reached…”);
in response to the moving object not reaching the target node, determining a first optimal node and a first optimal edge through which the moving object passes to reach the target node from a current location of the moving object (See at least Col. 9 lines 24-31 – “… Prior to determining a subsequent trajectory for the vehicle to follow (e.g., at one or more future time steps), the autonomous vehicle 102 may receive and/or determine a route 116 including a start state 118 (e.g., the current state of the autonomous vehicle 102) and an end state 120…”, Col. 10 lines 12-46 – “… As the autonomous vehicle operates to reach the end state 120… the planning component 112 may use the map data and/or perception data, and apply trajectory optimization techniques to determine a trajectory 126 for the autonomous vehicle 102 to follow … The trajectory 126 may continuously and feasibly connect the start state 118 … with the intended end state 120 of the driving route…”, and Col. 18 lines 5-9 of Chang – “… the cost evaluator 310 may implement an assumption that the autonomous vehicle 102 may continue performing the same candidate action throughout the driving route (e.g., until an end state or end time step is reached…”);
inputting obstacle information around the moving object, the target node, the first optimal node, and the first optimal edge to an artificial intelligence (AI) model (See at least Col. 4 line 45 through Col. 5 lines 1-19 of Chang – “… the techniques described herein also may include using one or more additional candidate actions during the tree search based on the output of predictive models. As used herein, a machine-learned (ML) prediction-based candidate action may refer to an action and/or trajectory determined using adaptive learning… ML models and/or other prediction-based techniques may be used to predict the future trajectory and/or the future state of the vehicle, based on an initial vehicle state (e.g., vehicle position, pose, trajectory) and environment state data including map data and/or any perceived static or dynamic objects within the environment… may be trained to output a predicted future trajectory and/or vehicle state, based on input including representation of a driving environment at a particular time (e.g., map data and/or a road network)… proximate agent data for static objects and/or dynamic agents in the environment at the time, and encoded vehicle state data including the intended destination of the vehicle at the time…”);
determining a candidate node through which the moving object is likely to pass after reaching the first optimal node to reach the target node (See at least Col. 6 lines 3-15 of Chang – “… the planning component may iteratively, at each node in the search, determine a set of candidate actions (e.g., including … adaptive learning-based predicted candidate actions)… evaluate the associated candidate action nodes using one or more costs functions, and traverse the tree based on determining the one (or more) lowest-cost action nodes. The tree traversal may continue until the end state of a driving route is reached, at which time the planning component may identify one or more potential trajectories for controlling the vehicle, as the lowest-cost set(s) of nodes connecting the current vehicle state to the end state of the driving route…”), based on a confidence of an output of the Al model included in the output of the Al model (See at least Col. 20 lines 21-31 – “… the candidate action generator 304 may determine the numbers of heuristics-based candidate actions (and/or which specific heuristics-based candidate actions) to evaluate for a particular node and/or a particular tree search, based on the confidence level of the ML prediction-based candidate action(s)… if the active prediction model 306 determines, as a candidate action, a predicted trajectory for the autonomous vehicle 102 having a high degree of confidence, then the candidate action generator 304 may evaluate fewer heuristics-based candidate actions…” and Col. 37 line 64 through Col. 38 lines 1-4 of Chang – “… The method of paragraph F… determining a confidence level associated with the first candidate action received from the machine learned model; and determining, based at least in part on the confidence level, a number of additional candidate actions associated with the first node of the tree structure…”); and
determining an optimal path for the moving object to reach the target node based on one or more candidate nodes including the candidate node (See at least Col. 28 lines 32-54 of Chang – “… the planning component 112 may determine whether the next vehicle state node determined in operation 612 represents the end state of the driving route… may iteratively determine new nodes representing additional vehicle states, determine various candidate actions for the vehicle states, and evaluate the candidate actions using cost functions… may determine additional vehicle states based on the selected candidate actions, and continue the tree traversal … reaching the end state of the driving route… Upon reaching the end state of the driving route (614: Yes), at operation 616 the tree search component 302 may determine and output the corresponding trajectory for the autonomous vehicle 102, based on the sequence of selected nodes through the tree structure. In various examples, the trajectory output in operation 616 may include a lowest-cost and/or optimal trajectory within the amount of the search space of possible trajectories that was explored during the tree search, and/or based on the cost metrics/thresholds used by the tree search component 302 to select candidate actions/vehicle states…”).
For claim 2, Chang discloses wherein the Al model is configured to output a first distribution of the optimal path based on the first optimal node, the confidence of the first distribution (See at least Col. 20 lines 21-31 – “… the candidate action generator 304 may determine the numbers of heuristics-based candidate actions (and/or which specific heuristics-based candidate actions) to evaluate for a particular node and/or a particular tree search, based on the confidence level of the ML prediction-based candidate action(s)… if the active prediction model 306 determines, as a candidate action, a predicted trajectory for the autonomous vehicle 102 having a high degree of confidence, then the candidate action generator 304 may evaluate fewer heuristics-based candidate actions…” and Col. 37 line 64 through Col. 38 lines 1-4 of Chang – “… The method of paragraph F… determining a confidence level associated with the first candidate action received from the machine learned model; and determining, based at least in part on the confidence level, a number of additional candidate actions associated with the first node of the tree structure…”), and a second distribution of the optimal path based on a target tree generated from the target node, based on the obstacle information, the target node, the first optimal node, and the first optimal edge (See at least Col. 13 line 21 through Col. 14 lines 1-21 of Change – “… FIG. 2B illustrates a representation 200 of four different sets of candidate actions (e.g., trajectories in the depicted example) generated at four different nodes representing vehicle states at four different action layers of a tree search… FIG. 2B depicts the vehicle state 202, which may be a starting state in a driving root, corresponding to a root node in a tree search. The space occupied by the autonomous vehicle 102 at the vehicle state 202 is represented as a dashed line 214. FIG. 2B also represents two roadway edges, roadway edge 216 and roadway edge 218… The first set of candidate actions 220 may be determined by the planning component 112 based at least in part on the vehicle state 202… as well as the environment state data associated with the root node… The second set of candidate actions 224 may be generated based at least in part on selecting a first candidate action of the first set of candidate actions 220 for exploration, and based at least in part on the vehicle state 222 (e.g., position, pose, velocity, steering rate, etc.), that the selected first candidate action would cause the vehicle to perform upon concluding execution of the first candidate action within the current state of the environment. In some cases, the vehicle state 222 may represent a subsequent vehicle state …. based on performing an ML prediction-based candidate action. When evaluating the first set of candidate actions 220 and/or when selecting the vehicle state 222 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 222….The third set of candidate actions 228 may similarly be based at least in part on selection of a second candidate action from among the second set of candidate actions 224, based at least in part on the vehicle state 226 that the selected second candidate action would cause the vehicle to perform upon concluding execution of the second candidate action within the subsequent state of the environment associated with vehicle state 226 (e.g., the future predicted environment state, vehicle state, agent positions, etc., at the time of vehicle state 226). When evaluating the second set of candidate actions 224 and/or when selecting the vehicle state 226 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 226… When evaluating the third set of candidate actions 228 and/or when selecting the vehicle state 230 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 230, and so on…”).
For claim 3, Chang discloses wherein the determining of the first optimal node and the first optimal edge comprises, in response to the current location of the moving object being on an edge, until the moving object reaches a node connected to the edge, determining the node and the edge to be the first optimal node and the first optimal edge, respectively (See at least Col. 6 lines 3-15 of Chang – “… the planning component may iteratively, at each node in the search, determine a set of candidate actions (e.g., including … adaptive learning-based predicted candidate actions)… evaluate the associated candidate action nodes using one or more costs functions, and traverse the tree based on determining the one (or more) lowest-cost action nodes. The tree traversal may continue until the end state of a driving route is reached, at which time the planning component may identify one or more potential trajectories for controlling the vehicle, as the lowest-cost set(s) of nodes connecting the current vehicle state to the end state of the driving route…”).
For claim 4, Chang discloses wherein the determining of the first optimal node and the first optimal edge comprises, in response to the current location of the moving object being on a node, determining the first optimal node and the first optimal edge among one or more candidate nodes determined while the moving object moves from a previous node of the node to the node and one or more candidate edges corresponding to the one or more candidate nodes (See at least Col. 13 line 21 through Col. 14 lines 1-21 of Change – “… FIG. 2B illustrates a representation 200 of four different sets of candidate actions (e.g., trajectories in the depicted example) generated at four different nodes representing vehicle states at four different action layers of a tree search… FIG. 2B depicts the vehicle state 202, which may be a starting state in a driving root, corresponding to a root node in a tree search. The space occupied by the autonomous vehicle 102 at the vehicle state 202 is represented as a dashed line 214. FIG. 2B also represents two roadway edges, roadway edge 216 and roadway edge 218… The first set of candidate actions 220 may be determined by the planning component 112 based at least in part on the vehicle state 202… as well as the environment state data associated with the root node… The second set of candidate actions 224 may be generated based at least in part on selecting a first candidate action of the first set of candidate actions 220 for exploration, and based at least in part on the vehicle state 222 (e.g., position, pose, velocity, steering rate, etc.), that the selected first candidate action would cause the vehicle to perform upon concluding execution of the first candidate action within the current state of the environment. In some cases, the vehicle state 222 may represent a subsequent vehicle state …. based on performing an ML prediction-based candidate action. When evaluating the first set of candidate actions 220 and/or when selecting the vehicle state 222 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 222….The third set of candidate actions 228 may similarly be based at least in part on selection of a second candidate action from among the second set of candidate actions 224, based at least in part on the vehicle state 226 that the selected second candidate action would cause the vehicle to perform upon concluding execution of the second candidate action within the subsequent state of the environment associated with vehicle state 226 (e.g., the future predicted environment state, vehicle state, agent positions, etc., at the time of vehicle state 226). When evaluating the second set of candidate actions 224 and/or when selecting the vehicle state 226 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 226… When evaluating the third set of candidate actions 228 and/or when selecting the vehicle state 230 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 230, and so on…”).
For claim 5, Chang discloses further comprising determining the one or more candidate nodes by repeating the determining of the first optimal node and the first optimal edge, the inputting to the Al model, and the determining of the candidate node, until the moving object reaches the first optimal node (See at least Col. 27 line 44 through Col. 28 lines 1-59 of Chang – “…At operation 606, the planning component 112 may determine one or more ML prediction-based candidate actions that may be used to control the vehicle from the root node to one or more subsequent vehicle states in the environment… Upon reaching the end state of the driving route (614: Yes), at operation 616 the tree search component 302 may determine and output the corresponding trajectory for the autonomous vehicle 102… In contrast, when the end state of the driving route has not yet been reached (614: No), then process 600 may return to operation 606 to determine additional sets of candidate actions and/or additional selected vehicle state nodes within the remaining node layers of the search tree…”).
For claim 6, Chang discloses wherein the determining of the candidate node comprises determining the candidate node based on any one of the first distribution, the second distribution, and an area comprising the first distribution and the second distribution (See at least Col. 13 line 21 through Col. 14 lines 1-21 of Change – “… FIG. 2B illustrates a representation 200 of four different sets of candidate actions (e.g., trajectories in the depicted example) generated at four different nodes representing vehicle states at four different action layers of a tree search… FIG. 2B depicts the vehicle state 202, which may be a starting state in a driving root, corresponding to a root node in a tree search. The space occupied by the autonomous vehicle 102 at the vehicle state 202 is represented as a dashed line 214. FIG. 2B also represents two roadway edges, roadway edge 216 and roadway edge 218… The first set of candidate actions 220 may be determined by the planning component 112 based at least in part on the vehicle state 202… as well as the environment state data associated with the root node… The second set of candidate actions 224 may be generated based at least in part on selecting a first candidate action of the first set of candidate actions 220 for exploration, and based at least in part on the vehicle state 222 (e.g., position, pose, velocity, steering rate, etc.), that the selected first candidate action would cause the vehicle to perform upon concluding execution of the first candidate action within the current state of the environment. In some cases, the vehicle state 222 may represent a subsequent vehicle state …. based on performing an ML prediction-based candidate action. When evaluating the first set of candidate actions 220 and/or when selecting the vehicle state 222 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 222….The third set of candidate actions 228 may similarly be based at least in part on selection of a second candidate action from among the second set of candidate actions 224, based at least in part on the vehicle state 226 that the selected second candidate action would cause the vehicle to perform upon concluding execution of the second candidate action within the subsequent state of the environment associated with vehicle state 226 (e.g., the future predicted environment state, vehicle state, agent positions, etc., at the time of vehicle state 226). When evaluating the second set of candidate actions 224 and/or when selecting the vehicle state 226 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 226… When evaluating the third set of candidate actions 228 and/or when selecting the vehicle state 230 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 230, and so on…”).
For claim 7, Chang discloses wherein the candidate node is more likely to be determined from the first distribution, the higher the confidence is (See at least Col. 20 lines 21-31 – “… the candidate action generator 304 may determine the numbers of heuristics-based candidate actions (and/or which specific heuristics-based candidate actions) to evaluate for a particular node and/or a particular tree search, based on the confidence level of the ML prediction-based candidate action(s)… if the active prediction model 306 determines, as a candidate action, a predicted trajectory for the autonomous vehicle 102 having a high degree of confidence, then the candidate action generator 304 may evaluate fewer heuristics-based candidate actions…” and Col. 37 line 64 through Col. 38 lines 1-4 of Chang – “… The method of paragraph F… determining a confidence level associated with the first candidate action received from the machine learned model; and determining, based at least in part on the confidence level, a number of additional candidate actions associated with the first node of the tree structure…”).
For claim 13, Chang discloses an electronic device (See at least Col. 28 line 60 through Col. 29 lines 1-18 of Chang – “… FIG. 7 is a block diagram of an example system 700 for implementing the techniques described herein… vehicle computing device 704 may include one or more processors 716 and memory 718 communicatively coupled with the processor(s) 716…”), comprising:
memory storing instructions (See at least Col. 35 lines 46-50 of Chang – “… Memory 718 and memory 738 are examples of non-transitory computer-readable media. The memory 718 and memory 738 may store an operating system and one or more software applications, instructions, programs, and/or data to implement the methods described herein…”); and
at least one processor configured to execute the instructions (See at least Col. 35 lines 1-50 of Chang – “… The processor(s) 716 of the vehicle 702 and the processor(s) 736 of the computing device(s) 734 may be any suitable processor capable of executing instructions to process data and perform operations as described herein… The memory 718 and memory 738 may store an operating system and one or more software applications, instructions, programs, and/or data to implement the methods described herein…”),
wherein the instructions, when executed by the at least one processor individually or collectively, cause the electronic device to:
determine whether a moving object has reached a target node (See at least Col. 10 lines 12-46 – “… As the autonomous vehicle operates to reach the end state 120… the planning component 112 may use the map data and/or perception data, and apply trajectory optimization techniques to determine a trajectory 126 for the autonomous vehicle 102 to follow … The trajectory 126 may continuously and feasibly connect the start state 118 … with the intended end state 120 of the driving route…” and Col. 18 lines 5-9 of Chang – “… the cost evaluator 310 may implement an assumption that the autonomous vehicle 102 may continue performing the same candidate action throughout the driving route (e.g., until an end state or end time step is reached…”);
in response to the moving object not reaching the target node, determine a first optimal node and a first optimal edge through which the moving object passes to reach the target node from a current location of the moving object (See at least Col. 9 lines 24-31 – “… Prior to determining a subsequent trajectory for the vehicle to follow (e.g., at one or more future time steps), the autonomous vehicle 102 may receive and/or determine a route 116 including a start state 118 (e.g., the current state of the autonomous vehicle 102) and an end state 120…”, Col. 10 lines 12-46 – “… As the autonomous vehicle operates to reach the end state 120… the planning component 112 may use the map data and/or perception data, and apply trajectory optimization techniques to determine a trajectory 126 for the autonomous vehicle 102 to follow … The trajectory 126 may continuously and feasibly connect the start state 118 … with the intended end state 120 of the driving route…”, and Col. 18 lines 5-9 of Chang – “… the cost evaluator 310 may implement an assumption that the autonomous vehicle 102 may continue performing the same candidate action throughout the driving route (e.g., until an end state or end time step is reached…”);
input obstacle information around the moving object, the target node, the first optimal node, and the first optimal edge to an artificial intelligence (AI) model (See at least Col. 4 line 45 through Col. 5 lines 1-19 of Chang – “… the techniques described herein also may include using one or more additional candidate actions during the tree search based on the output of predictive models. As used herein, a machine-learned (ML) prediction-based candidate action may refer to an action and/or trajectory determined using adaptive learning… ML models and/or other prediction-based techniques may be used to predict the future trajectory and/or the future state of the vehicle, based on an initial vehicle state (e.g., vehicle position, pose, trajectory) and environment state data including map data and/or any perceived static or dynamic objects within the environment… may be trained to output a predicted future trajectory and/or vehicle state, based on input including representation of a driving environment at a particular time (e.g., map data and/or a road network)… proximate agent data for static objects and/or dynamic agents in the environment at the time, and encoded vehicle state data including the intended destination of the vehicle at the time…”);
determine a candidate node through which the moving object is likely to pass after reaching the first optimal node to reach the target node (See at least Col. 6 lines 3-15 of Chang – “… the planning component may iteratively, at each node in the search, determine a set of candidate actions (e.g., including … adaptive learning-based predicted candidate actions)… evaluate the associated candidate action nodes using one or more costs functions, and traverse the tree based on determining the one (or more) lowest-cost action nodes. The tree traversal may continue until the end state of a driving route is reached, at which time the planning component may identify one or more potential trajectories for controlling the vehicle, as the lowest-cost set(s) of nodes connecting the current vehicle state to the end state of the driving route…”) based on a confidence of an output of the Al model included in the output of the Al model (See at least Col. 20 lines 21-31 – “… the candidate action generator 304 may determine the numbers of heuristics-based candidate actions (and/or which specific heuristics-based candidate actions) to evaluate for a particular node and/or a particular tree search, based on the confidence level of the ML prediction-based candidate action(s)… if the active prediction model 306 determines, as a candidate action, a predicted trajectory for the autonomous vehicle 102 having a high degree of confidence, then the candidate action generator 304 may evaluate fewer heuristics-based candidate actions…” and Col. 37 line 64 through Col. 38 lines 1-4 of Chang – “… The method of paragraph F… determining a confidence level associated with the first candidate action received from the machine learned model; and determining, based at least in part on the confidence level, a number of additional candidate actions associated with the first node of the tree structure…”); and
determine an optimal path for the moving object to reach the target node based on one or more candidate nodes including the candidate node (See at least Col. 28 lines 32-54 of Chang – “… the planning component 112 may determine whether the next vehicle state node determined in operation 612 represents the end state of the driving route… may iteratively determine new nodes representing additional vehicle states, determine various candidate actions for the vehicle states, and evaluate the candidate actions using cost functions… may determine additional vehicle states based on the selected candidate actions, and continue the tree traversal … reaching the end state of the driving route… Upon reaching the end state of the driving route (614: Yes), at operation 616 the tree search component 302 may determine and output the corresponding trajectory for the autonomous vehicle 102, based on the sequence of selected nodes through the tree structure. In various examples, the trajectory output in operation 616 may include a lowest-cost and/or optimal trajectory within the amount of the search space of possible trajectories that was explored during the tree search, and/or based on the cost metrics/thresholds used by the tree search component 302 to select candidate actions/vehicle states…”).
For claim 14, Chang discloses wherein the Al model is configured to output a first distribution of the optimal path based on the first optimal node, the confidence of the first distribution (See at least Col. 20 lines 21-31 – “… the candidate action generator 304 may determine the numbers of heuristics-based candidate actions (and/or which specific heuristics-based candidate actions) to evaluate for a particular node and/or a particular tree search, based on the confidence level of the ML prediction-based candidate action(s)… if the active prediction model 306 determines, as a candidate action, a predicted trajectory for the autonomous vehicle 102 having a high degree of confidence, then the candidate action generator 304 may evaluate fewer heuristics-based candidate actions…” and Col. 37 line 64 through Col. 38 lines 1-4 of Chang – “… The method of paragraph F… determining a confidence level associated with the first candidate action received from the machine learned model; and determining, based at least in part on the confidence level, a number of additional candidate actions associated with the first node of the tree structure…”), and a second distribution of the optimal path based on a target tree generated from the target node, based on the obstacle information, the target node, the first optimal node, and the first optimal edge (See at least Col. 13 line 21 through Col. 14 lines 1-21 of Change – “… FIG. 2B illustrates a representation 200 of four different sets of candidate actions (e.g., trajectories in the depicted example) generated at four different nodes representing vehicle states at four different action layers of a tree search… FIG. 2B depicts the vehicle state 202, which may be a starting state in a driving root, corresponding to a root node in a tree search. The space occupied by the autonomous vehicle 102 at the vehicle state 202 is represented as a dashed line 214. FIG. 2B also represents two roadway edges, roadway edge 216 and roadway edge 218… The first set of candidate actions 220 may be determined by the planning component 112 based at least in part on the vehicle state 202… as well as the environment state data associated with the root node… The second set of candidate actions 224 may be generated based at least in part on selecting a first candidate action of the first set of candidate actions 220 for exploration, and based at least in part on the vehicle state 222 (e.g., position, pose, velocity, steering rate, etc.), that the selected first candidate action would cause the vehicle to perform upon concluding execution of the first candidate action within the current state of the environment. In some cases, the vehicle state 222 may represent a subsequent vehicle state …. based on performing an ML prediction-based candidate action. When evaluating the first set of candidate actions 220 and/or when selecting the vehicle state 222 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 222….The third set of candidate actions 228 may similarly be based at least in part on selection of a second candidate action from among the second set of candidate actions 224, based at least in part on the vehicle state 226 that the selected second candidate action would cause the vehicle to perform upon concluding execution of the second candidate action within the subsequent state of the environment associated with vehicle state 226 (e.g., the future predicted environment state, vehicle state, agent positions, etc., at the time of vehicle state 226). When evaluating the second set of candidate actions 224 and/or when selecting the vehicle state 226 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 226… When evaluating the third set of candidate actions 228 and/or when selecting the vehicle state 230 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 230, and so on…”).
For claim 15, Chang discloses wherein the instructions, when executed by the at least one processor individually or collectively, cause the electronic device to, in response to the current location of the moving object being on an edge, until the moving object reaches a node connected to the edge, determine the node and the edge to be the first optimal node and the first optimal edge, respectively (See at least Col. 6 lines 3-15 of Chang – “… the planning component may iteratively, at each node in the search, determine a set of candidate actions (e.g., including … adaptive learning-based predicted candidate actions)… evaluate the associated candidate action nodes using one or more costs functions, and traverse the tree based on determining the one (or more) lowest-cost action nodes. The tree traversal may continue until the end state of a driving route is reached, at which time the planning component may identify one or more potential trajectories for controlling the vehicle, as the lowest-cost set(s) of nodes connecting the current vehicle state to the end state of the driving route…”).
For claim 16, Chang discloses wherein the instructions, when executed by the at least one processor individually or collectively, cause the electronic device to, in response to the current location of the moving object being on a node, determine the first optimal node and the first optimal edge among one or more candidate nodes determined while the moving object moves from a previous node of the node to the node and one or more candidate edges corresponding to the one or more candidate nodes (See at least Col. 13 line 21 through Col. 14 lines 1-21 of Change – “… FIG. 2B illustrates a representation 200 of four different sets of candidate actions (e.g., trajectories in the depicted example) generated at four different nodes representing vehicle states at four different action layers of a tree search… FIG. 2B depicts the vehicle state 202, which may be a starting state in a driving root, corresponding to a root node in a tree search. The space occupied by the autonomous vehicle 102 at the vehicle state 202 is represented as a dashed line 214. FIG. 2B also represents two roadway edges, roadway edge 216 and roadway edge 218… The first set of candidate actions 220 may be determined by the planning component 112 based at least in part on the vehicle state 202… as well as the environment state data associated with the root node… The second set of candidate actions 224 may be generated based at least in part on selecting a first candidate action of the first set of candidate actions 220 for exploration, and based at least in part on the vehicle state 222 (e.g., position, pose, velocity, steering rate, etc.), that the selected first candidate action would cause the vehicle to perform upon concluding execution of the first candidate action within the current state of the environment. In some cases, the vehicle state 222 may represent a subsequent vehicle state …. based on performing an ML prediction-based candidate action. When evaluating the first set of candidate actions 220 and/or when selecting the vehicle state 222 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 222….The third set of candidate actions 228 may similarly be based at least in part on selection of a second candidate action from among the second set of candidate actions 224, based at least in part on the vehicle state 226 that the selected second candidate action would cause the vehicle to perform upon concluding execution of the second candidate action within the subsequent state of the environment associated with vehicle state 226 (e.g., the future predicted environment state, vehicle state, agent positions, etc., at the time of vehicle state 226). When evaluating the second set of candidate actions 224 and/or when selecting the vehicle state 226 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 226… When evaluating the third set of candidate actions 228 and/or when selecting the vehicle state 230 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 230, and so on…”).
For claim 17, Chang discloses wherein the instructions, when executed by the at least one processor individually or collectively, cause the electronic device to, determine the one or more candidate nodes by repeating the determining of the first optimal node and the first optimal edge, the inputting to the Al model, and the determining of the candidate node, until the moving object reaches the first optimal node (See at least Col. 27 line 44 through Col. 28 lines 1-59 of Chang – “…At operation 606, the planning component 112 may determine one or more ML prediction-based candidate actions that may be used to control the vehicle from the root node to one or more subsequent vehicle states in the environment… Upon reaching the end state of the driving route (614: Yes), at operation 616 the tree search component 302 may determine and output the corresponding trajectory for the autonomous vehicle 102… In contrast, when the end state of the driving route has not yet been reached (614: No), then process 600 may return to operation 606 to determine additional sets of candidate actions and/or additional selected vehicle state nodes within the remaining node layers of the search tree…”).
For claim 18, Chang discloses wherein the instructions, when executed by the at least one processor individually or collectively, cause the electronic device to, determine the candidate node based on any one of the first distribution, the second distribution, and an area comprising the first distribution and the second distribution (See at least Col. 13 line 21 through Col. 14 lines 1-21 of Change – “… FIG. 2B illustrates a representation 200 of four different sets of candidate actions (e.g., trajectories in the depicted example) generated at four different nodes representing vehicle states at four different action layers of a tree search… FIG. 2B depicts the vehicle state 202, which may be a starting state in a driving root, corresponding to a root node in a tree search. The space occupied by the autonomous vehicle 102 at the vehicle state 202 is represented as a dashed line 214. FIG. 2B also represents two roadway edges, roadway edge 216 and roadway edge 218… The first set of candidate actions 220 may be determined by the planning component 112 based at least in part on the vehicle state 202… as well as the environment state data associated with the root node… The second set of candidate actions 224 may be generated based at least in part on selecting a first candidate action of the first set of candidate actions 220 for exploration, and based at least in part on the vehicle state 222 (e.g., position, pose, velocity, steering rate, etc.), that the selected first candidate action would cause the vehicle to perform upon concluding execution of the first candidate action within the current state of the environment. In some cases, the vehicle state 222 may represent a subsequent vehicle state …. based on performing an ML prediction-based candidate action. When evaluating the first set of candidate actions 220 and/or when selecting the vehicle state 222 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 222….The third set of candidate actions 228 may similarly be based at least in part on selection of a second candidate action from among the second set of candidate actions 224, based at least in part on the vehicle state 226 that the selected second candidate action would cause the vehicle to perform upon concluding execution of the second candidate action within the subsequent state of the environment associated with vehicle state 226 (e.g., the future predicted environment state, vehicle state, agent positions, etc., at the time of vehicle state 226). When evaluating the second set of candidate actions 224 and/or when selecting the vehicle state 226 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 226… When evaluating the third set of candidate actions 228 and/or when selecting the vehicle state 230 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 230, and so on…”).
For claim 20, Chang discloses a processor-implemented method (See at least Col. 28 line 60 through Col. 29 lines 1-18 of Chang – “… FIG. 7 is a block diagram of an example system 700 for implementing the techniques described herein… vehicle computing device 704 may include one or more processors 716 and memory 718 communicatively coupled with the processor(s) 716…”) comprising:
inputting, to an artificial intelligence (AI) model, obstacle information around a moving object, a target node, a first optimal node, and a first optimal edge through which the moving object passes to reach the target node from a current location of the moving object (See at least Col. 4 line 45 through Col. 5 lines 1-19 of Chang – “… the techniques described herein also may include using one or more additional candidate actions during the tree search based on the output of predictive models. As used herein, a machine-learned (ML) prediction-based candidate action may refer to an action and/or trajectory determined using adaptive learning… ML models and/or other prediction-based techniques may be used to predict the future trajectory and/or the future state of the vehicle, based on an initial vehicle state (e.g., vehicle position, pose, trajectory) and environment state data including map data and/or any perceived static or dynamic objects within the environment… may be trained to output a predicted future trajectory and/or vehicle state, based on input including representation of a driving environment at a particular time (e.g., map data and/or a road network)… proximate agent data for static objects and/or dynamic agents in the environment at the time, and encoded vehicle state data including the intended destination of the vehicle at the time…”);
determining, based on a confidence included in an output of the Al model (See at least Col. 20 lines 21-31 – “… the candidate action generator 304 may determine the numbers of heuristics-based candidate actions (and/or which specific heuristics-based candidate actions) to evaluate for a particular node and/or a particular tree search, based on the confidence level of the ML prediction-based candidate action(s)… if the active prediction model 306 determines, as a candidate action, a predicted trajectory for the autonomous vehicle 102 having a high degree of confidence, then the candidate action generator 304 may evaluate fewer heuristics-based candidate actions…” and Col. 37 line 64 through Col. 38 lines 1-4 of Chang – “… The method of paragraph F… determining a confidence level associated with the first candidate action received from the machine learned model; and determining, based at least in part on the confidence level, a number of additional candidate actions associated with the first node of the tree structure…”), a candidate node through which the moving object is likely to pass after reaching the first optimal node to reach the target node (See at least Col. 6 lines 3-15 of Chang – “… the planning component may iteratively, at each node in the search, determine a set of candidate actions (e.g., including … adaptive learning-based predicted candidate actions)… evaluate the associated candidate action nodes using one or more costs functions, and traverse the tree based on determining the one (or more) lowest-cost action nodes. The tree traversal may continue until the end state of a driving route is reached, at which time the planning component may identify one or more potential trajectories for controlling the vehicle, as the lowest-cost set(s) of nodes connecting the current vehicle state to the end state of the driving route…”), based on a selected one of a first distribution of the optimal path determined based on the first optimal node, a second distribution of the optimal path determined based on a target tree generated from the target node, and an area comprising the first distribution and the second distribution (See at least Col. 13 line 21 through Col. 14 lines 1-21 of Change – “… FIG. 2B illustrates a representation 200 of four different sets of candidate actions (e.g., trajectories in the depicted example) generated at four different nodes representing vehicle states at four different action layers of a tree search… FIG. 2B depicts the vehicle state 202, which may be a starting state in a driving root, corresponding to a root node in a tree search. The space occupied by the autonomous vehicle 102 at the vehicle state 202 is represented as a dashed line 214. FIG. 2B also represents two roadway edges, roadway edge 216 and roadway edge 218… The first set of candidate actions 220 may be determined by the planning component 112 based at least in part on the vehicle state 202… as well as the environment state data associated with the root node… The second set of candidate actions 224 may be generated based at least in part on selecting a first candidate action of the first set of candidate actions 220 for exploration, and based at least in part on the vehicle state 222 (e.g., position, pose, velocity, steering rate, etc.), that the selected first candidate action would cause the vehicle to perform upon concluding execution of the first candidate action within the current state of the environment. In some cases, the vehicle state 222 may represent a subsequent vehicle state …. based on performing an ML prediction-based candidate action. When evaluating the first set of candidate actions 220 and/or when selecting the vehicle state 222 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 222….The third set of candidate actions 228 may similarly be based at least in part on selection of a second candidate action from among the second set of candidate actions 224, based at least in part on the vehicle state 226 that the selected second candidate action would cause the vehicle to perform upon concluding execution of the second candidate action within the subsequent state of the environment associated with vehicle state 226 (e.g., the future predicted environment state, vehicle state, agent positions, etc., at the time of vehicle state 226). When evaluating the second set of candidate actions 224 and/or when selecting the vehicle state 226 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 226… When evaluating the third set of candidate actions 228 and/or when selecting the vehicle state 230 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 230, and so on…”); and
determining an optimal path for the moving object to reach the target node based on one or more candidate nodes including the candidate node (See at least Col. 28 lines 32-54 of Chang – “… the planning component 112 may determine whether the next vehicle state node determined in operation 612 represents the end state of the driving route… may iteratively determine new nodes representing additional vehicle states, determine various candidate actions for the vehicle states, and evaluate the candidate actions using cost functions… may determine additional vehicle states based on the selected candidate actions, and continue the tree traversal … reaching the end state of the driving route… Upon reaching the end state of the driving route (614: Yes), at operation 616 the tree search component 302 may determine and output the corresponding trajectory for the autonomous vehicle 102, based on the sequence of selected nodes through the tree structure. In various examples, the trajectory output in operation 616 may include a lowest-cost and/or optimal trajectory within the amount of the search space of possible trajectories that was explored during the tree search, and/or based on the cost metrics/thresholds used by the tree search component 302 to select candidate actions/vehicle states…”).
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.
Claim 8 is rejected under 35 U.S.C. 103 as being unpatentable over Chang in view of Tao “Efficient path planning for autonomous vehicles based on RRT* with variable probability strategy and artificial potential field approach”, October 21, 2024 (“Tao”).
For claim 8, Chang fails to specifically disclose wherein the determining of the candidate node comprises any one of:
determining the candidate node based on the first distribution, in response to a random value being less than a second parameter;
determining the candidate node based on the second distribution, in response to the random value being greater than or equal to the second parameter and less than a predetermined value; and
determining the candidate node based on the area comprising the first distribution and the second distribution, in response to the random value being greater than or equal to the predetermined value.
However, Tao, in the same field of endeavor teaches wherein the determining of the candidate node comprises any one of:
determining the candidate node based on the first distribution, in response to a random value being less than a second parameter (See at least page 7 of Tao – “… where rand() represents a random value ranging from 0 to 1, and P is the set goal probability threshold, which is used to determine the probability of selecting the target point during the sampling process. If the generated random number is less than the probability threshold, the target point is directly taken as the sampling point. Otherwise, according to the normal uniform distribution, a random point is generated in the search space as the sampling point. The goal biasing strategy is an improved method that makes the algorithm more inclined to expand the tree toward the target region. However, in Goal-bias RRT*, the probability P of selecting the target point as the sampling point is fixed. When the random tree gets trapped in a local minimum, using the target point as the sampling point is generally ineffective, which can waste a significant amount of computational resources…”);
determining the candidate node based on the second distribution, in response to the random value being greater than or equal to the second parameter and less than a predetermined value; and
determining the candidate node based on the area comprising the first distribution and the second distribution, in response to the random value being greater than or equal to the predetermined value. Thus, Chang discloses a path planning system for an autonomous vehicle that uses an artificial intelligence model to determine nodes and low-cost paths for a vehicle to move from a current position to a target position while considering other dynamic objects in the driving environment and the confidence levels of the outputs of artificial intelligence model, while Tao teaches a path planning system for autonomous vehicle that features determining a target point as a sampling point based on a random value being less than probability threshold.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify the method and electronic device as disclosed in Chang to include the feature of determining the candidate node based on the first distribution, in response to a random value being less than a second parameter as taught by Tao, with a reasonable expectation of success, in order to determine a target point as a sampling point or generate a random point in the search space as the sampling point as specified in at least page 7 of Tao.
Claims 10, 12, and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Chang in view of Di Cairano et al. US 20160375901 A1 (“Di Cairano”).
For claim 10, Chang discloses wherein the determining of the optimal path comprises:
in response to the moving object reaching the first optimal node, determining a second optimal node among the one or more candidate nodes (See at least Col. 13 line 21 through Col. 14 lines 1-21 of Change – “… FIG. 2B illustrates a representation 200 of four different sets of candidate actions (e.g., trajectories in the depicted example) generated at four different nodes representing vehicle states at four different action layers of a tree search… FIG. 2B depicts the vehicle state 202, which may be a starting state in a driving root, corresponding to a root node in a tree search. The space occupied by the autonomous vehicle 102 at the vehicle state 202 is represented as a dashed line 214. FIG. 2B also represents two roadway edges, roadway edge 216 and roadway edge 218… The first set of candidate actions 220 may be determined by the planning component 112 based at least in part on the vehicle state 202… as well as the environment state data associated with the root node… The second set of candidate actions 224 may be generated based at least in part on selecting a first candidate action of the first set of candidate actions 220 for exploration, and based at least in part on the vehicle state 222 (e.g., position, pose, velocity, steering rate, etc.), that the selected first candidate action would cause the vehicle to perform upon concluding execution of the first candidate action within the current state of the environment. In some cases, the vehicle state 222 may represent a subsequent vehicle state …. based on performing an ML prediction-based candidate action. When evaluating the first set of candidate actions 220 and/or when selecting the vehicle state 222 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 222….The third set of candidate actions 228 may similarly be based at least in part on selection of a second candidate action from among the second set of candidate actions 224, based at least in part on the vehicle state 226 that the selected second candidate action would cause the vehicle to perform upon concluding execution of the second candidate action within the subsequent state of the environment associated with vehicle state 226 (e.g., the future predicted environment state, vehicle state, agent positions, etc., at the time of vehicle state 226). When evaluating the second set of candidate actions 224 and/or when selecting the vehicle state 226 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 226… When evaluating the third set of candidate actions 228 and/or when selecting the vehicle state 230 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 230, and so on…”); and
determining the optimal path based on the second optimal node and the second optimal edge (See at least Col. 28 lines 32-54 of Chang – “… the planning component 112 may determine whether the next vehicle state node determined in operation 612 represents the end state of the driving route… may iteratively determine new nodes representing additional vehicle states, determine various candidate actions for the vehicle states, and evaluate the candidate actions using cost functions… may determine additional vehicle states based on the selected candidate actions, and continue the tree traversal … reaching the end state of the driving route… Upon reaching the end state of the driving route (614: Yes), at operation 616 the tree search component 302 may determine and output the corresponding trajectory for the autonomous vehicle 102, based on the sequence of selected nodes through the tree structure. In various examples, the trajectory output in operation 616 may include a lowest-cost and/or optimal trajectory within the amount of the search space of possible trajectories that was explored during the tree search, and/or based on the cost metrics/thresholds used by the tree search component 302 to select candidate actions/vehicle states…”).
Chang fails to specifically disclose removing candidate nodes other than the second optimal node from among the one or more candidate nodes, and removing candidate edges other than a second optimal edge corresponding to the second optimal node from among one or more candidate edges corresponding to the one or more candidate nodes.
However, Di Cairano, in the same field of endeavor teaches removing candidate nodes other than the second optimal node from among the one or more candidate nodes, and removing candidate edges other than a second optimal edge corresponding to the second optimal node from among one or more candidate edges corresponding to the one or more candidate nodes (See at least [0056] of Di Cairano – “… If the new node is added to the tree, then the nodes 425, 426 near the new node are evaluated to check if those nodes can be reached with paths with lowest cost by passing through the new node. To that end, the embodiment determines the cost to reach the new node and add the cost of reaching any near node from the new node. If such cost is smaller than that currently associated with the node, a link is added from the new node to the node, and the older link reaching the new node is removed…”). Thus, Chang discloses a path planning system for an autonomous vehicle that uses an artificial intelligence model to determine nodes and low-cost paths for a vehicle to move from a current position to a target position while considering other dynamic objects in the driving environment and the confidence levels of the outputs of artificial intelligence model, while Di Cairano teaches a path planning system for an autonomous vehicle that adds new nodes and links to a tree based on cost and deletes older links.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify the method and electronic device as disclosed in Chang to include the feature of removing candidate nodes other than the second optimal node from among the one or more candidate nodes as taught by Di Cairano, with a reasonable expectation of success, in order to remove older links as specified in at least [0056] of Di Cairano.
For claim 12, Chang discloses wherein the determining of the second optimal node comprises, in response to there being a candidate node connected to the target tree generated from the target node among the one or more candidate nodes, determining the candidate node connected to the target tree to be the second optimal node (See at least Col. 13 line 21 through Col. 14 lines 1-21 of Change – “… FIG. 2B illustrates a representation 200 of four different sets of candidate actions (e.g., trajectories in the depicted example) generated at four different nodes representing vehicle states at four different action layers of a tree search… FIG. 2B depicts the vehicle state 202, which may be a starting state in a driving root, corresponding to a root node in a tree search. The space occupied by the autonomous vehicle 102 at the vehicle state 202 is represented as a dashed line 214. FIG. 2B also represents two roadway edges, roadway edge 216 and roadway edge 218… The first set of candidate actions 220 may be determined by the planning component 112 based at least in part on the vehicle state 202… as well as the environment state data associated with the root node… The second set of candidate actions 224 may be generated based at least in part on selecting a first candidate action of the first set of candidate actions 220 for exploration, and based at least in part on the vehicle state 222 (e.g., position, pose, velocity, steering rate, etc.), that the selected first candidate action would cause the vehicle to perform upon concluding execution of the first candidate action within the current state of the environment. In some cases, the vehicle state 222 may represent a subsequent vehicle state …. based on performing an ML prediction-based candidate action. When evaluating the first set of candidate actions 220 and/or when selecting the vehicle state 222 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 222….The third set of candidate actions 228 may similarly be based at least in part on selection of a second candidate action from among the second set of candidate actions 224, based at least in part on the vehicle state 226 that the selected second candidate action would cause the vehicle to perform upon concluding execution of the second candidate action within the subsequent state of the environment associated with vehicle state 226 (e.g., the future predicted environment state, vehicle state, agent positions, etc., at the time of vehicle state 226). When evaluating the second set of candidate actions 224 and/or when selecting the vehicle state 226 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 226… When evaluating the third set of candidate actions 228 and/or when selecting the vehicle state 230 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 230, and so on…”).
For claim 19, Chang discloses wherein the instructions, when executed by the at least one processor individually or collectively, cause the electronic device to,
in response to the moving object reaching the first optimal node, determine a second optimal node among the one or more candidate nodes (See at least Col. 13 line 21 through Col. 14 lines 1-21 of Change – “… FIG. 2B illustrates a representation 200 of four different sets of candidate actions (e.g., trajectories in the depicted example) generated at four different nodes representing vehicle states at four different action layers of a tree search… FIG. 2B depicts the vehicle state 202, which may be a starting state in a driving root, corresponding to a root node in a tree search. The space occupied by the autonomous vehicle 102 at the vehicle state 202 is represented as a dashed line 214. FIG. 2B also represents two roadway edges, roadway edge 216 and roadway edge 218… The first set of candidate actions 220 may be determined by the planning component 112 based at least in part on the vehicle state 202… as well as the environment state data associated with the root node… The second set of candidate actions 224 may be generated based at least in part on selecting a first candidate action of the first set of candidate actions 220 for exploration, and based at least in part on the vehicle state 222 (e.g., position, pose, velocity, steering rate, etc.), that the selected first candidate action would cause the vehicle to perform upon concluding execution of the first candidate action within the current state of the environment. In some cases, the vehicle state 222 may represent a subsequent vehicle state …. based on performing an ML prediction-based candidate action. When evaluating the first set of candidate actions 220 and/or when selecting the vehicle state 222 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 222….The third set of candidate actions 228 may similarly be based at least in part on selection of a second candidate action from among the second set of candidate actions 224, based at least in part on the vehicle state 226 that the selected second candidate action would cause the vehicle to perform upon concluding execution of the second candidate action within the subsequent state of the environment associated with vehicle state 226 (e.g., the future predicted environment state, vehicle state, agent positions, etc., at the time of vehicle state 226). When evaluating the second set of candidate actions 224 and/or when selecting the vehicle state 226 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 226… When evaluating the third set of candidate actions 228 and/or when selecting the vehicle state 230 for further exploration in the tree search, the planning component 112 may generate a search tree node representing the selected vehicle state 230, and so on…”), and
determine the optimal path based on the second optimal node and the second optimal edge (See at least Col. 28 lines 32-54 of Chang – “… the planning component 112 may determine whether the next vehicle state node determined in operation 612 represents the end state of the driving route… may iteratively determine new nodes representing additional vehicle states, determine various candidate actions for the vehicle states, and evaluate the candidate actions using cost functions… may determine additional vehicle states based on the selected candidate actions, and continue the tree traversal … reaching the end state of the driving route… Upon reaching the end state of the driving route (614: Yes), at operation 616 the tree search component 302 may determine and output the corresponding trajectory for the autonomous vehicle 102, based on the sequence of selected nodes through the tree structure. In various examples, the trajectory output in operation 616 may include a lowest-cost and/or optimal trajectory within the amount of the search space of possible trajectories that was explored during the tree search, and/or based on the cost metrics/thresholds used by the tree search component 302 to select candidate actions/vehicle states…”).
Chang fails to specifically disclose remove candidate nodes other than the second optimal node from among the one or more candidate nodes, and remove candidate edges other than a second optimal edge corresponding to the second optimal node from among one or more candidate edges corresponding to the one or more candidate nodes.
However, Di Cairano, in the same field of endeavor teaches remove candidate nodes other than the second optimal node from among the one or more candidate nodes, and remove candidate edges other than a second optimal edge corresponding to the second optimal node from among one or more candidate edges corresponding to the one or more candidate nodes (See at least [0056] of Di Cairano – “… If the new node is added to the tree, then the nodes 425, 426 near the new node are evaluated to check if those nodes can be reached with paths with lowest cost by passing through the new node. To that end, the embodiment determines the cost to reach the new node and add the cost of reaching any near node from the new node. If such cost is smaller than that currently associated with the node, a link is added from the new node to the node, and the older link reaching the new node is removed…”). Thus, Chang discloses a path planning system for an autonomous vehicle that uses an artificial intelligence model to determine nodes and low-cost paths for a vehicle to move from a current position to a target position while considering other dynamic objects in the driving environment and the confidence levels of the outputs of artificial intelligence model, while Di Cairano teaches a path planning system for an autonomous vehicle that adds new nodes and links to a tree based on cost and deletes older links.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify the method and electronic device as disclosed in Chang to include the feature of removing candidate nodes other than the second optimal node from among the one or more candidate nodes as taught by Di Cairano, with a reasonable expectation of success, in order to remove older links as specified in at least [0056] of Di Cairano.
Claim 11 is rejected under 35 U.S.C. 103 as being unpatentable over Chang in view of Di Cairano, as applied to claim 10 above, and further in view of Huang et al. US 20230266131 A1 (“Huang”).
For claim 11, Chang fails to specifically disclose wherein the determining of the second optimal node comprises, in response to there being no candidate node connected to the target tree generated from the target node among one or more candidate nodes, determining a candidate node configured to be connected to the target node by the shortest distance among the one or more candidate nodes to be the second optimal node and the second optimal edge.
However, Huang, in the same field of endeavor teaches wherein the determining of the second optimal node comprises, in response to there being no candidate node connected to the target tree generated from the target node among one or more candidate nodes, determining a candidate node configured to be connected to the target node by the shortest distance among the one or more candidate nodes to be the second optimal node and the second optimal edge (See at least [0115] of Huang – “… At block 1025, a parent candidate is determined by finding a node in a spanning tree with the smallest haversine distance to the nearest node. The route planning system determines whether there exists shorter paths in nearby nodes, at block 1030. If a shorter path exists, at block 1030, then the route planning system rewires the paths at block 1035 and then continues to determine whether the inserted node has already been expanded by a tree of another objective…”). Thus, Chang discloses a path planning system for an autonomous vehicle that uses an artificial intelligence model to determine nodes and low-cost paths for a vehicle to move from a current position to a target position while considering other dynamic objects in the driving environment and the confidence levels of the outputs of artificial intelligence model, while Huang teaches a path planning system for a vehicle that determines shortest path to nodes for spanning a tree.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to modify the method and electronic device as disclosed in Chang to include the feature of in response to there being no candidate node connected to the target tree generated from the target node among one or more candidate nodes, determining a candidate node configured to be connected to the target node by the shortest distance among the one or more candidate nodes to be the second optimal node and the second optimal edge as taught by Huang, with a reasonable expectation of success, in order to rewires the paths when a shortest path exists as specified in at least [0115] of Huang.
Allowable Subject Matter
Claim 9 is objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
The following is an Examiner’s statement of reasons for allowance:
The closest prior art of record is Chang et al. US 12649462 B1 (“Chang”), Tao “Efficient path planning for autonomous vehicles based on RRT* with variable probability strategy and artificial potential field approach”, October 21, 2024 (“Tao”), Di Cairano et al. US 20160375901 A1 (“Di Cairano”), and Huang et al. US 20230266131 A1 (“Huang”).
Chang discloses a path planning system for an autonomous vehicle that uses an artificial intelligence model to determine nodes and low-cost paths for a vehicle to move from a current position to a target position while considering other dynamic objects in the driving environment and the confidence levels of the outputs of artificial intelligence model.
Tao teaches a path planning system for autonomous vehicle that features determining a target point as a sampling point based on a random value being less than probability threshold, however, the reference is silent on wherein the second parameter corresponds to a probability of determining the candidate node from the second distribution, and the predetermined value is determined based on the confidence of the output of the Al model, the second parameter, and a first parameter corresponding to a probability of determining the candidate node from the first distribution with a maximum usage ratio.
Di Cairano teaches a path planning system for an autonomous vehicle that adds new nodes and links to a tree based on cost and deletes older links.
Huang teaches a path planning system for a vehicle that determines shortest path to nodes for spanning a tree.
As to claim 9, the prior art of record, taken individually or in combination, fails to teach or suggest the following claimed subject matter:
“wherein
the second parameter corresponds to a probability of determining the candidate node from the second distribution, and
the predetermined value is determined based on the confidence of the output of the Al model, the second parameter, and a first parameter corresponding to a probability of determining the candidate node from the first distribution with a maximum usage ratio”
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MICHAEL J HERRERA whose telephone number is (571)270-5271. The examiner can normally be reached M-F 10:00 AM to 6:00 PM EST.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, FADEY JABR can be reached at (571)272-1516. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/M.J.H./Examiner, Art Unit 3668
/Fadey S. Jabr/Supervisory Patent Examiner, Art Unit 3668
Prosecution Insights