IP Library › Granted Patent US 12,428,025
Granted Patent B2
US 12,428,025 · App. 18/389,304 · Granted Sep 30, 2025

Multi-profile quadratic programming (MPQP) for optimal gap selection and speed planning of autonomous driving

Inventors: Alexandre Miranda Anon (Premia de Dalt, ES); Sangjae Bae (San Jose, CA); David Isele (Sunnyvale, CA); Manish Saroya (Santa Clara, CA); Kikuo Fujimura (Palo Alto, CA)
Assignee: Honda Motor Co., Ltd.
B60W60/001B60W30/14B60W30/143B60W50/00B60W60/0011B60W60/0016B60W60/00272B60W60/00276B60W2050/0003B60W2510/104B60W2554/4044B60W2554/80B60W2556/10
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,428,025
App. No.
18/389,304
Granted
Sep 30, 2025
Kind
B2
Abstract

A method for generating operable driving areas for an autonomous driving vehicle based on a path trajectory of the autonomous driving vehicle is provided. The method may form a space time (ST) graph indicating a distance of travel along the path trajectory with respect to time of the autonomous driving vehicle and path trajectories of devices intersecting with the path trajectory of the autonomous driving vehicle, wherein the path trajectory of each device is based on current and historical data for each device. The method may segment the ST graph into cells, wherein viable cells represent discretized viable unoccupied spaces in the ST graph. The method may find passage ways for the autonomous driving vehicle based on the viable cells. The method may select a desired passage way using quadratic programming (QP) optimization when multiple passage ways are found.

Claims (41)

1. A method for generating operable driving areas for an autonomous driving vehicle based on a path trajectory of the autonomous driving vehicle, comprising:

forming a space time (ST) graph indicating a distance of travel along the path trajectory with respect to time of the autonomous driving vehicle and path trajectories of devices intersecting with the path trajectory of the autonomous driving vehicle, wherein the path trajectory of each device is based on current and historical data for each device;

segmenting the ST graph Into cells, each cell having an upper bound and a lower bound defining a space over a time segment, wherein viable cells represent discretized viable unoccupied spaces in the ST graph;

finding passage ways for the autonomous driving vehicle based on the viable cells by expanding a profile of each viable cell to include adjacent overlapping viable cells forming the passage ways; and

selecting a desired passage way using quadratic programming (QP) optimization when multiple passage ways are found.

2. The method of claim 1 , wherein forming a space time (ST) graph comprises using temporal predictions based on current and historical data in forming the path trajectory of each device.

3. The method of claim 1 , wherein forming a space time (ST) graph comprises using intention estimation in forming the path trajectory of each device.

4. The method of claim 1 , wherein forming a space time (ST) graph comprises using intention estimation and chain reaction predictions in forming the path trajectory of each device.

5. The method of claim 1 , wherein forming the ST graph comprises forming the ST graph in a moving coordinate system.

6. The method of claim 1 , wherein forming the ST graph comprises forming the ST graph in Frenet frame, wherein each area where the path trajectory of each device intersects with the path trajectory of the autonomous driving vehicle is converted to Frenet frame.

7. The method of claim 1 , wherein forming a space time (ST) graph comprises using a pair of lines in forming the path trajectory of each device.

8. The method of claim 1 , wherein forming a space time (ST) graph comprises using a pair of parallel lines in forming the path trajectory of each device.

9. The method of claim 1 , wherein forming the ST graph comprises:

forming a polygon representing each device;

drawing the path trajectory for each device, wherein the path trajectory is formed of a pair of parallel lines; and

marking where each device intersects with the path trajectory of the autonomous driving vehicle.

10. The method of claim 9 , wherein each polygon is dimensioned based on a size of each device, each polygon being oversized by at least one of parameterized margins, noise, risk factor, prediction noise and combinations thereof.

11. A method of controlling an autonomous vehicle, the method implemented using a vehicle control system including a processor communicatively coupled to a memory device, the method comprising:

forming a space time (ST) graph indicating a distance of travel along the path trajectory with respect to time of the autonomous driving vehicle and path trajectories of devices intersecting with the path trajectory of the autonomous driving vehicle, wherein the path trajectory of each device is based on intention estimation and chain reaction predictions in forming the path trajectory of each device;

segmenting the ST graph into cells, each cell having an upper bound and a lower bound defining a space over a time segment, wherein viable cells represent discretized viable unoccupied spaces in the ST graph;

finding passage ways for the autonomous driving vehicle based on the viable cells by expanding a profile of each viable cell to include adjacent overlapping viable cells forming the passage ways; and

selecting a desired passage way using quadratic programming (QP) optimization when multiple passage ways are found.

12. The method of claim 11 , wherein forming the ST graph comprises forming the ST graph in a moving coordinate system.

13. The method of claim 11 , wherein forming the ST graph comprises forming the ST graph in Frenet frame, wherein each area where the path trajectory of each device intersects with the path trajectory of the autonomous driving vehicle is converted to Frenet frame.

14. The method of claim 11 , wherein forming a space time (ST) graph comprises using a pair of lines in forming the path trajectory of each device.

15. The method of claim 11 , wherein forming a space time (ST) graph comprises using a pair of parallel lines in forming the path trajectory of each device.

16. The method of claim 11 , wherein forming the ST graph comprises:

forming a polygon representing each device;

drawing the path trajectory for each device, wherein the path trajectory is formed of a pair of parallel lines; and

marking where each device Intersects with the path trajectory of the autonomous driving vehicle.

17. The method of claim 16 , wherein each polygon is dimensioned based on a size of each device, each polygon being oversized by at least one of parameterized margins, noise, risk factor, prediction noise and combinations thereof.

18. A method for generating operable driving areas for an autonomous driving vehicle based on a path trajectory of the autonomous driving vehicle, comprising:

forming a space time (ST) graph in a moving coordinate system indicating a distance of travel along the path trajectory with respect to time of the autonomous driving vehicle and path trajectories of devices intersecting with the path trajectory of the autonomous driving vehicle, wherein the path trajectory of each device is based on a temporal prediction using current and historical data for each device;

segmenting the ST graph Into cells, each cell having an upper bound and a lower bound defining a space over a time segment, wherein viable cells represent discretized viable unoccupied spaces in the ST graph;

finding passage ways for the autonomous driving vehicle based on the viable cells by expanding a profile of each viable cell to include adjacent overlapping viable cells forming the passage ways; and

selecting a desired passage way using quadratic programming (QP) optimization when multiple passage ways are found.

19. The method of claim 18 , wherein forming the ST graph comprises forming the ST graph in Frenet frame, wherein each area where the path trajectory of each device intersects with the path trajectory of the autonomous driving vehicle is converted to Frenet frame.

20. The method of claim 18 , wherein forming the ST graph comprises:

forming a polygon representing each device;

drawing the path trajectory for each device, wherein the path trajectory is formed of a pair of parallel lines; and

marking where each device intersects with the path trajectory of the autonomous driving vehicle.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Nov 14, 2023
From: MIRANDA ANON, ALEXANDRE; BAE, SANGJAE; ISLE, DAVID; SAROYA, MANISH; FUJIMURA, KIKUO
To: HONDA MOTOR CO., LTD.
Reel/Frame 065554/0446 →
Continuity (2)
Provisional Application 63541022 · Sep 28, 2023
Related Publication 20250108836A1 · Apr 3, 2025
References Cited (31)
US 12296857B2 · Afshar · 2025 [cited by examiner]
US 20190250617A1 · Ford · 2019 [cited by examiner]
US 20220227367A1 · Kario · 2022 [cited by examiner]
Lester E Dubins. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. American Journal of mathematics, 79(3):497-516, 1957. [cited by applicant]
James Reeds and Lawrence Shepp. Optimal paths for a car that goes both forwards and backwards. Pacific journal of mathematics, 145(2):367-393, 1990. [cited by applicant]
Alexander Heilmeier, Alexander Wischnewski, Leonhard Hermansdorfer, Johannes Betz, Markus Lienkamp, and Boris Lohmann. Minimum curvature trajectory planning and control for an autonomous race car. Vehicle System Dynamic… [cited by applicant]
Maxime Bouton, Alireza Nakhaei, David Isele, Kikuo Fujimura, and Mykel J Kochenderfer. Reinforcement learning with iterative reasoning for merging in dense traffic. In 2020 IEEE 23rd International Conference on Intellig… [cited by applicant]
Sangjae Bae, David Isele, Alireza Nakhaei, Peng Xu, Alexandre Miranda Anon, Chiho Choi, Kikuo Fujimura, and Scott Moura. Lane—change in dense traffic with model predictive control and neural networks. IEEE Transactions … [cited by applicant]
Boris Ivanovic, Amine Elhafsi, Guy Rosman, Adrien Gaidon, and Marco Pavone. Mats: An interpretable trajectory forecasting representation for planning and control. arXiv preprint arXiv:2009.07517, 2020. [cited by applicant]
Faizan M Tariq, David Isele, John S. Baras, and Sangjae Bae. RCMS: Risk-aware crash mitigation system for autonomous vehicles. IEEE Intelligent Vehicles Symposium, 2023. [cited by applicant]
Thierry Fraichard and Christian Laugier. Path-velocity decomposition revisited and applied to dynamic trajectory planning. In [1993] Proceedings IEEE International Conference on Robotics and Automation, pp. 40-45. IEEE,… [cited by applicant]
Piyush Gupta, David Isele, Donggun Lee, and Sangjae Bae. Interaction-aware trajectory planning for autonomous vehicles with analytic integration of neural networks into model predictive control. 2023 International Confe… [cited by applicant]
Anahita Mohseni-Kabir, David Isele, and Kikuo Fujimura. Interactionaware multi-agent reinforcement learning for mobile agents with individual goals. In 2019 International Conference on Robotics and Automation (ICRA), pp… [cited by applicant]
Kamal Kant and Steven W Zucker. Toward efficient trajectory planning: The path-velocity decomposition. The international journal of robotics research, 5(3):72-89, 1986. [cited by applicant]
Quang-Cuong Pham, Stephane Caron, Puttichai Lertkultanon, and Yoshihiko Nakamura. Planning truly dynamic motions: Path-velocity decomposition revisited. arXiv preprint arXiv:1411.4045, 2014. [cited by applicant]
Changliu Liu, Wei Zhan, and Masayoshi Tomizuka. Speed profile planning in dynamic environments via temporal optimization. In 2017 IEEE Intelligent Vehicles Symposium (IV), pp. 154-159, 2017. [cited by applicant]
Zeyu Yang, Jin Huang, Hui Yin, Diange Yang, and Zhihua Zhong. Path tracking control for underactuated vehicles with matched-mismatched uncertainties: An uncertainty decomposition based constraint-following approach. IEE… [cited by applicant]
Vasundhara Jain, Uli Kolbe, Gabi Breuel, and Christoph Stiller. Collision avoidance for multiple static obstacles using path-velocity decomposition. IFAC—PapersOnLine, 52(8):265-270, 2019. [cited by applicant]
Wenda Xu. Motion Planning for Autonomous Vehicles in Urban Scenarios: A Sequential Optimization Approach. PhD thesis, Carnegie Mellon University, Feb. 2022. [cited by applicant]
Till-Julius Kruger, Daniel G “ohring, and Fritz Ulbrich.” Graph-Based Speed Planning for Autonomous Driving. PhD thesis, Free University of Berlin Berlin, Germany, 2019. [cited by applicant]
Christoforos Mavrogiannis, Jonathan A DeCastro, and Siddhartha S Srinivasa. Implicit multiagent coordination at unsignalized intersections via multimodal inference enabled by topological braids. arXiv preprint arXiv:200… [cited by applicant]
Francesco Micheli, Mattia Bersani, Stefano Arrigoni, Francesco Braghin, and Federico Cheli. Nmpc trajectory planner for urban autonomous driving. Vehicle system dynamics, 61(5):1387-1409, 2023. [cited by applicant]
Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. [cited by applicant]
Chao Sun, Jacopo Guanetti, Francesco Borrelli, and Scott J Moura. Optimal eco-driving control of connected and autonomous vehicles through signalized intersections. IEEE Internet of Things Journal, 7(5):3759-3773, 2020. [cited by applicant]
Xiaowei Shi and Xiaopeng Li. Trajectory planning for an autonomous vehicle with conflicting moving objects along a fixed path-an exact solution method. Transportation Research Part B: Methodological, 173:228-246, 2023. [cited by applicant]
Moritz Werling, Julius Ziegler, Soren Kammel, and Sebastian Thrun. Optimal trajectory generation for dynamic street scenarios in a frenet frame. In 2010 IEEE international conference on robotics and automation, pp. 987-… [cited by applicant]
Alan Bundy and Lincoln Wallen. Breadth-first search. Catalogue of artificial intelligence tools, pp. 13-13, 1984. [cited by applicant]
Alexey Dosovitskiy, German Ros, Felipe Codevilla, Antonio Lopez, and Vladlen Koltun. CARLA: An open urban driving simulator. In Proceedings of the 1st Annual Conference on Robot Learning, pp. 1-16, 2017. [cited by applicant]
Arne Kesting, Martin Treiber, and Dirk Helbing. Enhanced intelligent driver model to access the impact of driving strategies on traffic capacity. Philosophical Transactions of the Royal Society A: Mathematical, Physical… [cited by applicant]
Clipper2—Polygon Clipping and Offsetting Library—angusj.com. http://www.angusj.com/clipper2/Docs/Overview.htm. [Accessed Jun. 27, 2023]. [cited by applicant]
Hans Joachim Ferreau, Christian Kirches, Andreas Potschka, Hans Georg Bock, and Moritz Diehl. qpoases: A parametric activeset algorithm for quadratic programming. Mathematical Programming Computation, 6:327-363, 2014. [cited by applicant]