IP Library › Granted Patent US 12,330,689
Granted Patent B2
US 12,330,689 · App. 17/727,617 · Granted Jun 17, 2025

Predicting agent trajectories

Inventors: Nachiket Deo (San Diego, CA); Oscar Olof Beijbom (Santa Monica, CA); Eric Wolff (Boston, MA)
Assignee: Motional AD LLC
B60W60/0027B60W50/0097G06N3/08B60W2050/0022B60W2556/40
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,330,689
App. No.
17/727,617
Granted
Jun 17, 2025
Kind
B2
Abstract

Provided are methods for predicting agent trajectories, which can include generating a graph corresponding to a map of a scene by encoding map features and agent features as node encodings of the graph and determining a policy for application to outgoing edges of the nodes of the graph. Some methods described also include sampling paths for a target vehicle in the scene according to the policy and predicting a set of trajectories based on the sampled paths traversed by the policy and a sampled latent variable. Systems and computer program products are also provided.

Claims (40)

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.

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.

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 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 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 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 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.

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 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.

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.

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.

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.

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.

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.

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.

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.

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.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 5, 2022
From: DEO, NACHIKET; BEIJBOM, OSCAR OLOF; WOLFF, ERIC
To: MOTIONAL AD LLC
Reel/Frame 059824/0614 →
Continuity (2)
Provisional Application 63179169 · Apr 23, 2021
Related Publication 20220355825A1 · Nov 10, 2022
References Cited (49)
US 20190163191A1 · Sorin et al. · 2019 [cited by applicant]
US 20200065374A1 · Gao · 2020 [cited by examiner]
US 20200172098A1 · Abrahams · 2020 [cited by examiner]
US 20200302250A1 · Chu · 2020 [cited by examiner]
US 20200379461A1 · Singh · 2020 [cited by examiner]
US 20210232913A1 · Martin · 2021 [cited by examiner]
US 20220157294A1 · Li · 2022 [cited by examiner]
[No Author Listed], “Surface Vehicle Recommended Practice: Taxonomy and Definitions for Terms Related to Driving Automation Systems for On-Road Motor Vehicles,” SAE International, Standard J3016, Sep. 30, 2016, 30 pages. [cited by applicant]
Caesar et al., “nuScenes: A multimodal dataset for autonomous driving,” CoRR, submitted on Mar. 26, arXiv:1903.11027, 2019, 16 pages. [cited by applicant]
Chai et al., “MultiPath: Multiple probabilistic anchor trajectory hypotheses for behavior prediction,” CoRR, submitted Oct. 12, 2019, arXiv:1910.05449, 14 pages. [cited by applicant]
Cui et al., “Multimodal trajectory predictions for autonomous driving using deep convolutional networks,” CoRR, revised Mar. 1, 2019, arXiv:1809.10732v2, 7 pages. [cited by applicant]
Deo et al., “Multimodal Trajectory Prediction Conditioned on Lane-Graph Traversals,” arXiv preprint, arXiv:2106.15004v2, Sep. 15, 2021, 12 pages. [cited by applicant]
Deo et al., “Trajectory forecasts in unknown environments conditioned on grid-based plans,” CoRR, submitted Jan. 3, 2020, arXiv:2001.00735, 12 pages. [cited by applicant]
Gao et al., “Vectornet: Encoding HD maps and agent dynamics from vectorized representation,” In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2018, pp. 11525-11533. [cited by applicant]
Gupta et al., “Social GAN: Socially acceptable trajectories with generative adversarial networks,” In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2018, pp. 2255-2264. [cited by applicant]
International Search Report and Written Opinion in International Appln. No. PCT/US2022/026045, dated Aug. 18, 2022, 10 pages. [cited by applicant]
Ivanovic et al., “The Trajectron: Probabilistic Multi-Agent Trajectory Modeling With Dynamic Spatiotemporal Graphs,” Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), 2019, pp. 2375-2384. [cited by applicant]
Khandelwal et al., “What-if motion prediction for autonomous driving,” CoRR, submitted on Aug. 24, 2020, arXiv:2008.10587, 16 pages. [cited by applicant]
Kipf et al., “Semi-supervised classification with graph convolutional networks,” CoRR, revised on Feb. 22, 2017, arXiv:1609.02907, 14 pages. [cited by applicant]
Kitani et al., “Activity Forecasting,” Computer Vision—ECCV 2012: 12th European Conference on Computer Vision, Florence, Italy, Oct. 7-13, 2012; Proceedings, 2012, Part IV(12):201-214. [cited by applicant]
Lee et al., “DESIRE: Distant future prediction in dynamic scenes with interacting agents,” IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2017, pp. 336-345. [cited by applicant]
Liang et al., “Learning Lane Graph Representations for Motion Forecasting,” CoRR, Submitted Jul. 27, 2020, arXiv:2007.13732, 18 pages. [cited by applicant]
Luo et al., “Probabilistic multi-modal trajectory prediction with lane attention for autonomous vehicles,” CoRR, submitted Jul. 6, 2020, arXiv:2007.02574, 7 pages. [cited by applicant]
Makansi et al., “Overcoming limitations of mixture density networks: A sampling and fitting framework for multimodal future prediction,” IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019, pp. 7… [cited by applicant]
Mangalam et al., “It is not the journey but the destination: Endpoint conditioned trajectory prediction,” CoRR, revised Jul. 18, 2020, arXiv:2004.02025, 19 pages. [cited by applicant]
Messaoud et al., “Trajectory prediction for autonomous driving based on multi-head attention with joint agent-map representation,” CoRR, revised on Sep. 2, 2020, arXiv:2005.02545, 8 pages. [cited by applicant]
nuscenes.org [online], “nuScenes by Aptiv,” available on or before Apr. 16, 2020, via Internet Archive: Wayback Machine URL <http://web.archive.org/web/20200416022447/https://www.nuscenes.org/>, retrieved on Mar. 21, 20… [cited by applicant]
Paden et al., “A survey of motion planning and control techniques for self-driving urban vehicles,” CoRR, submitted Apr. 25, 2016, arXiv:1604.07446, 27 pages. [cited by applicant]
Phan-Minh et al., “Covernet: Multimodal behavior prediction using trajectory sets,” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020, pp. 14074-14083. [cited by applicant]
Planning Algorithms, LaValle (ed.), 2006, 1023 pages. [cited by applicant]
Rhinehart et al., “PRECOG: PREdiction Conditioned on Goals in Visual Multi-Agent Settings,” Proceedings of the IEEE/CVF International Conference on Computer Vision, 2019, pp. 2821-2830. [cited by applicant]
Rhinehart et al., “R2P2: A ReparameteRized Pushforward Policy for Diverse, Precise Generative Path Forecasting,” Proceedings of the European Conference on Computer Vision (ECCV), 2018, pp. 772-788. [cited by applicant]
Sadeghian et al., “SoPhie: An Attentive GAN for Predicting Paths Compliant to Social and Physical Constraints,” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019, pp. 1349-13… [cited by applicant]
Salzmann et al., “Trajectron++: Dynamically-feasible trajectory forecasting with heterogeneous data,” CoRR, revised Nov. 21, 2020, arXiv:2001.03093, 23 pages. [cited by applicant]
Vaswani et al., “Attention is all you need,” 31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA, Dec. 4-9, 2017, 11 pages. [cited by applicant]
Veličković et al., “Graph attention networks,” CoRR, revised Feb. 4, 2018, arXiv:1710.10903, 12 pages. [cited by applicant]
Wang et al., “Stepwise goal-driven networks for trajectory prediction,” CoRR, submitted Mar. 25, 2021, arXiv:2103.14107, 11 pages. [cited by applicant]
Wulfmeier et al., “Maximum Entropy Deep Inverse Reinforcement Learning, ” CoRR, revised Mar. 11, 2016, arXiv:1507.04888, 10 pages. [cited by applicant]
Zeng et al., “End-to-end interpretable neural motion planner,” Proceedings of IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019, pp. 8660-8669. [cited by applicant]
Zeng et al., “LaneRCNN: Distributed representations for graph-centric motion forecasting,” CoRR, submitted Jan. 17, 2021, arXiv:2101.06653, 14 pages. [cited by applicant]
Zhang et al., “Map-adaptive goal-based trajectory prediction,” 4th Conference on Robot Learning (CoRL 2020), Cambridge MA, USA, Nov. 16-20, 2020; Proceedings of Machine Learning Research, PMLR, 2020, 155:1371-1383. [cited by applicant]
Zhao et al., “Multi-agent tensor fusion for contextual trajectory prediction,” IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019, 9 pages. [cited by applicant]
Zhao et al., “TNT: Target-driveN trajectory prediction,” 4th Conference on Robot Learning (CoRL 2020), Cambridge MA, USA, Nov. 16-20, 2020; Proceedings of Machine Learning Research, PMLR, 2020, 155:895-904. [cited by applicant]
Ziebart et al., “Maximum Entropy Inverse Reinforcement Learning,” AAAI-08: Twenty-Third Conference on Artificial Intelligence, Chicago, Illinois, Jul. 13-17, 2008, 8:1433-1438. [cited by applicant]
Ziebart et al., “Modeling Interaction via the Principle of Maximum Causal Entropy,” ICML'10: Proceedings of the 27th International Conference on International Conference on Machine Learning, Jun. 2010, pp. 1255-1262. [cited by applicant]
Ziebart, “Modeling Purposeful Adaptive Behavior with the Principle of Maximum Causal Entropy,” Doctoral Thesis for the degree of Doctor of Philosophy, Carnegie Mellon University, School of Computer Science, Dec. 2010, 2… [cited by applicant]
International Preliminary Report on Patentability in International Appln. No. PCT/US2022/026045, dated Nov. 2, 2023, 8 pages. [cited by applicant]
Cheng et al., “Exploring Dynamic Context for Multi-path Trajectory Prediction,” CoRR, revised on Mar. 24, 2021, or arXiv:2010.16267v3, 7 pages. [cited by applicant]
Extended European Search Report in European Appln. No. 22792623.5, mailed on Sep. 25, 2024, 10 pages. [cited by applicant]