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 .
This action is responsive to the Amendment filed on May 27, 2025. Claims 4-6 and 10 are cancelled. Claims 1, 11, and 12 are amended. Claims 1-3, 7-9, 11, and 12 are pending in the case. Claims 1, 11, and 12 are the independent claims.
This action is final.
Applicant’s Response
In the Amendment filed on May 27, 2025, Applicant amended the claims and provided arguments in response to the rejections of the claims under 35 USC 103 in the previous office action.
Response to Argument/Amendment
Applicant’s amendments to the claims in response to the rejection under 35 USC 103 are acknowledged, and Applicant’s corresponding arguments have been fully considered. Applicant argues that the independent claims have been amended to recite “wherein the policy selects the heuristic with an expected lowest planning time that expands exponentially so that the selected heuristic is sufficient to expand a search space to find the path to the goal state,” and that Ramamoorthy, Maturana, and the other cited references do not teach this limitation. Applicant’s argument is persuasive, and the rejection is withdrawn.
New grounds of rejection are provided below.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitations are “system for planning an operation of a technical system…the system configured to…obtain…determine…select…choose…and determine…” in claim 12.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Examiner notes that the system of claim 12 is not recited as a single means claim because it recites multiple functional limitations, where each of these is interpreted as a separate element (i.e. a system configured to “obtain state information…,” a system configured to “determine…costs…,” a system configured to “select a heuristic…,” a system configured to “choose a state…,” and a system configured to “determine an operation…,” as recited in claim 12). See MPEP 2181.
Claim Rejections – 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries set forth in Graham v. John Deere Co., 383 U.S. 1, 148 USPQ 459 (1966), that are applied 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 under pre-AIA 35 U.S.C. 103(a), the examiner presumes that the subject matter of the various claims was commonly owned at the time any inventions covered therein were made absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and invention dates of each claim that was not commonly owned at the time a later invention was made in order for the examiner to consider the applicability of pre-AIA 35 U.S.C. 103(c) and potential pre-AIA 35 U.S.C. 102€, (f) or (g) prior art under pre-AIA 35 U.S.C. 103(a).
Claims 1, 7, and 11-12 are rejected under 35 U.S.C. 103 as being unpatentable over Ramamoorthy et al. (US 20210370980 A1) in view of Keselman et al. (US 20200097015 A1), further in view of Bnayahu et al. (US 20170075859 A1), further in view of Maturana (US 20100017352 A1), further in view of Qiu et al. (US 20210048823 A1).
With respect to claims 1, 11, and 12, Ramamoorthy teaches a non-transitory machine-readable storage medium on which is stored a computer program for performing a computer-implemented method; a system for performing the computer-implemented method (e.g. paragraph 0089, electronic storage of autonomous vehicle, comprising autonomous vehicle planner configured to implement method using trained behavior model; paragraph 0098-0099, hardware configured to execute method steps disclosed, computer program comprising instructions to implement method; AV planner embodied in computer system configured to implement method steps); and the computer-implemented method, for planning an operation of a technical system within an environment of the technical system (e.g. abstract autonomous vehicle planning method determining a sequence of manoeuvres of the AV for an encountered driving scenario; paragraph 0011, parameters of driving scenario including road layout and other driving environment parameters), the environment being characterized by a current domain out of a set of different respective domains, a current state out of a set of states of the respective domains, and a set of possible operations which can be carried out by the technical system within each domain, wherein the domains characterize a structure, a classification and/or conditions of the environment of the technical system (e.g. paragraph 0011, parameters of driving scenario including road layout and other driving environment parameters; paragraph 0121, data processing system A2 processing sensor data to extract information, and performing functions of localization, object detection, object tracking; paragraph 0122, localization providing awareness of surrounding environment and AV’s location within it; paragraph 0123, object detection to detect and localize external objects within the environment; paragraph 0124, object tracking used to track movement of objects within the environment; paragraph 0127, combination of localization, object detection, and object tracking providing comprehensive representation of environment, current state of external actors within that environment, etc., and is continuously updated in real-time to provide up to date location and environment awareness; paragraph 0130, determining encountered driving scenario using outputs of data processing component A2, comprising parameters extracted from sensor data which provide representation of real-world scenario encountered by AV; paragraph 0137, actual driving scenario, different possible outcomes of different manoeuvres in the encountered driving scenario; paragraph 0141, current state of encountered driving scenario, capturing actual current state of vehicle and current state of any external agents within the encountered driving scenario, relative to surroundings and road layout/structure; paragraph 0144, possible manoeuvres hypothesized given current state; see also paragraphs 0415-0426, describing a plurality of example scenarios/domains; i.e. the vehicle’s current environment includes information indicating a current encountered scenario, analogous to a current domain, a current state within that scenario, including states of the vehicle/system, external objects, and surroundings, and a set of possible operations/maneuvers which may be performed by the vehicle/system, analogous to a structure, classification, and/or environment of the AV), the method comprising the following steps:
i) obtaining state information including at least the current domain, a time step, and the current state of the environment (e.g. paragraphs 0121-0124, 0127, 0130, 0141, and 0144, as cited above, sensor information is processed in order to obtain a current scenario/domain at a given time, such as time=0 as discussed in paragraph 0141, as well as state information of the environment including states of external objects and surroundings including road layout/structure);
ii) determining, by each heuristic out of a set of predefined heuristics, costs for a plurality of reachable states from the current state, wherein the heuristics are configured to estimate costs to reach a goal state from a given state (e.g. paragraph 0133, manoeuvre planning achieved using Monte Carlo Tree Search, which is a heuristic search algorithm for decision processes; paragraph 0137, systematically reasoning about different possible outcomes of different manoeuvres in the encountered driving scenario, taking into account predicted behavior of external agents; paragraph 0142, nodes representing anticipated states under different assumptions about vehicle behavior at different times; paragraph 0161, only possible/achievable manoeuvres hypothesized; paragraph 0286, manoeuvres implemented using hard-coded heuristics; paragraph 0305, within basic maneuvers that generate curved trajectories, target velocities set sign heuristic based on local curvature; paragraphs 0328-0329, plan means sequence of manoeuvres selected to reach a goal; inferring a goal from finite set of available goals based on cost penalties; paragraph 0325, heuristic goal generation function used to enumerate set of possible goals for car in given view region; paragraph 0335, likelihood for given goal defined as different between respective costs of two plans including optimal plan from initial location to goal location, and best available plan defined as optimal plan to goal location given observed behavior; paragraph 0339, cost taking into account factors including driving time, safety, and comfort; paragraph 0353, finding optimal plan for reaching specified goal from given location; nodes of graph represent maneuvers and aim is to find sequence of nodes/maneuvers which reach the goal at relatively low cost; for each node, a heuristic function provides an estimate of the cost from the node to the goal; paragraph 0358, cost heuristic to estimate remaining cost to goal; paragraph 0384, predicting possible trajectories using inverse planning, computing set of plans with associated costs, such as up to a fixed number of plans; paragraph 0388, predicting various plausible trajectories rather than a single optimal trajectory; paragraph 0397, planning done over set of maneuvers applicable in current state; paragraph 0399, MCTS using cost function, propagating resulting cost up search tree; paragraphs 0405-0411, describing cost function; paragraph 0414, alternatively associating costs with maneuvers; i.e. a plurality of predefined heuristics, forming a set, are utilized to determine/evaluate costs from the present state/node to goal states/nodes);
wherein, for each heuristic a list is used and a most promising state with a lowest cost of the corresponding list of the selected heuristic by the policy is expanded (e.g. paragraph 0134, using game tree data structure comprising possible outcomes, such as sequences of moves/paths through the tree, that are optimal with respect to defined reward function; paragraph 0135, game tree constructed dynamically as different paths are explored; paragraph 0140, example game tree shown in Fig. 2; paragraph 0158, each considered terminating node is assigned a score based on reward function that indicates desirability of the outcome it represents; successful outcomes scored more highly if they are reached in a shorter amount of time; paragraph 0159, each considered path assigned score/reward function, indicating desirability, such as scoring more highly if outcome reached in shorter amount of time; paragraph 0185, selecting expanded path determined to be most promising; paragraph 0186, most promising path may be the path having maximum score; paragraph 0198, selecting most promising maneuver sequence; paragraph 0339, cost taking into account factors including driving time, safety, and comfort; i.e. where a partially/dynamically constructed tree containing different paths to achieve an outcome is analogous to a list used for each heuristic, and where a most promising path (corresponding to a most promising state) having a highest reward/lowest cost (i.e. where both of these are based on the same criteria, such as reaching the goal/outcome in a shorter amount time) may be an expanded path, analogous to a most promising state with a lowest cost which is expanded);
iii) selecting a heuristic out of the set of predefined heuristics by a policy depending on the state information, such that a minimal number of state expansions is expected when planning a path to the goal state (e.g. paragraph 0011, applying generative behavior model to vehicle parameters and driving scenario parameters; paragraph 0012, generative behavior model is ML model which has been trained; paragraph 0022, generative behavior model comprising trained neural network; paragraph 0133, planning manoeuvres to perform to execute defined goal using MCTS, which is a heuristic search algorithm; paragraph 0134, MCTS applied to game tree with objective of determining sequence of moves that is optimal with respect to defined reward; paragraph 0137, MCTS applied as means of reasoning systematically about different possible outcomes of different manoeuvres in the encountered driving scenario; paragraph 0149, performance of manoeuvre by vehicle simulated using action policy learned for performing the manoeuvre given a particular state; paragraph 0157, game tree is finite tree in that every possible path terminates at a terminating node after a finite number of moves; paragraph 0158, each considered terminating node is assigned a score based on reward function that indicates desirability of the outcome it represents; successful outcomes scored more highly if they are reached in a shorter amount of time; paragraph 0159, each considered path assigned score/reward function, indicating desirability, such as scoring more highly if outcome reached in shorter amount of time; paragraph 0399, MCTS searching for feasible plans that achieve the goal and, among these searches for the best one; paragraph 0414, cost of plan defined as number of basic maneuvers in the plan; compare with specification of the instant application page 9, second full paragraph, indicating that the policy may be a neural network; i.e. where a generative behavior model, which is a trained neural network, is applied to apply an MCTS heuristic search algorithm and/or various underlying heuristics to determine an optima/highest scoring/lowest cost plan/set of maneuvers to reach a goal, this is analogous to a policy selecting at least one heuristic depending on state information; Examiner notes that where the set of predefined heuristics only includes one heuristic, using the single predefined heuristic is analogous to selecting that heuristic out of the set; moreover, where the selection of the heuristic results in an optimal path/number of moves such that the goal is reached in the shortest amount of time, this appears to be analogous with the apparently recited intended purpose/result of a minimal number of expected state expansions);
iv) choosing a state with a lowest cost determined by the selected heuristic by the policy from the reachable states (e.g. paragraph 0158, each considered terminating node is assigned a score based on reward function that indicates desirability of the outcome it represents; successful outcomes scored more highly if they are reached in a shorter amount of time; paragraph 0159, each considered path assigned score/reward function, indicating desirability, such as scoring more highly if outcome reached in shorter amount of time; paragraph 0185, selecting path determined to be most promising; paragraph 0186, most promising path may be the path having the maximum score; paragraph 0198-0199, select most promising maneuver sequences, taking into account scores; paragraphs 0328-0329, plan means sequence of manoeuvres selected to reach a goal; inferring a goal from finite set of available goals based on cost penalties; paragraph 0325, heuristic goal generation function used to enumerate set of possible goals for car in given view region; paragraph 0335, likelihood for given goal defined as different between respective costs of two plans including optimal plan from initial location to goal location, and best available plan defined as optimal plan to goal location given observed behavior; paragraph 0339, cost taking into account factors including driving time, safety, and comfort; paragraph 0346, full cost determined for best available trajectory; paragraph 0347, best available trajectory matching optimal trajectory for goal well, cost penalty, i.e. difference between cost of optimal trajectory and cost of best available trajectory, is low; paragraph 0351, determining optimal plan for goal given initial location and best available plan for that goal, given observations in subsequent time interval; paragraph 0353, finding optimal plan for reaching specified goal from given location; nodes of graph represent maneuvers and aim is to find sequence of nodes/maneuvers which reach the goal at relatively low cost; for each node, a heuristic function provides an estimate of the cost from the node to the goal; paragraph 0358, cost heuristic to estimate remaining cost to goal; paragraph 0384, predicting possible trajectories using inverse planning, computing set of plans with associated costs, such as up to a fixed number of plans; paragraph 0388, predicting various plausible trajectories rather than a single optimal trajectory; paragraph 0414, cost of plan defined as number of basic maneuvers in the plan; i.e. where a highest scoring path/state may be one which is considered the highest scoring/most optimal, such as by being reached in a shorter amount of time, and where driving time is also considered as a cost factor, such that a shortest amount of time (and therefore highest reward/score) may also correspond to a lowest cost, and the system selects the path (and corresponding state) having this highest score/lowest cost); and
v) determining an operation of the technical system out of the set of possible operations that has to be carried out by the technical system to reach the state with the lowest cost determined by the selected heuristic (e.g. paragraph 0184, selecting path determined to be most promising, generating control signals for controlling the AV to execute the corresponding sequence of manoeuvres in the real-world driving scenario encountered),
wherein the technical system is a robot or a transportation system, wherein the operations corresponds to predefined movements of the robot or the transportation system (e.g. abstract, determining sequence of autonomous vehicle manoeuvres; i.e. where an autonomous vehicle is analogous to a robot/transportation system, and where maneuvers are analogous to predefined movements of the autonomous vehicle);
wherein the steps i) to iv) are subsequently carried out several times until the current state corresponds to the goal state, wherein the chosen states with the lowest costs are stored in the list, wherein depending on the list, a sequence of operations is determined which generates a sequence of states of the list to reach the goal state (e.g. paragraphs 0180-0182, MCTS operates iteratively, game tree is constructed dynamically as MCTS is performed, nodes are added every time a new state is encountered, and possible manoeuvres from that state are hypothesized; this continues until terminating node is reached; each iteration commences by traversing existing tree, trying single path through game tree from root node to terminal node, if new node not terminal, simulating rollout to terminal node, scoring iteration, back propagating information about the score, selecting unvisited node, repeating the process; paragraph 0184, process repeats iteratively until it is terminated; paragraph 0197, multiple super-iterations of MCTS repeated, repetitions performed until stopping condition reached; paragraph 0198, having completed all super iterations, statistical analysis of all results is applied in order to select most promising maneuver sequences).
Ramamoorthy does not explicitly disclose wherein the policy has been trained to select the heuristic from the set of predefined heuristics. However, Keselman teaches wherein the policy has been trained to select the heuristic from the set of predefined heuristics, such that a minimal number of state expansions is expected when planning a path to the goal state (e.g. paragraph 0121, optimal quality factor; paragraph 0130, quality values assigned to actions of set of applicable actions, 0133, selecting top valued quality factors, such as maximal, predefined number, all over threshold, etc.; paragraph 0135, receiving the selection of one or more quality factors as an expansion heuristic to further expand the search tree; paragraph 0146, NN selecting quality factor values, simulator receiving them and relating to them as an expansion heuristic to select or determine one or more actions of applicable actions set; paragraph 0152, NN selecting optimal action associated with top valued quality factor; paragraph 0176, facilitating selection of optimal actions, intelligently traversing between nodes of search tree; paragraph 0188, NN receiving updated quality factors as feedback to train on optimally selecting a quality factor; paragraph 0202, NN selecting action to expand node which serves as expansion heuristic; i.e. where the neural network/policy is trained to select an optimal quality factor/heuristic, from a set of multiple quality factors/heuristics, for expanding the search tree to reach a target/goal state, where selection of an optimal expansion heuristic would be expected to result in optimal expansion of the search tree, such as a minimal number of expansions required to reach the target/goal).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention having the teachings of Ramamoorthy and Keselman in front of him to have modified the teachings of Ramamoorthy (directed to autonomous vehicle planning), to incorporate the teachings of Keselman (directed to motion planning of an autonomous driving machine) to include the capability to utilize a policy/neural network which is trained to select an optimal expansion heuristic, such that plan for reaching a target/goal state may be determined with optimized expansion (as taught by Keselman, where one of ordinary skill in the art would understand that one way in which expansion may be optimized is by performing a minimal number of expansions). One of ordinary skill would have been motivated to perform such a modification in order to facilitate selection of optimal actions and intelligently traverse between nodes of a search tree as described in Keselman (paragraph 0176).
Ramamoorthy and Keselman do not explicitly disclose wherein the set of heuristics includes at least one of the following heuristics: fast-forward planning heuristic or causal graph heuristic or context-enhanced additive heuristic or an additive heuristic. However, Bnayahu teaches wherein the set of heuristics includes at least one of the following heuristics: fast-forward planning heuristic or causal graph heuristic or context-enhanced additive heuristic or an additive heuristic (e.g. paragraph 0043, spatiotemporal search guidance module is a heuristic function which may be automatically generated from planning problem description, and may be based on a fast forward heuristic).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention having the teachings of Ramamoorthy, Keselman, and Bnayahu in front of him to have modified the teachings of Ramamoorthy (directed to autonomous vehicle planning) and Keselman (directed to motion planning of an autonomous driving machine), to incorporate the teachings of Bnayahu (directed to optimizing spatiotemporal computational problems) to include the capability to include, within the set of heuristics, a fast forward planning heuristic (as taught by Bnayahu). One of ordinary skill would have been motivated to perform such a modification in order to model and solve spatiotemporal planning problems using object oriented programming to provide system optimization as described in Bnayahu (paragraph 0016).
Although Ramamoorthy teaches scoring different successful outcomes more highly if they are reached in a shorter amount of time, and imposing a fixed time budget for computing the set of plans (paragraphs 0158-0159, 0384), Ramamoorthy, Keselman, and Bnayahu do not explicitly disclose wherein the policy selects the heuristic with an expected lowest planning time. However, Maturana teaches wherein the policy selects the heuristic with an expected lowest planning time (e.g. paragraph 0040, if canonical representation of constraint problem does not exist in problem cache, storing it, and forwarding canonical representation of constraint problem to solver to perform solving operation and generate a solution, where solver selects a heuristic from a number of available heuristics to generate a solution to the canonical representation; when selected heuristic fails to generate a solution within predetermined period of time, solver selects new heuristic and uses new solver heuristic to generate a solution to the canonical representation; paragraph 0042, if corresponding entry exists in problem cache, generating solution to canonical representation by reusing information, including solver heuristic, associated with previous operation; paragraph 0045, using background process to refine selection of solver heuristics, including selecting canonical representation of entry whose solution previously required more than a predetermined computation time, and attempting to generate a faster solution using a different solver heuristic; paragraph 0047, monitoring computation time when solving canonical representation and storing this time; paragraph 0048, when persistence flag not set, solver server is allowed to revisit canonical representations in problem cache to search for an optimal solver heuristic that can solve the canonical representation in a shorter computation time; paragraph 0058, Fig. 5, if entry corresponding to canonical representation exists selecting the corresponding solver heuristic; paragraph 0059, if corresponding entry does not exists, generating solution using solver heuristic and associating solver heuristic with new entry; paragraphs 0060-0061, Fig. 6, generating solution to canonical constraint representation; selecting solver heuristic from collection of available solver heuristics, using selected heuristic for predetermined period of time to generate a solution; if solution found, returning the solution and solver heuristic; if solution not found, repeating process for other unused solver heuristics; i.e. when a problem is first encountered, a solver heuristic is selected from a set of solver heuristics for solving the problem which is able to solve the problem within a predetermined execution/computation time, and this selected heuristic is associated with the problem for future use; subsequently, the system attempts to revisit the problem in order to select/determine heuristics which can generate a solution which are even faster/having shorter computation times, such that, at any given time, the selected heuristic used for solving a given problem is the heuristic having the lowest expected solution/planning/execution time).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention having the teachings of Ramamoorthy, Keselman, Bnayahu, and Maturana in front of him to have modified the teachings of Ramamoorthy (directed to autonomous vehicle planning), Keselman (directed to motion planning of an autonomous driving machine), and Bnayahu (directed to optimizing spatiotemporal computational problems), to incorporate the teachings of Maturana (directed to enhancing performance of a constraint solver across individual processes) to include the capability to include the capability to select, from among the set of heuristics a heuristic having the lowest expected execution time (i.e. time for generating a plan/solution). One of ordinary skill would have been motivated to perform such a modification in order to enable constraint solving information to be reused within a given problem domain and across a number of independent or related problem domains, facilitating regression testing, persistence of solutions over time, and random stability when revisiting a given constraint solving operation at a later time as described in Maturana (paragraph 0032).
Ramamoorthy, Keselman, Bnayahu, and Maturana do not explicitly disclose that the heuristic expands exponentially so that the selected heuristic is sufficient to expand a search space to find the path to the goal state. However, Qui teaches that the heuristic expands exponentially so that the selected heuristic is sufficient to expand a search space to find the path to the goal state (e.g. paragraph 0068, using partially observable differential dynamic programming (PODDP), constructing trajectory tree that approximates infinite space of possible control, state, observation, and belief sequences up to finite horizon T; for given node, generating branches corresponding to possible state transitions, observations, and belief updates; tree expansion proceeds recursively until finite horizon is reached; paragraph 0081, each node in trajectory tree having Z successor nodes such that the tree has exponential size; this exponential growth is manageable for short horizons; paragraph 0084, PODDP providing trajectory optimization; paragraph 0086, inducing agent to move to goal).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention having the teachings of Ramamoorthy, Keselman, Bnayahu, Maturana, and Qiu in front of him to have modified the teachings of Ramamoorthy (directed to autonomous vehicle planning), Keselman (directed to motion planning of an autonomous driving machine), Maturana (directed to enhancing performance of a constraint solver across individual processes), and Bnayahu (directed to optimizing spatiotemporal computational problems), to incorporate the teachings of Qiu (directed to latent belief space planning using a trajectory tree) to include the capability to utilize a selected heuristic/algorithm which expands exponentially such that it is sufficient to find the path to the goal state (i.e. where this exponential expansion, such as of the tree of possible different paths to a goal state, is manageable for at least short time horizons, as taught by Qiu). One of ordinary skill would have been motivated to perform such a modification in order to enable modeling and optimizing trajectories in many different scenarios including several important classes of nonlinear, continuous planning problems with uncertainty over discrete latent states as described in Qiu (paragraph 0037).
With respect to claim 7, Ramamoorthy in view of Keselman, further in view of Bnayahu, further in view of Maturana, further in view of Qiu teaches all of the limitations of claim 1 as previously discussed, and Ramamoorthy further teaches wherein the policy is trained via reinforcement learning (e.g. paragraph 0011, applying generative behavior model to vehicle parameters and driving scenario parameters; paragraph 0012, generative behavior model is ML model which has been trained; paragraph 0022, generative behavior model comprising trained neural network; paragraph 0148, simulating performance of manoeuvre by simulating or rolling out actions that the AV planner would take in real life given state of the driving scenario; paragraph 0149, simulating performance of manoeuvre by vehicle using action policy which can be learnt by reinforcement learning).
Claim 8 is rejected under 35 U.S.C. 103 as being unpatentable over Ramamoorthy in view of Keselman, further in view of Bnayahu, further in view of Maturana, further in view of Qiu, further in view of AutoML.org. Dynamic Algorithm Configuration. February 10, 2020. [Retreived on April 5, 2024]. Retrieved from the Internet: https://www.automl.org/dynamic-algorithm-configuration/. (Hereinafter referred to as AutoML).
With respect to claim 8, Ramamoorthy in view of Keselman, further in view of Bnayahu, further in view of Maturana, further in view of Qiu teaches all of the limitations of claim 7 as previously discussed. Ramamoorthy does not explicitly disclose wherein the policy is trained by Dynamic Algorithm Control (DAC). However, AutoML teaches wherein the policy is trained by Dynamic Algorithm Control (DAC) (e.g. page 4, final paragraph, AI planning system, heuristics guiding system in how to traverse through search landscapes/spaces, dynamic algorithm configuration allows to learn for which type of problems as well in which situations a heuristic should be chosen; page 5, first full paragraph through third full paragraph, learning dynamic configuration policies, informing dynamic configuration policy of how to adjust configuration, sing same features used for algorithm selection, accuracy of partially trained neural network used as a reward signal).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention having the teachings of Ramamoorthy, Keselman, Bnayahu, Maturana, Qiu, and AutoML in front of him to have modified the teachings of Ramamoorthy (directed to autonomous vehicle planning), Bnayahu (directed to optimizing spatiotemporal computational problems), Maturana (directed to enhancing performance of a constraint solver across individual processes), Qiu (directed to latent belief space planning using a trajectory tree), and Keselman (directed to motion planning of an autonomous driving machine), to incorporate the teachings of AutoML (directed to application of dynamic algorithm configuration in various contexts, including AI planning systems) to include the capability to train the policy/neural network (of Ramamoorthy) by dynamic algorithm configuration (as taught by AutoML). One of ordinary skill would have been motivated to perform such a modification in order to allow for learning which types of problems, and in which situations, a heuristic should be chosen for AI planning as described in AutoML (page 4, final paragraph).
Claim 9 is rejected under 35 U.S.C. 103 as being unpatentable over Ramamoorthy in view of Keselman, further in view of Bnayahu, further in view of Maturana, further in view of Qiu, further in view of AutoML, further in view of Toshev et al. (US 20200114506 A1).
With respect to claim 9, Ramamoorthy in view of Keselman, further in view of Bnayahu, further in view of Maturana, further in view of Qiu, further in view of AutoML teaches all of the limitations of claim 8 as previously discussed. Although Ramamoorthy teaches wherein a reward function is utilized (e.g. paragraph 0139, evaluating defined reward function for the purpose of scoring different paths through the game tree, driving execution of MCTS towards globally optimal path with respect to the reward function), Ramamoorthy and AutoML do not explicitly disclose that the reward function is a sparse reward function. However, Toshev teaches that the reward function is a sparse reward function (e.g. abstract, generating action prediction of how end effector of robot should be moved toward target; paragraph 0038, action predictions iteratively generated by recurrent neural network model; task planner; paragraph 0041, training policy implemented as deep neural network using sparse reward function).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention having the teachings of Ramamoorthy, Keselman, Bnayahu, Maturana, Qiu, AutoML, and Toshev in front of him to have modified the teachings of Ramamoorthy (directed to autonomous vehicle planning), Keselman (directed to motion planning of an autonomous driving machine), Bnayahu (directed to optimizing spatiotemporal computational problems), Maturana (directed to enhancing performance of a constraint solver across individual processes), Qiu (directed to latent belief space planning using a trajectory tree), and AutoML (directed to application of dynamic algorithm configuration in various contexts, including AI planning systems), to incorporate the teachings of Toshev (directed to movement of a robotic system to a target/goal, such as servoing of a robot end effector using a neural network) to include the capability to utilize a sparse reward function (as taught by Toshev). One of ordinary skill would have been motivated to perform such a modification in order to allow for a robotic/autonomous system to learn a policy which can generalize to new setups or deal with changes in a current setup, allowing the robotic system to become aware of its own physical properties without a precise model, making it more general without requiring tedious calibration procedures as described in Toshev (paragraph 0039).
Claims 2 and 3 are rejected under 35 U.S.C. 103 as being unpatentable over Ramamoorthy in view of Keselman, further in view of Bnayahu, further in view of Maturana, further in view of Qiu, further in view of Jacobs et al (US 20210295176 A1), further in view of Gupta et al. (US 20190321980 A1).
With respect to claim 2, Ramamoorthy in view of Keselman, further in view of Bnayahu, further in view of Maturana, further in view of Qiu teaches all of the limitations of claim 1 as previously discussed, and Ramamoorthy further teaches wherein the current state for each domain out of the plurality of domains is characterized by at least the following features: minimum cost that can be returned by each heuristic of the set of predefined heuristics, variance of costs returned from each heuristic of the set of predefined heuristics, number of states maintained by each heuristic of the set of predefined heuristics, and a current time step (e.g. paragraph 0141, game tree has root node representing current state of encountered driving scenario, at time t=0, capturing current state of vehicle and current state of any external agents; paragraph 0142, additional nodes of the MCT represent anticipated states of the scenario at different times in the future; paragraph 0341, optimal plan computed for each goal, determining optimal trajectory for each goal, computing full cost associated with optimal trajectory; paragraph 0347, difference between cost of optimal trajectory and cost of best available trajectory; paragraph 0358, cost heuristic to estimate remaining cost to goal h(n) providing estimate of minimum remaining cost; i.e. where a tree structure representing a current state for a scenario at a current time, t=0, as well as anticipated states at future times, provides features including a current time step and a number of states maintained by a given heuristic, where a determined cost difference between an optimal plan/trajectory and a best available trajectory provides a feature including variance of costs returned from the heuristic, where an estimated minimum remaining cost provides a feature including minimum cost that can be returned by the heuristic, and where these features further characterize the current state for a driving scenario/domain).
Ramamoorthy does not explicitly disclose that the current state for each domain is characterized by maximum cost that can be returned by each heuristic of the set of predefined heuristics. However, Jacobs teaches that the current state for each domain is characterized by maximum cost that can be returned by each heuristic of the set of predefined heuristics (e.g. paragraph (4) between paragraphs 0044 and 0045, determining maximum cost for heuristic solution).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention having the teachings of Ramamoorthy, Keselman, Bnayahu, Maturana, Qiu, and Jacobs in front of him to have modified the teachings of Ramamoorthy (directed to autonomous vehicle planning), Bnayahu (directed to optimizing spatiotemporal computational problems), Maturana (directed to enhancing performance of a constraint solver across individual processes), Qiu (directed to latent belief space planning using a trajectory tree), and Keselman (directed to motion planning of an autonomous driving machine), to incorporate the teachings of Jacobs (directed to generating robust solutions to optimization problems using machine learning) to include the capability to further provide, as a feature characterizing the current state, a maximum cost returned by a heuristic solution (as taught by Jacobs). One of ordinary skill would have been motivated to perform such a modification in order to generate robust solutions to optimization problems as described in Jacobs (paragraph 0018).
Ramamoorthy and Jacobs do not explicitly disclose that the current state for each domain is characterized by average costs returned from each heuristic of the set of predefined heuristics. However, Gupta teaches that the current state for each domain is characterized by average costs returned from each heuristic of the set of predefined heuristics (e.g. paragraph 0104, maintaining progress made using heuristic, such as based on mean change in heuristic cost, i.e. a moving average).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filing date of the invention having the teachings of Ramamoorthy, Keselman, Bnayahu, Maturana, Qiu, Jacobs, and Gupta in front of him to have modified the teachings of Ramamoorthy (directed to autonomous vehicle planning), Keselman (directed to motion planning of an autonomous driving machine), Bnayahu (directed to optimizing spatiotemporal computational problems), Maturana (directed to enhancing performance of a constraint solver across individual processes), Qiu (directed to latent belief space planning using a trajectory tree), and Jacobs (directed to generating robust solutions to optimization problems using machine learning), to incorporate the teachings of Gupta (directed to trajectory planning for manipulators in robotic finishing applications) to include the capability to further provide, as a feature characterizing the current state, mean/average costs returned by a heuristic solution (as taught by Gupta). One of ordinary skill would have been motivated to perform such a modification in order to improve computational efficiency of a planner and enable it to compute plans in real-time as described in Gupta (paragraph 0021).
With respect to claim 3, Ramamoorthy in view of Keselman, further in view of Bnayahu, further in view of Maturana, further in view of Qiu, further in view of Jacobs, further in view of Gupta teaches all of the limitations of claim 2 as previously discussed, and Ramamoorthy further teaches wherein the state further includes a features reflecting context information of the current domain (e.g. paragraphs 0121-0124, 0127, 0130, 0141, and 0144, as cited above, sensor information is processed in order to obtain a current scenario/domain at a given time, such as time=0 as discussed in paragraph 0141, as well as state information of the environment including states of external objects and surroundings including road layout/structure; see also paragraph 0131, parameters of encountered driving scenario, and paragraph 0137, parameterizing encountered driving scenario based on captured sensor data; i.e. where information used to derive the driving scenario/domain, including sensor data or corresponding parameterized information, such as information characterizing environmental information, time, etc., is analogous to features reflecting context information of the current scenario/domain).
It is noted that any citation to specific pages, columns, lines, or figures in the prior art references and any interpretation of the references should not be considered to be limiting in any way. “The use of patents as references is not limited to what the patentees describe as their own inventions or to the problems with which they are concerned. They are part of the literature of the art, relevant for all they contain,” In re Heck, 699 F.2d 1331, 1332-33, 216 USPQ 1038, 1039 (Fed. Cir. 1983) (quoting in re Lemelson, 397 F.2d 1006, 1009, 158 USPQ 275, 277 (GCPA 1968)). Further, a reference may be relied upon for all that it would have reasonably suggested to one having ordinary skill the art, including nonpreferred embodiments. Merck & Co, v. Biocraft Laboratories, 874 F.2d 804, 10 USPQ2d 1843 (Fed. Cir.),