Node-centric navigation optimization

• US 9,953,523 B2
• Filed: 04/22/2016
• Issued: 04/24/2018
• Est. Priority Date: 04/22/2016
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Linder, Eric
• Primary Examiner(s): Mawari, Redhwan K
• Assistant Examiner(s): Torchinsky, Edward
• Application Number:
  US15/135,863
• Publication Number:
  US 20170309172A1
• Time in Patent Office: 732 Days
• Field of Search: None
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G08G 1/0112 from the vehicle, e.g. floating car data [FCD]
• CPC Class Codes: G08G 1/0116 from roadside infrastructure, e.g. beacons
• CPC Class Codes: G08G 1/0133 for classifying traffic situation
• CPC Class Codes: G08G 1/0141 for traffic information dissemination
• CPC Class Codes: G08G 1/0145 for active traffic flow control
• CPC Class Codes: G08G 1/096811 where the route is computed offboard
• CPC Class Codes: G08G 1/096833 where different aspects are considered when computing the route
• CPC Class Codes: H04W 24/08 Testing, supervising or monitoring using real traffic
• CPC Class Codes: H04W 8/183 Processing at user equipment or user record carrier

Abstract

Vehicle position data from vehicles on a roadway are received. Affected nodes of the roadway are identified based on the vehicle position data. The roadway graph, representative of the roadway, is updated based on the affected nodes of the roadway. Routes of each vehicle are optimized based on updates to the roadway graph. An indication of change in the route of each vehicle may be provided for display.

Claims

1. A method of node-centric navigation optimization, the method comprising:

identifying a roadway graph representative of at least a portion of a roadway, the roadway graph comprising a plurality of nodes of the roadway and a weight for each of the plurality of nodes indicative of a number of vehicles of a fleet of vehicles corresponding to a node in a path of a vehicle of the fleet of vehicles;

receiving vehicle position data from a sensor of the vehicle of the fleet of vehicles on the roadway;

identifying an affected node of the roadway based on the vehicle position data;

incrementing a weight of the affected node if the affected node is a node in a forward path of the vehicle;

decrementing the weight of the affected node if the affected node is a node in a wake of the vehicle; and

updating the roadway graph based on the weight of the affected node of the roadway, wherein a route of the vehicle is optimized based on the updated roadway graph.

2. The method of claim 1, wherein identifying the affected node of the roadway further comprises:

determining whether the affected node is the node in the forward path of the vehicle or the node in the wake of the vehicle.

3. The method of claim 2, wherein determining whether the affected node is the node in the forward path of the vehicle or the node in the wake of the vehicle is based on a current position of the vehicle and a direction of travel.

4. The method of claim 3, wherein determining whether the affected node is the node in the forward path of the vehicle or the node in the wake of the vehicle is based on one or more previous positions of the vehicle.

5. The method of claim 1, further comprising:

receiving infrastructure data associated with the roadway; and

updating the roadway graph using the received vehicle position data and the received infrastructure data.

6. The method of claim 5, wherein the received infrastructure data includes traffic light duration data.

7. The method of claim 1, wherein the received vehicle position data includes vehicle identification information.

8. The method of claim 1, wherein optimizing the route of the vehicle further comprises:

calculating a best route of the vehicle based on weights of nodes along possible routes to a destination of the vehicle.

9. The method of claim 1, further comprising:

providing an indication of change in the route.

10. The method of claim 9, wherein providing an indication of change in the route further comprises:

providing graphical navigation information for display by the vehicle.

11. The method of claim 9, wherein providing the indication of change in the route further comprises:

providing instructions controlling autonomous operation of the vehicle;

or

providing a selection of possible navigation options for selection by a passenger of the vehicle, wherein the vehicle is capable of semi-autonomous operation.

12. An apparatus for node-centric navigation optimization comprising:

at least one processor; and

at least one memory including computer program code for one or more programs;

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least;

identify a roadway graph representative of at least a portion of a roadway, the roadway graph comprising a plurality of nodes of the roadway and a weight for each of the plurality of nodes indicative of a number of vehicles of a fleet of vehicles corresponding to a node in a path of a vehicle of the fleet of vehicles;

receive vehicle position data associated with the vehicle of the fleet of vehicles on the roadway;

identify an affected node of the roadway based on the vehicle position data;

increment a weight of the affected node if the affected node is a node in a forward path of the vehicle;

decrement the weight of the affected node if the affected node is a node in a wake of the vehicle; and

update the roadway graph representative based on the weight of the affected node of the roadway, wherein a route of the vehicle is optimized based on the updated roadway graph.

13. The apparatus of claim 12, wherein identification of the affected node of the roadway further causes the apparatus to:

determine whether the affected node is the node in a forward path of the vehicle or the node in the wake of the path of the vehicle.

14. An apparatus comprising:

at least one processor; and

at least one memory including computer program code for one or more programs;

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to at least;

receive vehicle position data for a vehicle;

identify an affected node of the roadway based on the vehicle position data;

increment a weight of the affected node if the affected node is a node in a forward path of the vehicle;

decrement the weight of the affected node if the affected node is a node in a wake of the vehicle;

update a roadway graph representative of at least a portion of the roadway based on the weight of the affected node of the roadway; and

provide at least a portion of the updated roadway graph to the vehicle on the roadway for optimization of a route of the vehicle.

15. A method of node-centric navigation optimization, the method comprising:

receiving vehicle position data based on a plurality of sensors of a fleet of associated vehicles on roadways of a geographic area;

identifying a roadway graph representative of at least a portion of the roadways, the roadway graph comprising a plurality of nodes of the roadways and a weight for each of the plurality of nodes indicative of a number of vehicles of the fleet of associated vehicles at a node in a path of a vehicle of the fleet of associated vehicles;

identifying one or more affected nodes of roadways based on vehicle position data of the fleet of associated vehicles;

updating the roadway graph based on the one or more affected nodes of the roadways; and

optimizing routes of the fleet of associated vehicles based the updated roadway graph.

16. The method of claim 15, wherein identifying the one or more affected nodes of the roadways further comprises:

determining whether each respective affected node is in a forward path of any vehicle of the fleet of associated vehicles or in a wake of a path of any vehicle of the fleet of associated vehicles.

17. The method of claim 15, wherein updating the roadway graph using the received vehicle position data further comprises:

incrementing a weight of each respective affected node in a forward path of any vehicle of the fleet of associated vehicles; and

decrementing the weight of each respective affected node in the wake of the path of any vehicle of the fleet of associated vehicles.