PREDICTING AGENT TRAJECTORIES

Application No. 19/217,266

• Filed: May 23, 2025
• Priority: Apr 23, 2021 — provisional 63/179,169
  • Apr 22, 2022 — continuation of 12/330,689
• Examiner: MATTA, ALEXANDER GEORGE
• Assignee: Motional AD LLC
• OA Round: 1 (Non-Final)

Office 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 .
Claim(s) 1-20 are pending for examination.
This Action is made NON-FINAL.
Specification
The title of the invention is not descriptive. A new title is required that is clearly indicative of the invention to which the claims are directed. The following title is recommend “Predicting agent trajectories based on sampled paths traversed and sampled latent variables”

Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.

The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.

The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are a “ graph encoder to….” as recited in claims 9, 11, and 14, a “header to….” as recited in claim 9, and “trajectory decoder to…..” as recited in claims 9 and 12.
Because these claim limitations are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, they are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
Regarding the graph encoder, header, and trajectory decoder the specification states para [0098] “In some embodiments, the agent trajectory prediction system 600 is included in the autonomous system 202 of FIG. 2, device 300 of FIG. 3, or the autonomous vehicle compute 400 of FIG. 4A. The example agent trajectory prediction system 600 includes graph encoder 602, policy header 604, and trajectory decoder 606.” And in para [0061] “In some embodiments, device 300 performs one or more processes described herein. Device 300 performs these processes based on processor 304 executing software instructions stored by a computer-readable medium, such as memory 305 and/or storage component 308. A computer-readable medium (e.g., a non-transitory computer readable medium) is defined herein as a non-transitory memory device. A non-transitory memory device includes memory space located inside a single physical storage device or memory space spread across multiple physical storage devices.”
Thus the structure of the graph encoder, header, and trajectory decoder in combination will be interpreted as at least one processor and memory.
If applicant does not intend to have these limitations interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitations to avoid them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recites sufficient structure to perform the claimed function so as to avoid them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.

Double Patenting
The nonstatutory double patenting rejection is based on a judicially created doctrine grounded in public policy (a policy reflected in the statute) so as to prevent the unjustified or improper timewise extension of the “right to exclude” granted by a patent and to prevent possible harassment by multiple assignees. A nonstatutory double patenting rejection is appropriate where the conflicting claims are not identical, but at least one examined application claim is not patentably distinct from the reference claim(s) because the examined application claim is either anticipated by, or would have been obvious over, the reference claim(s). See, e.g., In re Berg, 140 F.3d 1428, 46 USPQ2d 1226 (Fed. Cir. 1998); In re Goodman, 11 F.3d 1046, 29 USPQ2d 2010 (Fed. Cir. 1993); In re Longi, 759 F.2d 887, 225 USPQ 645 (Fed. Cir. 1985); In re Van Ornum, 686 F.2d 937, 214 USPQ 761 (CCPA 1982); In re Vogel, 422 F.2d 438, 164 USPQ 619 (CCPA 1970); In re Thorington, 418 F.2d 528, 163 USPQ 644 (CCPA 1969).
A timely filed terminal disclaimer in compliance with 37 CFR 1.321(c) or 1.321(d) may be used to overcome an actual or provisional rejection based on nonstatutory double patenting provided the reference application or patent either is shown to be commonly owned with the examined application, or claims an invention made as a result of activities undertaken within the scope of a joint research agreement. See MPEP § 717.02 for applications subject to examination under the first inventor to file provisions of the AIA as explained in MPEP § 2159. See MPEP § 2146 et seq. for applications not subject to examination under the first inventor to file provisions of the AIA . A terminal disclaimer must be signed in compliance with 37 CFR 1.321(b).
The USPTO Internet website contains terminal disclaimer forms which may be used. Please visit www.uspto.gov/patent/patents-forms. The filing date of the application in which the form is filed determines what form (e.g., PTO/SB/25, PTO/SB/26, PTO/AIA /25, or PTO/AIA /26) should be used. A web-based eTerminal Disclaimer may be filled out completely online using web-screens. An eTerminal Disclaimer that meets all requirements is auto-processed and approved immediately upon submission. For more information about eTerminal Disclaimers, refer to www.uspto.gov/patents/process/file/efs/guidance/eTD-info-I.jsp.
Claim(s) 9-14 are rejected on the ground of nonstatutory double patenting as being unpatentable over claim(s) 9-13 of Patent US 12330689 B2.
Table has been created below to compare claims of the instant application and claims of the Patent US 12330689 B2 application side by side.
Instant Application 19/217266
Patent US 12330689 B2
9. A system, comprising: a graph encoder to encode high definition maps and agent features into a graph for generating final node encodings; wherein the graph includes nodes and edges, the nodes representing segments of a lane centerline and edges representing transitions between nodes, wherein the graph is used to generate final node encodings; a header to learn a mapping for sampled graph traversals based on a motion of a target vehicle as well as local scene and agent context at neighboring nodes; and a trajectory decoder to predict trajectories based on node encodings along paths traversed by the mapping and a sampled latent variable.
9. A system, comprising: a graph encoder to encode high definition maps and agent features into a graph for generating final node encodings, wherein the graph includes nodes and edges, the nodes representing segments of a lane centerline and edges representing transitions between nodes, wherein the graph is used to generate the final node encodings; a policy header to learn a policy for sampled graph traversals based on a motion of a target vehicle as well as local scene and agent context at neighboring nodes; and a trajectory decoder to predict trajectories based on node encodings along paths traversed by the policy and a sampled latent variable, wherein the trajectory decoder comprising a multi-head attention layer configured to output a context vector for the policy, wherein the context vector is combined with motion encodings and the sampled latent variable to predict the trajectories.
10. The system of claim 9, wherein the mapping is a discrete probability distribution of transitions associated with a respective edge at a respective node.
10. The system of claim 9, wherein the policy is a discrete probability distribution of transitions associated with a respective edge at a respective node.
11. The system of claim 9, wherein the graph encoder includes one or more gated recurrent units to encode target vehicle trajectories, surrounding vehicle trajectories, and node features.
11. The system of claim 9, wherein the graph encoder includes one or more gated recurrent units to encode target vehicle trajectories, surrounding vehicle trajectories, and node features.
12. The system of claim 9, the trajectory decoder comprising a multi-head attention layer that outputs a context vector for each mapping, wherein the context vector is combined with motion encodings and the sampled latent variable to predict the trajectories.
9. A system, comprising: a graph encoder to encode high definition maps and agent features into a graph for generating final node encodings, wherein the graph includes nodes and edges, the nodes representing segments of a lane centerline and edges representing transitions between nodes, wherein the graph is used to generate the final node encodings; a policy header to learn a policy for sampled graph traversals based on a motion of a target vehicle as well as local scene and agent context at neighboring nodes; and a trajectory decoder to predict trajectories based on node encodings along paths traversed by the policy and a sampled latent variable, wherein the trajectory decoder comprising a multi-head attention layer configured to output a context vector for the policy, wherein the context vector is combined with motion encodings and the sampled latent variable to predict the trajectories.
13. The system of claim 9, wherein initial node encodings are updated with surrounding agent encodings by calculating scaled dot product attention weights to generate the final node encodings.
12. The system of claim 9, wherein initial node encodings are updated with surrounding agent encodings by calculating scaled dot product attention weights to generate the final node encodings.
14. The system of claim 9, wherein the graph encoder is configured to aggregate local context from neighboring nodes into the final node encodings of the graph using a graph neural network.
13. The system of claim 9, wherein the graph encoder is configured to aggregate local context from neighboring nodes into the final node encodings of the graph using a graph neural network.

Although the claims at issue are not identical, they are not patentably distinct from each other because both inventions are directed to operating a vehicle based on a graph corresponding at a scene. Claim(s) 9-14 are rejected based on claim(s) 9-13 of the Patent US 12330689 B2. Minor differences can be seen and noted in the table above, however it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to use the system of the Patent US 12330689 B2 to produce the system of the instant application.

Claim(s) 1-8 and 15-20 are rejected on the ground of nonstatutory double patenting as being unpatentable over claim(s) 1-8 and 14-19 of Patent US 12330689 B2 in view of Zhang et al (US 20220292867 A1, hereinafter known as Zhang).
Table has been created below to compare claims of the instant application and claims of Patent US 12330689 B2 side by side.

Instant Application 19/217266
Patent US 12330689 B2
1. A method comprising: generating, using at least one processor, a directed graph corresponding to a map of a scene by encoding map context and agent context as node encodings of the directed graph; determining, using the at least one processor, a mapping for graph traversal of the directed graph; sampling, using the at least one processor, paths for a target vehicle in the scene according to the mapping; predicting, using the at least one processor, a set of trajectories based on the sampled paths and a sampled latent variable indicating longitudinal variability of the set of trajectories; and operating, using the at least one processor, a vehicle based on the set of trajectories of the target vehicle.
1. A method comprising: generating, using at least one processor, a graph corresponding to a map of a scene by encoding map features and agent features as node encodings of the graph; determining, using the at least one processor, a policy for application to outgoing edges at nodes of the graph; sampling, using the at least one processor, paths for a target vehicle in the scene according to the policy; predicting, using the at least one processor, a set of trajectories based on the sampled paths traversed by the policy and a sampled latent variable; and operating, using the at least one processor, a vehicle based on the set of trajectories of the target vehicle, wherein predicting the set of trajectories comprises: outputting a context vector for the policy using a multi-head attention layer; and combining the context vector with motion encodings and the sampled latent variable to predict the set of trajectories.

Zhang teaches that the graph is a directed graph as discussed in para [0022-0023]

Zhang also teaches a sampled latent variable indicating longitudinal variability of the set of trajectories as discussed in para [0036-0038]
2. The method of claim 1, wherein a respective node corresponds to a segment of a lane centerline of the map.
2. The method of claim 1, wherein a respective node corresponds to a segment of a lane centerline of the map.
3. The method of claim 1, further comprising updating the node encodings with surrounding agent encodings by calculating scaled dot product attention weights.
3. The method of claim 1, further comprising updating the node encodings with surrounding agent encodings by calculating scaled dot product attention weights.
4. The method of claim 1, comprising aggregating local context from neighboring nodes into the node encodings of the directed graph using a graph neural network.
4. The method of claim 1, comprising aggregating local context from neighboring nodes into the node encodings of the graph using a graph neural network.
5. The method of claim 1, wherein the mapping is a discrete probability distribution over outgoing edges at nodes of the directed graph.
5. The method of claim 1, wherein the policy for application to the outgoing edges is a discrete probability distribution over the outgoing edges at the nodes of the graph.
6. The method of claim 1, wherein the mapping is predicted by training a multilayer perceptron (MLP) using behavior cloning.
6. The method of claim 1, wherein the policy is predicted by training a multilayer perceptron (MLP) using behavior cloning.
7. The method of claim 1, comprising selectively aggregating context along the sampled paths, and predicting the set of trajectories based on the sampled paths traversed by the mapping, the aggregated context, and the sampled latent variable.
7. The method of claim 1, comprising selectively aggregating context along the sampled paths, and predicting the set of trajectories based on the sampled paths traversed by the policy, the aggregated context, and the sampled latent variable.
8. The method of claim 7, wherein predicting the set of trajectories comprises: concatenating the aggregated context and the sampled latent variable with motion encodings; and inputting the concatenated aggregated context and the sampled latent variable to a multilayer perceptron, wherein the set of trajectories indicates predicted locations at future time steps.
8. The method of claim 7, wherein predicting the set of trajectories comprises: concatenating the aggregated context and the sampled latent variable with the motion encodings; and inputting the concatenated aggregated context and the sampled latent variable to a multilayer perceptron, wherein the set of trajectories indicates predicted locations at future time steps.
15. At least one non-transitory storage medium storing instructions that, when executed by at least one processor, cause the at least one processor to: generate a directed graph corresponding to a map of a scene by encoding map context and agent context as node encodings of the directed graph; determine a mapping for graph traversal of the directed graph; sample paths for a target vehicle in the scene according to the mapping; predict a set of trajectories based on the sampled paths and a sampled latent variable indicating longitudinal variability of the set of trajectories; and operate a vehicle based on the set of trajectories of the target vehicle.
14. At least one non-transitory storage medium storing instructions that, when executed by at least one processor, cause the at least one processor to: generate a graph corresponding to a map of a scene by encoding map features and agent features as node encodings of the graph; determine a policy for application to outgoing edges at nodes of the graph; sample paths for a target vehicle in the scene according to the policy; predict a set of trajectories based on the sampled paths traversed by the policy and a sampled latent variable; and operate a vehicle based on the set of trajectories of the target vehicle, wherein to predict the set of trajectories, the at least one processor is further caused to: output a context vector for the policy using a multi-head attention layer; and combine the context vector with motion encodings and the sampled latent variable to predict the set of trajectories.

Zhang teaches that the graph is a directed graph as discussed in para [0022-0023]

Zhang also teaches a sampled latent variable indicating longitudinal variability of the set of trajectories as discussed in para [0036-0038]
16. The at least one non-transitory storage medium of claim 15, wherein a respective node corresponds to a segment of a lane centerline of the map.
15. The at least one non-transitory storage medium of claim 14, wherein a respective node corresponds to a segment of a lane centerline of the map.
17. The at least one non-transitory storage medium of claim 15, comprising updating the node encodings with surrounding agent encodings by calculating scaled dot product attention weights.
16. The at least one non-transitory storage medium of claim 14, comprising updating the node encodings with surrounding agent encodings by calculating scaled dot product attention weights.
18. The at least one non-transitory storage medium of claim 15, comprising aggregating local context from neighboring nodes into the node encodings of the directed graph using a graph neural network.
17. The at least one non-transitory storage medium of claim 14, comprising aggregating local context from neighboring nodes into the node encodings of the graph using a graph neural network.
19. The at least one non-transitory storage medium of claim 15, wherein the mapping is a discrete probability distribution over outgoing edges at nodes of the directed graph.
18. The at least one non-transitory storage medium of claim 14, wherein the policy for application to the outgoing edges is a discrete probability distribution over the outgoing edges at nodes of the graph.
20. The at least one non-transitory storage medium of claim 15, wherein the mapping is predicted by training a multilayer perceptron (MLP) using behavior cloning.
19. The at least one non-transitory storage medium of claim 14, wherein the policy is predicted by training a multilayer perceptron (MLP) using behavior cloning.

Although the claims at issue are not identical, they are not patentably distinct from each other because both inventions are directed to operating a vehicle based on a graph corresponding at a scene. Claim(s) 1-8 and 15-20 is rejected based on Claim(s) 1-8 and 14-19 of the Patent US 12330689 B2. Minor differences can be seen and noted in the table above, however it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to use the method and the at least one non-transitory storage medium of the Patent US 12330689 B2 in view of Zhang to produce the method and the at least one non-transitory storage medium of the instant application because as discussed by Zhang in para [0011] “Advantageously, embodiments disclosed herein provide techniques to more accurately predict the movement of persons depicted in images. Doing so may improve the safety and reliability of different computing systems that predict where a person is moving. For example, using the techniques of the disclosure, a computing system may more accurately determine the future locations of one or more pedestrians depicted in an image. An autonomous vehicle may use the location data to determine that a future collision is likely to occur between the autonomous vehicle and one or more of the pedestrians. The autonomous vehicle may then perform an operation to avoid a collision with the pedestrian, e.g., by generating an alert that is outputted to the pedestrian (e.g., honking the horn of the autonomous vehicle) and/or changing the movement of the autonomous vehicle (e.g., slowing down, changing direction, and/or stopping). Embodiments are not limited in this context.”.

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 for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.

Claim(s) 1-2, 4-10, 14-16 and 18-20 are rejected under 35 U.S.C. 103 as being unpatentable over Singh et al. (US 20200379461 A1, hereinafter known as Singh) in view of Martin et al. (US 20210232913 A1, hereinafter known as Martin) and Zhang et al. (US 20220292867 A1, hereinafter known as Zhang).

Regarding claim 1, Singh teaches A method comprising: generating, using at least one processor, a
{para [0009] “In certain embodiments, the method may also include determining a reference path for each of the plurality of object trajectory sequences, and transforming each of the plurality of object trajectory sequences into a curvilinear coordinate system with respect to the corresponding reference path. Optionally, the reference path may be encoded in a vector map that comprises information corresponding to a plurality of semantic attributes. In some embodiments, the information corresponding to the plurality of semantic attributes may include, for example and without limitation, information relating to whether a lane is located within an intersection, information relating to whether a lane has an associated traffic control measure, a lane's turn direction (left, right, or none), one or more unique identifiers for a lane's predecessors, and/or one or more unique identifiers for a lane's successors. The reference path may be a centerline of a lane.”
Para [0037] “For example, the raw data may include data corresponding to motion and/or state of objects captured in different seasons, weather conditions, locations, times of day, or the like. The scenarios can be represented, for example, by an occupancy grid, a collection of vehicle states on a map, or a graphical representation, such as a top-down image of one or more areas of interest. The raw data also includes data corresponding to the motion and/or status of the objects in different scenarios and different object actions, behaviors, and intentions in a context. For example, for predictions relating to the surrounding environment of an autonomous vehicle, the raw data includes data corresponding to motion and/or status of objects: at intersections, slowing for a turn, while making turns, during lane changes, accelerating before lane changes, stopping for pedestrians or road blocks, in various traffic conditions, for different types of objects (e.g., vehicles, bicycles, pedestrians, stationary objects, etc.).”
Para [0043] “The vector maps of the current disclosure may include semantic lane or data represented as a localized graph (instead of a graph rasterized into discrete samples) based on reference paths. The vector may include lane centerlines as reference paths within a lane because vehicle trajectories typically follow the center of a lane. Each lane centerline may split the corresponding lane into lane segments, where a lane segment is a segment of road where vehicle move in single-file fashion in a single direction. Multiple lane segments may occupy the same physical space (e.g. in an intersection). Furthermore, turning lanes which allow traffic to flow in either direction may be represented by two different lanes that occupy the same physical space.”
Para [0051] “In certain embodiments the model may include a feedback system such as a recurrent neural network (RNN) (e.g., neural network 123(a) of FIG. 2). RNNS can be utilized to perform predictions due to the relative ease with which they can be deployed to model complex relationships and their ability to retain a potentially arbitrarily long history of an input signal. The RNN can model a complex relationship between the inputs and outputs of a sequence of temporal signals with a plurality of nodes. Each node performs a relatively simple data transformation on a single dimension, i.e., an activation function, such as a hyperbolic tangent, as compared to modeling the entire relationship. The activation function may take on a various forms including, without limitation, linear functions, step functions, ramp functions, sigmoid functions and Gaussian functions.”
}
determining, using the at least one processor, a mapping for graph traversal of the
{Para [0052] “The RNN's ability to retain a history of an input signal comes from the arrangement of the dependencies between the nodes and/or layers (horizontal collection of nodes) that perform the activation functions. The nodes may be arranged in a feed forward manner where the output of an earlier layer is the input for the subsequent layer. Thus, each layer of nodes may be dependent from the previous layer of nodes. The nodes may also be recurrent, i.e, dependent from the input of output of any of the nodes from an earlier portion of a temporal sequence. Therefore, an output of the RNN can be dependent upon the output of a plurality of interconnected nodes rather than a single transformation. A deep neural network includes multiple hidden layers in the network hierarchy. Referring to FIG. 5, a deep neural network 500 comprises a plurality of nodes, including input nodes (I) 502, hidden nodes (H) 503 and output nodes (O) 504. The nodes can be connected by edges, e.g., 505, which can be weighted according to the strength of the edges. It should be understood that deep neural networks typically have four or more hidden layers, and that FIG. 5 is merely an example used for describing exemplary embodiments. It is noted that embodiments of the present disclosure may comprise an RNN of any order of complexity, and are not limited to the relative simple RNNs which are shown and described herein for descriptive purposes. For example, an RNN may have any number of layers, nodes, trainable parameters (also known as weights) and/or recurrences.”
}
sampling, using the at least one processor, paths for a target vehicle in the scene according to the mapping;
{Para [0025] “The location subsystem 121 may include and/or may retrieve map data that provides detailed information about the surrounding environment of the autonomous vehicle. The map data can provide information regarding: the identity and location of different roadways, road segments, buildings, or other items; the location and directions of traffic lanes (e.g., the location and direction of a parking lane, a turning lane, a bicycle lane, or other lanes within a particular roadway); traffic control data (e.g., the location and instructions of signage, traffic lights, or other traffic control devices); and/or any other map data that provides information that assists the vehicle controller 112 in analyzing the surrounding environment of the autonomous vehicle. In certain embodiments, the map data may also include reference path information that correspond to common patterns of vehicle travel along one or more lanes such that the motion of the object is constrained to the reference path (e.g., locations within traffic lanes on which an object commonly travels). Such reference paths may be pre-defined such as the centerline of the traffic lanes. Optionally, the reference path may be generated based on a historical observations of vehicles or other objects over a period of time (e.g., reference paths for straight line travel, lane merge, a turn, or the like).”
}
predicting, using the at least one processor, a set of trajectories based on the sampled paths
{Para [0029] “The prediction and forecasting subsystem 123 may predict the future locations, trajectories, and/or actions of the objects based at least in part on perception information (e.g., the state data for each object) received from the perception subsystem 122, the location information received from the location subsystem 121, the sensor data, and/or any other data that describes the past and/or current state of the objects, the autonomous vehicle 101, the surrounding environment, and/or their relationship(s). For example, if an object is a vehicle and the current driving environment includes an intersection, prediction and forecasting subsystem 123 may predict whether the object will likely move straight forward or make a turn. If the perception data indicates that the intersection has no traffic light, prediction and forecasting subsystem 123 may also predict whether the vehicle may have to fully stop prior to enter the intersection. Such predictions may be made for a given time horizon (e.g., 5 seconds in the future).”
}
and operating, using the at least one processor, a vehicle based on the set of trajectories of the target vehicle.
{Para [0031] “The improved ability to predict future object locations, trajectories, and/or actions can enable improved motion planning or other control of the autonomous vehicle 101 based on such predicted future object locations, trajectories, and/or actions. This analysis of the perception and context data enables the embodiments to accurately predict the behavior of proximate vehicles and objects for a context in which the host vehicle is operating.”
Para [0034] “In one or more embodiments, the motion planning subsystem 124 may receive the predictions from the prediction and forecasting subsystem 123 and make a decision regarding how to handle objects in the environment of the autonomous vehicle 101. For example, for a particular object (e.g., a vehicle with a given speed, direction, turning angle, etc.), motion planning subsystem 124 decides whether to overtake, yield, stop, and/or pass based on, for example, traffic conditions, map data, state of the autonomous vehicle, etc. Furthermore, the motion planning subsystem also plans a path for the autonomous vehicle 101 to travel on a given route, as well as driving parameters (e.g., distance, speed, and/or turning angle). That is, for a given object, the motion planning subsystem 124 decides what to do with the object and determines how to do it. For example, for a given object, the motion planning subsystem 124 may decide to pass the object and may determine whether to pass on the left side or right side of the object (including motion parameters such as speed). Planning and control data is generated by the motion planning subsystem 124 that is transmitted to the vehicle control system 113 for execution.”
}

Singh does not teach, the graph being a directed graph
And
predicting, using the at least one processor, a set of trajectories based on the sampled paths and a sampled latent variable indicating longitudinal variability of the set of trajectories;

However, Martin teaches predicting, using the at least one processor, a set of trajectories based on the sampled paths and a sampled latent variable
{Para [0032] “Further, because the policy decoder 204, which may be trained with the interpretable reward function(s) determined by the reward decoder 206, may generate the corresponding interactive behavior between the agents of the system given the latent variables, the causal connection between the latent interaction graph 208 and the policy decoder 204 may be better aligned with human understanding as well. As a result, the GIRL model proposed herein may be able to provide human interpretability to one or more of its input/output spaces, and therefore actions taken (e.g., autonomous driving actions taken) based on the GIRL model, without the need for manual human annotations of interactions and/or direct supervision.”
Para [0064] “At 404, a policy decoder (e.g., decoder 204) may be provided. The policy decoder may operate on the inferred latent interaction graph to model the dynamics of the system. The policy decoder, which may be trained with the interpretable reward function(s) determined by a reward decoder, may generate the corresponding interactive behavior between the agents of the system given the latent variables. In some examples, the policy decoder may be modeled as a node-to-node message-passing GNN (e.g., made up of node-to-edge message-passing and edge-to-node message-passing). In some examples, the policy decoder may operate over the latent interaction graph, and may model the distribution π.sub.n(a.sup.t|x.sup.t,z), which may be factorized with π.sub.n(a.sub.j.sup.t|x.sup.t,z).”
Para [0066] “The reward decoder may be trained (e.g., the reward function(s) may be inferred/determined) from synthetic or actual trajectory data that describes the trajectories over time of the relevant agents in the system, and once the reward decoder is trained, the policy decoder may mimic the policy (or policies) of the agents in the system (e.g., the policies that define and/or control the behavior of the agents in the system).”
Para [0047] “The samples of the latent interaction graph 208 and an initial state of the training trajectory τ.sup.E,x.sup.E,0 212 may be used by the policy decoder 204 to generate a trajectory τ.sup.G 214 starting from the initial state τ.sup.E,x.sup.E,0 212.”
}
It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Singh to incorporate the teachings of Martin to include predict using a sampled latent variable because it allows for training without direct supervision (Martin para [0047] “Further, because the policy decoder 204, which may be trained with the interpretable reward function(s) determined by the reward decoder 206, may generate the corresponding interactive behavior between the agents of the system given the latent variables, the causal connection between the latent interaction graph 208 and the policy decoder 204 may be better aligned with human understanding as well. As a result, the GIRL model proposed herein may be able to provide human interpretability to one or more of its input/output spaces, and therefore actions taken (e.g., autonomous driving actions taken) based on the GIRL model, without the need for manual human annotations of interactions and/or direct supervision.”)

Singh in view of Martin does not teach, the graph being a directed graph
And
a sampled latent variable indicating longitudinal variability of the set of trajectories;

However, Zhang teaches generating, using at least one processor, a directed graph corresponding to a map of a scene by encoding map context and agent context as node encodings of the directed graph;
{para [0022-0023] “The social graphs 107 are directed graphs that are generated at different time intervals (e.g., at 1 second intervals, 2 second intervals, etc.) based on the current location and velocity of people depicted in the image captured by the image capture device 103 at the corresponding time interval. Generally, the image capture device 103 may capture images at periodic time intervals, and the social graphs 107 may be generated to reflect the pairwise social relationships between people depicted in the images at the corresponding time interval. Based on an analysis of the captured images, the trajectory module 104 may identify persons in the image, determine the present location of the person, and update the trajectory history for each identified person (e.g., as metadata of the image and/or in a separate data store). The trajectory history may reflect the actual movement of each person at each time interval and may include a vector reflecting direction and/or velocity of movement at each time interval. The movement of each person at each time interval may be based on a respective image captured by the image capture device 103 depicting the person.
In one or more embodiments, a social graph 107 may be a directed graph G=(N;E;A), where N is a plurality of graph nodes, E is one or more graph edges connecting two nodes, and A is a non-symmetric adjacency matrix. Based on a given image (which may be analyzed by the CV algorithms 106 to identify persons, determine movement, determine that one person is in view of another person, identify interactions, the types of interactions, etc.), each pedestrian is assigned to a node (n.sub.j∈N) in the social graph 107, and an edge e.sub.ij=(n.sub.i, n.sub.j)∈E linking from i-th to j-th person exists when the adjacency matrix entry a.sub.ij=1. Generally, at each time interval, the current position and speed direction of each person depicted in the corresponding image is used to determine whether another person is in the view of the person and generate the social graph 107 for the corresponding time interval. For example, a CV algorithm 106 and/or the trajectory module 104 may determine whether one or more rays emitted from a first person intersect with a second person in the image to determine whether the second person is in view of the first person at a given time interval. If the trajectory module 104 determines the person is in view, the trajectory module 104 may add an edge connecting the corresponding nodes in the social graph 107 for the time interval. However, if the first and second persons are no longer in view of each other at a later time interval, the social graph 107 for the later time interval will not include an edge connecting the first and second persons. Thus the social graph 107 is dynamically changed as the relative positions of people change across images.”
}

a sampled latent variable indicating longitudinal variability of the set of trajectories

{para [0036-0038] “Therefore, in the examples shown, the stochastic model 108 may include two LSTMs 110, namely prior LSTM.sub.ψ(f.sub.t-1.sup.S) in Equation 7, and posterior LSTM.sub.ϕ(f.sub.t.sup.S) in Equation 8. However, the stochastic model 108 may include any number of LSTMS 110, and the use of two LSTMs should not be considered limiting of the disclosure. The prior LSTM.sub.ψ(f.sub.t-1.sup.S) of Equation 7 may correspond to a Gaussian mean and variance, while the posterior LSTM.sub.ϕ(f.sub.t.sup.S) of Equation 8 may correspond to a Gaussian mean and variance. Generally, during training, the Gaussian distribution (e.g., mean and variance) of the prior LSTM.sub.ψ(f.sub.t-1.sup.S) is refined to approximate the Gaussian distribution of the posterior LSTM.sub.ϕ(f.sub.t.sup.S). Once the distributions reach a threshold degree of similarity, the prior distribution of the prior LSTM.sub.ψ(f.sub.t-1.sup.S) may replace the posterior distribution of the posterior LSTM.sub.ϕ(f.sub.t.sup.S). Therefore, the stochastic model 108 may sample the latent variable based on the Gaussian distribution of the posterior LSTM.sub.ϕ(f.sub.t.sup.S) during training and may sample the Gaussian distribution of the prior LSTM.sub.ψ(f.sub.t-1.sup.S) during testing (or runtime, or inference) operations. The prior LSTM.sub.ψ(f.sub.t-1.sup.S) may generally be learned based on past trajectory data of persons with recursive hidden states. The past trajectory data may include vectors describing the direction and speed of movement of the person at each time interval. The posterior LSTM.sub.ϕ(f.sub.t.sup.S) encodes scenes for the current time interval. As stated, the prior LSTM.sub.ψ(f.sub.t-1.sup.S) is trained to approximate the posterior LSTM.sub.ϕ(f.sub.t.sup.S) to capture uncertain social interactions.

The decoder model 109 is generally configured to generate output to predict the movement of a given person depicted in an image at time interval t. In one embodiment, the decoder model 109 leverages hierarchical LSTMs 111 to progressively decode the feature vectors and predict the offset (e.g., an output vector) of the location of each person. The output generated by the decoder model 109 may take any form suitable to convey direction and/or speed of movement. For example, in one embodiment, the predicted movement may comprise a vector indicating a velocity and direction of movement (e.g., movement in the (x,y) direction at a velocity in meters per second). However, during training, the inputs to the decoder model 109 may comprise the ground truth data of the previous image (e.g., the actual movement of the person). The hierarchical LSTMs 111 may be a generation LSTM represented by LSTM.sub.θ that stacks the two LSTMs with different inputs. The first LSTM 111-1 may receive social inputs (e.g., the feature vector f.sup.(S)) to predict social reactions, and is combined with the second LSTM (e.g., an LSTM 111-2 for individual destination feature vector f.sup.(D)) to generate socially-acceptable and destination-oriented trajectories. Equation 9 below may describe the operations performed by the decoder model 109:

p.sub.θ(y.sub.t|z.sub.≤t,f.sub.<t.sup.S,f.sub.<t.sup.D)=LSTM.sub.θ(z.sub.t,f.sub.t-1.sup.S,f.sub.t-1.sup.D)  Equation 9.

In Equation 9, y.sub.t corresponds to the output of the decoder model 109, e.g., a vector specifying the predicted speed and direction of movement of a given person at a time interval based on the sampled latent variable z and the feature vectors f.sup.(D), f.sup.(S) for each person. As stated, the output vector y.sub.t may be in any real-world unit of measure. In some embodiments, the decoder model 109 may compute a plurality of different estimated vectors y.sub.t for each person for each person depicted in the image. In one such embodiment, the LSTM.sub.θ of the decoder model 109 may correspond to Gaussian distribution with mean and variance. The decoder model 109 may sample the speed and/or direction of each person from this Gaussian distribution.”
}

It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Singh in view of Martin to incorporate the teachings of Zhang to use directed graphs as the graphs and to include a sampled latent variable indicating longitudinal variability of the set of trajectories because as discussed by Zhang in para [0011] “Advantageously, embodiments disclosed herein provide techniques to more accurately predict the movement of persons depicted in images. Doing so may improve the safety and reliability of different computing systems that predict where a person is moving. For example, using the techniques of the disclosure, a computing system may more accurately determine the future locations of one or more pedestrians depicted in an image. An autonomous vehicle may use the location data to determine that a future collision is likely to occur between the autonomous vehicle and one or more of the pedestrians. The autonomous vehicle may then perform an operation to avoid a collision with the pedestrian, e.g., by generating an alert that is outputted to the pedestrian (e.g., honking the horn of the autonomous vehicle) and/or changing the movement of the autonomous vehicle (e.g., slowing down, changing direction, and/or stopping). Embodiments are not limited in this context.”

Regarding claim 2, Singh in view of Martin and Zhang teaches The method of claim 1. Singh further teaches wherein a respective node corresponds to a segment of a lane centerline of the map.
{Para [0041] “At 306, the system may determine a reference path encoded in semantically rich vector maps for each object trajectory in the object data set. In certain embodiments, the reference paths may be the centerlines (“S”) which correspond to the center of lanes extracted from a vector map. However, other reference paths are within the scope of this disclosure (e.g., reference paths learned based on historical data for different environments, scenarios, etc.). In certain embodiments, an object trajectory V.sub.i may be mapped to reference centerlines by obtaining a list of candidate reference paths by considering all centerlines in the neighborhood of the trajectory, and then filtering down the candidate reference paths by considering various factors. Example of such factors may include, without limitation, difference in object heading and centerline direction, offset (distance between trajectory and centerline), predecessor and/or successor centerlines aligned to the object trajectory.”
}
Regarding claim 4, Singh in view of Martin and Zhang teaches The method of claim 1. Martin further teaches comprising aggregating local context from neighboring nodes into the node encodings of the directed graph using a graph neural network.
{Para [0038] “In some examples, agents in the system may be assumed to be heterogeneous, but with the same state space X, action space A, transition operator T and reward function r. For each node v.sub.i at time step t, its associated reward may depend on its own state x.sub.j.sup.t and action a.sub.j.sup.t, and in some examples, its interactions with its neighboring nodes/vertices. For example, a reward for a given node i at time step t may be represented as: where r.sub.θ.sup.n is the node reward function, r.sub.ψk.sup.e,k is the edge reward function corresponding to the k.sup.th type of interaction, and z.sub.j is the vector collecting {z.sub.i,j}.sub.i∈N.sub.j. In some examples, the edge reward function may be selected/defined based on the domain knowledge of humans, so that the corresponding interpretable behavior results by maximizing the rewards, as will be described in more detail later. In some examples, the edge reward function r.sub.ψk.sup.e,k(x.sub.i.sup.t, a.sub.i.sup.t, x.sub.j.sup.t, a.sub.j.sup.t) equals zero for k=0, which may indicate that the action of v.sub.j does not depend on its interaction with v.sub.i, for example.”

Zhang teaches the graph is a directed graph as discussed in the claim 1 rejection.
}

Regarding claim 5, Singh in view of Martin and Zhang teaches The method of claim 1. Martin further teaches wherein mapping is a discrete probability distribution over the outgoing edges at nodes of the directed graph.
{Para [0044] “As previously described, the policy decoder 204, which may be a GNN decoder, may operate over the latent interaction graph 208. In some examples, the policy decoder 204 may model the distribution π.sub.n(a.sup.t|x.sup.t,z), which may be factorized with π.sub.n(a.sub.j.sup.t|x.sup.t,z). The policy decoder 204 may model the policy as follows:”
Para [0045] “In some examples, π.sub.n may be modeled as a Gaussian distribution with mean value parameterized by the GNN policy decoder 204. In some examples, the variance σ.sup.−2 may not depend on x.sup.t and z. For example, the variance σ.sup.2 may be treated as a tunable parameter, and its value may be adjusted through gradient descent or other suitable methods. Agent trajectories may be sampled with the policy model using the action a.sup.t sampled from π.sub.n(a.sup.t|x.sup.t,z) to propagate x.sup.t to x.sup.t+1. In some examples, the propagation may be achieved with a transition operator T, or an environment with T defined as node dynamics for the nodes/vertices in the system.”

Zhang teaches the graph is a directed graph as discussed in the claim 1 rejection.
}

Regarding claim 6, Singh in view of Martin and Zhang teaches The method of claim 1. Martin further teaches wherein the mapping is predicted by training a multilayer perceptron (MLP) using behavior cloning.
{

PNG
media_image1.png
796
718
media_image1.png
Greyscale

}

Regarding claim 7, Singh in view of Martin and Zheng teaches The method of claim 1. Martin further teaches comprising selectively aggregating context along the sampled paths, and predicting the set of trajectories based on the sampled paths traversed by the mapping, the aggregated context, and the sampled latent variable.
{Para [0032] “Further, because the policy decoder 204, which may be trained with the interpretable reward function(s) determined by the reward decoder 206, may generate the corresponding interactive behavior between the agents of the system given the latent variables, the causal connection between the latent interaction graph 208 and the policy decoder 204 may be better aligned with human understanding as well. As a result, the GIRL model proposed herein may be able to provide human interpretability to one or more of its input/output spaces, and therefore actions taken (e.g., autonomous driving actions taken) based on the GIRL model, without the need for manual human annotations of interactions and/or direct supervision.”
Para [0064] “At 404, a policy decoder (e.g., decoder 204) may be provided. The policy decoder may operate on the inferred latent interaction graph to model the dynamics of the system. The policy decoder, which may be trained with the interpretable reward function(s) determined by a reward decoder, may generate the corresponding interactive behavior between the agents of the system given the latent variables. In some examples, the policy decoder may be modeled as a node-to-node message-passing GNN (e.g., made up of node-to-edge message-passing and edge-to-node message-passing). In some examples, the policy decoder may operate over the latent interaction graph, and may model the distribution π.sub.n(a.sup.t|x.sup.t,z), which may be factorized with π.sub.n(a.sub.j.sup.t|x.sup.t,z).”
Para [0066] “The reward decoder may be trained (e.g., the reward function(s) may be inferred/determined) from synthetic or actual trajectory data that describes the trajectories over time of the relevant agents in the system, and once the reward decoder is trained, the policy decoder may mimic the policy (or policies) of the agents in the system (e.g., the policies that define and/or control the behavior of the agents in the system).”
Para [0047] “The samples of the latent interaction graph 208 and an initial state of the training trajectory τ.sup.E,x.sup.E,0 212 may be used by the policy decoder 204 to generate a trajectory τ.sup.G 214 starting from the initial state τ.sup.E,x.sup.E,0 212.”
Para [0044] “As previously described, the policy decoder 204, which may be a GNN decoder, may operate over the latent interaction graph 208. In some examples, the policy decoder 204 may model the distribution π.sub.n(a.sup.t|x.sup.t,z), which may be factorized with π.sub.n(a.sub.j.sup.t|x.sup.t,z). The policy decoder 204 may model the policy as follows:”
Para [0045] “In some examples, π.sub.n may be modeled as a Gaussian distribution with mean value parameterized by the GNN policy decoder 204. In some examples, the variance σ.sup.−2 may not depend on x.sup.t and z. For example, the variance σ.sup.2 may be treated as a tunable parameter, and its value may be adjusted through gradient descent or other suitable methods. Agent trajectories may be sampled with the policy model using the action a.sup.t sampled from π.sub.n(a.sup.t|x.sup.t,z) to propagate x.sup.t to x.sup.t+1. In some examples, the propagation may be achieved with a transition operator T, or an environment with T defined as node dynamics for the nodes/vertices in the system.”

}

Regarding claim 8, Singh in view of Martin and Zheng teaches The method of claim 7. Martin further teaches wherein predicting the set of trajectories comprises: concatenating the aggregated context and the sampled latent variable with motion encodings; and inputting the concatenated aggregated context and the sampled latent variable to a multilayer perceptron, wherein the set of trajectories indicates predicted locations at future time steps.
{See at least para [0032-0049]
}

Regarding claim 9, Singh teaches A system, comprising: a graph encoder to encode high definition maps and agent features into a graph for generating final node encodings;
{ para [0009] “In certain embodiments, the method may also include determining a reference path for each of the plurality of object trajectory sequences, and transforming each of the plurality of object trajectory sequences into a curvilinear coordinate system with respect to the corresponding reference path. Optionally, the reference path may be encoded in a vector map that comprises information corresponding to a plurality of semantic attributes. In some embodiments, the information corresponding to the plurality of semantic attributes may include, for example and without limitation, information relating to whether a lane is located within an intersection, information relating to whether a lane has an associated traffic control measure, a lane's turn direction (left, right, or none), one or more unique identifiers for a lane's predecessors, and/or one or more unique identifiers for a lane's successors. The reference path may be a centerline of a lane.”
Para [0043] “The vector maps of the current disclosure may include semantic lane or data represented as a localized graph (instead of a graph rasterized into discrete samples) based on reference paths. The vector may include lane centerlines as reference paths within a lane because vehicle trajectories typically follow the center of a lane. Each lane centerline may split the corresponding lane into lane segments, where a lane segment is a segment of road where vehicle move in single-file fashion in a single direction. Multiple lane segments may occupy the same physical space (e.g. in an intersection). Furthermore, turning lanes which allow traffic to flow in either direction may be represented by two different lanes that occupy the same physical space.”
Para [0051] “In certain embodiments the model may include a feedback system such as a recurrent neural network (RNN) (e.g., neural network 123(a) of FIG. 2). RNNS can be utilized to perform predictions due to the relative ease with which they can be deployed to model complex relationships and their ability to retain a potentially arbitrarily long history of an input signal. The RNN can model a complex relationship between the inputs and outputs of a sequence of temporal signals with a plurality of nodes. Each node performs a relatively simple data transformation on a single dimension, i.e., an activation function, such as a hyperbolic tangent, as compared to modeling the entire relationship. The activation function may take on a various forms including, without limitation, linear functions, step functions, ramp functions, sigmoid functions and Gaussian functions.”
}
wherein the graph includes nodes and edges, the nodes representing segments of a lane centerline and edges representing transitions between nodes, wherein the graph is used to generate final node encodings;
{ Para [0052] “The RNN's ability to retain a history of an input signal comes from the arrangement of the dependencies between the nodes and/or layers (horizontal collection of nodes) that perform the activation functions. The nodes may be arranged in a feed forward manner where the output of an earlier layer is the input for the subsequent layer. Thus, each layer of nodes may be dependent from the previous layer of nodes. The nodes may also be recurrent, i.e, dependent from the input of output of any of the nodes from an earlier portion of a temporal sequence. Therefore, an output of the RNN can be dependent upon the output of a plurality of interconnected nodes rather than a single transformation. A deep neural network includes multiple hidden layers in the network hierarchy. Referring to FIG. 5, a deep neural network 500 comprises a plurality of nodes, including input nodes (I) 502, hidden nodes (H) 503 and output nodes (O) 504. The nodes can be connected by edges, e.g., 505, which can be weighted according to the strength of the edges. It should be understood that deep neural networks typically have four or more hidden layers, and that FIG. 5 is merely an example used for describing exemplary embodiments. It is noted that embodiments of the present disclosure may comprise an RNN of any order of complexity, and are not limited to the relative simple RNNs which are shown and described herein for descriptive purposes. For example, an RNN may have any number of layers, nodes, trainable parameters (also known as weights) and/or recurrences.”
Para[0041] “At 306, the system may determine a reference path encoded in semantically rich vector maps for each object trajectory in the object data set. In certain embodiments, the reference paths may be the centerlines (“S”) which correspond to the center of lanes extracted from a vector map. However, other reference paths are within the scope of this disclosure (e.g., reference paths learned based on historical data for different environments, scenarios, etc.). In certain embodiments, an object trajectory V.sub.i may be mapped to reference centerlines by obtaining a list of candidate reference paths by considering all centerlines in the neighborhood of the trajectory, and then filtering down the candidate reference paths by considering various factors. Example of such factors may include, without limitation, difference in object heading and centerline direction, offset (distance between trajectory and centerline), predecessor and/or successor centerlines aligned to the object trajectory.”
Para [0048] “Transformation of the object data into the 2D curvilinear coordinate system allows the system to perform predictions and trajectory forecasting as deviations from the reference paths (instead of forecasting trajectories directly), which improves computational efficiency. Use of the reference paths also allows the system to combine and use information across physical spaces (e.g., across cities) as well as semantically different lane segments (e.g., intersections and turns), leading to improved prediction and forecasting accuracy. Accuracy and efficiency is also improved because the underlying lane segments, such as width and curvature, are encoded as input features of the vector map rather than space (or substrate) for the predictions themselves. Furthermore, since the transformed trajectories include a series of normal and tangential coordinates with respect to the reference path, behavior of the vehicles (or objects) may be analyzed in relation to the behavior of other vehicles. For example, examples of left turns may be encoded and utilized to understand the behavior of a car going proceeding straight (and vice-versa). Finally, performing predictions as constrained to the references paths eliminate the possibility of impractical predictions such as those that relate to a vehicle traveling out of its lane, crashing into an opposite lane, driving into restricted areas, or the like.”
}
header to learn a mapping for sampled graph traversals based on a motion of a target vehicle
{Para [0057] “Training of the RNN in the current disclosure is performed over a short initial horizon followed by longer rolling horizons such that the trajectory of an object over the course of several seconds is determined based on both inertial constraints of the object and behavioral decisions of the object. The inertial constraints typically influence the motion and/or status of an object on a very short timescale (e.g., about 0.1 to about 1 second) and thus affect the short-term dynamics of the object. The horizon may be slowly increased during each training cycle to be for example, 0.1 second, 0.2 second, 0.3 second, 0.4 second, 0.5 second, 0.6 second, 0.7 second, 0.8 second, 0.9 second, 1 second; 0.1 second, 0.3 second, 0.5 second, and 1 second, or the like. The behavioral decisions of an object, however, typically influence the motion and/or status of the object on a longer timescale (e.g., about 1.5 to about 5 seconds) and thus affect the long-term dynamics of the object. The horizon may be slowly increased during each training cycle to be for example, 1.5 seconds, 1.7 seconds, 2.1 seconds, 2.4 seconds, 2.7 seconds, 3 seconds, 3.5 seconds, 4 seconds, 4.5 second, 5 seconds; 1.5 seconds, 2 seconds, 2.5 seconds, and 3 seconds, or the like. The two step training of this disclosure may include training the same policy class of the neural network at different time scales to capture both the short-term and long-term dynamics of the objects.”
Para [0063] “FIGS. 6A and 6B are graphical illustrations that show the effects of performing trajectory predictions using the RNN models as described above. FIG. 6A illustrates predictions performed using a model that is trained to predict trajectories for shorter time horizons (0.1 secs), while FIG. 6B illustrates performed using a model that is trained to predict trajectories for longer inertial behavioral rollout up to 30 time horizons (3 secs) in the future, as discussed above. The blue path in each figure corresponds to the 2 seconds of observed trajectory, the red path is for the trajectory corresponds to path predicted for the next 3 secs, and the green path corresponds to the actual trajectory followed by an AV in those 3 seconds. As shown in FIG. 2A, when the rollout is shorter time horizons (0.1 secs), the model learns the kinematic constraints (as evident from the smooth trajectory of the AV) only and not the higher level behavioral decisions (as evident from the AV not staying in the lane). However, when the rollout is 30, as shown in FIG. 6B, the model builds on the short term kinematic constraints and eventually learns some higher lever understanding on how to cross an intersection, stay in the lane, making turns without crossing lane boundaries, or the like.”
}

Singh does not teach, and a trajectory decoder to predict trajectories based on node encodings along paths traversed by the mapping and a sampled latent variable.
And does not explicitly teach
header to learn a mapping for sampled graph traversals based on ….. local scene and agent context at neighboring nodes;

However, Martin teaches
header to learn a mapping for sampled graph traversals based on a motion of a target vehicle as well as local scene and agent context at neighboring nodes;
{Para [0038] “In some examples, agents in the system may be assumed to be heterogeneous, but with the same state space X, action space A, transition operator T and reward function r. For each node v.sub.i at time step t, its associated reward may depend on its own state x.sub.j.sup.t and action a.sub.j.sup.t, and in some examples, its interactions with its neighboring nodes/vertices. For example, a reward for a given node i at time step t may be represented as: where r.sub.θ.sup.n is the node reward function, r.sub.ψk.sup.e,k is the edge reward function corresponding to the k.sup.th type of interaction, and z.sub.j is the vector collecting {z.sub.i,j}.sub.i∈N.sub.j. In some examples, the edge reward function may be selected/defined based on the domain knowledge of humans, so that the corresponding interpretable behavior results by maximizing the rewards, as will be described in more detail later. In some examples, the edge reward function r.sub.ψk.sup.e,k(x.sub.i.sup.t, a.sub.i.sup.t, x.sub.j.sup.t, a.sub.j.sup.t) equals zero for k=0, which may indicate that the action of v.sub.j does not depend on its interaction with v.sub.i, for example.”
}

and a trajectory decoder to predict trajectories based on node encodings along paths traversed by the mapping and a sampled latent variable.
{Para [0032] “Further, because the policy decoder 204, which may be trained with the interpretable reward function(s) determined by the reward decoder 206, may generate the corresponding interactive behavior between the agents of the system given the latent variables, the causal connection between the latent interaction graph 208 and the policy decoder 204 may be better aligned with human understanding as well. As a result, the GIRL model proposed herein may be able to provide human interpretability to one or more of its input/output spaces, and therefore actions taken (e.g., autonomous driving actions taken) based on the GIRL model, without the need for manual human annotations of interactions and/or direct supervision.”
Para [0064] “At 404, a policy decoder (e.g., decoder 204) may be provided. The policy decoder may operate on the inferred latent interaction graph to model the dynamics of the system. The policy decoder, which may be trained with the interpretable reward function(s) determined by a reward decoder, may generate the corresponding interactive behavior between the agents of the system given the latent variables. In some examples, the policy decoder may be modeled as a node-to-node message-passing GNN (e.g., made up of node-to-edge message-passing and edge-to-node message-passing). In some examples, the policy decoder may operate over the latent interaction graph, and may model the distribution π.sub.n(a.sup.t|x.sup.t,z), which may be factorized with π.sub.n(a.sub.j.sup.t|x.sup.t,z).”
Para [0066] “The reward decoder may be trained (e.g., the reward function(s) may be inferred/determined) from synthetic or actual trajectory data that describes the trajectories over time of the relevant agents in the system, and once the reward decoder is trained, the policy decoder may mimic the policy (or policies) of the agents in the system (e.g., the policies that define and/or control the behavior of the agents in the system).”
Para [0047] “The samples of the latent interaction graph 208 and an initial state of the training trajectory τ.sup.E,x.sup.E,0 212 may be used by the policy decoder 204 to generate a trajectory τ.sup.G 214 starting from the initial state τ.sup.E,x.sup.E,0 212.”
}

It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Singh to incorporate the teachings of Martin to include predict using a sampled latent variable because it allows for training without direct supervision (Martin para [0047] “Further, because the policy decoder 204, which may be trained with the interpretable reward function(s) determined by the reward decoder 206, may generate the corresponding interactive behavior between the agents of the system given the latent variables, the causal connection between the latent interaction graph 208 and the policy decoder 204 may be better aligned with human understanding as well. As a result, the GIRL model proposed herein may be able to provide human interpretability to one or more of its input/output spaces, and therefore actions taken (e.g., autonomous driving actions taken) based on the GIRL model, without the need for manual human annotations of interactions and/or direct supervision.”)
Also It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Singh to incorporate the teachings of Martin to learn a policy based on context at neighboring nodes because at allows for interaction between agents to be better accounted for during prediction likely improving prediction.

Regarding claim 10, Singh in view of Martin teaches The system of claim 9. Martin further teaches wherein the mapping is a discrete probability distribution of transitions associated with a respective edge at a respective node.
{Para [0044] “As previously described, the policy decoder 204, which may be a GNN decoder, may operate over the latent interaction graph 208. In some examples, the policy decoder 204 may model the distribution π.sub.n(a.sup.t|x.sup.t,z), which may be factorized with π.sub.n(a.sub.j.sup.t|x.sup.t,z). The policy decoder 204 may model the policy as follows:”
Para [0045] “In some examples, π.sub.n may be modeled as a Gaussian distribution with mean value parameterized by the GNN policy decoder 204. In some examples, the variance σ.sup.−2 may not depend on x.sup.t and z. For example, the variance σ.sup.2 may be treated as a tunable parameter, and its value may be adjusted through gradient descent or other suitable methods. Agent trajectories may be sampled with the policy model using the action a.sup.t sampled from π.sub.n(a.sup.t|x.sup.t,z) to propagate x.sup.t to x.sup.t+1. In some examples, the propagation may be achieved with a transition operator T, or an environment with T defined as node dynamics for the nodes/vertices in the system.”
}
Regarding claim 14, Singh in view of Martin teaches The system of claim 9. Martin further teaches wherein the graph encoder is configured to aggregate local context from neighboring nodes into the final node encodings of the graph using a graph neural network.
{Para [0038] “In some examples, agents in the system may be assumed to be heterogeneous, but with the same state space X, action space A, transition operator T and reward function r. For each node v.sub.i at time step t, its associated reward may depend on its own state x.sub.j.sup.t and action a.sub.j.sup.t, and in some examples, its interactions with its neighboring nodes/vertices. For example, a reward for a given node i at time step t may be represented as: where r.sub.θ.sup.n is the node reward function, r.sub.ψk.sup.e,k is the edge reward function corresponding to the k.sup.th type of interaction, and z.sub.j is the vector collecting {z.sub.i,j}.sub.i∈N.sub.j. In some examples, the edge reward function may be selected/defined based on the domain knowledge of humans, so that the corresponding interpretable behavior results by maximizing the rewards, as will be described in more detail later. In some examples, the edge reward function r.sub.ψk.sup.e,k(x.sub.i.sup.t, a.sub.i.sup.t, x.sub.j.sup.t, a.sub.j.sup.t) equals zero for k=0, which may indicate that the action of v.sub.j does not depend on its interaction with v.sub.i, for example.”
}

Regarding claim 15, it recites At least one non-transitory storage medium having limitations similar to those of claim 1 and therefore is rejected on the same basis.
Additionally Singh teaches At least one non-transitory storage medium storing instructions that, when executed by at least one processor, cause the at least one processor to…
{Para [0065] “FIG. 8 depicts an example of internal hardware that may be included in any of the electronic components of the system, such as the controller (or components of the controller) of the autonomous vehicle, the control system, servers etc. described above. An electrical bus 800 serves as an information highway interconnecting the other illustrated components of the hardware. Processor 805 is a central processing device of the system, configured to perform calculations and logic operations required to execute programming instructions. As used in this document and in the claims, the terms “processor” and “processing device” may refer to a single processor or any number of processors in a set of processors that collectively perform a set of operations, such as a central processing unit (CPU), a graphics processing unit (GPU), a remote server, or a combination of these. Read only memory (ROM), random access memory (RAM), flash memory, hard drives and other devices capable of storing electronic data constitute examples of memory devices 825. A memory device may include a single device or a collection of devices across which data and/or instructions are stored. Various embodiments of the invention may include a computer-readable medium containing programming instructions that are configured to cause one or more processors, print devices and/or scanning devices to perform the functions described in the context of the previous figures.”
}
Regarding claim 16, it recites At least one non-transitory storage medium having limitations similar to those of claim 2 and therefore is rejected on the same basis.

Regarding claim 18, it recites At least one non-transitory storage medium having limitations similar to those of claim 4 and therefore is rejected on the same basis.

Regarding claim 19, it recites At least one non-transitory storage medium having limitations similar to those of claim 5 and therefore is rejected on the same basis.

Regarding claim 20, it recites At least one non-transitory storage medium having limitations similar to those of claim 6 and therefore is rejected on the same basis.

Claim(s) 3, 13, and 17 are rejected under 35 U.S.C. 103 as being unpatentable over Singh et al. (US 20200379461 A1, hereinafter known as Singh) in view of Martin et al. (US 20210232913 A1, hereinafter known as Martin), Zhang et al. (US 20220292867 A1, hereinafter Zhang), and Gao et al. (US 20200065374 A1, hereinafter known as Gao).

Regarding claim 3, Singh in view of Martin and Zhang teaches The method of claim 1. Singh further teaches further comprising updating the node encodings with surrounding agent encodings by calculating
{para [0052] “e RNN's ability to retain a history of an input signal comes from the arrangement of the dependencies between the nodes and/or layers (horizontal collection of nodes) that perform the activation functions. The nodes may be arranged in a feed forward manner where the output of an earlier layer is the input for the subsequent layer. Thus, each layer of nodes may be dependent from the previous layer of nodes. The nodes may also be recurrent, i.e, dependent from the input of output of any of the nodes from an earlier portion of a temporal sequence. Therefore, an output of the RNN can be dependent upon the output of a plurality of interconnected nodes rather than a single transformation. A deep neural network includes multiple hidden layers in the network hierarchy. Referring to FIG. 5, a deep neural network 500 comprises a plurality of nodes, including input nodes (I) 502, hidden nodes (H) 503 and output nodes (O) 504. The nodes can be connected by edges, e.g., 505, which can be weighted according to the strength of the edges. It should be understood that deep neural networks typically have four or more hidden layers, and that FIG. 5 is merely an example used for describing exemplary embodiments. It is noted that embodiments of the present disclosure may comprise an RNN of any order of complexity, and are not limited to the relative simple RNNs which are shown and described herein for descriptive purposes. For example, an RNN may have any number of layers, nodes, trainable parameters (also known as weights) and/or recurrences.”
Para [0037] “The RNN is developed and dynamically updated (i.e., validation error reduced) using the training data set and is then evaluated using the test data set. During training, a part of the training data set may be used to continuously and dynamically update various iterations of the RNN model. The RNN model learns to infer a sequence of future values (called “horizon”) based on a given lag by learning over multiple pairs of lag-horizon taken across the available timeline. The model may be trained and validated by iterating through the whole training dataset of trajectory sequences based on pre-set number of epochs (e.g., about 50 to about 750 epochs). For example, the model may be trained for a desired number of epochs, and then checked for an error metric by calculating a cost function (such as Mean Squared Error (MSE) score, Average Displacement Error (ADE) and Final Displacement Error (FDE)). If the cost function is not satisfactory (i.e., the error metric is high), the hyperparameters of the model (e.g., learning rate and number of epochs) are tuned and the model is trained again to reduce the error metric. When a satisfactory (or as expected) cost function is achieved, the training process of the algorithm terminates (i.e., when the error metric starts increasing instead of decreasing).”
}
Singh in view of Martin does not teach, calculating scaled dot product attention weights

However, Gao teaches calculating scaled dot product attention weights
{Para [0032] “In some embodiments, attention-based subword encoder sublayer 211 is designed to differentiate these subwords and explicitly considering their importance. For example, attention-based subword encoder sublayer 211 may employ an attention layer over the output of CNN, which will enable the model to learn salient subwords automatically. In one implementation, the attention layer will generate an importance score for each subword based on the dot product of the attention weight vector and the encoding of the subword. The score may be further normalized using a softmax function.”
}
It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Singh in view of Martin and Zhang to incorporate the teachings of Gao to use scaled dot product attention weights because it allows the decoder to "look back” at the complete input and extracts significant information that is useful in decoding.
Regarding claim 17, it recites At least one non-transitory storage medium having limitations similar to those of claim 3 and therefore is rejected on the same basis.

Claim(s) 13 are rejected under 35 U.S.C. 103 as being unpatentable over Singh et al. (US 20200379461 A1, hereinafter known as Singh) in view of Martin et al. (US 20210232913 A1, hereinafter known as Martin) and Gao et al. (US 20200065374 A1, hereinafter known as Gao).

Regarding claim 13, Singh in view of Martin teaches The system of claim 9. Singh further teaches wherein initial node encodings are updated with surrounding agent encodings by calculating
{para [0052] “e RNN's ability to retain a history of an input signal comes from the arrangement of the dependencies between the nodes and/or layers (horizontal collection of nodes) that perform the activation functions. The nodes may be arranged in a feed forward manner where the output of an earlier layer is the input for the subsequent layer. Thus, each layer of nodes may be dependent from the previous layer of nodes. The nodes may also be recurrent, i.e, dependent from the input of output of any of the nodes from an earlier portion of a temporal sequence. Therefore, an output of the RNN can be dependent upon the output of a plurality of interconnected nodes rather than a single transformation. A deep neural network includes multiple hidden layers in the network hierarchy. Referring to FIG. 5, a deep neural network 500 comprises a plurality of nodes, including input nodes (I) 502, hidden nodes (H) 503 and output nodes (O) 504. The nodes can be connected by edges, e.g., 505, which can be weighted according to the strength of the edges. It should be understood that deep neural networks typically have four or more hidden layers, and that FIG. 5 is merely an example used for describing exemplary embodiments. It is noted that embodiments of the present disclosure may comprise an RNN of any order of complexity, and are not limited to the relative simple RNNs which are shown and described herein for descriptive purposes. For example, an RNN may have any number of layers, nodes, trainable parameters (also known as weights) and/or recurrences.”
Para [0037] “The RNN is developed and dynamically updated (i.e., validation error reduced) using the training data set and is then evaluated using the test data set. During training, a part of the training data set may be used to continuously and dynamically update various iterations of the RNN model. The RNN model learns to infer a sequence of future values (called “horizon”) based on a given lag by learning over multiple pairs of lag-horizon taken across the available timeline. The model may be trained and validated by iterating through the whole training dataset of trajectory sequences based on pre-set number of epochs (e.g., about 50 to about 750 epochs). For example, the model may be trained for a desired number of epochs, and then checked for an error metric by calculating a cost function (such as Mean Squared Error (MSE) score, Average Displacement Error (ADE) and Final Displacement Error (FDE)). If the cost function is not satisfactory (i.e., the error metric is high), the hyperparameters of the model (e.g., learning rate and number of epochs) are tuned and the model is trained again to reduce the error metric. When a satisfactory (or as expected) cost function is achieved, the training process of the algorithm terminates (i.e., when the error metric starts increasing instead of decreasing).”
}

Singh in view of Martin does not teach, calculating scaled dot product attention weights

However, Gao teaches calculating scaled dot product attention weights
{Para [0032] “In some embodiments, attention-based subword encoder sublayer 211 is designed to differentiate these subwords and explicitly considering their importance. For example, attention-based subword encoder sublayer 211 may employ an attention layer over the output of CNN, which will enable the model to learn salient subwords automatically. In one implementation, the attention layer will generate an importance score for each subword based on the dot product of the attention weight vector and the encoding of the subword. The score may be further normalized using a softmax function.”
}

It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Singh in view of Martin to incorporate the teachings of Gao to use scaled dot product attention weights because it allows the decoder to "look back” at the complete input and extracts significant information that is useful in decoding.

Claim(s) 11 is rejected under 35 U.S.C. 103 as being unpatentable over Singh et al. (US 20200379461 A1, hereinafter known as Singh) in view of Martin et al. (US 20210232913 A1, hereinafter known as Martin) and Chu et al. (US 20200302250 A1, hereinafter known as Chu).

Regarding claim 11, Singh in view of Martin teaches The system of claim 9.
Singh in view of Martin does not teach wherein the graph encoder includes one or more gated recurrent units to encode target vehicle trajectories, surrounding vehicle trajectories, and node features.

However, Chu teaches wherein the graph encoder includes one or more gated recurrent units to encode target vehicle trajectories, surrounding vehicle trajectories, and node features.
{Para [0032] “FIG. 4 illustrates a neural network architecture of an example generative model, including an encoder-decoder design. First, an encoder Gated Recurrent Unit (GRU) consumes the motion trajectory ?x.sup.in of each incoming path of neighboring nodes 402. An order-invariant representation can be produced by summing up the last-state hidden vectors across all paths. In this example, a decoder RNN then produces “commands” to advance the paths and produce new nodes, which can correspond to advancing the “turtle” in a turtle graphics-based approach. An optional attribute vector 404 can be further added to the decoder depending on factors such as the task to be performed.”
}

It would have been prima facie obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified Singh in view of Martin to incorporate the teachings of Chu to gated recurrent units to encode because it GRU uses less memory and is faster than LSTM.

Allowable Subject Matter
Claim 12 objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.

Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure: Liu et al. (US 20240272637 A1) teaches in the abstract “Systems and methods for basis path generation are provided. In particular, a computing system can obtain a target nominal path. The computing system can determine a current pose for an autonomous vehicle. The computing system can determine, based at least in part on the current pose of the autonomous vehicle and the target nominal path, a lane change region. The computing system can determine one or more merge points on the target nominal path. The computing system can, for each respective merge point in the one or more merge points, generate a candidate basis path from the current pose of the autonomous vehicle to the respective merge point. The computing system can generate a suitability classification for each candidate basis path. The computing system can select one or more candidate basis paths based on the suitability classification for each respective candidate basis path in the plurality of candidate basis paths.”
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ALEXANDER MATTA whose telephone number is [phone]. The examiner can normally be reached Mon - Fri 10:00-6:00.
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, James Lee can be reached on [phone]. 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.

/A.G.M./Examiner, Art Unit 3668
/ABDHESH K JHA/Primary Examiner, Art Unit 3668

Prosecution Timeline

• May 23, 2025: Application Filed
• Jun 29, 2026: Non-Final Rejection mailed — §103 (current)