IP Library › Granted Patent US 12,365,361
Granted Patent B2
US 12,365,361 · App. 18/423,136 · Granted Jul 22, 2025

Agent trajectory prediction using target locations

Inventors: Hang Zhao (Sunnyvale, CA); Jiyang Gao (Foster City, CA); Chen Sun (Great Neck, NY); Yi Shen (Sunnyvale, CA); Yuning Chai (San Mateo, CA); Cordelia Luise Schmid (Saint Ismier, FR); Congcong Li (Cupertino, CA); Benjamin Sapp (Marina del Rey, CA); Dragomir Anguelov (San Francisco, CA); Tian Lan (Sunnyvale, CA); Yue Shen (Mountain View, CA)
Assignee: Waymo LLC
B60W60/001G06N3/02B60W2420/403B60W2554/4049
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,365,361
App. No.
18/423,136
Granted
Jul 22, 2025
Kind
B2
Abstract

A system obtains scene context data characterizing the environment. The scene context data includes data that characterizes a trajectory of an agent in a vicinity of a vehicle up to a current time point. The system identifies a plurality of initial target locations, and generates, for each of a plurality of target locations that each corresponds to one of the initial target locations, a respective predicted likelihood score that represents a likelihood that the target location will be an intended final location for a future trajectory of the agent. For each target location in a first subset of the target locations, the system generates a predicted future trajectory for the agent given that the target location is the intended final location for the future trajectory. The system further selects, as likely future trajectories of the agent, one or more of the predicted future trajectories.

Claims (57)

1. A method performed by one or more computers, the method comprising:

obtaining scene context data characterizing an environment, the scene context data comprising data that characterizes a trajectory of an agent in a vicinity of a vehicle in an environment up to a current time point;

processing the scene context data using a context encoding neural network to generate an encoded representation of the scene context data;

identifying a plurality of initial target locations in the environment;

for each of a plurality of target locations that each corresponds to one of the initial target locations, using a target prediction neural network to process (i) the encoded representation generated by the context encoding neural network and (ii) data specifying the respective initial target location corresponding to the respective target location to generate a target prediction output that specifies a respective predicted likelihood score that represents a likelihood that the target location will be an intended final location for a future trajectory of the agent starting from the current time point;

selecting a first subset of the target locations based on the respective predicted likelihood scores of the target locations;

for each target location in the first subset of the target locations, generating a predicted future trajectory for the agent that is a prediction of the future trajectory of the agent given that the target location is the intended final location for the future trajectory;

selecting, as likely future trajectories of the agent starting from the current time point, one or more of the predicted future trajectories; and

controlling the vehicle using the one or more selected predicted future trajectories.

2. The method of claim 1 , wherein the scene context data further comprises data that characterizes respective trajectories of one or more other agents in the environment up to the current time point.

3. The method of claim 1 , wherein selecting the first subset of the target locations comprises selecting a threshold number of target locations having the highest respective predicted likelihood scores.

4. The method of claim 1 , wherein identifying the plurality of initial target locations in the environment comprises:

dividing a region of the environment that is in a vicinity of the agent into a grid having a plurality of grid points; and

selecting at least some of the grid points in the grid as initial target locations.

5. The method of claim 1 , wherein identifying the plurality of initial target locations in the environment comprises:

obtaining road graph data identifying lanes on one or more roads in the environment; and

sampling, as initial target locations, points from the identified lanes.

6. The method of claim 5 , wherein sampling points from the identified lanes comprises:

for each identified lane, sampling points on a lane center line of the identified lane.

7. The method of claim 1 , wherein generating the predicted future trajectory for the agent that is a prediction of the future trajectory of the agent given that the target location is the intended final location for the future trajectory comprises:

processing (i) the encoded representation and data specifying the (ii) target location using a motion estimation neural network to generate the predicted future trajectory.

8. The method of claim 7 , wherein the target prediction neural network and the motion estimation neural network have been jointly trained.

9. The method of claim 7 , wherein selecting, as likely future trajectories of the agent starting from the current time point, one or more of the predicted future trajectories comprises:

generating a respective refined score for each of the predicted future trajectories that represents a likelihood that the predicted future trajectory will be the future trajectory of the agent after the current time point given the scene context data; and

selecting one or more of the predicted future trajectories based on the refined scores.

10. The method of claim 9 , wherein generating a respective refined score for each of the predicted future trajectories that represents a likelihood that the predicted future trajectory will be the future trajectory of the agent after the current time point given the scene context data comprises:

processing (i) the encoded representation and (ii) the predicted future trajectory using a trajectory scoring neural network to generate the respective refined score for the predicted future trajectory.

11. The method of claim 10 , wherein the target prediction neural network, the motion estimation neural network, and the trajectory scoring neural network have been jointly trained end-to-end.

12. The method of claim 10 , wherein selecting one or more of the predicted future trajectories comprises:

ordering the predicted future trajectories according to the respective refined scores; and

for each predicted future trajectory starting from a first predicted future trajectory in the order and until a specified number of trajectories have been selected:

determining whether the predicted future trajectory is more than a threshold distance from all trajectories that have already been selected according to a distance metric; and

selecting the predicted future trajectory only if the predicted trajectory is more than a threshold distance from all trajectories that have already been selected according to a distance metric.

13. The method of claim 1 , wherein the target prediction output further comprises data defining an offset for the corresponding initial target location, and wherein the target location is a location that is generated by applying the offset to coordinates of the initial target location.

14. The method of claim 13 , wherein the data defining the offset comprises, for each coordinate of the initial target location, parameters of respective probability distributions over offsets for the coordinate, and wherein the method further comprises generating the offset by sampling from the respective probability distributions.

15. The method of claim 13 , wherein the data defining the offset comprises, for each coordinate of the initial target location, a respective offset for the coordinate.

16. A system comprising:

one or more computers; and

one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising:

obtaining scene context data characterizing an environment, the scene context data comprising data that characterizes a trajectory of an agent in a vicinity of a vehicle in an environment up to a current time point;

processing the scene context data using a context encoding neural network to generate an encoded representation of the scene context data;

identifying a plurality of initial target locations in the environment;

for each of a plurality of target locations that each corresponds to one of the initial target locations, using a target prediction neural network to process (i) the encoded representation generated by the context encoding neural network and (ii) data specifying the respective initial target location corresponding to the respective target location to generate a target prediction output that specifies a respective predicted likelihood score that represents a likelihood that the target location will be an intended final location for a future trajectory of the agent starting from the current time point;

selecting a first subset of the target locations based on the respective predicted likelihood scores of the target locations;

for each target location in the first subset of the target locations, generating a predicted future trajectory for the agent that is a prediction of the future trajectory of the agent given that the target location is the intended final location for the future trajectory;

selecting, as likely future trajectories of the agent starting from the current time point, one or more of the predicted future trajectories; and

controlling the vehicle using the one or more selected predicted future trajectories.

17. The system of claim 16 , wherein the scene context data further comprises data that characterizes respective trajectories of one or more other agents in the environment up to the current time point.

18. The system of claim 16 , wherein selecting the first subset of the target locations comprises selecting a threshold number of target locations having the highest respective predicted likelihood scores.

19. One or more non-transitory computer-readable storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

obtaining scene context data characterizing an environment, the scene context data comprising data that characterizes a trajectory of an agent in a vicinity of a vehicle in an environment up to a current time point;

processing the scene context data using a context encoding neural network to generate an encoded representation of the scene context data;

identifying a plurality of initial target locations in the environment;

for each of a plurality of target locations that each corresponds to one of the initial target locations, using a target prediction neural network to process (i) the encoded representation generated by the context encoding neural network and (ii) data specifying the respective initial target location corresponding to the respective target location to generate a target prediction output that specifies a respective predicted likelihood score that represents a likelihood that the target location will be an intended final location for a future trajectory of the agent starting from the current time point; selecting a first subset of the target locations based on the respective predicted likelihood scores of the target locations;

for each target location in the first subset of the target locations, generating a predicted future trajectory for the agent that is a prediction of the future trajectory of the agent given that the target location is the intended final location for the future trajectory;

selecting, as likely future trajectories of the agent starting from the current time point, one or more of the predicted future trajectories; and

controlling the vehicle using the one or more selected predicted future trajectories.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jan 30, 2024
From: ZHAO, HANG; GAO, JIYANG; SUN, CHEN; SHEN, YI; CHAI, YUNING; SCHMID, CORDELIA LUISE; LI, CONGCONG; SAPP, BENJAMIN; ANGUELOV, DRAGOMIR; LAN, TIAN; SHEN, YUE
To: WAYMO LLC
Reel/Frame 066300/0588 →
Continuity (3)
Continuation 17387852 · Jul 28, 2021
Provisional Application 63057717 · Jul 28, 2020
Related Publication 20240278803A1 · Aug 22, 2024
References Cited (54)
US 10102750B2 · Aso et al. · 2018 [cited by applicant]
US 20180189578A1 · Yang · 2018 [cited by examiner]
US 20190025841A1 · Haynes · 2019 [cited by examiner]
US 20190369637A1 · Shalev-Shwartz et al. · 2019 [cited by applicant]
US 20200110416A1 · Hong · 2020 [cited by examiner]
US 20200156632A1 · Ding et al. · 2020 [cited by applicant]
US 20200307562A1 · Ghafarianzadeh · 2020 [cited by examiner]
US 20210139024A1 · Crego · 2021 [cited by examiner]
US 20210370980A1 · Ramamoorthy · 2021 [cited by examiner]
US 20210402991A1 · Gautam · 2021 [cited by examiner]
CN 110415266 · 2019 [cited by applicant]
WO WO2018232680 · 2018 [cited by applicant]
Alahi et al., “Social LSTM: Human Trajectory Prediction in Crowded Spaces,” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016, pp. 961-971. [cited by applicant]
Broadhurst et al., “A prediction and planning framework for road safety analysis, obstacle avoidance and driver information,” Carnegie Mellon University, the Robotics Institute, 2004, 31 pages. [cited by applicant]
Casas et al., “Intentnet: Learning to predict intention from raw sensor data,” Proceedings of The 2nd Conference on Robot Learning, 2018, 87:947-956. [cited by applicant]
Chai et al., “Multipath: Multiple probabilistic anchor trajectory hypotheses for behavior prediction,” CoRR, Oct. 2019, arxiv.org/abs/1910.05449, 14 pages. [cited by applicant]
Colyar et al., “US highway 101 dataset,” Next Generation Simulation, Jan. 2007, 3 pages. [cited by applicant]
Cui et al., “Multimodal trajectory predictions for autonomous driving using deep convolutional networks,” 2019 International Conference on Robotics and Automation, May 2019, 7 pages. [cited by applicant]
Deo et al., “Trajectory Forecasts in Unknown Environments Conditioned on Grid-Based Plans,” CoRR, Apr. 29, 2021, arXiv:2001.00735v2, 12 pages. [cited by applicant]
Gao et al., “VectorNet: Encoding HD Maps and Agent Dynamics from Vectorized Representation,” CoRR, May 2020, arxiv.org/abs/2005.04259, 9 pages. [cited by applicant]
Gupta et al., “Social GAN: Socially acceptable trajectories with generative adversarial networks,” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018, pp. 2255-2264. [cited by applicant]
He et al., “Deep residual learning for image recognition,” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016, pp. 770-778. [cited by applicant]
Helbing et al., “Social force model for pedestrian dynamics,” Physical Review E 51, (5):4282. [cited by applicant]
Hong et al., “Rules of the road: Predicting driving behavior with a convolutional model of semantic interactions,” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019, pp. 8454-8462. [cited by applicant]
International Preliminary Report on Patentability in International Appln. No. PCT/US2021/043541, dated Feb. 9, 2023, 7 pages. [cited by applicant]
International Search Report and Written Opinion in International Appln. No. PCT/US2021/043541, dated Mar. 2, 2022, 10 pages. [cited by applicant]
Kingma et al., “Adam: A method for stochastic optimization,” CoRR, Jan. 2017, arXiv:1412.6980, 15 pages. [cited by applicant]
Kingma et al., “Auto-encoding variational bayes,” CoRR, Dec. 2013, arXiv:1312.6114, 14 pages. [cited by applicant]
Kitani et al., “Activity forecasting,” European Conference on Computer Vision, 2012, pp. 201-214. [cited by applicant]
Krajewski et al., “The highD dataset: A drone dataset of naturalistic vehicle trajectories on German highways for validation of highly automated driving systems,” 2018 21st International Conference on Intelligent Transp… [cited by applicant]
Lambert et al., “Argoverse: 3d tracking and forecasting with rich maps,” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019, pp. 8748-8757. [cited by applicant]
Lee et al., “Desire: Distant future prediction in dynamic scenes with interacting agents,” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017, pp. 336-345. [cited by applicant]
Ma et al., “Forecasting interactive dynamics of pedestrians with fictitious play,” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017, pp. 774-782. [cited by applicant]
Mangalam et al., “It is not the journey but the destination: Endpoint conditioned trajectory prediction,” European Conference on Computer Vision, Nov. 2020, 19 pages. [cited by applicant]
Office Action in European Appln. No. 21856432.6, dated May 28, 2024, 11 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]
Rehder et al., “Goal-directed pedestrian prediction,” Proceedings of the IEEE International Conference on Computer Vision (ICCV) Workshops, 2015, pp. 50-58. [cited by applicant]
Rehder et al., “Pedestrian prediction by planning using deep neural networks,” 2018 IEEE International Conference on Robotics and Automation, May 2018, 9 pages. [cited by applicant]
Rezende et al., “Variational inference with normalizing flows,” Proceedings of the 32nd International Conference on Machine Learning, 2015, 37:1530-1538. [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, 2018, pp. 772-788. [cited by applicant]
Robicquet et al., “Forecasting social navigation in crowded complex scenes,” CoRR, Jan. 2016, arxiv.org/abs/1601.00998, 16 pages. [cited by applicant]
Sadeghian et al., “Sophie: An attentive gan for predicting paths compliant to social and physical constraints,” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019, pp. 1349-1358. [cited by applicant]
Salimans et al., “Improved techniques for training GANs,” 30th Conference on Neural Information Processing Systems, 2016, 9 pages. [cited by applicant]
Sun et al., “Stochastic prediction of multi agent interactions from partial observations,” CoRR, Feb. 2019, arxiv.org/abs/1902.09641, 15 pages. [cited by applicant]
Tang et al., “Multiple futures prediction,” 33rd Conference on Neural Information Processing Systems, 2019, 11 pages. [cited by applicant]
Tsubouchi et al., “Behavior of a mobile robot navigated by an ‘iterated forecast and planning’ scheme in the presence of multiple moving obstacles,” Proceedings of the 1994 IEEE International Conference on Robotics and … [cited by applicant]
Williams et al., “A learning algorithm for continually running fully recurrent neural networks,” Neural Computation, Jun. 1989, 1(2):270-280. [cited by applicant]
Yeh et al., “Diverse generation for multi-agent sports games,” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019, pp. 4610-4619. [cited by applicant]
Yuan et al., “Diverse trajectory forecasting with determinantal point processes,” CoRR, Dec. 2019, arxiv.org/abs/1907.04967, 15 pages. [cited by applicant]
Zhan et al., “Generative multi-agent behavioral cloning,” Generative Multi-Agent Behavioral Cloning, 2018, 12 pages. [cited by applicant]
Zhan et al., “Interaction Dataset: An INTERnational, Adversarial and Cooperative moTION Dataset in Interactive Driving Scenarios with Semantic Maps,” CoRR, Sep. 2019, arXiv:1910.03088, 13 pages. [cited by applicant]
Zheng et al., “Generating long-term trajectories using deep hierarchical networks,” CoRR, Jun. 2017, arxiv.org/abs/1706.07138, 9 pages. [cited by applicant]
Ziebart et al., “Planning-based prediction for pedestrians,” 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, Oct. 2009, 6 pages. [cited by applicant]