HK1246391B - Node-centric navigation optimization - Google Patents

Description

Node-centric navigation optimization

Technical Field

The following disclosure relates to navigation optimization, and more specifically to optimizing vehicle navigation routes based on assessments of traffic conditions at road junctions.

Background Technology

Traffic congestion can be identified by monitoring a combination of traffic data sources, such as traffic channels, radio, and personal navigation devices. Therefore, traffic information is reported to multiple data storage devices based on the type of data being monitored. The traffic information provided to routing algorithms from these congestion identification sources comes from auxiliary devices, where traffic determination frequently requires analysis of source data to determine the presence of congestion. The aggregation of traffic data from multiple sources limits the speed at which congestion information is updated based on changing traffic conditions.

Traffic reports can provide a high-level view of traffic conditions. For example, traffic at the Traffic Message Channel (TMC) code level provides a generalized view of traffic conditions based on accumulated traffic information across multiple road segments. This form of congestion monitoring relies on the range and averages of past vehicles and may not report the number of vehicles approaching a particular stop light in the same direction within the same city and their waiting times. Furthermore, vehicle platoons or groups are not grouped. While some routing algorithms may take traffic congestion information into account, this information is provided by traffic broadcasts that do not consider information from other drivers obtained from centralized traffic maps.

Currently available probe data from Global Positioning System (GPS) devices provides data point information for urban areas suffering from multipath and other problems. These problems lead to errors associated with traffic congestion analysis using GPS points. Autonomous vehicles use a variety of data to determine their approximate location, including GPS sensors, LiDAR (Light Detection and Ranging), visual street signs, and other information. Therefore, autonomous vehicles are better able to perceive their location than location determination along GPS points, thus enabling more accurate and precise traffic and congestion analysis. Consequently, using only GPS location information combined with traffic congestion reporting has limitations in terms of accuracy and precision when reporting vehicle location and traffic congestion.

Summary of the Invention

In one embodiment, a node-centric navigation optimization method is provided. Vehicle location data is received from vehicles on a road, and valid nodes on the road are identified based on the vehicle location data. A road map representing at least a portion of the road is updated based on the affected nodes. The vehicle route is optimized based on the updated road map. The method further includes providing indications of route changes for display to passengers in vehicles on the road.

In another embodiment, a node-centric navigation device is provided, 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 are configured, together with the at least one processor, to cause the device to receive vehicle location data associated with vehicles on a road and to identify affected nodes of the road based on the vehicle location data. The computer program code and the processor may further cause the device to update a road map representing at least a portion of the road based on the affected nodes of the road and to optimize the vehicle's route based on the updated road map. The computer program code and the processor may further cause the device to provide passengers of vehicles on the road with indications of route changes.

In another embodiment, a node-centric navigation device is provided, 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 are configured, together with the at least one processor, to cause the device to receive vehicle position data and identify affected nodes of a road based on the vehicle position data. The computer program code and the processor may further cause the device to update a road map representing at least a portion of the road based on the affected nodes of the road, and to provide the updated road map to vehicles on the road to optimize vehicle routes.

In another embodiment, a node-centric navigation optimization method includes: receiving vehicle location data for a group of associated vehicles on a road within a geographic region. The method identifies one or more affected nodes on the road based on the vehicle location data of the group of vehicles. The method further includes: updating a road map representing the road within the geographic region based on the affected nodes on the road, and optimizing the routes of the group of associated vehicles based on the updated road map. The method also provides indications of route changes to the vehicles in the group.

Attached Figure Description

Exemplary embodiments of this disclosure are described herein with reference to the following accompanying drawings.

Figure 1 is a flowchart of the node-centric navigation optimization theme technology.

Figure 2 is a flowchart of the node-centric navigation optimization theme technology.

Figure 3A illustrates a block diagram of a road map database and a geographic database based on a node-centric navigation optimization theme technology.

Figure 3B illustrates a block diagram of the components of the data records contained in the geodatabase of Figure 3A.

Figures 4A to 4H illustrate vehicles moving relative to road nodes according to node-centric navigation optimization techniques.

Figure 5 illustrates an example system of node-centric navigation optimization theme technology.

Figure 6 illustrates an example mobile device using a node-centric navigation optimization theme technique.

Figure 7 illustrates an example server for a node-centric navigation optimization topic technique.

Detailed Implementation

Traffic congestion monitoring and reporting suffers from drawbacks such as slow reporting, overly generalized congestion determination, and inability to be specific to vehicle fleets. The goal of the following embodiments is to provide a real-time, highly detailed assessment of road conditions specific to each intersection. Intersections in traffic clustering can be represented as nodes. To identify traffic at each node, a road map describing the current state of each node relative to its neighboring nodes can be built. The road map can be shared among vehicle fleets, all vehicles within a geographic area, or one or more selected vehicles within a geographic area. As vehicles travel through a geographic area, each vehicle in the group provides vehicle location information. This vehicle location information describes the current state of each node. Road map updates can be determined substantially in real-time as vehicles move from node to node and report their positions.

Real-time or substantially real-time continuous updates or traffic reports are intended to provide route optimization to vehicles currently traveling along the route. Real-time and substantially real-time mean instantaneous or have imperceptible delays. In the disclosed embodiments, transmission and processing delays caused by using multiple data sources are reduced by using a single source to determine congestion information and/or using a centralized cloud-based data storage device to store congestion information. The disclosed goal of the node-centric navigation optimization theme is to provide a granular view of road conditions at the intersection level. This granular view provides a more comprehensive view of the area, rather than how traffic is reported. The following embodiments highlight the importance of the integrity and interdependence of their components to achieve the goal of better fleet performance. The following embodiments provide granular quantification of traffic flow and congestion, thereby addressing the limitations of cloud-based traffic analytics and the broadcasting of traffic congestion data.

Traffic congestion is categorized into three to four levels, and color-coded on the road surface to indicate congestion. For example, black, red, yellow, and green levels can provide an indicator of the extent to which traffic congestion levels decrease. However, these levels do not convey sufficient information to optimize vehicle routes within individual segments of a road with the same level of congestion. Therefore, navigation cannot be optimized at the intersection level. The following embodiments determine congestion at each intersection based on the number of vehicles at and/or near each intersection, and provide route changes and/or navigation direction changes based on changes in traffic between road segments.

Congestion determination based on the average speed of vehicles traveling along a north-to-south road does not provide sufficient information to allow for optimized route selection for east-to-west roads crossing north-to-south roads. In other words, the navigation system cannot select the optimal intersection for crossing north-to-south roads. Navigation systems that determine congestion using average speed rank each link in the chain equally. Consequently, congestion at each node cannot be determined. In highly congested areas, as provided herein, determining the road conditions at each node allows navigation systems and routing algorithms to optimize navigation with a higher degree of specificity (e.g., in highly congested areas) to achieve the best or fastest possible travel time within that area. The disclosed embodiments advantageously provide continuously updated road information, resulting in reduced travel time, minimized travel distance, or other desired optimizations.

The term "vehicle" as used herein encompasses its simple and general meanings, including but not limited to automobiles, buses, trains, airplanes, ships, bicycles, trams, or pedestrian movement. The term "vehicle" includes any form of motorized or non-motorized transport and/or motion. Navigation optimization systems can be used with autonomous or semi-autonomous vehicles. Drivers or passengers in the vehicle may use the navigation optimization system. "Passenger" can refer to any one or more passengers in the vehicle, including the driver. The use of navigation optimization systems can be specifically applied to applications associated with semi-autonomous or autonomous vehicles.

As used in this document, the term "autonomous" can refer to an automated or driverless mode of driving that does not require passengers to operate the vehicle. Autonomous vehicles can be referred to as robotic vehicles or autonomous vehicles. Autonomous vehicles may include passengers but do not require a driver. Autonomous vehicles can park themselves or move goods between locations without a human operator. Autonomous vehicles may include multiple modes and transitions between modes.

As described herein, semi-autonomous or highly assisted driving (HAD) vehicles can refer to vehicles that do not completely replace a human operator. Rather, in highly assisted driving modes, the vehicle can perform some driving functions, while the human operator can perform other driving functions. Vehicles can also be driven in manual mode, where the human operator has some degree of control over the vehicle's movement. Vehicles can also include a fully driverless mode. Other levels of automation are possible.

The node-centric navigation optimization theme technology is applicable to autonomous and semi-autonomous vehicles, and provides navigation assistance for user-operated vehicles. Route optimization using theme technology can further enhance route selection by prioritizing routes based on road condition comparisons at the intersection level. Additionally, node-centric navigation optimization theme technology can assist autonomous vehicle navigation.

Figure 1 is a flowchart of a node-centric navigation optimization technique. Actions are described with reference to the systems and components depicted in Figures 5 through 7. Additional, different, or fewer actions may be provided. Actions may be performed in a different order than presented herein.

In action A100, vehicle location data is received. Vehicle location data can be received from vehicle 129 traveling on the road via server 125. Vehicle location data may include vehicle identification information. Vehicle location data may also include geographic location information, speed, direction of travel, or any other indication of the vehicle's position. Further vehicle identification information may be provided from vehicles that identify specific features such as manufacture, model, type, size, associated fleet, and other information.

In action A110, affected nodes are identified based on vehicle position. Affected nodes can be any one or more nodes affected by changes in vehicle position data. Identifying affected nodes on the road may include, as illustrated in step A112, determining whether the affected node is in the vehicle's forward path or in its path trail. Nodes in the vehicle's path trail are nodes the vehicle has passed or nodes the vehicle has left. Affected nodes in the vehicle's path trail can be the last node the vehicle has passed and/or the last node the vehicle has left. Nodes in the vehicle's forward path can be the next node in the vehicle's direction of travel. Determining whether the vehicle is approaching or leaving a node can be based on the vehicle's current position and direction of travel. Alternatively, determining whether an affected node is in the vehicle's forward path or in its path trail can be based on the vehicle's current position and one or more previous positions. Vehicles stopped at intersections maintain the vehicle position and/or last vehicle position associated with the intersection where the vehicle stopped. Vehicles under traffic signals, vehicles moving slowly or at low speeds due to congestion, or vehicles under stop signs are some examples of instances where vehicles stop at or near intersections.

In some embodiments, infrastructure information can be further used to determine the traffic status of roads and their nodes. Server 125 may receive infrastructure information via network device 135, traffic device 137, or other sources. Infrastructure information may include data associated with timed traffic light information, current traffic light timing information associated with sensor-based traffic light control, or other information associated with traffic clustering, which is associated with traffic device 137. In action A120, infrastructure data is received. Infrastructure data may include traffic light duration data. Infrastructure data may be obtained from geodatabase 116. For example, traffic signals with predetermined patterns may be stored in geodatabase 116. Infrastructure data associated with changes in predetermined patterns (e.g., emergency service vehicles preempting timed traffic signals) may be provided from traffic device 137, vehicle 129, network device 135, and stored as infrastructure data record 301.

In action A130, the road map is updated. The road map may represent at least a portion of a road and is updated based on the affected nodes of the road. Each node in the road map may include a weight indicating the traffic state of the node. For example, the weight may indicate the number of vehicles stopped at the node, and/or the number of vehicles at nodes in the vehicle's path. The weights of the nodes in the road map provide an indication of the traffic state at the intersection. If the affected node is a node in the vehicle's path, the weight of the affected node may be increased, as in action A132. Further, if the affected node is in the vehicle's path trail, the weight of the affected node may be decreased, as in action A134. A single movement of a vehicle may affect two nodes simultaneously; a vehicle may be leaving one node while approaching another.

In embodiments where infrastructure information is used to determine the traffic status of roads and their nodes, updating road map data may include using the received infrastructure information in addition to the received vehicle location data. The infrastructure information may be used to further increment, decrement, or otherwise scale the weights at a given node based on the current infrastructure status or known behavior of infrastructure elements.

In action A140, the vehicle route is optimized. The route can be optimized based on the updated road map. As illustrated in action A142, optimizing the vehicle's route based on the routing algorithm can also include calculating the vehicle's optimal (e.g., fastest or shortest) route based on the weights of nodes along possible routes to the vehicle's destination. Any known routing algorithm can be used. The routing algorithm can prioritize route decisions based on user-input preferences, fleet preferences, or other preferences.

In action A150, a route change instruction is provided. This instruction can be provided to passengers in a vehicle on the road. Changing the vehicle's route direction may include providing graphical navigation information for display in the vehicle, as in action A152. Alternatively or additionally, providing the vehicle with the changed route direction may include providing instructions for controlling the autonomous operation of the vehicle, as in action A154. Additionally or alternatively, providing the vehicle with the changed route direction may also include, in action A156, providing a selection of possible navigation options for vehicle passengers to choose from. For example, the selection of navigation options may be used in embodiments that include semi-autonomous operation of the vehicle.

In one embodiment, vehicle location data can be received from vehicle 129 via network 127. Vehicle location information can be provided directly from vehicle 129 to server 125, or it can be provided to server 125 via intermediate networking device 135. Vehicle location information can be provided through a combination of direct transmission from vehicle 129 and vehicle information data collected at intermediate networking device 135 and transmitted to server 125. These networking devices can further act as intermediaries to provide optimized routing information from server 125 to vehicles.

In other embodiments, the server may transmit road map information and send the updated map information to the vehicles or intermediate networking devices 135. The vehicles or networking devices can then use the updated road map information to optimize the route information for each vehicle.

Node-centric optimization can be performed using vehicle location information for some or all vehicles within a geographic area. Some vehicles may not provide location information and therefore may not be reflected in the road map. Optimization can be provided for specific groups of vehicles. For example, a fleet of vehicles may be centrally owned or operated. The interests of these groups of vehicles can be met by creating a road map with only vehicle inputs from vehicles identified as belonging to that group. In some embodiments, vehicle information can be used to update a road map limited to a single group of vehicles. For example, a fleet of vehicles such as taxis may have unique optimization needs, such as maximizing speed, maximizing flag-pull, minimizing idle time, staying within a specific geographic area, or other desired outcomes. Larger commercial vehicle fleets may form separate groups with optimization needs such as maximizing straightaways, minimizing significant changes in acceleration or speed, or including single-turn lanes or multi-lane road preferences. Larger commercial vehicle fleets may further minimize paths across intersections with short traffic light durations.

Figure 2 is a flowchart of a node-centric navigation optimization technique for selecting a vehicle convoy. Actions are described with reference to the systems and components depicted in Figures 5 through 7. Additional, different, or fewer actions may be provided. Actions may be performed in a different order than presented herein. For example, some embodiments may omit action A220. In other embodiments, action A240 may be performed using actions other than A242. In action A200, vehicle position data of the convoy vehicles is received. Vehicle position data for each vehicle in the convoy is received for roads in the geographic area.

In action A210, affected nodes are identified based on the vehicle positions of the convoy. Affected nodes on the road are identified based on the vehicle position data of each vehicle in the group of associated vehicles. Identification of affected nodes may include action A212. As in action A212, it is determined whether each corresponding affected node is on the forward path of any of the multiple associated vehicles or in the path trail of any of the multiple associated vehicles. Identifying nodes on roads within a geographic area may include determining whether a node is on the forward path of the convoy vehicles or in the path trail, as in action A212. This determination of whether a vehicle is approaching or leaving a node can be based on the vehicle's current position and direction of travel.

In action A220, infrastructure data is received. As illustrated in action A242, optimizing a vehicle's route based on a routing algorithm may further include: calculating the optimal route for the vehicle based on the weights of nodes along possible routes to the vehicle's destination. The optimal route may be the shortest distance, the shortest travel time, a route that maximizes desired road characteristics, or a combination thereof.

In action A230, the road map is updated. The road map representing the geographic region is updated based on one or more affected nodes of the road. As illustrated in action A232, the weight of the affected node can be increased if it is a node in the vehicle's path. Further, as illustrated in action A234, the weight of the affected node can be decreased if it is in the vehicle's path trail.

In action A240, routes are optimized for vehicles in the convoy. For each vehicle in the convoy, these routes are optimized. Optimizing vehicle routes based on routing algorithms can also include, as illustrated in action A142, calculating the fastest route for each vehicle based on the weights of nodes along possible routes to its destination. Any known routing algorithm can be used. Routing algorithms can prioritize route decisions based on user-input preferences, convoy preferences, or other preferences.

In action A250, a route change instruction is provided to the vehicle. This route change instruction may also be provided to passengers of the vehicle on the road. As illustrated in action A252, changing the direction of arrival at the vehicle may include providing graphical navigation information for display by the vehicle. Alternatively or additionally, providing the changed route direction to the vehicle may include providing instructions for autonomous operation of the vehicle, as in action A254. Additionally or alternatively, providing the changed route direction to the vehicle may also include providing a selection of possible navigation options for vehicle passengers to choose from. For example, the selection of navigation options may be used in embodiments including semi-autonomous operation of the vehicle, as in action A256.

Figure 3A illustrates a block diagram of a road map database 114 and a geographic database 116 according to a node-centric navigation optimization theme technique. In one embodiment, the geographic database 116 contains data 302 representing some of the physical geographic features in the geographic region of Figure 4A. The data in the road map database 114 may include vehicle location information 301 received from vehicles traveling through geographic region 400. Infrastructure information may be further included in the data record 301, if available. This information can be updated in real time and as soon as it is received. The current vehicle location and infrastructure data record 301 can be received directly from vehicle 129, network device 135, and traffic device 137 via network 127. That is, while additional traffic congestion information may be obtained via geographic database 116 or other sources, the road map database does not rely on traffic flow data and/or traffic congestion data from conventional sources such as traffic channels, radio, or other aggregated traffic data. The geographic data 302 may include node data records 306 and other information defining geographic region 400. Node weight data 303 is based on vehicle location and infrastructure data record 301, which includes the current weight values of nodes in the geographic region.

The data 302 included in the geodatabase 116 may include data representing the road network of geographic region 400 of Figure 4A. The geodatabase 116 may represent geographic region 400 and may contain at least one road segment database record 304 (also referred to as an "entity" or "entry") for each road segment in geographic region 400. The geodatabase 116 representing geographic region 400 may also include node database records 306 (or "entities" or "entries") for each node N1 to N9 in geographic region 400. The terms "node" and "segment" are only one term used to describe a physical geographic feature; other terms used to describe features are intended to be encompassed within the scope of these concepts.

The geodatabase 116 may also include other types of data 312. These other types of data 312 may represent other types of geographic features or any other type of data. Other types of data may include point-of-interest (POI) data. For example, POI data may include POI records that include types (e.g., POI types such as restaurants, hotels, city halls, police stations, historical landmarks, ATMs, golf courses, etc.), POI locations, telephone numbers, operating hours, etc. The geodatabase 116 also includes an index 314. The index 314 may include various types of indexes that correlate different types of data with each other or with other aspects of the data contained in the geodatabase 116. For example, the index 314 may correlate nodes in node data record 306 with endpoints of road segments in road segment data record 304. As another example, the index 314 may correlate POI data in other data record 312 with road segments in segment data record 304.

Figure 3B illustrates a block diagram of the components of a data record contained in the geodatabase of Figure 3. According to one embodiment, some or all of the components of the road segment data record 304 may be included in the geodatabase 116. The road segment data record 304 may include a segment ID 304(1) that identifies the data record in the geodatabase 116. Each road segment data record 304 may be associated with information such as “attributes”, “fields”, etc., describing the characteristics of the road segment represented. The road segment data record 304 may include data 304(2) indicating, if any, restrictions on the permitted directions of vehicle travel on the represented road segment. The road segment data record 304 may include data 304(3) indicating speed limits or speed categories (i.e., maximum permitted vehicle speeds) on the represented road segment. Road segment data record 304 may also include data 304(4) indicating whether the road segment represented is part of a controlled interchange (such as a highway), ramps of a controlled interchange, bridges, tunnels, toll roads, ferries, etc.

Traffic flow data can be stored as separate records 308, 310, or stored in road segment data record 304. Geodatabase 116 may include road segment data record 304 (or data entity) describing, for example, traffic flow 304(5) or traffic flow estimate 304(6). The estimated flow can be stored as a field or record using a range of values such as 1 to 100 (1 being low flow, 100 being high flow) or based on a measurement scale such as vehicles per meter (or square meter) or a range thereof. The estimated traffic flow can be stored using categories such as low, medium, and high. Additional schemes can be used to describe the estimated traffic flow. Geodatabase 116 can store other data 312 related to the flow, such as raw, unadjusted data. Attribute data related to links/segments 304, nodes 306, link strings, regions, or areas can be stored. Geodatabase 116 can store information or settings for display preferences. Geodatabase 116 can be coupled to a display. The display can be configured to show road networks and data entities using different colors or schemes. The geodatabase 116 can store information related to the locations where hazardous conditions may exist, for example, by analyzing data records and current/historical traffic conditions. Road segments with high traffic volume can be used to identify or supplement other data entities, such as potential hazards. High traffic volume, along with geographic data records such as high speed, can be combined to indicate unsafe locations on the road.

The road segment data record 304 also includes data 304(7) providing the geographic coordinates (e.g., latitude and longitude) of the endpoints of the represented road segment. In one embodiment, data 304(7) is a reference to node data record 306, representing a node corresponding to an endpoint or sub-segment of the represented road segment.

The road segment data record 304 may also include other data 304(7) or other data 304(7) associated with various other attributes relating to the road segment represented. The various attributes associated with the road segment may be included in a single road segment record, or may be included in more than one type of record that cross-references each other. For example, the road segment data record 304 may include data identifying what turning restrictions exist at each node of the nodes corresponding to the intersection at the end of the road section represented by the road segment, the known name or multiple names of the represented road segment, the street address range along the represented road segment, and so on.

Figure 3B also depicts some of the components that may be included in the node data record 306 in the geodatabase 116. Each node data record in node data record 306 may have associated information (such as "attributes", "fields", etc.) that allows identification of the geographic location (e.g., its latitude and longitude coordinates) of the road segments (multiples) and/or nodes connected to it. Node data records 306(1) and 306(2) may include the latitude and longitude coordinates of their nodes 306(1)(1) and 306(2)(1). Node data records 306(1) and 306(2) may also include additional data 306(1)(3) and 306(2)(3) relating to various other attributes of the nodes.

The geographic database 116 can be maintained by a content provider (e.g., a map developer). As an example, a map developer can collect geographic data to generate and enhance the geographic database 116. The map developer can obtain data from sources such as businesses, cities, or corresponding geographic management agencies. Additionally, the map developer can utilize field personnel walking throughout the geographic area to observe features and/or record information about roads. Remote sensing, such as aerial or satellite photography, can be used. Database 116 is connected to server 125.

Geodatabase 116 and the data stored within it can be licensed or delivered on demand. Other navigation service or traffic server providers can access the traffic data and estimated traffic flow data stored in geodatabase 116. Data, including estimated traffic flow data for links, can be broadcast as a service.

Server 125 may be a host for a website or web service such as a mapping service and/or a navigation service. The mapping service may provide maps generated from geographic data in database 116, and the navigation service may generate routes or other indications from the geographic data in database 116. The mapping service may also provide information generated from attribute data included in the database. Server 125 may also provide historical, future, recent, or current traffic conditions for links, segments, paths, or routes using historically collected data, recently collected data, or real-time collected data. Server 125 may be configured to analyze collected traffic data and/or probe reports to determine estimated traffic flow for segments or links. Server 125 may be configured to analyze data from segments and links to determine correlations between similar types of segments and nodes. For example, segments with similar traffic usage may have similar incident profiles or traffic patterns.

Figures 4A through 4H illustrate vehicles moving relative to nodes on roads according to a node-centric navigation optimization technique. Figure 4A illustrates a geographic area 400 including several roads and intersections. Each intersection corresponds to nodes _N1 through _N9 . Each lane may include one or more directions of travel and one or more lanes through which vehicles _V1 and _V2 are traveling. Vehicle _V1 starts at _N1 and is destined for _N9 . Vehicle _V1 has an initial planned route from _N1 to _N2 to _N3 to _N6 and to its destination _N9 . Vehicle _V2 also starts at _N1 and is destined for node _N9 . This example begins with vehicle _V2 having a current route that leads to its destination node _N9 after _N1 to _N4 to _N5 to _N6 . The route of vehicle _V2 has been adjusted to avoid congestion based on the current location of vehicle _V1 . Figures 4B through 4H show simplified views of the geographic area of Figure 4A.

Figure 4B illustrates vehicles _V1 and _V2 at the same time point as those appearing in Figures 4A, 4B, through 4H. The vehicle positions in Figure 4B are provided in Table 1 below. A vehicle's position can be described based on the node it is approaching in the direction of its path. In Figure 4B, vehicle _V1 is leaving node _N1 and approaching node _N2 ; the position of vehicle _V1 is represented by node _N2 . Vehicle _V2 has the position of node _N4 because it is traveling from _N1 to _N4 .

Table 1

Each vehicle's position influences the road map based on its current position and direction. Vehicle _V1 leaves node _N1 and approaches node _N2 . Therefore, vehicle _V1 influences nodes _N1 and _N2 in the road map. Table 2 illustrates the values corresponding to the road map in Figure 4B, providing the weight of a node relative to each node it connects to. The weight of a node is based on the number of vehicles approaching the node and the number of vehicles leaving the node. As shown in the road map of Figure 4B, vehicle _V1 is approaching node _N2 and leaving node _N1 . Therefore, the weight value at node _N1 is 0 relative to node _N2 , and the value is 0 relative to node _N4. Because vehicle _V1 approaches node _N2 from _N1 , the weight of node _N2 in the road map is 1 relative to _N1. Vehicle _V2 approaches _N4 from node _N1 . Therefore, the road map weight value of node _N4 is 1 relative to node _N1 . Because vehicle _V2 leaves node _N1 and approaches node _N4 , the weight of node _N1 relative to node _N4 is 0. The remaining value of the road map is 0, indicating that no other vehicles are traveling through or stopping at the intersection in the geographic area. Since the road map values for vehicle _V1 's route do not indicate any congestion, vehicle _V1 's route remains unchanged.

Table 2

Figure 4C illustrates the next increment of the path of vehicle _V1 from node _N2 to node _N3 . Vehicle _V1 leaves node _N2 and approaches node _N3 . Therefore, Table 3 below corresponds to the vehicle positions in Figure 4C. Node _N3 is the new current position of vehicle _V1 . Vehicle _V2 is not shown to have changed; therefore, the position of vehicle _V2 is node _N4 .

Table 3

Node _N2 is now in the wake of vehicle _V1 . Therefore, as depicted in Table 4, the corresponding road map in Figure 4C decreases the weight of _N2 relative to node _N1 to 0 and increases the weight of node _N3 relative to node _N2 to 1. The weight of node _N4 remains constant.

Table 4

The vehicles did not cause congestion in their existing routes; therefore, based on the change in the road map from Figure 4B to Figure 4C, the routes of each vehicle remained unchanged.

Figure 4D illustrates the next increment of the path for vehicle _V2 as it leaves node _N4 and approaches node _N5 . Therefore, Table 5 (the vehicle position table corresponding to Figure 4D) shows the position of vehicle _V2 at node _N5 . The position of vehicle _V1 remains unchanged.

Table 5

Vehicle _V2 leaves node _N4 ; therefore, the road map corresponding to Figure 4D reduces the weight of node _N4 relative to node _N5 to 0 and increases the weight of node _N5 relative to node _N4 to reflect the path of vehicle _V2 . Based on the change in the road map corresponding to Figure 4D, the route optimization for the vehicle does not need to be changed.

Table 6

Figure 4E illustrates the subsequent path of vehicle _V1 as it leaves node _N3 and approaches node _N6 . The corresponding vehicle position table in Figure 4E (Figure 7) shows the current position of vehicle _V1 as node _N6 .

Table 7

The road map values provided in Table 8 correspond to those in Figure 4E. The weight of node _N3 decreases to 0 relative to node _N6 , and the weight of node _N6 (relative to node _N3 ) increases to 1. This increase in the weight of node _N6 relative to node _N3 significantly alters the optimal path for vehicle _V2 . That is, vehicle _V2 's current route is from node _N5 to node _N6 and then to node _N9 . This change in the road map values corresponding to Figure 4E now indicates that vehicle _V2 's route has been optimized to a path from node _N5 to node _N8 and then to its destination node _N9 . Therefore, indications of route changes can be provided to vehicles.

Table 8

To achieve the route change, Figure 4F illustrates the path of vehicle _V2 leaving node _N5 in the direction of node _N8 . The corresponding vehicle position table in Figure 4F (as shown in Table 9) contains vehicle _V2 as the current position of node _N8 .

Table 9

The road map values shown in Table 10 correspond to those in Figure 4F. The weight of node _N5 decreases to 0 relative to node _N4 , and the weight of node _N8 increases to 1 relative to node _N5 .

Table 10

Vehicle _V1 moves from node _N6 to node _N9 in Figure 4G. Therefore, Table 11 (corresponding to the vehicle position table) shows the position of vehicle _N1 as node _N9 .

Table 11

The road map corresponding to Figure 4G increments the value of node _N9 relative to node _N6 and decrements the value of node _N6 relative to _N3 . The values for the road map are provided in Table 12. Based on the changes to the road map corresponding to Figure 4G, the vehicle route optimization does not need to be changed.

Table 12

Therefore, vehicle _V1 has reached its destination at node _N9 . Vehicle _V1 can enter a parking lot or roadside parking lot, and its ignition may be turned off. Thus, once vehicle _V1 is no longer on the road, it no longer appears relative to the vehicle location table or road map. Therefore, as shown in Figure 4H, the weight of the corresponding node associated with vehicle _V1 is decreased.

In Figure 4H, vehicle _V2 travels from node _N8 to its destination node _N9 . The corresponding vehicle position table (Table 13) indicates the position of vehicle _V2 at node _N9 .

Table 13

Table 14 includes the values of the road map corresponding to Figure 4H, which illustrates that the value of node _N8 decreases to 0 and the value of node _N9 increases to 1.

Table 14

Figure 5 illustrates an example system 120 for node-centric navigation optimization. System 120 includes a node-centric navigation optimization system 121, one or more mobile devices 122 (navigation devices), workstations 128, and a network 127. The system may also include networked devices 135, transportation devices 137, and/or vehicles 129 including mobile devices 122 and sensors 126. Additional, different, or fewer components may be provided. For example, many mobile devices 122, vehicles 129, and/or workstations 128 are connected to the network 127. The node-centric navigation optimization system 121 includes a server 125 and one or more databases. The server 125 may maintain multiple databases 123a, 123b...123n. One or more of these databases may include the databases illustrated in Figures 3A to 3B. The term database refers to a collection of data stored in a storage medium and may not necessarily reflect any specific requirements regarding the relational organization of the data. The term "server" is used herein to uniformly include the computing device at the node-centric navigation optimization system 121 used to create, maintain, and update multiple databases 123a to 123n. Any computing device may replace the mobile device 122. The computing device may be a host for a website or web service such as a mapping service or a navigation service. The mapping service may use node-centric navigation optimization information to provide maps generated from databases 123a to 123n, and the navigation service may calculate routes or other instructions from the geographic data of databases 123a to 123n and the node-centric navigation optimization information.

Mobile device 122, vehicle 129, and/or network device 135 may include a processor and database providing some or all of the services offered by the node-centric navigation optimizer 121. The local node-centric navigation optimizer 121 of mobile device 122 may work in conjunction with the node-centric navigation optimizer 121 via network 127. As described herein, the processes of affected node determination, road map updating, navigation, route calculation, estimated travel time, and estimated arrival time are described with reference to a node-centric navigation optimizer. Additionally, alternatively, or jointly, the actions of the disclosed embodiments may be performed by a node-centric navigation optimizer disposed in or integrated with mobile device 122, network device 135, and/or vehicle 129.

Databases 123a to 123n may include road map databases, which may include road element information, current node weights, historical node weights, navigation information, traffic information, driver profile information, historical traffic information, road images including street-level images, point cloud data, and/or existing map data. As shown in Figure 7, a primary copy of database 123a may be stored in a node-centric navigation optimizer 121, and databases 123b to 123n may include aggregated generalized road maps and/or alternative or past versions of optimization algorithms associated with the navigation map. The primary copy of database 123a may be the most current or most recent copy of the database. Additionally, mobile device 122 may store a local copy of database 124. In one example, the local copy of database 123b is a complete copy of the database; in another example, the local copy of database 124 may be a cached portion or a partial portion of the database.

A local copy of database 124 located on mobile device 122 may include data from various versions of databases 123a to 123n. The cached portion can be defined based on the geographic location, position, or orientation of mobile device 122, or user selections made at mobile device 122. Server 125 can send node-centric navigation optimization information to mobile device 122.

Mobile device 122 may be a personal navigation device (PND), a portable navigation device smartphone, mobile phone, personal digital assistant (PDA), automobile, tablet computer, laptop computer, and/or any other known or later-developed connectivity device or personal computer. Non-limiting embodiments of the navigation device may also include relational database service devices, mobile phone devices, or car navigation devices. Vehicle 129 having mobile device 122 and sensor 126 may be an autonomous vehicle, a data acquisition vehicle, or a vehicle equipped with navigation or other communication capabilities.

A node-centric navigation optimizer 121, workstation 128, mobile device 122, and vehicle 129 are coupled to network 127. The phrase "coupled" is defined as meaning a direct connection to one or more intermediate components or an indirect connection through one or more intermediate components. Such intermediate components may include hardware-based components and/or software-based components.

Network 127 may include a wired network, a wireless network, or a combination thereof. The wireless network may be a cellular telephone network, an 802.11, 802.16, 802.20, or a WiMax network. Furthermore, network 127 may be a public network such as the Internet, a private network such as an intranet, or a combination thereof, and may utilize a variety of networking protocols now available or to be developed later, including but not limited to TCP/IP-based networking protocols.

Figure 6 illustrates an exemplary mobile device 122 of the system of Figure 5. Mobile device 122 includes a processor 200, a memory 204, an input device 203, a communication interface 205, a position circuitry 207, and a display 211. Additional, different, or fewer components are possible for mobile device 122. Figures 1 and 2 illustrate example flowcharts for the operation of mobile device 122 and processor 200. Additional, different, or fewer actions may be provided.

Positioning circuitry 207 may include a Global Positioning System (GPS), a Global Navigation Satellite System (GLONASS), or a cellular location sensor or similar location sensor for providing location data. The positioning system may utilize GPS-type technology, dead reckoning systems, cellular positioning, or a combination of these or other systems. Positioning circuitry 207 may include suitable sensing devices for measuring the distance traveled, speed, direction, etc., of the mobile device 122. The positioning system may also include a receiver and associated chips to obtain GPS signals. Alternatively or additionally, one or more detectors or sensors may include an accelerometer built into or embedded within the mobile device 122. The accelerometer is operable to detect, identify, or measure the rate of change of translational and/or rotational motion of the mobile device 122. The mobile device 122 receives location data from the positioning system. The location data indicates the position of the mobile device 122.

Input device 203 may be one or more buttons, keypads, keyboards, mice, styluses, trackballs, rocker switches, touchpads, voice recognition circuitry, or other devices or components for inputting data to mobile device 100. Input device 203 and display 211 may be combined to form a touchscreen, which may be capacitive or resistive. Display 211 may be a liquid crystal display (LCD) panel, a light-emitting diode (LED) screen, a thin-film transistor (TFT) screen, or other types of display.

Processor 200 and/or processor 300 may include general-purpose processors, digital signal processors, application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), analog circuits, digital circuits, combinations thereof, or other processors now known or developed hereafter. Processor 200 and/or processor 300 may be a single device or a combination of devices, such as those associated with a network, distributed processing, or cloud computing. Processor 200 and/or processor 300 may include a node-centric navigation optimizer. Mobile device 122 may receive and store map information, road element information, and mobility information, as well as metadata associated with these types of information. Processor 200 may receive route information via network 127 and calculate the route from the origin to the destination. Processor 200 may perform all travel time estimations and arrival time estimations on mobile device 122. That is, mobile device 122 may receive map and/or navigation information via network 127, which identifies road elements, mobility, link information, traffic information, and other information via network 127. The processor 200 of mobile device 122 can calculate initial route information based on destination information and the vehicle's current location data, receive road map data, and optimize the vehicle's route on mobile device 122. The processor 200 of mobile device 122 can additionally receive information associated with the vehicle 129 and its ground realism, i.e., actual travel time and actual route information associated with the trip. The processor 200 can then update and add location data and/or route data based on data collected during the trip. The processor 200 of mobile device 122 can collaborate with server 125 via network 127 to perform some or all of route determination, route optimization, vehicle location data, or road map weight values. Alternatively, the processor 200 can be used to transmit anonymous and/or non-geographically specific and/or generalized vehicle location information via network 127 for updating the road map information of the node-centric navigation optimizer 121. Anonymous or non-geographically specific information associated with driver profile information can be sent to a network via network 127 to the node-centric navigation optimizer 121, enabling road map information to be updated from multiple drivers, regardless of whether all vehicles use route optimization features. The road map information received by the node-centric navigation optimizer 121 can be used in conjunction with current traffic information stored in the navigation and/or node-centric navigation optimizer 121's databases 123a to 123n.

Memory 204 and/or memory 301 may be volatile or non-volatile memory. Memory 204 and/or memory 301 may include one or more of read-only memory (ROM), random access memory (RAM), flash memory, electronically erasable program read-only memory (EEPROM), or other types of memory. Memory 204 and/or memory 301 may be removed from mobile device 122 such as a secure digital (SD) memory card.

Communication interface 205 and/or communication interface 305 may include any operable connection. An operable connection may be a connection capable of transmitting and/or receiving signals, physical communication, and/or logical communication. An operable connection may include a physical interface, an electrical interface, and/or a data interface. Communication interface 205 and/or communication interface 305 provide wireless and/or wired communication in any format now known or later developed.

Mobile device 122 is configured to execute mapping algorithms to determine a route along a road network from the origin/starting point to the destination/destination location within a geographic area where a map including large-scale scan information can be used. Mobile device 122 may be configured to acquire vehicle location data, direction of travel, images, or other data. Using input from the end user, navigation device 122 can examine potential routes between the origin and destination locations to determine the optimal route before route optimization using a node-centric navigation optimizer 121. Navigation device 122 can then provide the end user with information about the optimal route, travel information, and travel time information in the form of guidance, which identifies the maneuvers required for the end user to travel from the starting point to the destination location. Some navigation devices 122 display a detailed map on the screen outlining the route, the types of maneuvers taken at different locations along the route, the location of certain types of features, and so on.

Using input from the driver or other passengers in the vehicle (such as origin and/or destination), mobile device 122 can request and receive navigation information via network 127 for specified road elements, maneuvers, and routes from the origin to the destination. Mobile device 122 can receive road map information via network 127. Additionally, mobile device 122 receives current traffic information via network 127 from sources other than the node-centric navigation optimizer 121.

Figure 7 illustrates an example server 125. Server 125 includes a processor 300, a communication interface 305, and a memory 301. Server 125 can be coupled to one or more databases 123 and workstations 128. Workstation 128 can be used to input information about geographic area maps, traffic clustering data, road element information, mobility information, navigation information, traffic information, driver profile information, historical traffic information, road images including street-level images, point cloud data, and/or existing map data. Database 123 can include information input from workstation 128. Additional, different, or fewer components can be provided in server 125. Figures 1 and 2 illustrate example flowcharts for the operation of server 125. Additional, different, or fewer actions can be provided.

Processor 300 and/or processor 200 may include a general-purpose processor, digital signal processor, ASIC, FPGA, analog circuit, digital circuit, combination thereof, or other processors now known or to be developed later. Processor 300 and/or processor 200 may be a single device or a combination of devices, such as those associated with a network, distributed processing, or cloud computing. Processor 300 and/or processor 200 performs operations associated with a node-centric navigation optimizer. Server 125 may receive and store map information, road element information and mobility information, aggregated driver information, driver profile information, personalization information, current traffic information, and metadata associated with these types of information. Processor 300 may receive starting points, intermediate travel points, and/or destination points from mobile device 122 via network 127, and determine vehicle position data, vehicle direction information, affected node information, road map information, map information, road element information, mobility information, aggregated driver information, driver profile information, personalization information, current traffic information, and metadata. Processor 300 may perform all updates to the road map information and may further optimize the routes of one or more individual vehicles at server 125. The processor 300 can continuously update and store road map data based on the received vehicle location information and/or send the updated road map data to the mobile device 122. The processor 200 of the mobile device 122 can work in conjunction with the processor 300 and the server 125 via the network 127 to perform some or all of the functions of the node-centric navigation optimizer 121.

Memory 301 and/or memory 204 may be volatile or non-volatile memory. Memory 301 and/or memory 204 may include one or more of read-only memory (ROM), random access memory (RAM), flash memory, electronically erasable program read-only memory (EEPROM), or other types of memory.

Communication interface 305 and/or communication interface 205 may include any operable connection. An operable connection may be a connection capable of transmitting and/or receiving signals, physical communication, and/or logical communication. An operable connection may include a physical interface, an electrical interface, and/or a data interface. Communication interface 305 and/or communication interface 205 provide wireless and/or wired communication in any format now known or later developed.

The term "computer-readable medium" includes a single medium or multiple media, such as a centralized or distributed database, and/or an associated cache and server storing one or more sets of instructions. The term "computer-readable medium" shall also include any medium capable of storing, encoding, or carrying a set of instructions for execution by a processor or to cause a computer system to perform any one or more of the methods or operations disclosed herein.

In specific, non-limiting exemplary embodiments, a computer-readable medium may include solid-state memory, such as a memory card or other package housing one or more non-volatile read-only memories. Further, a computer-readable medium may be random access memory or other volatile rewritable memory. Additionally, a computer-readable medium may include magneto-optical or optical media, such as disks or tapes or other storage devices, to capture carrier signals, such as signals transmitted via a transmission medium. Digital file attachments to emails or other independent information archives or archive sets can be considered distribution media of tangible storage media. Therefore, this disclosure is considered to include any one or more of computer-readable media or distribution media capable of storing data or instructions, as well as other equivalents and successor media. These examples may be collectively referred to as non-transitory computer-readable media.

In alternative embodiments, dedicated hardware implementations (such as application-specific integrated circuits, programmable logic arrays, and other hardware devices) can be configured to implement one or more of the methods described herein. Applications that may include various embodiments of the apparatus and systems can broadly encompass a wide range of electronic and computer systems. One or more embodiments described herein may implement functionality using two or more specific interconnected hardware modules or devices having associated control and data signals that can communicate between and through the modules or as part of an application-specific integrated circuit. Therefore, this system encompasses software implementations, firmware implementations, and hardware implementations.

According to various embodiments of this disclosure, the methods described herein can be implemented by a software program executable by a computer system. Further, in exemplary non-limiting embodiments, implementation may include distributed processing, component/object distributed processing, and parallel processing. Alternatively, virtual computer system processing may be configured to implement one or more of the methods or functionalities described herein.

Although this specification describes components and functions that may be implemented in specific embodiments with reference to specific standards and protocols, the invention is not limited to such standards and protocols. For example, standards for Internet and other packet-switched network transports (e.g., TCP/IP, UDP/IP, HTML, HTTP, HTTPS) represent examples of the state of the prior art. These standards are periodically superseded by faster or more efficient equivalents with substantially the same functionality. Therefore, alternative standards and protocols having the same or similar functionality as those disclosed herein are considered equivalents.

Computer programs (also known as programs, software, software applications, scripts, or code) can be written in any programming language, including compiled or interpreted languages, and can be deployed in any form, including as standalone programs or as modules, components, subroutines, or other units adapted to a computing environment. A computer program does not necessarily correspond to a file in a file system. A program can be stored as part of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinating files (e.g., a file storing one or more modules, subroutines, or code sections). Computer programs can be deployed to execute on a single computer, at a single site, or distributed across multiple computers interconnected by a communication network.

The processes, actions, and logical flows described in this specification can be executed by one or more programmable processors that execute one or more computer programs to perform functions by manipulating input data and generating output. The processes, actions, and logical flows can also be executed by special-purpose logic circuitry (e.g., FPGAs or ASICs), and the apparatus can also be implemented as special-purpose logic circuitry.

As used in this application, the term "circuit" or "circuit" means all of the following: (a) a hardware circuit implementation only (such as an implementation only in analog and/or digital circuits); (b) a combination of circuits and software (and/or firmware), such as (if applicable): (i) a combination of processors or (ii) a portion of processor/software (including digital signal processors), software, and memory that work together to enable a device such as a mobile phone or server to perform various functions); and (c) a circuit, such as a microprocessor or a portion of a microprocessor, which requires software or firmware to operate even if the software or firmware is not physically present.

This definition of "circuit" applies to all uses of the term included in any claim herein. As another example, as used herein, the term "circuit" will also cover implementations of a processor (or processors) or a portion thereof and its accompanying software and/or firmware. The term "circuit" will also cover (e.g., and if applicable, baseband integrated circuits or application processor integrated circuits for mobile phones; or similar integrated circuits in servers, cellular network devices, or other network devices.

Processors suitable for executing computer programs include, for example, general-purpose microprocessors and special-purpose microprocessors, as well as any one or more processors of any kind of digital computer. Typically, a processor receives instructions and data from read-only memory or random access memory, or both. The fundamental elements of a computer are a processor for executing instructions and one or more memory devices for storing instructions and data. Typically, a computer also includes, or is operatively coupled to, receiving data from or transferring data to one or more high-volume storage devices (e.g., disks, magneto-optical disks, or optical disks), or both, to store data. However, a computer does not require such devices. Moreover, a computer can be embedded in another device, such as a mobile phone, a personal digital assistant (PDA), a vehicle, a navigation device, a mobile audio player, a Global Positioning System (GPS) receiver, to name just a few. Computer-readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media, and memory devices, including, for example, semiconductor memory devices, such as EPROM, EEPROM, and flash memory devices; disks, such as internal hard disks or removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks. The processor and memory may be supplemented or incorporated therein by dedicated logic circuitry.

To provide interaction with the user, embodiments of the subject matter described in this specification can be implemented on a device with a display, such as a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user, a keyboard, and a pointing device (e.g., a mouse or trackball), through which the user can provide input to the computer. Other types of devices can also be used to provide interaction with the user; for example, feedback provided to the user can be any form of sensory feedback, such as visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including sound input, voice input, or tactile input.

Embodiments of the subject matter described in this specification can be implemented in a computing system that includes back-end components (e.g., as a data server), middleware components (e.g., an application server), or front-end components (e.g., a client computer with a graphical user interface or web browser through which a user can interact with the implementation of the subject matter described in this specification), or any combination of one or more such back-end, middleware, or front-end components. The components of the system can be interconnected through any form or medium of digital data communication (e.g., a communication network). Examples of communication networks include local area networks (LANs) and wide area networks (WANs), such as the Internet.

A computing system may include clients and servers. Clients and servers are typically geographically separated and usually interact via a communication network. The relationship between clients and servers is established by computer programs running on their respective computers and having a client-server relationship with each other.

The illustrations of the embodiments described herein are intended to provide a general understanding of the structure of various embodiments. These illustrations are not intended as a complete description of all elements and features of apparatuses and systems utilizing the structures or methods described herein. Many other embodiments will be apparent to those skilled in the art upon reading this disclosure. Other embodiments can be utilized and derived from this disclosure, allowing structural and logical substitutions and changes to be made without departing from the scope of this disclosure. Additionally, the illustrations are merely illustrative and may not be drawn to scale. Some scales in the illustrations may be exaggerated, while others may be minimized. Therefore, this disclosure and the accompanying drawings are to be considered illustrative rather than restrictive.

While this specification contains numerous details, these descriptions should not be construed as limiting the scope of the invention or the scope of the claims, but rather as descriptions of features specific to particular embodiments of the invention. Certain features described in the context of individual embodiments in this specification may also be implemented in combination in a single embodiment. Conversely, various features described in the context of a single embodiment may also be implemented separately or in any suitable sub-combination in multiple embodiments. Although features may be described above as acting in a particular combination, and even initially claimed in this way, one or more features from a claimed combination may be removed from that combination in some cases, and the claimed combination may be for sub-combinations or variations thereof.

Similarly, although operations and actions are depicted in the accompanying drawings and described herein in a specific order, this should not be construed as requiring these operations to be performed in the specific order shown or sequentially, or to perform all illustrated operations to achieve the desired result. In some cases, multitasking and parallel processing may be advantageous. Furthermore, the separation of the various system components in the embodiments described above should not be construed as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.

One or more embodiments of this disclosure may be individually and/or collectively referred to herein as the "invention," for convenience only, and are not intended to voluntarily limit the scope of this application to any particular invention or inventive concept. Moreover, although specific embodiments have been illustrated and described herein, it should be understood that any subsequent arrangements designed to achieve the same or similar purpose may replace the specific embodiments shown. This disclosure is intended to cover any and all subsequent adaptations or variations of the various embodiments. Combinations of the above embodiments and other embodiments not specifically described herein will be apparent to those skilled in the art upon reading the description.

An abstract is provided to comply with 37 C.F.R. §1.72(b), provided that the abstract is not used to interpret or limit the scope or meaning of the claims. Additionally, in the foregoing detailed description, various features may be combined together or described in a single embodiment for the purposes of this disclosure. This disclosure should not be construed as reflecting an intention to require more features than those expressly listed in each claim. Rather, as reflected in the following claims, the subject matter of the invention may be directed to fewer than all features of any of the disclosed embodiments. Therefore, the following claims are incorporated into the detailed description, while each claim serves as a separate definition of the claimed subject matter.

The specific embodiments described above are intended to be illustrative rather than restrictive, and it should be understood that the appended claims, including all equivalents, are intended to define the scope of the invention. Unless otherwise stated, the claims should not be read as limited to the order or elements described. Therefore, all embodiments falling within the scope and spirit of the appended claims and their equivalents are claimed as part of the invention.

Claims (17)

1. A node-centric navigation optimization method, the method comprising: Receive vehicle position data from sensors on vehicles in a convoy of vehicles on the road; The affected nodes of the road are identified based on the vehicle location data; A road map representing at least a portion of a road is updated based on the affected nodes. The road map includes a plurality of nodes of the road and a weight for each of the plurality of nodes, the weight indicating the number of vehicles in the vehicle platoon corresponding to a node in the path of the vehicle in the vehicle platoon. If the affected node is a node in the vehicle's forward path, then the weight of the affected node is increased; If the affected node is a node in the vehicle trail, then the weight of the affected node is decreased; and The road map is updated based on the weights of the affected nodes of the road, wherein the vehicle's route is optimized based on the updated road map. 2. The method according to claim 1, wherein the affected node identifying the road further comprises: Determine whether the affected node is a node in the vehicle's forward path or a node in the vehicle's trail. 3. The method of claim 2, wherein determining whether the affected node is a node in the vehicle's forward path or in the vehicle's trail is based on the vehicle's current position and direction of travel. 4. The method of claim 3, wherein determining whether the affected node is a node in the forward path of the vehicle or a node in the vehicle trail is based on one or more previous positions of the vehicle. 5. The method according to claim 1, further comprising: Receive infrastructure data associated with the road; and The road map is updated using the received vehicle location 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 according to claim 1, wherein the received vehicle location data includes vehicle identification information. 8. The method of claim 1, wherein optimizing the route of the vehicle further comprises: The optimal route for the vehicle is calculated based on the weights of the nodes along the possible routes to the vehicle's destination. 9. The method according to claim 1, further comprising: Provide instructions for changes to the route. 10. The method of claim 9, wherein providing the indication of the change of route further comprises: Provides graphical navigation information for display on the vehicle. 11. The method of claim 9, wherein providing the indication of a change in the route further comprises: Provide instructions for controlling the autonomous operation of the vehicle; or The vehicle provides a selection of possible navigation options for its passengers, and 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 are configured, together with the at least one processor, to cause the device to at least: Receive vehicle location data associated with vehicles in a convoy of vehicles on the road; The affected nodes of the road are identified based on the vehicle location data; A road map representing at least a portion of a road is updated based on the affected nodes. The road map includes a plurality of nodes of the road and a weight for each of the plurality of nodes, the weight indicating the number of vehicles in the vehicle platoon corresponding to a node in the path of the vehicle in the vehicle platoon. If the affected node is a node in the vehicle's forward path, then the weight of the affected node is increased; If the affected node is a node in the vehicle trail, then the weight of the affected node is decreased; and The road map is updated based on the weights of the affected nodes of the road, wherein the vehicle's route is optimized based on the updated road map. 13. The apparatus of claim 12, wherein identifying the affected node of the road further enables the apparatus to: Determine whether the affected node is a node in the forward path of the vehicle or a node in the trail of the vehicle's path. 14. 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 are configured, together with the at least one processor, to cause the device to at least: Receive vehicle location data for the vehicle; The affected nodes of the road are identified based on the vehicle location data; If the affected node is a node in the vehicle's forward path, then the weight of the affected node is increased. If the affected node is a node in the vehicle trail, then the weight of the affected node is decreased; The road map representing at least a portion of the road is updated based on the weights of the affected nodes of the road; and At least a portion of the updated road map is provided to the vehicles on the road for route optimization. 15. A node-centric navigation optimization method, the method comprising: Multiple sensors on a convoy of associated vehicles on a road within a geographic region are used to receive vehicle location data. A road map representing at least a portion of a road, the road map including a plurality of nodes of the road and a weight for each of the plurality of nodes, the weight indicating the number of vehicles in the associated vehicle platoon corresponding to a node in the path of a vehicle in the associated vehicle platoon; One or more affected nodes on the road are identified based on the vehicle location data of the associated vehicle fleet; Update the road map based on the one or more affected nodes of the road; and The routes of the associated vehicle convoys are optimized based on the updated road map. 16. The method of claim 15, wherein the one or more affected nodes identifying the road further include: Determine whether each corresponding affected node is on the forward path of any vehicle in the associated vehicle convoy or in the trail of any vehicle in the associated vehicle convoy. 17. The method of claim 15, wherein updating the road map using the received vehicle location data further comprises: Increment the weight of each corresponding affected node in the forward path of any vehicle in the associated vehicle convoy; and Decrease the weight of each corresponding affected node in the trail of the path of any vehicle in the associated vehicle convoy.