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 is a Final Office Action on the merits. Claims 1-6, 8-14, and 16-22 are currently pending and are addressed below.
Response to Amendment
1. The amendment filed 11/03/2025 has been entered. Claims 1-6, 8-14, and 16-22remain pending in the application.
Response to Arguments
2. Applicant’s amendments/arguments filed 11/03/2025 with respect to 35 USC 103,
have been fully considered but moot because the arguments do not apply to the combination of references and/or rationale being used in the current rejection.
Claim Rejections - 35 USC § 103
3. 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 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.
4. Claims 1-6, 8-9, 14, and 16-17 is/are rejected under 35 U.S.C. 103 as being unpatentable over Wang (US 20200097014, hereinafter Wang) and Huang et al. (US 20210020045, hereinafter Huang) and in view of Berntorp et al. (US 9568915, hereinafter Berntorp).
Regarding claim 1, Wang teaches a system (see at least Abstract: “A system for controlling a movement of a vehicle from an initial state of the vehicle and a target state of the vehicle constructs a graph having multiple nodes defining states of the vehicle and including an initial node defining the initial state of the vehicle and a target node defining the target state of the vehicle and determines a path through the graph connecting the initial node with the target node.”) comprising:
one or more processors (see at least Fig. 2B and [0072]: “FIG. 2B shows a block diagram of a general structure of the motion-planning system 203 according to one embodiment. The motion-planning system 203 includes at least one processor 270 for executing modules of the motion-planning system 203.”); and
one or more non-transitory computer-readable media storing computer-executable instructions that, when executed, cause the one or more processors to perform operations (see at least [0072]: “In some embodiments, the memory 280 can include stored instructions implementing the method for the automated vehicle control, wherein the instructions, when executed by the processor 270 carry out at least some steps of the method.”) comprising:
receiving a set of actions for controlling a vehicle through an environment (see at least [0050]: “It is another object of some embodiments to disclose a motion planning method that allows real-time automated vehicle control, e.g., suitable for automated parking system and method. For clarity purposes only, some embodiments are described in relation to automated parking scenario. However, principles explained in relation to parking scenarios are used by alternative embodiments in other automated vehicle control applications.”; [0068]: “FIG. 2A shows a block diagram of automated vehicle control system 299 according to one embodiment. Environment mapping and localization block 201 constructs or updates the map of the space, e.g., parking space, and determines the current location of the vehicle by sensing the environment and vehicle operation condition…A global positioning system sensor can be used to provide position and velocity of the vehicle. Sensors to sense the environment 200 can be video cameras capturing obstacles including other vehicles, pedestrians, and buildings, ultrasonic/radar and LiDAR sensors detecting distance between the vehicle and obstacles, etc. In one embodiment, the environment map is further processed to generate a geometric representation of the parking space as shown in FIG. 1C.”);
generating a tree structure (see at least Figs. 3A-3B and [0073]: “FIG. 3A shows a block diagram of a method performed by a motion planner 203 of a system 299 for controlling a movement of a vehicle from an initial state of the vehicle and a target state of the vehicle according to some embodiments. The motion planner is configured to construct 310 a graph having multiple nodes defining states of the vehicle. The nodes include an initial node defining the initial state of the vehicle and a target node defining the target state of the vehicle. Each pair of nodes in the graph is connected with an edge defined by one of collision free primitive motions moving the vehicle between the states of the connected nodes.”) by:
creating a plurality of nodes associated with controlling the vehicle in accordance with an action of the set of actions over a period of time corresponding to a receding horizon (see at least Fig. 3B and [0075]: “In some embodiments, the motion planner constructs 310 the graph using doubletree construction. Specifically, motion planner determines the graph by constructing an initial tree of nodes originating at the initial node and by constructing a target tree of nodes originating at the target node. To construct the initial tree or the target tree, the motion planner is configured to select 315 an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend 320 the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”; [0079]: “FIG. 3B shows a schematic of determining the graph using doubletree construction according to one embodiment. In this example, the graph is constructed from both ends using an initial tree 321, having an initial node 311 corresponding to the initial state 101, and a target tree 322, having a target node 312 corresponding to the target state 102. The initial tree has a node set and an edge set. The target tree also has a node set and an edge set.”);
determining, for an intermediate node, an estimated cost associated with a trajectory passing from a root node to the intermediate node (see at least [0075]: “In some embodiments, the motion planner constructs 310 the graph using doubletree construction. Specifically, motion planner determines the graph by constructing an initial tree of nodes originating at the initial node and by constructing a target tree of nodes originating at the target node. To construct the initial tree or the target tree, the motion planner is configured to select 315 an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend 320 the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”);
determining, based on the estimated cost, whether to expand the intermediate node (see at least [0075]: “In some embodiments, the motion planner constructs 310 the graph using doubletree construction. Specifically, motion planner determines the graph by constructing an initial tree of nodes originating at the initial node and by constructing a target tree of nodes originating at the target node. To construct the initial tree or the target tree, the motion planner is configured to select 315 an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend 320 the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”);
expanding a set of nodes that are deeper than the intermediate node to an end of the period of time (see at least [0076]: “As used herein, the cost of a node is a minimum cost for reaching the target node from the initial node through the node and includes a first cost of a first path through nodes of the initial tree, a second cost of a second path through nodes of the target tree, and a third cost of a third path between nodes of the initial tree and the target tree. In various embodiments, the cost of the node is indicative of one or combination of a travel time of the vehicle from the initial state to the target state through the state of the node, a distance the vehicle travels from the initial state to the target state through the state of the node, a rate of change of a mode of movement of the vehicle traveling from the initial state to the target state through the state of the node.”; [0078]: “Some embodiments take advantage of computational efficiency of double trees space exploration by selecting the node on the initial or target tree to expand. Specifically, some embodiments select an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”); and
determining whether to include a final node in the tree structure based at least in part on whether a corresponding trace reaches a termination state (see at least [0076]: “As used herein, the cost of a node is a minimum cost for reaching the target node from the initial node through the node and includes a first cost of a first path through nodes of the initial tree, a second cost of a second path through nodes of the target tree, and a third cost of a third path between nodes of the initial tree and the target tree. In various embodiments, the cost of the node is indicative of one or combination of a travel time of the vehicle from the initial state to the target state through the state of the node, a distance the vehicle travels from the initial state to the target state through the state of the node, a rate of change of a mode of movement of the vehicle traveling from the initial state to the target state through the state of the node.”);
determining, based at least in part on the tree structure, a trace through the tree structure having a lowest cost, the trace associated with an optimal trajectory (see at least [0079]: “FIG. 3B shows a schematic of determining the graph using doubletree construction according to one embodiment. In this example, the graph is constructed from both ends using an initial tree 321, having an initial node 311 corresponding to the initial state 101, and a target tree 322, having a target node 312 corresponding to the target state 102. The initial tree has a node set and an edge set. The target tree also has a node set and an edge set.”; [0082]: “For example, if all primitive motions that can reduce the cost of the node 313 lead to the obstacles 103, then the node 313 is not expandable, and the embodiments select another node, e.g., a node 331 with cost greater than the cost of the node 313 to expand. If the node 331 is expandable, i.e., there is a collision free motion primitive, such as 336 that reduces the cost of the expandable node 331, the embodiment uses the edge 336 defined by this collision free motion primitive to add to the initial tree 321 a child node 337 that have a cost less than the cost of the node 331.”); and
controlling the vehicle based at least in part on the optimal trajectory (see at least [0074]: “The motion planner also configured to determine 330 a path through the graph connecting the initial node with the target node, such that the path defines a sequence of primitive motions moving the vehicle from the initial state to the target state; and to transmit 335 the sequence of primitive motions to a controller of the vehicle configured to control the movement of the vehicle using the sequence of primitive motions. Having the graph, the path can be determined using various optimization techniques optimizing a parameter of the path, such as one or combination of its cost and smoothness.”; [0087]: “FIG. 3C shows a block diagram of a method for a motion planning method according to some embodiments. Beginning with the geometry of vehicle, the map of the parking space, and initial and target states, the method first initializes 345 a graph custom-character and outputs an initial graph 350. Based on the initial graph and primitive motions 355, the graph is constructed 360 by repeating two steps: node selection and node expansion using prioritized control actions…Reference trajectory 390 is fed into a control module to control 395 the motion of the vehicle such that the vehicle motion follows the reference trajectory, based on sensed signal 391 such as vehicle's current state.”).
Wang fails to explicitly teach determining, based at least on a machine learned model, an estimated cost associated with a trajectory.
However, Huang teaches a system and method for autonomous vehicle guidance that determines, based at least on a machine learned model, an estimated cost associated with a trajectory (see at least [0036]: “The techniques may comprise determining a total cost of a path based at least in part on the costs associated with the contiguous set of contiguous connections making up the path. In some examples, the cost associated with a connection may comprise a cost indicated by a cost plot and/or may be based at least in part on: a cost associated with the motion primitive connecting the first node to the second node (e.g., the greater the curvature of the motion primitive, the higher cost), a cost associated with a safety margin (e.g., higher cost for bringing the autonomous vehicle closer to an object, may depend on the velocity and/or other kinematics), a cost associated with a difference between the ending position and/or pose associated with a terminus of the motion primitive and a target position and/or pose, a cost associated with a starting position and/or pose of the autonomous vehicle (e.g., a cost associated with a position and/or pose associated with a beginning of the motion primitive and/or the first node and/or a difference between a position and/or pose associated with the first node and the starting position and/or pose), a cost associated with a difference between a motion primitive connecting a first layer and second layer and a motion primitive connecting a previous layer to the first layer, and/or the like. In some examples, at least one of the costs may be based at least in part on a difference between a motion primitive and output generated by a machine-learned model trained to generate steering commands based at least in part on being trained using steering commands generated by human and/or simulated human drivers and/or inferred from observation of human drivers.”; [0128]: “In some instances, the memory 1120 and/or memory 1124 may store a set of motion primitives 1132 and/or cost plot 1134 in association with the set of motion primitives, such as those motion primitives and/or cost plots as described herein. In some examples, memory 1124 may additionally or alternatively store a motion primitives and/or cost plot generator 1136. In some examples, the motion primitives and/or cost plot generator 1136 may comprise a machine-learned (ML) model (e.g., a neural network) and/or a parallel processing component.”).
Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wang to incorporate the teachings of Huang and provide a means to determine, based at least on a machine learned model, an estimated cost associated with a trajectory, with a reasonable expectation of success, in order to utilize the learning model that can be trained and refined overtime to provide more accurate data.
The combination of Wang and Huang fails to explicitly teach expanding a set of nodes to an end of the period of time, the period of time having a predetermined length.
However, Berntorp teaches a system and method for controlling autonomous vehicle expand a set of nodes to an end of a period of time, the period of time having a predetermined length (see at least Fig. 3 and Col. 8, lines 40-55: “FIG. 3 shows a schematic of a tree of state transitions defining the motion of the vehicle according to some embodiments of the invention. The current tree in the drivable space 330 is shown with root node 300 indicating the current state of the vehicle and includes the states as nodes and the state transitions as edges in state space, arising from control inputs chosen according to other embodiments of the invention. For example, edge 321 is the motion generated by applying a control input for a predefined time from root node 300 to state 320. The tree can include a target state 310 and target region 340 of the vehicle. In one embodiment of the invention, there can be several target states 310 and regions 340. A probability can be associated to the control input generating edge 321 and therefore also state 320, which accounts for uncertainties in the models of the vehicle, obstacles, and the environment.”; Col. 11, lines 27-31: “The motion is determined iteratively until a termination condition is met, for example, for a time period or for a predetermined number of iterations. An iteration of the method of FIG. 6A includes the following steps.”).
Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wang and Huang to incorporate the teachings of Berntorp and provide a means to expand a set of nodes to an end of a period of time, the period of time having a predetermined length, with a reasonable expectation of success, in order to expand based on an established set time period and minimize extra computational power.
Regarding claim 2, modified Wang teaches the limitations of claim 1. Wang further teaches wherein the intermediate node is associated with a set of layers of the tree structure that excludes a first layer and a final layer of the tree structure (see at least Fig. 3B and [0079]: “FIG. 3B shows a schematic of determining the graph using doubletree construction according to one embodiment. In this example, the graph is constructed from both ends using an initial tree 321, having an initial node 311 corresponding to the initial state 101, and a target tree 322, having a target node 312 corresponding to the target state 102. The initial tree has a node set and an edge set. The target tree also has a node set and an edge set.”; [0082]: “For example, if all primitive motions that can reduce the cost of the node 313 lead to the obstacles 103, then the node 313 is not expandable, and the embodiments select another node, e.g., a node 331 with cost greater than the cost of the node 313 to expand. If the node 331 is expandable, i.e., there is a collision free motion primitive, such as 336 that reduces the cost of the expandable node 331, the embodiment uses the edge 336 defined by this collision free motion primitive to add to the initial tree 321 a child node 337 that have a cost less than the cost of the node 331.”).
Regarding claim 3, modified Wang teaches the limitations of claim 1. Wang further teaches wherein the intermediate node is expanded based on the estimated cost and a known cost associated with reaching a state corresponding to the intermediate node (see at least Fig. 3B and [0074]: “The motion planner also configured to determine 330 a path through the graph connecting the initial node with the target node, such that the path defines a sequence of primitive motions moving the vehicle from the initial state to the target state; and to transmit 335 the sequence of primitive motions to a controller of the vehicle configured to control the movement of the vehicle using the sequence of primitive motions. Having the graph, the path can be determined using various optimization techniques optimizing a parameter of the path, such as one or combination of its cost and smoothness.” [0082]: “For example, if all primitive motions that can reduce the cost of the node 313 lead to the obstacles 103, then the node 313 is not expandable, and the embodiments select another node, e.g., a node 331 with cost greater than the cost of the node 313 to expand. If the node 331 is expandable, i.e., there is a collision free motion primitive, such as 336 that reduces the cost of the expandable node 331, the embodiment uses the edge 336 defined by this collision free motion primitive to add to the initial tree 321 a child node 337 that have a cost less than the cost of the node 331.”).
Wang fails to explicitly teach wherein the known cost is determined based on at least one of: a safety cost associated with reaching the state, a comfort cost associated with reaching the state, or a measure determined based on compliance of a second action associated with the state with a policy.
However, Huang teaches a system and method for autonomous vehicle guidance wherein a known cost is determined based on at least one of: a safety cost associated with reaching a state, a comfort cost associated with reaching the state, or a measure determined based on compliance of a second action associated with the state with a policy (see at least [0036]: “The techniques may comprise determining a total cost of a path based at least in part on the costs associated with the contiguous set of contiguous connections making up the path. In some examples, the cost associated with a connection may comprise a cost indicated by a cost plot and/or may be based at least in part on: a cost associated with the motion primitive connecting the first node to the second node (e.g., the greater the curvature of the motion primitive, the higher cost), a cost associated with a safety margin (e.g., higher cost for bringing the autonomous vehicle closer to an object, may depend on the velocity and/or other kinematics), a cost associated with a difference between the ending position and/or pose associated with a terminus of the motion primitive and a target position and/or pose, a cost associated with a starting position and/or pose of the autonomous vehicle (e.g., a cost associated with a position and/or pose associated with a beginning of the motion primitive and/or the first node and/or a difference between a position and/or pose associated with the first node and the starting position and/or pose), a cost associated with a difference between a motion primitive connecting a first layer and second layer and a motion primitive connecting a previous layer to the first layer, and/or the like.”; [0089]: “Determining whether a motion primitive is collision-free may comprise determining the safety margin cost discussed below in regard to expression (3)—a safety margin cost above a threshold safety margin cost may indicate a collision, in some examples. In an additional or alternate example, determining whether a motion primitive is collision-free may comprise determining a shape that has an arc-length equal to an arc-length of the motion primitive and a width that corresponds to a width of the autonomous vehicle (e.g., the width may equal the width of the autonomous vehicle, the width may be 150% of the width of the autonomous vehicle) and determining whether any portion of the shape overlaps a portion of the occupancy map indicated as being occupied.”).
Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wang to incorporate the teachings of Huang wherein a known cost is determined based on at least one of: a safety cost associated with reaching a state, a comfort cost associated with reaching the state, or a measure determined based on compliance of a second action associated with the state with a policy, with a reasonable expectation of success, in order to take into consideration safety margin for trajectory planning.
Regarding claim 4, modified Wang teaches the limitations of claim 1. Wang further teaches wherein the set of actions comprises at least one of:
slowing the vehicle down, turning the vehicle to left, turning the vehicle to right, or
speeding the vehicle up (see at least [0009]: “Some embodiments are based on recognition that an automated vehicle control system for controlling a movement of a vehicle from an initial state of the vehicle and a target state of the vehicle can include a motion planner configured to construct a graph having multiple nodes defining states of the vehicle. A motion planner can use such a graph to explore the state space of the vehicle and to select control actions for moving a vehicle. For example, the nodes of the graph include an initial node defining the initial state of the vehicle and a target node defining the target state of the vehicle. Each pair of nodes in the graph is connected with an edge defined by one of collision free primitive motions moving the vehicle between the states of the connected nodes. A primitive motion is formed by a combination of a control action and an integration time defining the type and the extend of the primitive motion.”; [0132]: “For example, the driving mode can be a forward driving mode or a backward driving mode, in which the forward driving mode includes forward primitive motions defining a straight movement, a right turn movement, and a left turn movement in a forward direction, and the backward driving mode includes backward primitive motions defining a straight movement, a right turn movement, and a left turn movement in a backward direction. Additionally, or alternatively, the driving mode can be a straight driving mode or a turn driving mode, wherein the turn driving mode includes different primitive motions for turning movements of the vehicle with different curvatures.”).
Regarding claim 5, modified Wang teaches the limitations of claim 1. Wang further teaches expanding the intermediate node and refraining from expanding a second intermediate node based at least in part on determining that the estimated cost associated with the intermediate node exceeds a second estimated cost associated with the second intermediate node (see at least [0103]: “FIG. 5A shows a flow chart of a method for tuning graph growth parameters 401 for a single tree custom-character.sub.sg of the graph 365 according to principles of some embodiments. The value of the sparsity defining the neighbor of a vehicle state is adjusted 503 according to the length of the expandable node list 502. In particular, if the length of the expandable node list custom-character.sub.sg is below a certain threshold (lower bound), the sparsity defining a distance to a neighbor of a vehicle state is reduced to avoid premature termination of the graph construction (which means no path is feasible). In some embodiments, the sparsity is reduced proportionally and recursively. If the node length goes above another threshold (upper bound), the sparsity is increased proportionally and recursively. The sparsity maintain constants when the length of the node list is between the lower and upper bounds.”).
Regarding claim 6, Wang teaches a method (see at least Figs. 3C-5E) comprising:
creating a plurality of nodes associated with a tree structure for controlling a vehicle (see at least [0050]: “It is another object of some embodiments to disclose a motion planning method that allows real-time automated vehicle control, e.g., suitable for automated parking system and method. For clarity purposes only, some embodiments are described in relation to automated parking scenario. However, principles explained in relation to parking scenarios are used by alternative embodiments in other automated vehicle control applications.”; [0068]: “FIG. 2A shows a block diagram of automated vehicle control system 299 according to one embodiment. Environment mapping and localization block 201 constructs or updates the map of the space, e.g., parking space, and determines the current location of the vehicle by sensing the environment and vehicle operation condition…A global positioning system sensor can be used to provide position and velocity of the vehicle. Sensors to sense the environment 200 can be video cameras capturing obstacles including other vehicles, pedestrians, and buildings, ultrasonic/radar and LiDAR sensors detecting distance between the vehicle and obstacles, etc. In one embodiment, the environment map is further processed to generate a geometric representation of the parking space as shown in FIG. 1C.”; Figs. 3A-3B and [0073]: “FIG. 3A shows a block diagram of a method performed by a motion planner 203 of a system 299 for controlling a movement of a vehicle from an initial state of the vehicle and a target state of the vehicle according to some embodiments. The motion planner is configured to construct 310 a graph having multiple nodes defining states of the vehicle. The nodes include an initial node defining the initial state of the vehicle and a target node defining the target state of the vehicle. Each pair of nodes in the graph is connected with an edge defined by one of collision free primitive motions moving the vehicle between the states of the connected nodes.”), the tree structure comprising a root node and an intermediate node (see at least Fig. 3B and [0075]: “In some embodiments, the motion planner constructs 310 the graph using doubletree construction. Specifically, motion planner determines the graph by constructing an initial tree of nodes originating at the initial node and by constructing a target tree of nodes originating at the target node. To construct the initial tree or the target tree, the motion planner is configured to select 315 an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend 320 the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”; [0079]: “FIG. 3B shows a schematic of determining the graph using doubletree construction according to one embodiment. In this example, the graph is constructed from both ends using an initial tree 321, having an initial node 311 corresponding to the initial state 101, and a target tree 322, having a target node 312 corresponding to the target state 102. The initial tree has a node set and an edge set. The target tree also has a node set and an edge set.”);
determining, for the intermediate node, an estimated cost associated with a trajectory passing from the root node to the intermediate node (see at least [0075]: “In some embodiments, the motion planner constructs 310 the graph using doubletree construction. Specifically, motion planner determines the graph by constructing an initial tree of nodes originating at the initial node and by constructing a target tree of nodes originating at the target node. To construct the initial tree or the target tree, the motion planner is configured to select 315 an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend 320 the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”);
determining, based on the estimated cost, whether to expand the intermediate node (see at least [0075]: “In some embodiments, the motion planner constructs 310 the graph using doubletree construction. Specifically, motion planner determines the graph by constructing an initial tree of nodes originating at the initial node and by constructing a target tree of nodes originating at the target node. To construct the initial tree or the target tree, the motion planner is configured to select 315 an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend 320 the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”);
expanding a set of nodes that are deeper than the intermediate node to an end of a period of time (see at least [0076]: “As used herein, the cost of a node is a minimum cost for reaching the target node from the initial node through the node and includes a first cost of a first path through nodes of the initial tree, a second cost of a second path through nodes of the target tree, and a third cost of a third path between nodes of the initial tree and the target tree. In various embodiments, the cost of the node is indicative of one or combination of a travel time of the vehicle from the initial state to the target state through the state of the node, a distance the vehicle travels from the initial state to the target state through the state of the node, a rate of change of a mode of movement of the vehicle traveling from the initial state to the target state through the state of the node.”; [0078]: “Some embodiments take advantage of computational efficiency of double trees space exploration by selecting the node on the initial or target tree to expand. Specifically, some embodiments select an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”);
determining, based at least in part on the tree structure, a trace through the tree structure having a lowest cost (see at least [0079]: “FIG. 3B shows a schematic of determining the graph using doubletree construction according to one embodiment. In this example, the graph is constructed from both ends using an initial tree 321, having an initial node 311 corresponding to the initial state 101, and a target tree 322, having a target node 312 corresponding to the target state 102. The initial tree has a node set and an edge set. The target tree also has a node set and an edge set.”; [0082]: “For example, if all primitive motions that can reduce the cost of the node 313 lead to the obstacles 103, then the node 313 is not expandable, and the embodiments select another node, e.g., a node 331 with cost greater than the cost of the node 313 to expand. If the node 331 is expandable, i.e., there is a collision free motion primitive, such as 336 that reduces the cost of the expandable node 331, the embodiment uses the edge 336 defined by this collision free motion primitive to add to the initial tree 321 a child node 337 that have a cost less than the cost of the node 331.”); and
controlling the vehicle based at least in part on the trace (see at least [0074]: “The motion planner also configured to determine 330 a path through the graph connecting the initial node with the target node, such that the path defines a sequence of primitive motions moving the vehicle from the initial state to the target state; and to transmit 335 the sequence of primitive motions to a controller of the vehicle configured to control the movement of the vehicle using the sequence of primitive motions. Having the graph, the path can be determined using various optimization techniques optimizing a parameter of the path, such as one or combination of its cost and smoothness.”; [0087]: “FIG. 3C shows a block diagram of a method for a motion planning method according to some embodiments. Beginning with the geometry of vehicle, the map of the parking space, and initial and target states, the method first initializes 345 a graph custom-character and outputs an initial graph 350. Based on the initial graph and primitive motions 355, the graph is constructed 360 by repeating two steps: node selection and node expansion using prioritized control actions…Reference trajectory 390 is fed into a control module to control 395 the motion of the vehicle such that the vehicle motion follows the reference trajectory, based on sensed signal 391 such as vehicle's current state.”).
Wang fails to explicitly teach determining, based at least on a machine learned model, an estimated cost associated with a trajectory.
However, Huang teaches a system and method for autonomous vehicle guidance that determines, based at least on a machine learned model, an estimated cost associated with a trajectory (see at least [0036]: “The techniques may comprise determining a total cost of a path based at least in part on the costs associated with the contiguous set of contiguous connections making up the path. In some examples, the cost associated with a connection may comprise a cost indicated by a cost plot and/or may be based at least in part on: a cost associated with the motion primitive connecting the first node to the second node (e.g., the greater the curvature of the motion primitive, the higher cost), a cost associated with a safety margin (e.g., higher cost for bringing the autonomous vehicle closer to an object, may depend on the velocity and/or other kinematics), a cost associated with a difference between the ending position and/or pose associated with a terminus of the motion primitive and a target position and/or pose, a cost associated with a starting position and/or pose of the autonomous vehicle (e.g., a cost associated with a position and/or pose associated with a beginning of the motion primitive and/or the first node and/or a difference between a position and/or pose associated with the first node and the starting position and/or pose), a cost associated with a difference between a motion primitive connecting a first layer and second layer and a motion primitive connecting a previous layer to the first layer, and/or the like. In some examples, at least one of the costs may be based at least in part on a difference between a motion primitive and output generated by a machine-learned model trained to generate steering commands based at least in part on being trained using steering commands generated by human and/or simulated human drivers and/or inferred from observation of human drivers.”; [0128]: “In some instances, the memory 1120 and/or memory 1124 may store a set of motion primitives 1132 and/or cost plot 1134 in association with the set of motion primitives, such as those motion primitives and/or cost plots as described herein. In some examples, memory 1124 may additionally or alternatively store a motion primitives and/or cost plot generator 1136. In some examples, the motion primitives and/or cost plot generator 1136 may comprise a machine-learned (ML) model (e.g., a neural network) and/or a parallel processing component.”).
Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wang to incorporate the teachings of Huang and provide a means to determine, based at least on a machine learned model, an estimated cost associated with a trajectory, with a reasonable expectation of success, in order to utilize the learning model that can be trained and refined overtime to provide more accurate data.
The combination of Wang and Huang fails to explicitly teach expanding a set of nodes to an end of the period of time, the period of time having a predetermined length.
However, Berntorp teaches a system and method for controlling autonomous vehicle expand a set of nodes to an end of a period of time, the period of time having a predetermined length (see at least Fig. 3 and Col. 8, lines 40-55: “FIG. 3 shows a schematic of a tree of state transitions defining the motion of the vehicle according to some embodiments of the invention. The current tree in the drivable space 330 is shown with root node 300 indicating the current state of the vehicle and includes the states as nodes and the state transitions as edges in state space, arising from control inputs chosen according to other embodiments of the invention. For example, edge 321 is the motion generated by applying a control input for a predefined time from root node 300 to state 320. The tree can include a target state 310 and target region 340 of the vehicle. In one embodiment of the invention, there can be several target states 310 and regions 340. A probability can be associated to the control input generating edge 321 and therefore also state 320, which accounts for uncertainties in the models of the vehicle, obstacles, and the environment.”; Col. 11, lines 27-31: “The motion is determined iteratively until a termination condition is met, for example, for a time period or for a predetermined number of iterations. An iteration of the method of FIG. 6A includes the following steps.”).
Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wang and Huang to incorporate the teachings of Berntorp and provide a means to expand a set of nodes to an end of a period of time, the period of time having a predetermined length, with a reasonable expectation of success, in order to expand based on an established set time period and minimize extra computational power.
Regarding claim 8, modified Wang teaches the limitations of claim 6. Wang further teaches refraining from expanding a node of the tree structure that is deeper than the intermediate node in the tree structure based on determining that a corresponding trace fails to reach a termination state (see at least Figs. 3B, 5A-5B, and [0103]: “FIG. 5A shows a flow chart of a method for tuning graph growth parameters 401 for a single tree custom-character.sub.sg of the graph 365 according to principles of some embodiments. The value of the sparsity defining the neighbor of a vehicle state is adjusted 503 according to the length of the expandable node list 502. In particular, if the length of the expandable node list custom-character.sub.sg is below a certain threshold (lower bound), the sparsity defining a distance to a neighbor of a vehicle state is reduced to avoid premature termination of the graph construction (which means no path is feasible). In some embodiments, the sparsity is reduced proportionally and recursively. If the node length goes above another threshold (upper bound), the sparsity is increased proportionally and recursively. The sparsity maintain constants when the length of the node list is between the lower and upper bounds.”; [0109]: “FIG. 5E shows a block diagram of several stop criteria used 404 by some embodiments to terminate the iterative graph construction. In one embodiment, a test is conducted 551 to check whether the added child node is close enough to X.sub.f (reaches a pre-defined neighbor of X.sub.f). In another embodiment, one tries to construct 552 a standard Reeds-Shepp's path between the added child node and X.sub.f and verifies 552 if the Reeds-Shepp's path is collision free. If it is, then the Reeds-Shepp's path is added to the edge set of the graph, and the graph construction stops. The graph construction can terminate if the number of nodes exceeds a threshold, in which case the method fails to find a feasible path between X.sub.0 and X.sub.f.”).
Regarding claim 9, modified Wang teaches the limitations of claim 6. Wang further teaches wherein a first number of intermediate node layers is determined based on at least one of: at least two less than a total number of layers associated with the tree structure, or an amount of available computational resources at a time associated with generating the tree structure (see at least [0130]: “Some embodiments perform a node expansion, in addition to a node selection, in a deterministic manner to reduce the need to explore the space around the node with all possible primitive motions. To that end, an embodiment selects a first collision free primitive motion that reduces the cost of the expandable node, i.e., without testing subsequent primitive motions. To further reduce the computational burden, some embodiments order a set of primitive motions based on similarity of each of the primitive motions to a primitive motion defining an edge of the graph leading to the expandable node and tests the primitive motions in that order. These embodiments encourage smoothness of vehicle movement, as human operator would want, and, in practice, help to reduce the complexity of the constructed graph.”).
Regarding claim 14, Wang teaches one or more non-transitory computer-readable media storing instructions executable by one or more processors, wherein the instructions, when executed, cause the one or more processors to perform operations (see at least [0072]: “In some embodiments, the memory 280 can include stored instructions implementing the method for the automated vehicle control, wherein the instructions, when executed by the processor 270 carry out at least some steps of the method.”) comprising:
creating a plurality of nodes associated with a tree structure for controlling a vehicle (see at least [0050]: “It is another object of some embodiments to disclose a motion planning method that allows real-time automated vehicle control, e.g., suitable for automated parking system and method. For clarity purposes only, some embodiments are described in relation to automated parking scenario. However, principles explained in relation to parking scenarios are used by alternative embodiments in other automated vehicle control applications.”; [0068]: “FIG. 2A shows a block diagram of automated vehicle control system 299 according to one embodiment. Environment mapping and localization block 201 constructs or updates the map of the space, e.g., parking space, and determines the current location of the vehicle by sensing the environment and vehicle operation condition…A global positioning system sensor can be used to provide position and velocity of the vehicle. Sensors to sense the environment 200 can be video cameras capturing obstacles including other vehicles, pedestrians, and buildings, ultrasonic/radar and LiDAR sensors detecting distance between the vehicle and obstacles, etc. In one embodiment, the environment map is further processed to generate a geometric representation of the parking space as shown in FIG. 1C.”; Figs. 3A-3B and [0073]: “FIG. 3A shows a block diagram of a method performed by a motion planner 203 of a system 299 for controlling a movement of a vehicle from an initial state of the vehicle and a target state of the vehicle according to some embodiments. The motion planner is configured to construct 310 a graph having multiple nodes defining states of the vehicle. The nodes include an initial node defining the initial state of the vehicle and a target node defining the target state of the vehicle. Each pair of nodes in the graph is connected with an edge defined by one of collision free primitive motions moving the vehicle between the states of the connected nodes.”), the tree structure comprising a root node and an intermediate node (see at least Fig. 3B and [0075]: “In some embodiments, the motion planner constructs 310 the graph using doubletree construction. Specifically, motion planner determines the graph by constructing an initial tree of nodes originating at the initial node and by constructing a target tree of nodes originating at the target node. To construct the initial tree or the target tree, the motion planner is configured to select 315 an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend 320 the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”; [0079]: “FIG. 3B shows a schematic of determining the graph using doubletree construction according to one embodiment. In this example, the graph is constructed from both ends using an initial tree 321, having an initial node 311 corresponding to the initial state 101, and a target tree 322, having a target node 312 corresponding to the target state 102. The initial tree has a node set and an edge set. The target tree also has a node set and an edge set.”);
determining, for the intermediate node, an estimated cost associated with a trajectory passing from the root node to the intermediate node (see at least [0075]: “In some embodiments, the motion planner constructs 310 the graph using doubletree construction. Specifically, motion planner determines the graph by constructing an initial tree of nodes originating at the initial node and by constructing a target tree of nodes originating at the target node. To construct the initial tree or the target tree, the motion planner is configured to select 315 an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend 320 the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”);
determining, based on the estimated cost, whether to expand the intermediate node (see at least [0075]: “In some embodiments, the motion planner constructs 310 the graph using doubletree construction. Specifically, motion planner determines the graph by constructing an initial tree of nodes originating at the initial node and by constructing a target tree of nodes originating at the target node. To construct the initial tree or the target tree, the motion planner is configured to select 315 an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend 320 the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”);
expanding a set of nodes that are deeper than the intermediate node to an end of a period of time (see at least [0076]: “As used herein, the cost of a node is a minimum cost for reaching the target node from the initial node through the node and includes a first cost of a first path through nodes of the initial tree, a second cost of a second path through nodes of the target tree, and a third cost of a third path between nodes of the initial tree and the target tree. In various embodiments, the cost of the node is indicative of one or combination of a travel time of the vehicle from the initial state to the target state through the state of the node, a distance the vehicle travels from the initial state to the target state through the state of the node, a rate of change of a mode of movement of the vehicle traveling from the initial state to the target state through the state of the node.”; [0078]: “Some embodiments take advantage of computational efficiency of double trees space exploration by selecting the node on the initial or target tree to expand. Specifically, some embodiments select an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”);
determining, based at least in part on the tree structure, a trace through the tree structure having a lowest cost (see at least [0079]: “FIG. 3B shows a schematic of determining the graph using doubletree construction according to one embodiment. In this example, the graph is constructed from both ends using an initial tree 321, having an initial node 311 corresponding to the initial state 101, and a target tree 322, having a target node 312 corresponding to the target state 102. The initial tree has a node set and an edge set. The target tree also has a node set and an edge set.”; [0082]: “For example, if all primitive motions that can reduce the cost of the node 313 lead to the obstacles 103, then the node 313 is not expandable, and the embodiments select another node, e.g., a node 331 with cost greater than the cost of the node 313 to expand. If the node 331 is expandable, i.e., there is a collision free motion primitive, such as 336 that reduces the cost of the expandable node 331, the embodiment uses the edge 336 defined by this collision free motion primitive to add to the initial tree 321 a child node 337 that have a cost less than the cost of the node 331.”); and
controlling the vehicle based at least in part on the trace (see at least [0074]: “The motion planner also configured to determine 330 a path through the graph connecting the initial node with the target node, such that the path defines a sequence of primitive motions moving the vehicle from the initial state to the target state; and to transmit 335 the sequence of primitive motions to a controller of the vehicle configured to control the movement of the vehicle using the sequence of primitive motions. Having the graph, the path can be determined using various optimization techniques optimizing a parameter of the path, such as one or combination of its cost and smoothness.”; [0087]: “FIG. 3C shows a block diagram of a method for a motion planning method according to some embodiments. Beginning with the geometry of vehicle, the map of the parking space, and initial and target states, the method first initializes 345 a graph custom-character and outputs an initial graph 350. Based on the initial graph and primitive motions 355, the graph is constructed 360 by repeating two steps: node selection and node expansion using prioritized control actions…Reference trajectory 390 is fed into a control module to control 395 the motion of the vehicle such that the vehicle motion follows the reference trajectory, based on sensed signal 391 such as vehicle's current state.”).
Wang fails to explicitly teach determining, based at least on a machine learned model, an estimated cost associated with a trajectory.
However, Huang teaches a system and method for autonomous vehicle guidance that determines, based at least on a machine learned model, an estimated cost associated with a trajectory (see at least [0036]: “The techniques may comprise determining a total cost of a path based at least in part on the costs associated with the contiguous set of contiguous connections making up the path. In some examples, the cost associated with a connection may comprise a cost indicated by a cost plot and/or may be based at least in part on: a cost associated with the motion primitive connecting the first node to the second node (e.g., the greater the curvature of the motion primitive, the higher cost), a cost associated with a safety margin (e.g., higher cost for bringing the autonomous vehicle closer to an object, may depend on the velocity and/or other kinematics), a cost associated with a difference between the ending position and/or pose associated with a terminus of the motion primitive and a target position and/or pose, a cost associated with a starting position and/or pose of the autonomous vehicle (e.g., a cost associated with a position and/or pose associated with a beginning of the motion primitive and/or the first node and/or a difference between a position and/or pose associated with the first node and the starting position and/or pose), a cost associated with a difference between a motion primitive connecting a first layer and second layer and a motion primitive connecting a previous layer to the first layer, and/or the like. In some examples, at least one of the costs may be based at least in part on a difference between a motion primitive and output generated by a machine-learned model trained to generate steering commands based at least in part on being trained using steering commands generated by human and/or simulated human drivers and/or inferred from observation of human drivers.”; [0128]: “In some instances, the memory 1120 and/or memory 1124 may store a set of motion primitives 1132 and/or cost plot 1134 in association with the set of motion primitives, such as those motion primitives and/or cost plots as described herein. In some examples, memory 1124 may additionally or alternatively store a motion primitives and/or cost plot generator 1136. In some examples, the motion primitives and/or cost plot generator 1136 may comprise a machine-learned (ML) model (e.g., a neural network) and/or a parallel processing component.”).
Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wang to incorporate the teachings of Huang and provide a means to determine, based at least on a machine learned model, an estimated cost associated with a trajectory, with a reasonable expectation of success, in order to utilize the learning model that can be trained and refined overtime to provide more accurate data.
The combination of Wang and Huang fails to explicitly teach expanding a set of nodes to an end of the period of time, the period of time having a predetermined length.
However, Berntorp teaches a system and method for controlling autonomous vehicle expand a set of nodes to an end of a period of time, the period of time having a predetermined length (see at least Fig. 3 and Col. 8, lines 40-55: “FIG. 3 shows a schematic of a tree of state transitions defining the motion of the vehicle according to some embodiments of the invention. The current tree in the drivable space 330 is shown with root node 300 indicating the current state of the vehicle and includes the states as nodes and the state transitions as edges in state space, arising from control inputs chosen according to other embodiments of the invention. For example, edge 321 is the motion generated by applying a control input for a predefined time from root node 300 to state 320. The tree can include a target state 310 and target region 340 of the vehicle. In one embodiment of the invention, there can be several target states 310 and regions 340. A probability can be associated to the control input generating edge 321 and therefore also state 320, which accounts for uncertainties in the models of the vehicle, obstacles, and the environment.”; Col. 11, lines 27-31: “The motion is determined iteratively until a termination condition is met, for example, for a time period or for a predetermined number of iterations. An iteration of the method of FIG. 6A includes the following steps.”).
Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wang and Huang to incorporate the teachings of Berntorp and provide a means to expand a set of nodes to an end of a period of time, the period of time having a predetermined length, with a reasonable expectation of success, in order to expand based on an established set time period and minimize extra computational power.
Regarding claim 16, modified Wang teaches the limitations of claim 14. Wang further teaches refraining from expanding a node of the tree structure that is deeper than the intermediate node in the tree structure based on determining that a corresponding trace fails to reach a termination state (see at least Figs. 3B, 5A-5B, and [0103]: “FIG. 5A shows a flow chart of a method for tuning graph growth parameters 401 for a single tree custom-character.sub.sg of the graph 365 according to principles of some embodiments. The value of the sparsity defining the neighbor of a vehicle state is adjusted 503 according to the length of the expandable node list 502. In particular, if the length of the expandable node list custom-character.sub.sg is below a certain threshold (lower bound), the sparsity defining a distance to a neighbor of a vehicle state is reduced to avoid premature termination of the graph construction (which means no path is feasible). In some embodiments, the sparsity is reduced proportionally and recursively. If the node length goes above another threshold (upper bound), the sparsity is increased proportionally and recursively. The sparsity maintain constants when the length of the node list is between the lower and upper bounds.”; [0109]: “FIG. 5E shows a block diagram of several stop criteria used 404 by some embodiments to terminate the iterative graph construction. In one embodiment, a test is conducted 551 to check whether the added child node is close enough to X.sub.f (reaches a pre-defined neighbor of X.sub.f). In another embodiment, one tries to construct 552 a standard Reeds-Shepp's path between the added child node and X.sub.f and verifies 552 if the Reeds-Shepp's path is collision free. If it is, then the Reeds-Shepp's path is added to the edge set of the graph, and the graph construction stops. The graph construction can terminate if the number of nodes exceeds a threshold, in which case the method fails to find a feasible path between X.sub.0 and X.sub.f.”).
Regarding claim 17, modified Wang teaches the limitations of claim 14. Wang further teaches wherein a first number of intermediate node layers is determined based on at least one of: at least two less than a total number of layers associated with the tree structure, or an amount of available computational resources at a time associated with generating the tree structure (see at least [0130]: “Some embodiments perform a node expansion, in addition to a node selection, in a deterministic manner to reduce the need to explore the space around the node with all possible primitive motions. To that end, an embodiment selects a first collision free primitive motion that reduces the cost of the expandable node, i.e., without testing subsequent primitive motions. To further reduce the computational burden, some embodiments order a set of primitive motions based on similarity of each of the primitive motions to a primitive motion defining an edge of the graph leading to the expandable node and tests the primitive motions in that order. These embodiments encourage smoothness of vehicle movement, as human operator would want, and, in practice, help to reduce the complexity of the constructed graph.”).
Claim Rejections - 35 USC § 103
5. Claims 10-12 and 18-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Wang (US 20200097014, hereinafter Wang) and Huang et al. (US 20210020045, hereinafter Huang) and Berntorp et al. (US 9568915, hereinafter Berntorp) in view of Wang (US 20170323194, hereinafter Wang 194’).
Regarding claim 10, modified Wang teaches the limitations of claim 6. Wang further teaches determining the estimated cost based on a cost associated with reaching the intermediate node (see at least [0075]: “In some embodiments, the motion planner constructs 310 the graph using doubletree construction. Specifically, motion planner determines the graph by constructing an initial tree of nodes originating at the initial node and by constructing a target tree of nodes originating at the target node. To construct the initial tree or the target tree, the motion planner is configured to select 315 an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend 320 the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”); and
determining the estimated cost based on a deviation between a path comprising the intermediate node and a maximum-cost path (see at least [0076]: “As used herein, the cost of a node is a minimum cost for reaching the target node from the initial node through the node and includes a first cost of a first path through nodes of the initial tree, a second cost of a second path through nodes of the target tree, and a third cost of a third path between nodes of the initial tree and the target tree. In various embodiments, the cost of the node is indicative of one or combination of a travel time of the vehicle from the initial state to the target state through the state of the node, a distance the vehicle travels from the initial state to the target state through the state of the node, a rate of change of a mode of movement of the vehicle traveling from the initial state to the target state through the state of the node.”; [0078]: “Some embodiments take advantage of computational efficiency of double trees space exploration by selecting the node on the initial or target tree to expand. Specifically, some embodiments select an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”; [0082]: “For example, if all primitive motions that can reduce the cost of the node 313 lead to the obstacles 103, then the node 313 is not expandable, and the embodiments select another node, e.g., a node 331 with cost greater than the cost of the node 313 to expand. If the node 331 is expandable, i.e., there is a collision free motion primitive, such as 336 that reduces the cost of the expandable node 331, the embodiment uses the edge 336 defined by this collision free motion primitive to add to the initial tree 321 a child node 337 that have a cost less than the cost of the node 331.”).
Wang fails to explicitly teach determining a lower bound for the cost and determining an upper bound for the cost
However, Wang 194’ teaches a method and system for determining a lower bound and an upper bound for a cost for a route (see at least [0016]: “Described herein is a framework using a robust optimization technique for path determination in a stochastic network. In accordance with one aspect, the framework models uncertain costs of the network using a reference point (or nominal value) and upper bound and lower bound parameters of the uncertain costs. The uncertain costs, in one implementation, may be the travel time costs. For example, the framework uses a reference point and upper bound and lower bound parameters to model travel time costs in a traffic network to determine an optimal route. The travel time may be historical data which is collected from the traffic network. Alternatively, the travel time data may be real-time data. The framework solves a robust optimization problem based on the modeled costs and outputs a resultant path based on the solution of the robust optimization problem.”; [0024]: “The historical data may be the recorded information of vehicles. For example, the historical travel data may be recorded data of public transportation systems. In other implementations, the data may be real time data such as real time travel data collected as a commuter completes his or her trip. For example, the real time travel data may be collected via a sensor device mounted on a vehicle on which a commuter rides. Depending on the application, providing other types of data in the data source may also be useful.”).
Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wang to incorporate the teachings of Wang 194’ and provide a means to determine a lower bound and an upper bound for a cost, with a reasonable expectation of success, in order to have a parameter limit on the data in determining an optimal route [0016].
Regarding claim 11, modified Wang teaches the limitations of claim 10. Wang further teaches wherein determining the tree structure comprises:
expanding a node of the tree structure with a respective tree depth value that falls below a threshold range (see at least Figs. 3B, 5A-5B, and [0103]: “FIG. 5A shows a flow chart of a method for tuning graph growth parameters 401 for a single tree custom-character.sub.sg of the graph 365 according to principles of some embodiments. The value of the sparsity defining the neighbor of a vehicle state is adjusted 503 according to the length of the expandable node list 502. In particular, if the length of the expandable node list custom-character.sub.sg is below a certain threshold (lower bound), the sparsity defining a distance to a neighbor of a vehicle state is reduced to avoid premature termination of the graph construction (which means no path is feasible). In some embodiments, the sparsity is reduced proportionally and recursively. If the node length goes above another threshold (upper bound), the sparsity is increased proportionally and recursively. The sparsity maintain constants when the length of the node list is between the lower and upper bounds.”).
Regarding claim 12, modified Wang teaches the limitations of claim 10. Wang further teaches wherein determining the tree structure comprises:
expanding a node of the tree structure that is associated with a predefined action sequence (see at least 3B and [0014]: “For example, one embodiment constructs the graph (or tree) by iteratively selecting a node and expanding the selected node with a finite set of pre-defined primitive motions. The challenge of this method is in determining of how to deterministically identify the node to expand and/or how to deterministically select a motion primitive for expending the node to ensure computational efficiency of the method.”; [0079]: “FIG. 3B shows a schematic of determining the graph using doubletree construction according to one embodiment. In this example, the graph is constructed from both ends using an initial tree 321, having an initial node 311 corresponding to the initial state 101, and a target tree 322, having a target node 312 corresponding to the target state 102. The initial tree has a node set and an edge set. The target tree also has a node set and an edge set.”).
Regarding claim 18, modified Wang teaches the limitations of claim 14. Wang further teaches determining the estimated cost based on a cost associated with reaching the intermediate node (see at least [0075]: “In some embodiments, the motion planner constructs 310 the graph using doubletree construction. Specifically, motion planner determines the graph by constructing an initial tree of nodes originating at the initial node and by constructing a target tree of nodes originating at the target node. To construct the initial tree or the target tree, the motion planner is configured to select 315 an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend 320 the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”); and
determining the estimated cost based on a deviation between a path comprising the intermediate node and a maximum-cost path (see at least [0076]: “As used herein, the cost of a node is a minimum cost for reaching the target node from the initial node through the node and includes a first cost of a first path through nodes of the initial tree, a second cost of a second path through nodes of the target tree, and a third cost of a third path between nodes of the initial tree and the target tree. In various embodiments, the cost of the node is indicative of one or combination of a travel time of the vehicle from the initial state to the target state through the state of the node, a distance the vehicle travels from the initial state to the target state through the state of the node, a rate of change of a mode of movement of the vehicle traveling from the initial state to the target state through the state of the node.”; [0078]: “Some embodiments take advantage of computational efficiency of double trees space exploration by selecting the node on the initial or target tree to expand. Specifically, some embodiments select an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”; [0082]: “For example, if all primitive motions that can reduce the cost of the node 313 lead to the obstacles 103, then the node 313 is not expandable, and the embodiments select another node, e.g., a node 331 with cost greater than the cost of the node 313 to expand. If the node 331 is expandable, i.e., there is a collision free motion primitive, such as 336 that reduces the cost of the expandable node 331, the embodiment uses the edge 336 defined by this collision free motion primitive to add to the initial tree 321 a child node 337 that have a cost less than the cost of the node 331.”).
Wang fails to explicitly teach determining a lower bound for the cost and determining an upper bound for the cost.
However, Wang 194’ teaches a method and system for determining a lower bound and an upper bound for a cost for an optimal route (see at least [0016]: “Described herein is a framework using a robust optimization technique for path determination in a stochastic network. In accordance with one aspect, the framework models uncertain costs of the network using a reference point (or nominal value) and upper bound and lower bound parameters of the uncertain costs. The uncertain costs, in one implementation, may be the travel time costs. For example, the framework uses a reference point and upper bound and lower bound parameters to model travel time costs in a traffic network to determine an optimal route. The travel time may be historical data which is collected from the traffic network. Alternatively, the travel time data may be real-time data. The framework solves a robust optimization problem based on the modeled costs and outputs a resultant path based on the solution of the robust optimization problem.”; [0024]: “The historical data may be the recorded information of vehicles. For example, the historical travel data may be recorded data of public transportation systems. In other implementations, the data may be real time data such as real time travel data collected as a commuter completes his or her trip. For example, the real time travel data may be collected via a sensor device mounted on a vehicle on which a commuter rides. Depending on the application, providing other types of data in the data source may also be useful.”).
Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wang to incorporate the teachings of Wang 194’ and provide a means to determine a lower bound and an upper bound for a cost, with a reasonable expectation of success, in order to have a parameter limit on the data in determining an optimal route [0016].
Regarding claim 19, modified Wang teaches the limitations of claim 18. Wang further teaches wherein determining the tree structure comprises:
expanding a node of the tree structure with a respective tree depth value that falls below a threshold range (see at least Figs. 3B, 5A-5B, and [0103]: “FIG. 5A shows a flow chart of a method for tuning graph growth parameters 401 for a single tree custom-character.sub.sg of the graph 365 according to principles of some embodiments. The value of the sparsity defining the neighbor of a vehicle state is adjusted 503 according to the length of the expandable node list 502. In particular, if the length of the expandable node list custom-character.sub.sg is below a certain threshold (lower bound), the sparsity defining a distance to a neighbor of a vehicle state is reduced to avoid premature termination of the graph construction (which means no path is feasible). In some embodiments, the sparsity is reduced proportionally and recursively. If the node length goes above another threshold (upper bound), the sparsity is increased proportionally and recursively. The sparsity maintain constants when the length of the node list is between the lower and upper bounds.”).
Regarding claim 20, modified Wang teaches the limitations of claim 18. Wang further teaches wherein determining the tree structure comprises:
expanding a node of the tree structure that is associated with a predefined action sequence (see at least 3B and [0014]: “For example, one embodiment constructs the graph (or tree) by iteratively selecting a node and expanding the selected node with a finite set of pre-defined primitive motions. The challenge of this method is in determining of how to deterministically identify the node to expand and/or how to deterministically select a motion primitive for expending the node to ensure computational efficiency of the method.”; [0079]: “FIG. 3B shows a schematic of determining the graph using doubletree construction according to one embodiment. In this example, the graph is constructed from both ends using an initial tree 321, having an initial node 311 corresponding to the initial state 101, and a target tree 322, having a target node 312 corresponding to the target state 102. The initial tree has a node set and an edge set. The target tree also has a node set and an edge set.”).
Claim Rejections - 35 USC § 103
6. Claim 13 is/are rejected under 35 U.S.C. 103 as being unpatentable over Wang (US 20200097014, hereinafter Wang) and Huang et al. (US 20210020045, hereinafter Huang) and Berntorp et al. (US 9568915, hereinafter Berntorp) in view of Bagnell et al. (US 20240166237, hereinafter Bagnell).
Regarding claim 13, modified Wang teaches the limitations of claim 6.
Wang fails to explicitly teach wherein the estimated cost is determined based on at least one of: environment state data representing a state characteristic of an environment of the vehicle at a first predicted state associated with the intermediate node; or object data representing a characteristic of at least one of a dynamic object or the vehicle at the first predicted state.
However, Bagnell teaches a method and system for multistage autonomous vehicle motion planning that comprises an estimated cost that is determined based on at least one of: environment state data representing a state characteristic of an environment of the vehicle at a first predicted state associated with the intermediate node; or object data representing a characteristic of at least one of a dynamic object or the vehicle at the first predicted state (see at least Fig. 1 and [0077]: “In some implementations, the planning system 250 can perform interactive forecasting. The planning system 250 can determine a motion plan for an autonomous platform with an understanding of how forecasted future states of the environment can be affected by execution of one or more candidate motion plans. By way of example, with reference again to FIG. 1, the autonomous platform 110 can determine candidate motion plans corresponding to a set of platform trajectories 112A-C that respectively correspond to the first actor trajectories 122A-C for the first actor 120, trajectories 132 for the second actor 130, and trajectories 142 for the third actor 140 (e.g., with respective trajectory correspondence indicated with matching line styles). For instance, the autonomous platform 110 (e.g., using its autonomy system 200) can forecast that a platform trajectory 112A to more quickly move the autonomous platform 110 into the area in front of the first actor 120 is likely associated with the first actor 120 decreasing forward speed and yielding more quickly to the autonomous platform 110 in accordance with first actor trajectory 122A. Additionally or alternatively, the autonomous platform 110 can forecast that a platform trajectory 112B to gently move the autonomous platform 110 into the area in front of the first actor 120 is likely associated with the first actor 120 slightly decreasing speed and yielding slowly to the autonomous platform 110 in accordance with first actor trajectory 122B. Additionally or alternatively, the autonomous platform 110 can forecast that a platform trajectory 112C to remain in a parallel alignment with the first actor 120 is likely associated with the first actor 120 not yielding any distance to the autonomous platform 110 in accordance with first actor trajectory 122C. Based on comparison of the forecasted scenarios to a set of desired outcomes (e.g., by scoring scenarios based on a cost or reward), the planning system 250 can select a motion plan (and its associated trajectory) in view of the autonomous platform's interaction with the environment 100. In this manner, for example, the autonomous platform 110 can interleave its forecasting and motion planning functionality.”).
Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wang to incorporate the teachings of Bagnell and provide an estimated cost that is determined based on at least one of: environment state data representing a state characteristic of an environment of the vehicle at a first predicted state associated with the intermediate node; or object data representing a characteristic of at least one of a dynamic object or the vehicle at the first predicted state, with a reasonable expectation of success, in order to take into consideration the surrounding of the vehicle when making a motion plan decision.
Claim Rejections - 35 USC § 103
7. Claims 21-22 is/are rejected under 35 U.S.C. 103 as being unpatentable over Wang (US 20200097014, hereinafter Wang) and Huang et al. (US 20210020045, hereinafter Huang) and Berntorp et al. (US 9568915, hereinafter Berntorp) in view of Serree (US 20050119825, hereinafter Serree).
Regarding claim 21, modified Wang teaches the limitations of claim 1. Wang further teaches wherein determining the estimated cost and determining whether to expand the intermediate node is based on determining that the intermediate node is associated with the tree structure (see at least [0075]: “In some embodiments, the motion planner constructs 310 the graph using doubletree construction. Specifically, motion planner determines the graph by constructing an initial tree of nodes originating at the initial node and by constructing a target tree of nodes originating at the target node. To construct the initial tree or the target tree, the motion planner is configured to select 315 an expandable node in the initial tree or the target tree based on a cost of the expandable node, and expend 320 the graph by adding a child node connected to the expandable node with an edge defined by a collision free primitive motion, such that a cost of the child node is less than the cost of the expandable node.”).
Wang fails to explicitly teach determining whether to expand based on determining that the node is associated with one of a predefined set of intermediate levels of the tree structure.
However, Serree teaches a method and apparatus for determining a minimal cost path between two points of a road network that determines whether to expand based on determining that a node is associated with one of a predefined set of intermediate levels of a tree structure (see at least Fig. 3 and [0028]: “during the development of at least one of the two graphs, the number of segments of the graph which belong to the lowest level m.sub.inf is calculated; and”; [0029]: “starting from a predefined threshold of number of segments of level m.sub.inf, the graph is developed taking into account only the segments which belong to the levels which are strictly higher than the level m.sub.inf.”; [0030]: “Thus, when the graph contains a number of segments of level m.sub.inf which is higher than the threshold, there is transition from the level m.sub.inf to the following level m.sub.inf+1 and the development of the graph is continued by taking into account only the segments with a level higher than, or equal to, the level m.sub.inf. This therefore reduces considerably the number of calculations, and consequently the calculation time.”).
Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wang to incorporate the teachings of Serree and provide means to determine that the node is associated with one of a predefined set of intermediate levels of the tree structure, with a reasonable expectation of success, in order to determine when to expand based on a predefined variable to reduce the number of calculations and consequently calculation time.
Regarding claim 22, modified Wang teaches the limitations of claim 21. Wang further teaches based on a state of the tree structure after selectively expand nodes associated with the intermediate levels, determining a set of costs associated with a set of trajectories represented by the state (see at least [0070]: “For example, in one embodiment, the reference trajectory defines profiles of the vehicle velocity and steer angle over time. In another embodiment, the reference trajectory defines the profile of the vehicle state (x, y, θ) over time.”; [0071]: “The motion-planner transmits the reference trajectory determined by the sequence of primitive motions to controller 204 of the vehicle.”; [0076]: “As used herein, the cost of a node is a minimum cost for reaching the target node from the initial node through the node and includes a first cost of a first path through nodes of the initial tree, a second cost of a second path through nodes of the target tree, and a third cost of a third path between nodes of the initial tree and the target tree.”);
determining a first trajectory of the set of trajectories based on the set of costs (see at least [0082]: “For example, if all primitive motions that can reduce the cost of the node 313 lead to the obstacles 103, then the node 313 is not expandable, and the embodiments select another node, e.g., a node 331 with cost greater than the cost of the node 313 to expand. If the node 331 is expandable, i.e., there is a collision free motion primitive, such as 336 that reduces the cost of the expandable node 331, the embodiment uses the edge 336 defined by this collision free motion primitive to add to the initial tree 321 a child node 337 that have a cost less than the cost of the node 331.”); and
expanding a subtree associated with the first trajectory until the end of the period of time (see at least [0071]: “The motion-planner transmits the reference trajectory determined by the sequence of primitive motions to controller 204 of the vehicle.”; [0076]: “As used herein, the cost of a node is a minimum cost for reaching the target node from the initial node through the node and includes a first cost of a first path through nodes of the initial tree, a second cost of a second path through nodes of the target tree, and a third cost of a third path between nodes of the initial tree and the target tree. In various embodiments, the cost of the node is indicative of one or combination of a travel time of the vehicle from the initial state to the target state through the state of the node, a distance the vehicle travels from the initial state to the target state through the state of the node, a rate of change of a mode of movement of the vehicle traveling from the initial state to the target state through the state of the node.”).
Wang fails to explicitly teach expanding nodes associated with the predefined set of intermediate levels.
However, Serree teaches a method and apparatus for determining a minimal cost path between two points of a road network that expand nodes associated with a predefined set of intermediate levels (see at least Fig. 3 and [0028]: “during the development of at least one of the two graphs, the number of segments of the graph which belong to the lowest level m.sub.inf is calculated; and”; [0029]: “starting from a predefined threshold of number of segments of level m.sub.inf, the graph is developed taking into account only the segments which belong to the levels which are strictly higher than the level m.sub.inf.”; [0030]: “Thus, when the graph contains a number of segments of level m.sub.inf which is higher than the threshold, there is transition from the level m.sub.inf to the following level m.sub.inf+1 and the development of the graph is continued by taking into account only the segments with a level higher than, or equal to, the level m.sub.inf. This therefore reduces considerably the number of calculations, and consequently the calculation time.”).
Therefore, it would have been obvious to someone of ordinary skill in the art before the effective filing date of the claimed invention to have modified Wang to incorporate the teachings of Serree and provide means to expand nodes associated with a predefined set of intermediate levels, with a reasonable expectation of success, in order to determine when to expand based on a predefined variable to reduce the number of calculations and consequently calculation time.
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any extension fee pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to TIEN MINH LE whose telephone number is (571)272-3903. The examiner can normally be reached Monday to Friday (8:30am-5:30pm eastern time).
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, Khoi Tran can be reached on (571)272-6919. 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.
/T.M.L./Examiner, Art Unit 3656
/KHOI H TRAN/Supervisory Patent Examiner, Art Unit 3656