# US 2021/0239476 A1 · Methods and Devices Arranged for Routing Autonomous Driving

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0239476 A1
- Document ID: US20210239476A1
- Status: Published application
- Kind: A1
- Application number: 16/972,179
- Filed: 2019-08-09
- Published: 2021-08-05
- Earliest claimed: 2018-08-14
- Assignees: Bayerische Motoren Werke Aktiengesellschaft
- Applicants: Bayerische Motoren Werke Aktiengesellschaft
- Inventors: Stefaan DUYM; Felix REMPE
- Web page: https://patentgrep.com/patent/US20210239476A1

## CPC

- G01C 21/3453: {Special cost functions, i.e. other than distance or default speed limit of road segments}
- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- G05D 1/0061: {for transition from automatic pilot to manual pilot and vice versa}
- G05D 1/0217: {in accordance with energy consumption, time reduction or distance reduction criteria}
- G05D 1/644: Optimisation of travel parameters, e.g. of energy consumption, journey time or distance
- G05D 1/81: Handing over between on-board automatic and on-board manual control
- G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem
- G06Q 10/06: Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
- G08G 1/096827: {where the route is computed onboard}
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93})

## Abstract

The present invention is directed to a method and to a device for determining routes for autonomous driving. The following steps are executed; computing K alternative routes from a route source to a route destination; evaluating each one of the K alternative routes, wherein the evaluating comprises determining a Pareto front of the K alternative routes, wherein the Pareto front of the K alternative routes comprises a set of Pareto-optimized routes that are Pareto-optimized with regard to route constraints comprising travel time T, manual driving time TM, and transition count M that indicates a count of transitions from the autonomous driving to a manual driving in a route; if the set of Pareto-optimized routes comprises more than P routes, reducing number of Pareto-optimized routes in the set of Pareto-optimized routes to P; and outputing the Paretooplimized routes of the set of Pareto-optimized routes as the determined routes for autonomous driving.

## Claims

### Claim 1

A method for determining routes for autonomous driving, the method comprising:
computing K alternative routes from a route source to a route destination;
evaluating each one of the K alternative routes, wherein the evaluating comprises determining a Pareto front of the K alternative routes, wherein the Pareto front of the K alternative routes comprises a set of Pareto-optimized routes that are Pareto-optimized with regard to route constraints comprising travel time T, manual driving time TM, and transition count M that indicates a count of transitions from the autonomous driving to a manual driving in a route;
when the set of Pareto-optimized routes comprises more than P routes, reducing number of Pareto-optimized routes in the set of Pareto-optimized routes to P; and
outputting the Pareto-optimized routes of the set of Pareto-optimized routes as the determined routes for autonomous driving.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the evaluating each one of the K alternative routes comprises executing the following steps with regard to each one of the K alternative routes:
evaluating each realization of the corresponding alternative route from a plurality of realizations of the corresponding alternative route, wherein the realizations of the corresponding alternative route in the plurality of realizations of the corresponding alternative route differ with regard to the route constraints, wherein the evaluating each realization of the corresponding alternative route from a plurality of realizations of the corresponding alternative route comprises determining a Pareto front of the corresponding alternative route comprising a set of Pareto-optimized route realizations of the corresponding alternative route that are Pareto-optimized with regard to the route constraints; and
inserting into the Pareto front of the K alternative routes Pareto-optimized route realizations of the set of Pareto-optimized route realizations of the corresponding alternative route.

### Claim 3 (depends on 1)

The method according to claim 1, wherein
the route constraints further comprise a stressing cost function indicating a stress caused by the transitions from the autonomous driving to the manual driving in the route.

### Claim 4 (depends on 3)

The method according to claim 3, wherein
the route constraints further comprise autonomous travel time.

### Claim 5 (depends on 1)

The method according to claim 1, wherein
the K alternative routes are computed with regard to a digital road map comprising roads divided into corresponding road sections, and wherein each one of the K alternative routes is a path of corresponding road sections.

### Claim 6 (depends on 1)

The method according to claim 1, wherein
the K alternative routes are computed by taking into consideration road clearance values, each road clearance value being associated with a respective road section and indicating whether or not it is possible to drive autonomously on the respective road section.

### Claim 7 (depends on 5)

The method according to claim 5, wherein:
a manual travel time TM of the route is calculated as
T
M
=
∑
i
=
1
N
⁢
(
1
-
C
i
)
·
T
i
wherein Ci is a road clearance value associated with i-th road section of the route, wherein Ci=1 if it is possible to drive autonomously on the i-th road section, wherein Ci=0 if it is not possible to drive autonomously on the i-th road section, and wherein N is a number of road sections in the route;
a transition count M of the route is calculated as
M
=
1
-
C
1
+
∑
i
=
2
N
⁢
C
i
-
1
·
(
1
-
C
i
)
;
a travel time T of a route comprising N road sections is calculated as
T
=
∑
i
=
1
N
⁢
T
i
wherein Ti is a travel time for i-th road section of the route; and/or
a stressing cost function S of the route is calculated as
S
=
(
1
-
C
1
)
·
f
1
+
∑
1
=
2
N
⁢
(
C
i
-
1
·
(
1
-
C
i
)
)
·
f
i
wherein ƒi is a weighting function characterizing a stress caused by a transition at the i-th road section or the route.

### Claim 8 (depends on 1)

The method according to claim 1, wherein the reducing number of Pareto-optimized routes in the set of Pareto-optimized routes to P comprises selecting from the set of Pareto-optimized routes P Pareto-optimized routes that meet one or more of the following criteria:
minimal travel time T in comparison to the Pareto-optimized routes in the set of Pareto-optimized routes;
minimal manual travel time TM in comparison to the Pareto-optimized routes in the set of Pareto-optimized routes;
minimal amount of transitions M in comparison to the Pareto-optimized routes in the set of Pareto-optimized routes;
minimal stressing cost function S in comparison to the Pareto-optimized routes in the set of Pareto-optimized routes.

### Claim 9 (depends on 1)

The method according to claim 1, wherein the reducing number of Pareto-optimized routes in the set of Pareto-optimized routes to P comprises selecting from the set of Pareto-optimized routes P Pareto-optimized routes that maximize a quality measure Q:
Q
=
1
δ
·
T
M
+
γ
·
T
+
β
·
M
,
wherein δ, γ, β are weights.

### Claim 10

A device configured to determine routes for autonomous driving, comprising:
a memory with computer executable instructions stored therein; and
a processor, coupled to the memory and configured to:
compute K alternative routes from a route source to a route destination;
evaluate each one of the K alternative routes, wherein the evaluating comprises determining a Pareto front of the K alternative routes, wherein the Pareto front of the K alternative routes comprises a set of Pareto-optimized routes that are Pareto-optimized with regard to route constraints comprising travel time T, manual driving time TM and transition count M that indicates a count of transitions from the autonomous driving to a manual driving in a route;
when the set of Pareto-optimized routes comprises more than P routes, reduce number of Pareto-optimized routes in the set of Pareto-optimized routes to P; and
output the Pareto-optimized routes of the set of Pareto-optimized routes as the determined routes for autonomous driving.