IP Library › Granted Patent US 12,553,732
Granted Patent B2
US 12,553,732 · App. 18/339,703 · Granted Feb 17, 2026

Routing graph management in autonomous vehicle routing

Inventors: Michael Voznesensky (San Francisco, CA); Adam Panzica (Pittsburgh, PA); Brent Goldman (San Francisco, CA); Bryan John Nagy (Allison Park, PA); Mark Yen (San Francisco, CA); Adrian Rechy Romero (Pittsburgh, PA)
Assignee: Uber Technologies, Inc.
G01C21/3492G01C21/3415G05D1/0027G05D1/0088G06F16/9024
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,553,732
App. No.
18/339,703
Granted
Feb 17, 2026
Kind
B2
Abstract

Various examples are directed to routing autonomous vehicles. A processor unit accesses first routing graph modification data and second routing graph modification data. The first routing graph modification data based at least in part on first vehicle capability data describing a first type of autonomous vehicle and the second routing graph modification data based at least in part on second vehicle capability data describing a second type of autonomous vehicle. The processor unit accesses routing graph data describing a plurality of graph elements and generates a first route for a first autonomous vehicle of the first type based at least in part on the first routing graph modification data and the routing graph data. The processor unit also generates a second route for a second autonomous vehicle of the second type based at least in part on the second routing graph modification data and the routing graph data.

Claims (51)

1 . A method for routing autonomous vehicles, the method comprising:

accessing vehicle routing data comprising connections between vehicle navigation locations;

identifying a first subset of the vehicle routing data described by first routing element descriptor data;

modifying the first subset of the vehicle routing data based at least in part on first constraint data to generate a first modified subset of the vehicle routing data, the first constraint data including operational routing constraints that restrict vehicle navigation through specific locations or connections;

modifying the first modified subset of the vehicle routing data based at least in part on second constraint data to generate a second modified subset of the vehicle routing data, the second constraint data including a different type of operational routing constraint than the first constraint data, wherein modifying the first modified subset comprises applying the second constraint data to the first modified subset of the vehicle routing data that has already been modified by the first constraint data;

generating an autonomous vehicle route based on the second modified subset of the vehicle routing data; and

transmitting data corresponding to the autonomous vehicle route to a computing system associated with an autonomous vehicle to cause an autonomous vehicle to begin traveling the autonomous vehicle route.

2 . The method of claim 1 , wherein:

the first constraint data comprises a first roadway condition navigation constraint; and

the second constraint data comprises a second roadway condition navigation constraint.

3 . The method of claim 1 , wherein:

first constraint data comprises a first business policy navigation constraint; and

the second constraint data comprises a second business policy navigation constraint.

4 . The method of claim 1 , further including applying a cost constraint to a subset of the vehicle navigation locations to generate a cost constrained subset of the vehicle routing data, wherein generating the autonomous vehicle route is further based on the cost constrained subset.

5 . The method of claim 1 , further including disabling at least one connection between the vehicle navigation locations within the vehicle routing data to generate a reduced connection subset of the vehicle routing data, wherein generating the autonomous vehicle route is further based on the reduced connection subset.

6 . The method of claim 1 , further including applying a navigation mode constraint to a subset of the vehicle navigation locations to generate a navigation mode constrained subset of the vehicle routing data, wherein generating the autonomous vehicle route is further based on the navigation mode constrained subset.

7 . The method of claim 6 , wherein the navigation mode constraint comprises an indication that a subset of the vehicle routing data is to be navigated in a manual vehicle navigation mode or a semi-autonomous vehicle navigation mode.

8 . A system for routing autonomous vehicles, the system comprising:

at least one processor unit programmed to perform operations comprising:

accessing vehicle routing data comprising connections between vehicle navigation locations;

identifying a first subset of the vehicle routing data described by first routing element descriptor data;

modifying the first subset of the vehicle routing data based at least in part on first constraint data to generate a first modified subset of the vehicle routing data, the first constraint data including operational routing constraints that restrict vehicle navigation through specific locations or connections;

modifying the first modified subset of the vehicle routing data based at least in part on second constraint data to generate a second modified subset of the vehicle routing data, the second constraint data including a different type of operational routing constraint than the first constraint data, wherein modifying the first modified subset comprises applying the second constraint data to the first modified subset of the vehicle routing data that has already been modified by the first constraint data;

generating an autonomous vehicle route based on the second modified subset of the vehicle routing data; and

transmitting data corresponding to the autonomous vehicle route to a computing system associated with an autonomous vehicle to cause an autonomous vehicle to begin traveling autonomous vehicle route.

9 . The system of claim 8 , wherein:

the first constraint data comprises a first roadway condition navigation constraint; and

the second constraint data comprises a second roadway condition navigation constraint.

10 . The system of claim 8 , wherein:

the first constraint data comprises a first business policy navigation constraint; and

the second constraint data comprises a second business policy navigation constraint.

11 . The system of claim 8 , the operations further including applying a cost constraint to a subset of the vehicle navigation locations to generate a cost constrained subset of the vehicle routing data, wherein generating the autonomous vehicle route is further based on the cost constrained subset.

12 . The system of claim 8 , the operations further including disabling at least one connection between the vehicle navigation locations within the vehicle routing data to generate a reduced connection subset of the vehicle routing data, wherein generating the autonomous vehicle route is further based on the reduced connection subset.

13 . The system of claim 8 , the operations further including applying a navigation mode constraint to a subset of the vehicle navigation locations to generate a navigation mode constrained subset of the vehicle routing data, wherein generating the autonomous vehicle route is further based on the navigation mode constrained subset.

14 . The system of claim 13 , wherein the navigation mode constraint comprises an indication that a subset of the vehicle routing data is to be navigated in a manual vehicle navigation mode or a semi-autonomous vehicle navigation mode.

15 . A non-transitory machine-readable medium comprising instructions stored thereon that, when executed by at least one processor unit, cause the at least one processor unit to perform operations comprising:

accessing vehicle routing data comprising connections between vehicle navigation locations;

identifying a first subset of the vehicle routing data described by first routing element descriptor data;

modifying the first subset of the vehicle routing data based at least in part on first constraint data to generate a first modified subset of the vehicle routing data, the first constraint data including operational routing constraints that restrict vehicle navigation through specific locations or connections;

modifying the first modified subset of the vehicle routing data based at least in part on second constraint data to generate a second modified subset of the vehicle routing data, the second constraint data including a different type of operational routing constraint than the first constraint data, wherein modifying the first modified subset comprises applying the second constraint data to the first modified subset of the vehicle routing data that has already been modified by the first constraint data;

generating an autonomous vehicle route based on the second modified subset of the vehicle routing data; and

transmitting data corresponding to the autonomous vehicle route to a computing system associated with an autonomous vehicle to cause an autonomous vehicle to begin traveling autonomous vehicle route.

16 . The non-transitory machine-readable medium of claim 15 , wherein:

the first constraint data comprises a first roadway condition navigation constraint; and

the second constraint data comprises a second roadway condition navigation constraint.

17 . The non-transitory machine-readable medium of claim 15 , wherein:

the first constraint data comprises a first business policy navigation constraint; and

the second constraint data comprises a second business policy navigation constraint.

18 . The non-transitory machine-readable medium of claim 15 , the operations further including applying a cost constraint to a subset of the vehicle navigation locations to generate a cost constrained subset of the vehicle routing data, wherein generating the autonomous vehicle route is further based on the cost constrained subset.

19 . The non-transitory machine-readable medium of claim 15 , the operations further including disabling at least one connection between the vehicle navigation locations within the vehicle routing data to generate a reduced connection subset of the vehicle routing data, wherein generating the autonomous vehicle route is further based on the reduced connection subset.

20 . The non-transitory machine-readable medium of claim 15 , the operations further including applying a navigation mode constraint to a subset of the vehicle navigation locations to generate a navigation mode constrained subset of the vehicle routing data, wherein generating the autonomous vehicle route is further based on the navigation mode constrained subset.

Assignments (3)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 28, 2023
From: VOZNESENSKY, MICHAEL
To: UBER TECHNOLOGIES, INC.
Reel/Frame 064096/0600 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 28, 2023
From: GOLDMAN, BRENT
To: UBER TECHNOLOGIES, INC.
Reel/Frame 064098/0203 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 28, 2023
From: PANZICA, ADAM; NAGY, BRYAN JOHN; YEN, MARK; ROMERO, ADRIAN RECHY
To: UBER TECHNOLOGIES, INC.
Reel/Frame 064098/0526 →
Continuity (3)
Continuation 16696227 · Nov 26, 2019
Provisional Application 62771545 · Nov 26, 2018
Related Publication 20230358554A1 · Nov 9, 2023
References Cited (81)
US 7542882B2 · Agrawala et al. · 2009 [cited by applicant]
US 7603235B2 · Makela et al. · 2009 [cited by applicant]
US 7840287B2 · Wojsznis et al. · 2010 [cited by applicant]
US 8126604B2 · Mcgrogan et al. · 2012 [cited by applicant]
US 8295993B2 · Kumar · 2012 [cited by applicant]
US 8498871B2 · Miglietta et al. · 2013 [cited by applicant]
US 8688306B1 · Nemec · 2014 [cited by examiner]
US 8825265B1 · Ferguson · 2014 [cited by examiner]
US 8989917B2 · Kumar · 2015 [cited by applicant]
US 9494439B1 · Ross et al. · 2016 [cited by applicant]
US 9552564B1 · Martenis · 2017 [cited by applicant]
US 10901415B1 · Herbach et al. · 2021 [cited by applicant]
US 10956855B1 · Coughran et al. · 2021 [cited by applicant]
US 11713975B2 · Voznesensky · 2023 [cited by examiner]
US 11829135B2 · Voznesensky et al. · 2023 [cited by applicant]
US 20090187291A1 · Mckay et al. · 2009 [cited by applicant]
US 20160305787A1 · Sato · 2016 [cited by examiner]
US 20170132934A1 · Kentley et al. · 2017 [cited by applicant]
US 20170193627A1 · Urmson et al. · 2017 [cited by applicant]
US 20170300049A1 · Seally · 2017 [cited by applicant]
US 20180143643A1 · Fairfield · 2018 [cited by examiner]
US 20180204158A1 · Ratti et al. · 2018 [cited by applicant]
US 20180275661A1 · Glaser · 2018 [cited by applicant]
US 20180308064A1 · Glaser · 2018 [cited by applicant]
US 20180315146A1 · Matthiesen et al. · 2018 [cited by applicant]
US 20180321050A1 · Chase et al. · 2018 [cited by applicant]
US 20180322775A1 · Chase et al. · 2018 [cited by applicant]
US 20180329428A1 · Nagy et al. · 2018 [cited by applicant]
US 20180366004A1 · Laetz · 2018 [cited by applicant]
US 20190064846A1 · Sankavaram et al. · 2019 [cited by applicant]
US 20190079521A1 · Blum et al. · 2019 [cited by applicant]
US 20190186936A1 · Ebner et al. · 2019 [cited by applicant]
US 20190241192A1 · Matthews et al. · 2019 [cited by applicant]
US 20200057438A1 · Engle et al. · 2020 [cited by applicant]
US 20200126417A1 · Selvam et al. · 2020 [cited by applicant]
US 20200160705A1 · Chase · 2020 [cited by applicant]
US 20200166361A1 · Voznesensky et al. · 2020 [cited by applicant]
US 20200166936A1 · Voznesensky et al. · 2020 [cited by applicant]
US 20200201355A1 · Colijn et al. · 2020 [cited by applicant]
US 20200292333A1 · Colijn et al. · 2020 [cited by applicant]
US 20210043089A1 · Herbach et al. · 2021 [cited by applicant]
US 20210140777A1 · Balva · 2021 [cited by applicant]
US 20210163040A1 · Kojo · 2021 [cited by applicant]
US 20210200217A1 · Nix et al. · 2021 [cited by applicant]
US 20210217125A1 · Engle et al. · 2021 [cited by applicant]
US 20210248555A1 · Berdinis et al. · 2021 [cited by applicant]
WO WO2020112799A1 · 2020 [cited by applicant]
WO WO2020113038A1 · 2020 [cited by applicant]
U.S. Appl. No. 16/696,227, filed Nov. 26, 2019, Routing Graph Management in Autonomous Vehicle Routing. [cited by applicant]
U.S. Appl. No. 16/698,061, filed Nov. 27, 2019, Tuning Autonomous Vehicle Dispatch Using Autonomous Vehicle Performance. [cited by applicant]
“U.S. Appl. No. 16/696,227, Examiner Interview Summary mailed Jul. 15, 2022”, 2 pgs. [cited by applicant]
“U.S. Appl. No. 16/696,227, Final Office Action mailed Apr. 12, 2022”, 14 pgs. [cited by applicant]
“U.S. Appl. No. 16/696,227, Non Final Office Action mailed Aug. 31, 2022”, 15 pgs. [cited by applicant]
“U.S. Appl. No. 16/696,227, Non Final Office Action mailed Oct. 1, 2021”, 13 pgs. [cited by applicant]
“U.S. Appl. No. 16/696,227, Notice of Allowance mailed Mar. 15, 2023”, 11 pgs. [cited by applicant]
“U.S. Appl. No. 16/696,227, Notice of Allowance mailed Dec. 19, 2022”, 11 pgs. [cited by applicant]
“U.S. Appl. No. 16/696,227, Response filed Jan. 3, 2022 to Non Final Office Action mailed Oct. 1, 2021”, 13 pgs. [cited by applicant]
“U.S. Appl. No. 16/696,227, Response filed Jul. 12, 2022 to Final Office Action mailed Apr. 12, 2022”, 12 pgs. [cited by applicant]
“U.S. Appl. No. 16/696,227, Response filed Nov. 29, 2022 to Non Final Office Action mailed Aug. 31, 2022”, 19 pgs. [cited by applicant]
“U.S. Appl. No. 16/698,061, Examiner Interview Summary mailed Jan. 30, 2023”, 3 pgs. [cited by applicant]
“U.S. Appl. No. 16/698,061, Examiner Interview Summary mailed Jun. 13, 2023”, 3 pgs. [cited by applicant]
“U.S. Appl. No. 16/698,061, Examiner Interview Summary mailed Jul. 11, 2022”, 2 pgs. [cited by applicant]
“U.S. Appl. No. 16/698,061, Final Office Action mailed Mar. 30, 2022”, 29 pgs. [cited by applicant]
“U.S. Appl. No. 16/698,061, Final Office Action mailed Nov. 28, 2022”, 28 pgs. [cited by applicant]
“U.S. Appl. No. 16/698,061, Non Final Office Action mailed Mar. 17, 2023”, 30 pgs. [cited by applicant]
“U.S. Appl. No. 16/698,061, Non Final Office Action mailed Aug. 5, 2022”, 28 pgs. [cited by applicant]
“U.S. Appl. No. 16/698,061, Non Final Office Action mailed Dec. 27, 2021”, 25 pgs. [cited by applicant]
“U.S. Appl. No. 16/698,061, Response filed Feb. 28, 2023 to Final Office Action mailed Nov. 28, 2022”, 13 pgs. [cited by applicant]
“U.S. Appl. No. 16/698,061, Response filed Mar. 15, 2022 to Non Final Office Action mailed Dec. 27, 2021”, 11 pgs. [cited by applicant]
“U.S. Appl. No. 16/698,061, Response filed Jun. 14, 2023 to Non Final Office Action mailed Mar. 17, 2023”, 12 pgs. [cited by applicant]
“U.S. Appl. No. 16/698,061, Response filed Jun. 30, 2022 to Final Office Action mailed Mar. 30, 2022”, 11 pgs. [cited by applicant]
“U.S. Appl. No. 16/698,061, Response filed Nov. 7, 2022 to Non Final Office Action mailed Aug. 5, 2022”, 11 pgs. [cited by applicant]
“European Application Serial No. 19831952.7, Response to Communication persuant to Rules 161 and 162 filed Jan. 17, 2022”, 21 pgs. [cited by applicant]
“International Application Serial No. PCT/US2019/063286, International Preliminary Report on Patentability mailed Jun. 10, 2021”, 9 pgs. [cited by applicant]
“International Application Serial No. PCT/US2019/063286, International Search Report mailed Mar. 5, 2020”, 4 pgs. [cited by applicant]
“International Application Serial No. PCT/US2019/063286, Written Opinion mailed Mar. 5, 2020”, 7 pgs. [cited by applicant]
“International Application Serial No. PCT/US2019/063654, International Preliminary Report on Patentability mailed Jun. 10, 2021”, 8 pgs. [cited by applicant]
“International Application Serial No. PCT/US2019/063654, International Search Report mailed Feb. 4, 2020”, 4 pgs. [cited by applicant]
“International Application Serial No. PCT/US2019/063654, Written Opinion mailed Feb. 4, 2020”, 8 pgs. [cited by applicant]
U.S. Appl. No. 16/698,061, Notice of Allowance mailed Jul. 20, 2023, 14 pgs. [cited by applicant]
Canadian Application Serial No. 3,120,965, Office Action mailed Jan. 8, 2024, 1 pg. [cited by applicant]