IP Library › Granted Patent US 12,709,302
Granted Patent B2
US 12,709,302 · App. 18/366,202 · Granted Aug 18, 2026

Motion planning

Inventors: Yuxiao Chen (Newark, CA); Sushant Veer (Sunnyvale, CA); Peter Karkus (Zurich, CH); Marco Pavone (Stanford, CA)
Assignee: NVIDIA Corporation
B60W60/0027B60W2554/404B60W2554/4046B60W2554/802
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,709,302
App. No.
18/366,202
Granted
Aug 18, 2026
Kind
B2
Abstract

In various examples, a gradient-based motion planner evaluates a cost function corresponding to routes for a machine and an obstacle to jointly update the routes. The cost function may include terms to penalize deviation from an initial route predicted for the obstacle and acceleration or jerk for the obstacle. The routes for the machine and the obstacle that are updated may be selected using motion classes that characterize relative motion between a route for the machine and a route for the obstacle. A motion class may be based at least on an angular distance between the machine and the agent and free-end homotopy, where members of the class execute the same relative motion with respect to other agents while being continuously transformable to any other member of the class. The members of the class may have the same start point and different end points.

Claims (83)

1 . A system comprising:

one or more processing units to perform operations including:

evaluating, over one or more time steps, a cost function that combines one or more first costs corresponding to at least one first route corresponding to a machine with one or more second costs corresponding to at least one second route corresponding to at least one agent to form one or more cost values corresponding to the cost function;

jointly updating, over the one or more time steps and using the one or more cost values, the at least one first route to at least one updated first route and the at least one second route to at least one updated second route that corresponds to a predicted reaction to the at least one updated first route based at least on determining, using a gradient of the cost function, that the at least one updated first route and the at least one updated second route reduce the cost function;

determining a trajectory for the machine based at least on the jointly updating; and

performing one or more control operations for the machine using the trajectory.

2 . The system of claim 1 , wherein the cost function includes one or more terms that penalize the at least one updated second route based at least on an amount of deviation of the at least one updated second route from the at least one second route corresponding to the at least one agent.

3 . The system of claim 1 , wherein the cost function includes one or more terms that penalize one or more of acceleration or jerk for the at least one updated second route of the at least one agent.

4 . The system of claim 1 , wherein the cost function includes one or more variables that alter a relative distribution of emphasis in the cost function between the machine and the at least one agent.

5 . The system of claim 1 , wherein the jointly updating includes updating the at least one first route and the at least one second route over a plurality of iterations, and the determining the trajectory includes determining a first portion of the trajectory in a first iteration of the plurality of iterations and a second portion of the trajectory in a second iteration of the plurality of iterations.

6 . The system of claim 1 , wherein the operations further include:

categorizing sets of routes for the machine and the at least one agent into a homotopy class based at least on the sets including trajectories for the machine that have a same initial point and a different end point; and

selecting a subset of the sets of the routes for the evaluating, wherein the at least one first route and the at least one second route are included in the subset and the jointly updating constrains the at least one updated second route and the at least one updated first route to the homotopy class.

7 . The system of claim 1 , wherein the operations further include:

categorizing sets of routes for the machine and the at least one agent based at least on angular distances between the machine and the at least one agent to determine categorized sets of the routes; and

selecting a subset of the sets of the routes for the evaluating, wherein the at least one first route and the at least one second route are included in the subset.

8 . The system of claim 1 , wherein jointly updating constrains the at least one updated first route and the at least one updated second route to a motion class selected for a motion plan, the motion class characterizing a relative motion between the machine and the at least one agent.

9 . The system of claim 1 , wherein the at least one second route includes an initial route that represents a trajectory prediction for the at least one agent that is unconditioned on the machine, and the cost function includes one or more terms that penalize the at least one updated second route based at least on an amount of deviation of the at least one updated second route from the initial route.

10 . The system of claim 1 , wherein the system is comprised in at least one of:

a control system for an autonomous or semi-autonomous machine;

a perception system for an autonomous or semi-autonomous machine;

a system for performing simulation operations;

a system for performing digital twin operations;

a system for performing light transport simulation;

a system for performing collaborative content creation for 3D assets;

a system for performing deep learning operations;

a system implemented using an edge device;

a system implemented using a robot;

a system for performing conversational AI operations;

a system implementing one or more language models;

a system implementing one or more large language models (LLMs);

a system for performing one or more generative AI applications;

a system for generating synthetic data;

a system for presenting at least one of virtual reality content, augmented reality content, or mixed reality content;

a system incorporating one or more virtual machines (VMs);

a system implemented at least partially in a data center; or

a system implemented at least partially using cloud computing resources.

11 . A method comprising:

evaluating, over a plurality of time steps, gradients corresponding to a cost function that combines one or more first costs corresponding to at least one first route corresponding to a machine with one or more second costs corresponding to at least one second route corresponding to at least one agent;

adjusting the at least one first route to at least one updated first route and the at least one second route to at least one updated second route that corresponds to a predicted reaction to the at least one updated first route based at least on determining, using the gradients, that the at least one updated first route and the at least one updated second route reduce the cost function;

determining a path for the machine based at least on the adjusting; and

performing one or more control operations for the machine using the path.

12 . The method of claim 11 , wherein the cost function includes one or more terms that penalize one or more of deviation from the at least one second route corresponding to the at least one agent, acceleration for the at least one agent, or jerk for the at least one agent.

13 . The method of claim 11 , further comprising:

categorizing sets of routes for the machine and the at least one agent into a homotopy class based at least on the sets including trajectories for the machine that have a same initial point and a different end point; and

selecting a subset of the sets of the routes for the evaluating, wherein the at least one first route and the at least one second route are included in the subset.

14 . The method of claim 11 , further comprising:

categorizing sets of routes for the machine and the at least one agent based at least on angular distances between the machine and the at least one agent to determine categorized sets of the routes; and

selecting a subset of the sets of the routes for the evaluating, wherein the at least one first route and the at least one second route are included in the subset.

15 . The method of claim 11 , wherein the evaluating includes:

evaluating, using the cost function, a first version of the at least one first route and a first version of the at least one second route to determine a second version of the at least one first route and a second version of the at least one second route; and

evaluating, using the cost function, the second version of the at least one first route and the second version of the at least one second route to determine a third version of the at least one first route and a third version of the at least one second route, wherein the path is based at least on the third version of the at least one first route.

16 . A system comprising:

one or more circuits to perform operations including:

performing one or more control operations for a machine using a trajectory, the trajectory determined based at least on:

adjusting, using a cost function that combines one or more first costs corresponding to at least one first route corresponding to the machine with one or more second costs corresponding to at least one second route corresponding to at least one agent, the at least one first route to at least one updated first route and the at least one second route to at least one updated second route that corresponds to a predicted reaction to the at least one updated first route,

the adjusting being based at least on determining, using a gradient of the cost function, that the at least one updated first route and the at least one updated second route reduce the cost function.

17 . The system of claim 16 , wherein the cost function includes one or more terms that penalize one or more of deviation from the at least one second route corresponding to the at least one agent, acceleration for the at least one agent, or jerk for the at least one agent.

18 . The system of claim 16 , wherein the trajectory is further determined based at least on:

categorizing sets of routes for the machine and the at least one agent into a homotopy class based at least on the sets including trajectories for the machine that have a same initial point and a different end point; and

selecting a subset of the sets of the routes for the adjusting, wherein the at least one first route and the at least one second route are included in the subset.

19 . The system of claim 16 , wherein the trajectory is further determined based at least on:

categorizing sets of routes for the machine and the at least one agent based at least on angular distances between the machine and the at least one agent to determine categorized sets of the routes; and

selecting a subset of the sets of the routes for the adjusting, wherein the at least one first route and the at least one second route are included in the subset.

20 . The system of claim 16 , wherein the system is comprised in at least one of:

a control system for an autonomous or semi-autonomous machine;

a perception system for an autonomous or semi-autonomous machine;

a system for performing simulation operations;

a system for performing digital twin operations;

a system for performing light transport simulation;

a system for performing collaborative content creation for 3D assets;

a system for performing deep learning operations;

a system implemented using an edge device;

a system implemented using a robot;

a system for performing conversational AI operations;

a system implementing one or more language models;

a system implementing one or more large language models (LLMs);

a system for performing one or more generative AI applications;

a system for generating synthetic data;

a system for presenting at least one of virtual reality content, augmented reality content, or mixed reality content;

a system incorporating one or more virtual machines (VMs);

a system implemented at least partially in a data center; or

a system implemented at least partially using cloud computing resources.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 16, 2023
From: CHEN, YUXIAO; VEER, SUSHANT; KARKUS, PETER; PAVONE, MARCO
To: NVIDIA CORPORATION
Reel/Frame 064604/0494 →
Continuity (1)
Related Publication 20250058802A1 · Feb 20, 2025
References Cited (49)
US 20190243371A1 · Nister et al. · 2019 [cited by applicant]
US 20190258251A1 · Ditty et al. · 2019 [cited by applicant]
US 20190384304A1 · Towal et al. · 2019 [cited by applicant]
US 20200159225A1 · Zeng · 2020 [cited by examiner]
US 20200249674A1 · Dally et al. · 2020 [cited by applicant]
US 20210149404A1 · Zeng · 2021 [cited by examiner]
US 20210213978A1 · Edling · 2021 [cited by examiner]
US 20210253128A1 · Nister et al. · 2021 [cited by applicant]
US 20220032960A1 · Wang · 2022 [cited by examiner]
US 20220176995A1 · Subramanian · 2022 [cited by examiner]
US 20220219726A1 · Yadmellat · 2022 [cited by examiner]
US 20220355822A1 · Molinari · 2022 [cited by examiner]
US 20230089978A1 · Pulver · 2023 [cited by examiner]
KR 20210003752A · 2021 [cited by examiner]
Campana et al., “A gradient-based path optimization method for motion planning”, 2016, Hal Open Science (Year: 2016). [cited by examiner]
English translation of KR-20210003752-A (Year: 2021). [cited by examiner]
Bradbury, J., et al.; “JAX: composable transformations of Python+NumPy programs”, 2018. URL http://github.com/google/jax. [cited by applicant]
Ziebart, et al.; “Maximum Entropy Inverse Reinforcement Learning,” in AAAI Conference on Artificial Intelligence, vol. 8, 2008, pp. 1433-1438. [cited by applicant]
Salzmann, et al.; “Trajectron++:Dynamically-feasible Trajectory Forecasting with Heterogeneous Data”; In European Conference on Computer Vision, pp. 683-700, Springer, 2020. [cited by applicant]
Rhinehart, et al.; “Precog: Prediction Conditioned on Goals in Visual Multi-Agent Settings”; In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 2821-2830, 2019. [cited by applicant]
Cui, et al.; “LookOut: Diverse Multi-Future Prediction and Planning for Self-Driving”; In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 16107-16116, 2021; 10 pgs. [cited by applicant]
Chen, et al.; “Interactive Multi-Modal Motion Planning with Branch Model Predictive Control”; arXiv:2109.05128; Sep. 18, 2021, 10 pgs. [cited by applicant]
Chen, et al.; “ScePT: Scene-Consistent, Policy-Based Trajectory Predictions for Planning”; In Conference on Computer Vision and Pattern Recognition, 2022, 10 pgs. [cited by applicant]
Sadigh, et al., “Planning for Autonomous Cars That Leverage Effects on Human Actions,” In Robotics: Science and Systems, 2016, 9 pgs. [cited by applicant]
Zuo, et al.; “MPC-based Cooperative Control Strategy of Path Planning and Trajectory tracking for Intelligent Vehicles,” IEEE Transactions of Intelligent Vehicles, vol. X, No. X, Jan. 2020, 10 pgs. [cited by applicant]
Liebner, et al.; “Driver Intent Inference at Urban Intersections Using the Intelligent Driver Model,” in 2012 IEEE intelligent vehicles symposium, 2012, 6 pgs. [cited by applicant]
Yuan, et al.; “AgentFormer: Agent-Aware Transformers for Socio-Temporal Multi-Agent Forecasting,” in IEEE Int. Conf. on Computer Vision, 2021, 11 pgs. [cited by applicant]
Chen, et al.; “Tree-Structured Policy Planning with Learned Behavior Models,” https://arxiv.org/abs/2301.11902; Feb. 27, 2023, 8 pgs. [cited by applicant]
Rosolia, et al.; “Autonomous Vehicle Control: A Nonconvex Approach for Obstacle Avoidance,” IEEE Transactions on Control Systems Technology, vol. 25, No. 2, Mar. 2017, 16 pgs. [cited by applicant]
Censi, et al.; “A Bayesian Framework for Optimal Motion Planning with Uncertainty,” i n2008 IEEE International Conference on Robotics and Automation, 2008, 8 pgs. [cited by applicant]
Batz, et al.; “Recognition of Dangerous Situations with a Cooperative Group of Vehicles,” in 2009 IEEE Intelligent Vehicles Symposium. IEEE, 2009, pp. 907-912. [cited by applicant]
Ammoun, et al.; “Real Time Trajectory Prediction for Collision Risk Estimation Between Vehicles,” Located at chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://inria.hal.science/inria-00438624/document; Dec. 4,… [cited by applicant]
Trautman, et al.; “Unfreezing the Robot: Navigation in Dense, Interacting Crowds,” in 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, IEEE, 2010, 7 pgs. [cited by applicant]
Trautman, et al.; “Robot Navigation in Dense Human Crowds: The Case from Cooperation,” in 2013 IEEE International Conference on Robotics and Automation. IEEE. 2013, 8 pgs. [cited by applicant]
Chen, et al.; “Crowd-Robot Interaction: Crowd-Aware Robot Navigation with Attention-based Deep Reinforcement Learning,” https://arxiv.org/abs/1809.08835#; Feb. 19, 2019, 8 pgs. [cited by applicant]
Sidigh, et al.; “Active Preference-Based Learning of Reward Functions,” 2017, 9 pgs. [cited by applicant]
Pfeiffer, et al.; “Predicting Action to Act Predictably: Cooperative Partial Motion Planning with Maximum Entropy Models,” in 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2016, … [cited by applicant]
Li, et al.; “Game Theoretic Modeling of Driver and Vehicle Interactions for Verification and Validation of Autonomous Vehicle Control Systems,” https://arxiv.org/abs/1608.08589, Aug. 30, 2016, 13 pgs. [cited by applicant]
Wei, et al.; “Autonomous Vehicle Social Behavior for Highway Entrance Ramp Management,” in IEEE Intelligent Vehicles Symposium, 2013, 7 pgs. [cited by applicant]
Hubmann, et al.; “Decision Making for Autonomous Driving Considering Interaction and Uncertain Prediction of Surrounding Vehicles,” in IEEE Intelligent Vehicles Symposium, 2017, 8 pgs. [cited by applicant]
Hoermann, et al.; “Probabilistic Long-Term Prediction for Autonomous Vehicles,” in 2017 IEEE Intelligent Vehicles Symposium (IV). IEEE, 2017, 7 pgs. [cited by applicant]
Dong, et al.; “Intention Estimation for Ramp Merging Control in Autonomous Driving,” in 2017 IEEE Intelligent Vehicles Symposium (IV). IEEE, 2017, 6 pgs. [cited by applicant]
During, et al.; “Cooperative Decentralized Decision Making for Conflict Resolution Among Autonomous Agents,” in 2014 IEEE International Symposium on Innovations in Intelligent Systems and Applications (INISTA) Proceedin… [cited by applicant]
Bhattacharya, et al.; “Topological Constraints in Search-Based Robot Path Planning,” Autonomous Robots, vol. 33, No. 3, 2012, 23 pgs. [cited by applicant]
Yi, et al.; “Model Predictive Trajectory Planning for Automated Driving,” IEEE Transactions on Intelligent Vehicles, vol. 4, No. 1, pp. 24-38, 2018. [cited by applicant]
Anderson, et al.; “Constraint-Based Planning and Control for Safe, Semi-Autonomous Operation of Vehicles,” in 2012 IEEE Intelligent Vehicles Symposium. IEEE, 2012, 6 pgs. [cited by applicant]
Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,” 2023. [Online]. Available: https://www.gurobi.com; 44 pgs. [cited by applicant]
Zanelli, et al.; “Forces NLP: An Efficient Implementation of Interior-Point . . . Methods for Multistage Nonlinear Nonconvex Programs,” International Journal of Control, 2017, 18 pgs. [cited by applicant]
Caesar, et al.; “NuPlan: A Closed-Loop ML-Based Planning Benchmark for Autonomous Vehicles,” https://arxiv.org/abs/2106.11810; Feb. 4, 2022, 5 pgs. [cited by applicant]