# US 2019/0170523 A1 · Systems and methods for digital route planning

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

- Number: US 2019/0170523 A1
- Document ID: US20190170523A1
- Status: Published application
- Kind: A1
- Application number: 16/266,009
- Filed: 2019-02-02
- Published: 2019-06-06
- Earliest claimed: 2017-05-16
- Assignees: Beijing Didi Infinity Technology and Development Co., Ltd.
- Applicants: Beijing Didi Infinity Technology and Development Co., Ltd.
- Inventors: Rui PAN; Zheng WANG
- Web page: https://patentgrep.com/patent/US20190170523A1

## CPC

- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- G01C 21/3453: {Special cost functions, i.e. other than distance or default speed limit of road segments}
- G06F 15/76: Architectures of general purpose stored program computers (with program plugboard G06F15/08; multicomputers G06F15/16)
- G06N 20/00: Machine learning
- G01C 21/3484: {Personalized, e.g. from learned user behaviour or user-defined profiles}
- 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)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A method for recommending a route includes obtaining a first start point and a first end point relating to a road network. The method also includes obtaining a route recommendation model. The method further includes determining a recommendation route from the first start point to the first end point based on the route recommendation model.

## Claims

### Claim at position 1

1-20. (canceled)

### Claim 21

A method implemented on at least one device each of which has at least one processor and a storage device, the method comprising:
obtaining, by the at least one processor, a first start point and a first end point relating to a road network, wherein the road network includes multiple links, and the first start point and the first end point are acquired from a location device;
obtaining, by the at least one processor, a route recommendation model, wherein the route recommendation model being related to weights of the multiple links of the road network; and
determining, by the at least one processor, a recommended route from the first start point to the first end point based on the route recommendation model; and
causing a user terminal to display the recommended route on an user interface.

### Claim 22 (depends on 21)

The method of claim 21, wherein the route recommendation model is generated based on a method for generating a recommended route, the method comprising:
obtaining a second start point and a second end point relating to the road network;
obtaining a plurality of historical routes from a storage device, each of the plurality of historical routes including the second start point and the second end point;
determining a plurality of links between the second start point and the second end point;
determining preliminary weights of the plurality of links;
determining one or more ordinary routes from the second start point to the second end point based, at least in part, on the primary weights of the plurality of links;
adjusting primary weights of links on the one or more ordinary routes;
adjusting primary weights of links on the historical routes; and
determining the route recommendation model based on the adjusted weights of the links on the one or more ordinary routes and the adjusted weights of the links on the historical routes.

### Claim 23 (depends on 22)

The method of claim 22, wherein determining the primary weights of the plurality of links includes:
obtaining road network data related to the road network, the road network data including one or more road features of the plurality of links between the second start point and the second end point; and
determining the primary weights of the plurality of links based on the one or more road features of the plurality of links.

### Claim 24 (depends on 22)

The method of claim 22, wherein the one or more ordinary routes are determined according to maximum margin planning (MMP) algorithm or maximum entropy inverse reinforcement learning (IRL) algorithm.

### Claim 25 (depends on 22)

The method of claim 22, wherein the one or more ordinary routes are determined according to the MMP algorithm, the one or more ordinary routes being the shortest route from the second start point to the second end point.

### Claim 26 (depends on 22)

The method of claim 22, wherein adjusting the primary weights of the links on the one or more ordinary routes and the primary weights on the historical routes includes:
increasing the primary weights of the links on the historical routes; and
decreasing the primary weights of the links on the one or more ordinary routes.

### Claim 27 (depends on 22)

The method of claim 22, further including:
obtaining a loss function associated with the route recommendation model;
determining whether a convergence of the loss function is reached;
in response to the determination that the convergence of the loss function is reached,
outputting the route recommendation model to the terminal device; and
in response to the determination that the convergence of the loss function is not reached,
initating a next iteration to update the route recommendation model,
wherein the next iteration includes:
determining another one or more ordinary routes from the second start point to the second end point based, at least in part, on the primary weights of the plurality of links;
adjusting primary weights of links on the another one or more ordinary routes;
adjusting the primary weights of links on the historical routes; and
determining the route recommendation model based on the adjusted primary weights of the links on the another one or more ordinary routes and the adjusted primary weights of the links on the historical routes.

### Claim 28 (depends on 22)

The method of claim 22, further including:
obtaining a preset number of iterations;
determining whether the preset number of iterations are performed;
in response to the determination that the preset number of iterations are performed,
outputting the route recommendation model to the terminal device; and
in response to the determination that the preset number of iterations are not performed,
initating a next iteration to update the route recommendation model, wherein the next iteration includes:
determining new one or more ordinary routes from the second start point to the second end point based, at least in part, on the primary weights of the plurality of links;
adjusting primary weights of links on the new one or more ordinary routes;
adjusting the primary weights of links on the historical routes; and
determining the route recommendation model based on the adjusted primary weights of the links on the new one or more ordinary routes and the adjusted primary weights of the links on the historical routes.

### Claim 29 (depends on 21)

The method of claim 21, wherein the weights of the multiple links of the road network relate to a parameter of the route recommendation model.

### Claim 30 (depends on 21)

The method of claim 21, wherein the weights of the multiple links of the road network may be determined based on at least one of a road width, a road length, a traffic flow, traffic lights, road safety, intersections, the direction of the road, or a road type.

### Claim 31

A system, comprising:
at least one storage medium including a set of instructions; and
at least one processor configured to communicate with the at least one storage medium, wherein when executing the set of instructions, the at least one processor is directed to:
obtain a first start point and a first end point relating to a road network, wherein the road network includes multiple links, and the first start point and the first end point are acquired from a location device;
obtain a route recommendation model, wherein the route recommendation model being related to weights of the multiple links of the road network; and
determine a recommended route from the first start point to the first end point based on the route recommendation model; and
cause a user terminal to display the recommended route on an user interface.

### Claim 32 (depends on 31)

The system of claim 31, wherein to generate the route recommendation model, the at least one processor is directed to:
obtain a second start point and a second end point relating to the road network;
obtain a plurality of historical routes from a storage device, each of the plurality of historical routes including the second start point and the second end point;
determine a plurality of links between the second start point and the second end point;
determine preliminary weights of the plurality of links;
determine one or more ordinary routes from the second start point to the second end point based, at least in part, on the primary weights of the plurality of links;
adjust primary weights of links on the one or more ordinary routes;
adjust primary weights of links on the historical routes; and
determine the route recommendation model based on the adjusted weights of the links on the one or more ordinary routes and the adjusted weights of the links on the historical routes.

### Claim 33 (depends on 32)

The system of claim 32, wherein to determine the primary weights of the plurality of links, the at least one processor is directed to:
obtain road network data related to the road network, the road network data including one or more road features of the plurality of links between the second start point and the second end point; and
determine the primary weights of the plurality of links based on the one or more road features of the plurality of links.

### Claim 34 (depends on 32)

The system of claim 32, wherein the one or more ordinary routes are determined according to the MMP algorithm, the one or more ordinary routes being the shortest route from the second start point to the second end point.

### Claim 35 (depends on 32)

The system of claim 32, wherein to adjust the primary weights of the links on the one or more ordinary routes and the primary weights on the historical routes, the at least one processor is directed to:
increase the primary weights of the links on the historical routes; and
decrease the primary weights of the links on the one or more ordinary routes.

### Claim 36 (depends on 32)

The system of claim 32, the at least one processor is further directed to:
obtain a loss function associated with the route recommendation model;
determine whether a convergence of the loss function is reached;
in response to the determination that the convergence of the loss function is reached,
output the route recommendation model to the terminal device; and
in response to the determination that the convergence of the loss function is not reached,
initate a next iteration to update the route recommendation model, wherein the next iteration includes:
determine another one or more ordinary routes from the second start point to the second end point based, at least in part, on the primary weights of the plurality of links;
adjust primary weights of links on the another one or more ordinary routes;
adjust the primary weights of links on the historical routes; and
determine the route recommendation model based on the adjusted primary weights of the links on the another one or more ordinary routes and the adjusted primary weights of the links on the historical routes.

### Claim 37 (depends on 32)

The system of claim 32, the at least one processor is further directed to:
obtain a preset number of iterations;
determine whether the preset number of iterations are performed;
in response to the determination that the preset number of iterations are performed,
output the route recommendation model to the terminal device; and
in response to the determination that the preset number of iterations are not performed,
initate a next iteration to update the route recommendation model, wherein the next iteration includes:
determine new one or more ordinary routes from the second start point to the second end point based, at least in part, on the primary weights of the plurality of links;
adjust primary weights of links on the new one or more ordinary routes;
adjust the primary weights of links on the historical routes; and
determine the route recommendation model based on the adjusted primary weights of the links on the new one or more ordinary routes and the adjusted primary weights of the links on the historical routes.

### Claim 38 (depends on 31)

The method of claim 31, wherein the weights of the multiple links of the road network relate to a parameter of the route recommendation model.

### Claim 39 (depends on 31)

The system of claim 31, wherein the weights of the multiple links of the road network may be determined based on at least one of a road width, a road length, a traffic flow, traffic lights, road safety, intersections, the direction of the road, or a road type.

### Claim 40

A non-transitory computer readable medium storing instructions, the instructions, when executed by a computing device, causing the computing device to:
obtain a first start point and a first end point relating to a road network, wherein the road network includes multiple links, and the first start point and the first end point are acquired from a location device;
obtain a route recommendation model, wherein the route recommendation model being related to weights of the multiple links of the road network; and
determine a recommended route from the first start point to the first end point based on the route recommendation model; and
cause a user terminal to display the recommended route on an user interface.