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 .
Priority
Receipt is acknowledged of certified copies of papers required by 37 CFR 1.55. Priority is being given to 09/04/2023.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 05/13/2024 and 10/21/2024 is/are in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Status of Claims
This action is in reply to the application filed on 05/13/2024.
Claims 1-20 are currently pending and have been examined.
Claims 1-20 are currently rejected.
This action is made NON-FINAL.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claim(s) 1-4, 6- is/are rejected under 35 U.S.C. 103 as being unpatentable over Garimella et. al. (US 2022/0274625), herein Garimella in view of Floyd-Jones et. al. (US 2020/0377085), herein Floyd-Jones.
Regarding claim 1:
Garimella teaches:
A processor-implemented method (The processor(s) 216 of the vehicle 202 and the processor(s) 242 of the computing device(s) 240 can be any suitable processor capable of executing instructions to process data and perform operations as described herein [0062]), the method comprising:
embedding sensing information, from a plurality of sensors (one or more sensor systems 206 [0032]), at a current time point (based on the data currently perceived by the autonomous vehicle [0025]) with a previous path of a vehicle at a previous time point (objects within the environment that were previously perceived by the autonomous vehicle but may be temporarily occluded from the sensors of the autonomous vehicle at the current time, may be retained within the GNN and/or may be updated based on the prediction data determined from the previous GNN [0025]) and topology information (map data can include any number of data structures, modeled in two or more dimensions that are capable of providing information about an environment, such as, but not limited to, topologies, intersections, streets, roads, terrain, and the environment in general [0013]) for a topology including plural nodes at the previous time point (certain object nodes, attributes, and/or edge data may be preserved from a previous version of the GNN [0025]);
determining, by inputting the embedded sensing information to a topology-based neural network (may generate and use a graph neural network (GNN) that includes a combination of vectorized map element nodes and/or entity nodes [0010]), a first distribution area (a GNN including nodes representing map element objects and entity objects within the environment of the vehicle 202 [0045]) and [a second distribution area within a search area], where the first distribution area includes a determined feasible path (planning component 236 can generate an instruction for guiding the autonomous vehicle along at least a portion of the route from the first location to the second location [0048]) and the second distribution area includes disconnected nodes that are determined to be reconnected or rewired (may create new nodes within the GNN, remove nodes from the GNN, and/or modify existing nodes of the GNN based on the received map data and/or entity data [0020]) due to an obstacle (the map data may depict these and other types of permanent or semi-permanent map elements (e.g., road closures, road damage, construction sites, accidents, etc.), but might not include impermanent objects such other vehicles, bicycles, and pedestrians in the environment, or temporary road features such as disabled vehicles, road hazards, or short-term construction projects [0014]); and
generating a current path at the current time point from a target location of the vehicle to a current position of the vehicle (the planning component 236 can determine a route to travel from a first location (e.g., a current location) to a second location (e.g., a target location). For the purpose of this discussion, a route can be a sequence of waypoints for travelling between two locations [0048]) using topology information at the current time point determined based on the determining (the planning component 236 can generate one or more trajectories for the vehicle 202 based at least in part on predicted location(s) associated with object(s) in an environment [0049]).
Floyd-Jones also teaches:
A processor-implemented method (such operations may be performed entirely in hardware circuitry or as software stored in a memory storage, such as system memory 214, and executed by one or more hardware processors 212a [01008]), the method comprising:
embedding sensing information, from a plurality of sensors, at a current time point (One or more sensors 282, an object detector 284, an object behavior predictor 286 and an actuator system 266 are also communicatively coupled to the motion planner 280 [0113]) with a previous path of a vehicle at a previous time point (the current and past positions of all of the agents A.sub.j and the primary agent are provided as inputs to the probabilistic behavioral models [0221])
generating a current path at the current time point from a target location of the vehicle to a current position of the vehicle using topology information at the current time point determined based on the determining (the motion planner 280 performs an optimization to identify a path 512 in the resulting planning lattice 500 that provides a route of travel of the primary agent 102 as specified by the path with a relatively low potential of a collision with dynamic obstacle B 112. [0157]).
Garimella does not explicitly teaches, however Floyd-Jones teaches:
a first distribution area (fig. 5, area of path 510) and a second distribution area (fig. 5, area of path 520) within a search area (fig. 5, area 500), where the first distribution area includes a determined feasible path (a first least-cost path from node no to goal (node n.sub.15) which passes through candidate nodes n.sub.4, n.sub.9, n.sub.13 and n.sub.16 [0171]) and the second distribution area includes disconnected nodes that are determined to be reconnected or rewired (a second least-cost path from node no to goal which passes through candidate nodes n.sub.5, n.sub.10, n.sub.14, and n.sub.16 (also shown in bolded line) [0171]; see fig. 5, n14 to n15 through n16; examiner notes that c14,15 is disconnected due to obstacle and the path is rewired though node n16) due to an obstacle (a static obstacle (e.g., edge between n.sub.14 and n.sub.15) [0166]); and
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Garimella to include the teachings as taught by Floyd-Jones with a reasonable expectation of success. Both arts are in the same field of endeavor of controlling motion planning of an autonomous vehicle. Floyd-Jones teaches the benefit of “A trajectory of a primary agent and/or dynamic obstacle may advantageously be represented by respective sets of fitted functions (e.g., fitted polynomial functions), for instance in lieu of motion equations. Fitted functions may advantageously require less computational expense when performing collision assessment than motion equations for example by avoiding the need to evaluate trigonometric functions [Floyd-Jones, 0005]”.
Regarding claim 2:
Garimella in view of Floyd-Jones teaches all the limitations of claim 1, upon which this claim is dependent.
Garimella further teaches:
wherein the embedding comprises: reordering the topology information at the previous time point (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]) based on previous path nodes corresponding to the previous path at the previous time point (the GNN may fully or partially preserve its state during subsequent executions of the GNN generation process, in which certain object nodes, attributes, and/or edge data may be preserved from a previous version of the GNN while other data is updated [0025]); and
embedding the reordered topology information with the sensing information at the current time point (create new nodes within the GNN, remove nodes from the GNN, and/or modify existing nodes of the GNN based on the received map data and/or entity data [0020]; the autonomous vehicle 402 perceives new entities within its environment, it may classify the entities, generate vectorized representations of the entities, and store the representations as nodes in the graph structure 400 [0077]).
Regarding claim 3:
Garimella in view of Floyd-Jones teaches all the limitations of claim 2, upon which this claim is dependent.
Garimella further teaches:
wherein the reordering of the topology information at the previous time point (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment. [0077]) comprises assigning a weight to paths, comprised in the topology information at the previous time point, based on a distance from the previous path at the previous time point (the GNN component 232 may perform a horizon-culling function in some cases, in which nodes greater than a certain distance away from the autonomous vehicle 402, and/or nodes having an edge weight value less than a threshold value with respect to the autonomous vehicle 402, are removed from the graph structure 400. In such cases, the GNN component 232 may periodically analyze the edge features connected to the autonomous vehicle 402 to determine the weight values and/or relative distances of each object from the autonomous vehicle 402, and may remove any nodes representing objects less than threshold relevance metric (e.g., using the weight value) and/or farther than a threshold distance away from the autonomous vehicle 402 [0078]).
Regarding claim 4:
Garimella in view of Floyd-Jones teaches all the limitations of claim 2, upon which this claim is dependent.
Garimella further teaches:
wherein the topology-based neural network comprises one or more of a first head (the planning component 236 to determine a location of the vehicle 202, identify objects in an environment, and/or generate routes and/or trajectories to navigate within an environment [0037]), a second head (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]), and a third head (a horizon-culling function [0078]), the one or more first head, second head, and third head each being respectively trained to output a respective sampling area corresponding to the first distribution area (a GNN including nodes representing map element objects and entity objects within the environment of the vehicle 202 [0045]), the second distribution area (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]), and a third distribution area (a horizon-culling function in some cases, in which nodes greater than a certain distance away from the autonomous vehicle 402, and/or nodes having an edge weight value less than a threshold value with respect to the autonomous vehicle 402, are removed from the graph structure 400 [0078]), the third distribution area including determined prune-eligible nodes which are to be pruned in response to the reordered topology information and the sensing information being received by the topology-based neural network (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]).
Floyd-Jones further teaches:
wherein the topology-based neural network comprises one or more of a first head (the motion planner 280 performs an optimization to identify a path 512 in the resulting planning lattice 500 that provides a route of travel of the primary agent 102 as specified by the path with a relatively low potential of a collision with dynamic obstacle B 112. [0157]), a second head (a second least-cost path from node no to goal which passes through candidate nodes n.sub.5, n.sub.10, n.sub.14, and n.sub.16 (also shown in bolded line) [0171]; see fig. 5, n14 to n15 through n16; examiner notes that c14,15 is disconnected due to obstacle and the path is rewired though node n16), and [a third head], the one or more first head, second head, and third head each being respectively trained to output a respective sampling area corresponding to the first distribution area (fig. 5, area of path 510), the second distribution area (fig. 5, area of path 520)
Regarding claim 6:
Garimella in view of Floyd-Jones teaches all the limitations of claim 1, upon which this claim is dependent.
Garimella further teaches:
wherein the topology information at the previous time point comprises information on expanded nodes that were expanded up until the previous time point (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]).
Regarding claim 7:
Garimella in view of Floyd-Jones teaches all the limitations of claim 1, upon which this claim is dependent.
Garimella further teaches:
wherein the sensing information at the current time point comprises one or more of surrounding environment information on a surrounding object of the vehicle and an obstacle around the vehicle (the autonomous vehicle may perceive additional objects in the environment, including entities such as other dynamic objects (e.g., vehicles, bicycles, pedestrians, etc.) moving or operating in the environment [0018]), a current location of the vehicle (a current location [0048]), and the target location of the vehicle (a target location [0048]), and wherein the method further comprises: receiving the surrounding environment information from a sensor (the sensor system(s) 206 can include time of flight sensors, lidar sensors, radar sensors, ultrasonic transducers, sonar sensors, location sensors (e.g., GPS, compass, etc.), inertial sensors (e.g., inertial measurement units (IMUs), accelerometers, magnetometers, gyroscopes, etc.), cameras (e.g., RGB, IR, intensity, depth, etc.), microphones, wheel encoders, environment sensors (e.g., temperature sensors, humidity sensors, light sensors, pressure sensors, etc.), etc [0051]) or capturing an image of the surrounding environment information from an image sensor (the camera sensors can include multiple cameras disposed at various locations about the exterior and/or interior of the vehicle 202 [0051]).
Regarding claim 8:
Garimella in view of Floyd-Jones teaches all the limitations of claim 1, upon which this claim is dependent.
Garimella further teaches:
wherein the determining of the first distribution area and the second distribution area comprises: expanding one or more of the plural nodes (Nodes and/or edges may be added [0077]) according to a determined feasible path found in the first distribution area (generate routes and/or trajectories to navigate within an environment [0037]); and
Floyd-Jones further teaches:
rewiring one or more of the plural nodes that are determined to be disconnected, in which the plural nodes are determined to be disconnected or newly connected, in the second distribution area (a second least-cost path from node no to goal which passes through candidate nodes n.sub.5, n.sub.10, n.sub.14, and n.sub.16 (also shown in bolded line) [0171]; see fig. 5, n14 to n15 through n16; examiner notes that c14,15 is disconnected due to obstacle and the path is rewired though node n16) based on the topology information at the previous time point and the sensing information at the current time point (at time T=i+1, the candidate node n′ with the lowest average cost becomes the current node n for the next time step, T=i+2 [0172]).
Regarding claim 9:
Garimella in view of Floyd-Jones teaches all the limitations of claim 8, upon which this claim is dependent.
Garimella further teaches:
performing second sampling on the determined feasible path randomly in an entirety of the search area (Random Forest) [0061]); and
performing the expanding of one or more of the plural nodes based on a first sampling result and a second sampling result (a GNN component within the autonomous vehicle may receive vectorized representations of objects (e.g., map elements and/or entities) from the vectorization component, and may create new nodes within the GNN [0020]).
Floyd-Jones further teaches:
wherein the expanding of the plural nodes comprises: performing first sampling on the determined feasible path non-uniformly in the first distribution area (The assumed or inferred intentions may be sampled, e.g., using behavioral models based on probabilistic functions, to produce a trajectory t for each agent A.sub.j, resulting in a set S of trajectories [0169]);
Regarding claim 10:
Garimella in view of Floyd-Jones teaches all the limitations of claim 8, upon which this claim is dependent.
Garimella further teaches:
wherein, in a third distribution area, the identified prune-eligible nodes are pruned from the topology upon a determination that one or more of the plural nodes are irrelevant to a moving path of the vehicle (the GNN component 232 may periodically analyze the edge features connected to the autonomous vehicle 402 to determine the weight values and/or relative distances of each object from the autonomous vehicle 402, and may remove any nodes representing objects less than threshold relevance metric (e.g., using the weight value) and/or farther than a threshold distance away from the autonomous vehicle 402 [0078]), and wherein the prune-eligible nodes are identified based on the third distribution area, from the topology information at the previous time point (the autonomous vehicle 402 may identify map elements and generate vectorized representations of the map elements, which may be stored as nodes in the graph structure 400 of a GNN [0077]).
Regarding claim 11:
Garimella in view of Floyd-Jones teaches all the limitations of claim 10, upon which this claim is dependent.
Garimella further teaches:
wherein the prune-eligible nodes comprise one or more of: a first node in an area where the vehicle has passed at the current time point (the GNN component 232 may perform a horizon-culling function in some cases, in which nodes greater than a certain distance away from the autonomous vehicle 402 [0078]); and
a second node in an area irrelevant to a moving path of the vehicle (remove any nodes representing objects less than threshold relevance metric (e.g., using the weight value) [0078]).
Regarding claim 12:
Garimella in view of Floyd-Jones teaches all the limitations of claim 8, upon which this claim is dependent.
Floyd-Jones further teaches:
further comprising: assigning objects observed in the second distribution area to be objects of interest (Based at least in part on the current detected trajectory of the dynamic obstacle (104, 112) in the environment 100 as indicated by the trajectory information 308, object behavior predictor 286 generates one or more predicted trajectories of the dynamic obstacle (104, 112) and communicates this information as part of the predicted trajectory information 306 to the motion planner 280. For example, if the trajectory information 308 indicates dynamic obstacle A 104 is currently on a trajectory heading in a particular direction, the object behavior predictor 286 may predict with 40% probability that dynamic obstacle A 104 will continue in its current trajectory, with 60% probability it does something else. [0132]) by identifying location information of the vehicle changed from the current path at the current time point based on the sensing information of the current time point and the one or more rewired nodes (Once all edge weights of the planning lattice have been adjusted, the path optimizer 292 performs a least cost path algorithm from the current position of the primary agent 102 indicated in the planning lattice to possible next states or goal states of the primary agent 102. The least cost path in the planning lattice is typically then selected by the motion planner 280 [0145]).
Regarding claim 13:
Garimella in view of Floyd-Jones teaches all the limitations of claim 1, upon which this claim is dependent.
Garimella further teaches:
further comprising: iteratively finding the current path at the current time point from the target location of the vehicle to a moved current location of the vehicle as the vehicle moves (the planning component 236 can determine a route to travel from a first location (e.g., a current location) to a second location (e.g., a target location) [0048]; the maps 224 can be used in connection with the localization component 220, the perception component 222, the prediction component 228, and/or the planning component 236 to determine a location of the vehicle 202, identify objects in an environment, and/or generate routes and/or trajectories to navigate within an environment [0037]).
Regarding claim 14:
Garimella teaches:
A training method of a neural network (the GNN component 232 and/or entity prediction component 234 can be trained by based on driving data logs to determine the behaviors, movements, and/or interactions between objects in the environment, including behaviors and interactions between entities and map elements, and between entities and other entities [0047]), the method comprising:
receiving a training data set comprising sensing information of a vehicle at a previous time point (objects within the environment that were previously perceived by the autonomous vehicle but may be temporarily occluded from the sensors of the autonomous vehicle at the current time, may be retained within the GNN and/or may be updated based on the prediction data determined from the previous GNN [0025]), topology information for a topology including plural nodes at the previous time point (map data can include any number of data structures, modeled in two or more dimensions that are capable of providing information about an environment, such as, but not limited to, topologies, intersections, streets, roads, terrain, and the environment in general [0013]), a first area including a feasible path at a current time point corresponding to the topology information at the previous time point (a GNN including nodes representing map element objects and entity objects within the environment of the vehicle 202 [0045]),
and a third area in which prune-eligible nodes of the plural nodes are to be pruned as being irrelevant to a moving path of the vehicle at the current time point (a horizon-culling function in some cases, in which nodes greater than a certain distance away from the autonomous vehicle 402, and/or nodes having an edge weight value less than a threshold value with respect to the autonomous vehicle 402, are removed from the graph structure 400 [0078]); and
training the neural network to output one or more sampling areas, the sampling areas including a first distribution area including the feasible path (the planning component 236 to determine a location of the vehicle 202, identify objects in an environment, and/or generate routes and/or trajectories to navigate within an environment [0037]), a second distribution area including the blocked nodes (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]), and a third distribution area including the prune-eligible nodes based on the training data set (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]).
Floyd-Jones also teaches:
training the neural network to output one or more sampling areas, the sampling areas including a first distribution area including the feasible path (the motion planner 280 performs an optimization to identify a path 512 in the resulting planning lattice 500 that provides a route of travel of the primary agent 102 as specified by the path with a relatively low potential of a collision with dynamic obstacle B 112. [0157]), a second distribution area including the blocked nodes (a second least-cost path from node no to goal which passes through candidate nodes n.sub.5, n.sub.10, n.sub.14, and n.sub.16 (also shown in bolded line) [0171]; see fig. 5, n14 to n15 through n16; examiner notes that c14,15 is disconnected due to obstacle and the path is rewired though node n16), and a third distribution area including the prune-eligible nodes based on the training data set (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]).
Garimella does not explicitly teaches, however Floyd-Jones teaches:
a second area in which blocked nodes of the plural nodes are determined for rewiring due to an obstacle at the current time point (a second least-cost path from node no to goal which passes through candidate nodes n.sub.5, n.sub.10, n.sub.14, and n.sub.16 (also shown in bolded line) [0171]; see fig. 5, n14 to n15 through n16; examiner notes that c14,15 is disconnected due to obstacle and the path is rewired though node n16)
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Garimella to include the teachings as taught by Floyd-Jones with a reasonable expectation of success. Both arts are in the same field of endeavor of controlling motion planning of an autonomous vehicle. Floyd-Jones teaches the benefit of “A trajectory of a primary agent and/or dynamic obstacle may advantageously be represented by respective sets of fitted functions (e.g., fitted polynomial functions), for instance in lieu of motion equations. Fitted functions may advantageously require less computational expense when performing collision assessment than motion equations for example by avoiding the need to evaluate trigonometric functions [Floyd-Jones, 0005]”.
Regarding claim 15:
Garimella in view of Floyd-Jones teaches all the limitations of claim 14, upon which this claim is dependent.
Garimella further teaches:
wherein the neural network comprises a first head (the planning component 236 to determine a location of the vehicle 202, identify objects in an environment, and/or generate routes and/or trajectories to navigate within an environment [0037]), a second head (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]), and a third head (a horizon-culling function [0078]), the first head, the second head, and the third head being respectively trained to output respective sampling areas corresponding to the first distribution area (a GNN including nodes representing map element objects and entity objects within the environment of the vehicle 202 [0045]), the second distribution area (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]), and the third distribution area (a horizon-culling function in some cases, in which nodes greater than a certain distance away from the autonomous vehicle 402, and/or nodes having an edge weight value less than a threshold value with respect to the autonomous vehicle 402, are removed from the graph structure 400 [0078]) in response to the topology information in which the nodes are rewired and the sensing information at the current time point being received by the neural network (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]).
Floyd-Jones further teaches:
a first head (the motion planner 280 performs an optimization to identify a path 512 in the resulting planning lattice 500 that provides a route of travel of the primary agent 102 as specified by the path with a relatively low potential of a collision with dynamic obstacle B 112. [0157]), a second head (a second least-cost path from node no to goal which passes through candidate nodes n.sub.5, n.sub.10, n.sub.14, and n.sub.16 (also shown in bolded line) [0171]; see fig. 5, n14 to n15 through n16; examiner notes that c14,15 is disconnected due to obstacle and the path is rewired though node n16), and [a third head], the one or more first head, second head, and third head each being respectively trained to output a respective sampling area corresponding to the first distribution area (fig. 5, area of path 510), the second distribution area (fig. 5, area of path 520)
Regarding claim 17:
Garimella teaches:
An electronic apparatus (The processor(s) 216 of the vehicle 202 and the processor(s) 242 of the computing device(s) 240 can be any suitable processor capable of executing instructions to process data and perform operations as described herein [0062]), the apparatus comprising:
processors configured to execute instructions (The processor(s) 216 of the vehicle 202 and the processor(s) 242 of the computing device(s) 240 can be any suitable processor capable of executing instructions to process data and perform operations as described herein [0062]);
a plurality of sensors configured to sense sensing information at a current time point (one or more sensor systems 206 [0032]);
and a memory storing the instructions (The memory 218 [0036]), wherein execution of the instructions configures the processors to:
embed the sensing information at the current time point (based on the data currently perceived by the autonomous vehicle [0025]) with a previous path of a vehicle at a previous time point (objects within the environment that were previously perceived by the autonomous vehicle but may be temporarily occluded from the sensors of the autonomous vehicle at the current time, may be retained within the GNN and/or may be updated based on the prediction data determined from the previous GNN [0025]) and topology information (map data can include any number of data structures, modeled in two or more dimensions that are capable of providing information about an environment, such as, but not limited to, topologies, intersections, streets, roads, terrain, and the environment in general [0013]) of a topology including plural nodes at the previous time point (certain object nodes, attributes, and/or edge data may be preserved from a previous version of the GNN [0025]),
determine, by inputting the embedded sensing information to a topology-based neural network (may generate and use a graph neural network (GNN) that includes a combination of vectorized map element nodes and/or entity nodes [0010]), a first distribution area (a GNN including nodes representing map element objects and entity objects within the environment of the vehicle 202 [0045]) and [a second distribution area within a search area], and a third distribution area within a search area, where the first distribution area includes a determined feasible path (planning component 236 can generate an instruction for guiding the autonomous vehicle along at least a portion of the route from the first location to the second location [0048]), the second distribution area includes disconnected nodes that are determined to be reconnected or rewired (may create new nodes within the GNN, remove nodes from the GNN, and/or modify existing nodes of the GNN based on the received map data and/or entity data [0020]) due to an obstacle (the map data may depict these and other types of permanent or semi-permanent map elements (e.g., road closures, road damage, construction sites, accidents, etc.), but might not include impermanent objects such other vehicles, bicycles, and pedestrians in the environment, or temporary road features such as disabled vehicles, road hazards, or short-term construction projects [0014]), and the third distribution area (a horizon-culling function in some cases, in which nodes greater than a certain distance away from the autonomous vehicle 402, and/or nodes having an edge weight value less than a threshold value with respect to the autonomous vehicle 402, are removed from the graph structure 400 [0078]) includes prune-eligible nodes that are determined to be pruned from the topology as being irrelevant to a moving path of the vehicle (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]), and
generate a current path at the current time point from a target location of the vehicle to a current position of the vehicle (the planning component 236 can determine a route to travel from a first location (e.g., a current location) to a second location (e.g., a target location). For the purpose of this discussion, a route can be a sequence of waypoints for travelling between two locations [0048]) using topology information at the current time point determined based on the first distribution area (the planning component 236 can generate one or more trajectories for the vehicle 202 based at least in part on predicted location(s) associated with object(s) in an environment [0049]), the second distribution area, and the third distribution area.
Floyd-Jones also teaches:
embed the sensing information at the current time point (One or more sensors 282, an object detector 284, an object behavior predictor 286 and an actuator system 266 are also communicatively coupled to the motion planner 280 [0113]) with a previous path of a vehicle at a previous time point (the current and past positions of all of the agents A.sub.j and the primary agent are provided as inputs to the probabilistic behavioral models [0221])
generate a current path at the current time point from a target location of the vehicle to a current position of the vehicle using topology information at the current time point determined based on the first distribution area, the second distribution area (the motion planner 280 performs an optimization to identify a path 512 in the resulting planning lattice 500 that provides a route of travel of the primary agent 102 as specified by the path with a relatively low potential of a collision with dynamic obstacle B 112. [0157]), and the third distribution area.
Garimella does not explicitly teaches, however Floyd-Jones teaches:
determine, by inputting the embedded sensing information to a topology-based neural network, a first distribution area (fig. 5, area of path 510), a second distribution area (fig. 5, area of path 520), and a third distribution area within a search area (fig. 5, area 500), where the first distribution area includes a determined feasible path (a first least-cost path from node no to goal (node n.sub.15) which passes through candidate nodes n.sub.4, n.sub.9, n.sub.13 and n.sub.16 [0171]), the second distribution area includes disconnected nodes that are determined to be reconnected or rewired (a second least-cost path from node no to goal which passes through candidate nodes n.sub.5, n.sub.10, n.sub.14, and n.sub.16 (also shown in bolded line) [0171]; see fig. 5, n14 to n15 through n16; examiner notes that c14,15 is disconnected due to obstacle and the path is rewired though node n16) due to an obstacle (a static obstacle (e.g., edge between n.sub.14 and n.sub.15) [0166]),
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Garimella to include the teachings as taught by Floyd-Jones with a reasonable expectation of success. Both arts are in the same field of endeavor of controlling motion planning of an autonomous vehicle. Floyd-Jones teaches the benefit of “A trajectory of a primary agent and/or dynamic obstacle may advantageously be represented by respective sets of fitted functions (e.g., fitted polynomial functions), for instance in lieu of motion equations. Fitted functions may advantageously require less computational expense when performing collision assessment than motion equations for example by avoiding the need to evaluate trigonometric functions [Floyd-Jones, 0005]”.
Regarding claim 18:
Garimella in view of Floyd-Jones teaches all the limitations of claim 17, upon which this claim is dependent.
Garimella further teaches:
expand one or more of the plural nodes (Nodes and/or edges may be added [0077]) according to a determined feasible path found in the first distribution area (generate routes and/or trajectories to navigate within an environment [0037]),
among the rewired nodes, prune a prune-eligible node (the GNN component 232 may periodically analyze the edge features connected to the autonomous vehicle 402 to determine the weight values and/or relative distances of each object from the autonomous vehicle 402, and may remove any nodes representing objects less than threshold relevance metric (e.g., using the weight value) and/or farther than a threshold distance away from the autonomous vehicle 402 [0078]), based on the third distribution area, from the topology information (the autonomous vehicle 402 may identify map elements and generate vectorized representations of the map elements, which may be stored as nodes in the graph structure 400 of a GNN [0077]).
Floyd-Jones further teaches:
rewire the one or more plural nodes in an area in which one or more of the plural nodes are determined to be disconnected or newly connected, in the second distribution area (a second least-cost path from node no to goal which passes through candidate nodes n.sub.5, n.sub.10, n.sub.14, and n.sub.16 (also shown in bolded line) [0171]; see fig. 5, n14 to n15 through n16; examiner notes that c14,15 is disconnected due to obstacle and the path is rewired though node n16), based on the topology information at the previous time point and the sensing information at the current time point (at time T=i+1, the candidate node n′ with the lowest average cost becomes the current node n for the next time step, T=i+2 [0172]), and
Regarding claim 19:
Garimella in view of Floyd-Jones teaches all the limitations of claim 17, upon which this claim is dependent.
Garimella further teaches:
reordering the topology information at the previous time point (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]) based on previous path nodes corresponding to the previous path at the previous time point (the GNN may fully or partially preserve its state during subsequent executions of the GNN generation process, in which certain object nodes, attributes, and/or edge data may be preserved from a previous version of the GNN while other data is updated [0025]); and
embedding the reordered topology information with the sensing information at the current time point (create new nodes within the GNN, remove nodes from the GNN, and/or modify existing nodes of the GNN based on the received map data and/or entity data [0020]; the autonomous vehicle 402 perceives new entities within its environment, it may classify the entities, generate vectorized representations of the entities, and store the representations as nodes in the graph structure 400 [0077]),
wherein the topology-based neural network comprises:
a first head (the planning component 236 to determine a location of the vehicle 202, identify objects in an environment, and/or generate routes and/or trajectories to navigate within an environment [0037]), a second head (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]), and a third head (a horizon-culling function [0078]) respectively trained to output a respective sampling area corresponding to the first distribution area (a GNN including nodes representing map element objects and entity objects within the environment of the vehicle 202 [0045]), the second distribution area (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]), and a third distribution area (a horizon-culling function in some cases, in which nodes greater than a certain distance away from the autonomous vehicle 402, and/or nodes having an edge weight value less than a threshold value with respect to the autonomous vehicle 402, are removed from the graph structure 400 [0078]) comprising the determined prune-eligible nodes in response to the reordered topology information and the sensing information at the current time point being received by the topology-based neural network (Nodes and/or edges may be added, removed, and modifies from the graph structure 400 overtime as the autonomous vehicle 402 operates in the environment [0077]).
Floyd-Jones further teaches:
wherein the topology-based neural network comprises one or more of a first head (the motion planner 280 performs an optimization to identify a path 512 in the resulting planning lattice 500 that provides a route of travel of the primary agent 102 as specified by the path with a relatively low potential of a collision with dynamic obstacle B 112. [0157]), a second head (a second least-cost path from node no to goal which passes through candidate nodes n.sub.5, n.sub.10, n.sub.14, and n.sub.16 (also shown in bolded line) [0171]; see fig. 5, n14 to n15 through n16; examiner notes that c14,15 is disconnected due to obstacle and the path is rewired though node n16),
trained to output a respective sampling area corresponding to the first distribution area (fig. 5, area of path 510), the second distribution area (fig. 5, area of path 520)
Claim(s) 5, 16, and 20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Garimella et. al. (US 2022/0274625), herein Garimella in view of Floyd-Jones et. al. (US 2020/0377085), herein Floyd-Jones in further view of Yu et. al. (CN114882970), herein Yu.
Regarding claim 5:
Garimella in view of Floyd-Jones teaches all the limitations of claim 4, upon which this claim is dependent.
Garimella further teaches:
further comprising: training at least one of the first head, the second head, or the third head (During the training, a known result (e.g., a ground truth, such as the known “future” attributes) can be used to adjust weights and/or parameters of the machine learning models to improve the accuracy of inferred updated GNN states and to minimize errors. [0047]) based on:
Garimella in view of Floyd-Jones does not explicitly teach, however Yu teaches:
a first loss based on cross-entropy between a training sampling area and a first ground truth area corresponding to a training search area (the loss function in the pre-training process is the sum of cross entropy loss and mean square error loss [claim 1]); and
a second loss based on a mean squared error between a resultant found previous path and a second ground truth area corresponding to a first distribution area of training the topology-based neural network and a second distribution area of training the topology-based neural network (the loss function in the pre-training process is the sum of cross entropy loss and mean square error loss [claim 1]).
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Garimella and Floyd-Jones to include the teachings as taught by Yu with a reasonable expectation of success. Yu teaches the benefit of calculating a loss function using known methods to achieve a predictable result. It would therefore be obvious to one having ordinary skill in the art to apply the loss function of Yu to the teachings of Garimella and Floyd-Jones to arrive at the claimed invention.
Regarding claim 16:
Garimella in view of Floyd-Jones teaches all the limitations of claim 15, upon which this claim is dependent.
Garimella further teaches:
further comprising: training at least one of the first head, the second head, or the third head (During the training, a known result (e.g., a ground truth, such as the known “future” attributes) can be used to adjust weights and/or parameters of the machine learning models to improve the accuracy of inferred updated GNN states and to minimize errors. [0047]) based on:
Garimella in view of Floyd-Jones does not explicitly teach, however Yu teaches:
a first loss based on cross-entropy between a training sampling area and a first ground truth area corresponding to a training search area (the loss function in the pre-training process is the sum of cross entropy loss and mean square error loss [claim 1]); and
a second loss based on a mean squared error between a resultant found previous path and a second ground truth area corresponding to a first distribution area of training the topology-based neural network and a second distribution area of training the topology-based neural network (the loss function in the pre-training process is the sum of cross entropy loss and mean square error loss [claim 1]).
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Garimella and Floyd-Jones to include the teachings as taught by Yu with a reasonable expectation of success. Yu teaches the benefit of calculating a loss function using known methods to achieve a predictable result. It would therefore be obvious to one having ordinary skill in the art to apply the loss function of Yu to the teachings of Garimella and Floyd-Jones to arrive at the claimed invention.
Regarding claim 20:
Garimella in view of Floyd-Jones teaches all the limitations of claim 19, upon which this claim is dependent.
Garimella further teaches:
at least one of the first head, the second head, or the third head (During the training, a known result (e.g., a ground truth, such as the known “future” attributes) can be used to adjust weights and/or parameters of the machine learning models to improve the accuracy of inferred updated GNN states and to minimize errors. [0047]) is trained based on:
Garimella in view of Floyd-Jones does not explicitly teach, however Yu teaches:
a first loss based on cross-entropy between a training sampling area and a first ground truth area corresponding to a training search area (the loss function in the pre-training process is the sum of cross entropy loss and mean square error loss [claim 1]); and
a second loss based on a mean squared error between a resultant found previous path and a second ground truth area corresponding to a first distribution area of training the topology-based neural network and a second distribution area of training the topology-based neural network (the loss function in the pre-training process is the sum of cross entropy loss and mean square error loss [claim 1]).
It would have been obvious to one of ordinary skill in the art at the time of the effective filing date of the claimed invention to have modified Garimella and Floyd-Jones to include the teachings as taught by Yu with a reasonable expectation of success. Yu teaches the benefit of calculating a loss function using known methods to achieve a predictable result. It would therefore be obvious to one having ordinary skill in the art to apply the loss function of Yu to the teachings of Garimella and Floyd-Jones to arrive at the claimed invention.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Afrouzi (US 11,274,929) discloses a method including: capturing, with at least one sensor of a robot, first data indicative of the position of the robot in relation to objects within the workspace and second data indicative of movement of the robot; recognizing, with a processor of the robot, a first area of the workspace based on observing at least one of: a first part of the first data and a first part of the second data; generating, with the processor of the robot, at least part of a map of the workspace based on at least one of: the first part of the first data and the first part of the second data; generating, with the processor of the robot, a first movement path covering at least part of the first recognized area; actuating, with the processor of the robot, the robot to move along the first movement path.
Zeng (US 2022/0153315) discloses Systems and methods are provided for forecasting the motion of actors within a surrounding environment of an autonomous platform. For example, a computing system of an autonomous platform can use machine-learned model(s) to generate actor-specific graphs with past motions of actors and the local map topology. The computing system can project the actor-specific graphs of all actors to a global graph. The global graph can allow the computing system to determine which actors may interact with one another by propagating information over the global graph. The computing system can distribute the interactions determined using the global graph to the individual actor-specific graphs. The computing system can then predict a motion trajectory for an actor based on the associated actor-specific graph, which captures the actor-to-actor interactions and actor-to-map relations.
Aldeborgh (US 2021/0156693) discloses A device may receive an architectural floor plan of an interior of a building, and may process the architectural floor plan, with a vectorization model, to generate a vectorized floor plan of polygons. The device may process the vectorized floor plan, with a convex hull model, to create convex hull polygons around the polygons of the vectorized floor plan, and may reduce a quantity of vertices associated with the convex hull polygons to generate simplified convex hull polygons. The device may generate, based on the simplified convex hull polygons, one of a visibility graph that identifies potential paths through the interior of the building, or a walking path network through the interior. The device may process the one of the visibility graph or the walking path network, with a pathfinding model, to identify paths through the interior of the building, and may perform actions based on the identified paths.
Redding (US 2018/0089563) discloses A behavior planner for a vehicle generates a plurality of conditional action sequences of the vehicle using a tree search algorithm and heuristics obtained from one or more machine learning models. Each sequence corresponds to a sequence of anticipated states of the vehicle. At least some of the action sequences are provided to a motion selector of the vehicle. The motion selector generates motion-control directives based on the received conditional action sequences and on data received from one or more sensors of the vehicle, and transmits the directives to control subsystems of the vehicle.
Li (CN108592912) discloses The invention claims a kind of indoor mobile robot based on laser radar self-search method, establishing the topological nodes. extracting result according to the search target point, generating one node of the topology map and adding the node in the topological map. redundancy topological node processing. detecting existing all topology nodes in the topological map, eliminating redundant topology node. topological map closed loop processing. detecting the current topology node and all other topological nodes whether there is closed loop. if so, adding the corresponding edge finish ring closing on the topology map. in the environment not search the node, ending the automatic search. the method does not need to depend on grid map extracting edge target points, but by extracting laser data search target point, while greatly reducing the extracting algorithm complexity with ensuring the accuracy and stability of the extraction result for the topological map for redundant node elimination and closed loop detection, which greatly improves the indoor mobile robot autonomously searching efficiency.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Scott R Jagolinzer whose telephone number is (571)272-4180. The examiner can normally be reached M-Th 8AM - 4PM Eastern.
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, Christian Chace can be reached at (571)272-4190. 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.
Scott R. Jagolinzer
Examiner
Art Unit 3665
/S.R.J./Examiner, Art Unit 3665 /CHRISTIAN CHACE/Supervisory Patent Examiner, Art Unit 3665