Patent Publication Number: US-8996295-B2

Title: Vehicle range projection

Description:
FIELD OF THE INVENTION 
     The subject invention relates to data processing, and more particularly, to determining a geographically reachable area for a vehicle based on both routing objectives and travel constraints. 
     BACKGROUND 
     Global positioning systems (GPSs), handheld devices, and online map routing services provide mechanisms to navigate from one point to another by calculating paths based on information derived from roadway maps. Routing systems typically have usability features to automatically calculate the type of directions desired. The usability features allow an operator to specify routing objectives such as: shortest distance (using an algorithm to determine the shortest distance from one point to the next); least amount of travel time (using an algorithm to determine the shortest distance based on the road&#39;s speed limit and distance, and calculating the resulting driving time); least use of freeways; least use of energy (gasoline and/or electricity); and least use of toll roads. 
     Routing systems (also referred to herein as mapping engines) typically include cartographic maps and map databases to determine an appropriate driving route. The map databases represent a network of roads and often include information about toll roads, speed limits, highway exit points, and points of interest (POIs). The map databases also include points on a map (also known as waypoints) represented in the form of latitudes and longitudes, universal transverse Mercator (UTM) coordinates, and/or geospatial coordinates. Some examples of waypoints include POIs (e.g., museums, restaurants, railways, exit points, etc.), satellites, user-entered destinations, and fixed reference points along a route. These waypoints can be marked on maps in the routing systems. 
     A route is a series of two or more waypoints. In order to determine a suggested route, a routing system first determines a set of waypoints between a starting point and a destination point. The routing system then guides a user to a nearest waypoint along the route, then to the next waypoint in the route, and so on, until the user reaches the destination point. A typical routing system resolves the starting point and the destination point into its nearest known waypoints on the network and then uses a “great circle routing algorithm” to determine a route between two points. Some routing systems also use a search algorithm to search a graph of nodes (representing waypoints) and edges (representing paths between waypoints). Some examples of search algorithms that can be used to determine a route between two points are Dijkstra&#39;s algorithm (to determine the shortest path), an A* algorithm (to determine the shortest path along a weighted graph), and a bi-directional search algorithm. 
     Routing systems are designed to take into account routing objectives when determining a route between two points. However, a vehicle operator may also be constrained by other factors that impact a range that the vehicle can travel. For example, when selecting POIs, an operator may only have a specified amount of time to travel to the POI. In another example, an operator of an electric vehicle may be looking for a recharge station that is within a selected kilowatt hour (kwHr) range of the current location of the vehicle. Accordingly, it would be desirable to provide a way to determine a range of geographic locations that a vehicle can visit based on both routing objectives and travel constraints. 
     SUMMARY OF THE INVENTION 
     In one exemplary embodiment of the invention, a system for providing vehicle range projection is provided. The system includes a host system computer and logic executable by the host system computer. The logic is configured to implement a method. The method includes identifying a starting location of a vehicle and identifying destination locations for the vehicle. Routes are built from the starting location to the destination locations based on routing objectives and travel constraints. At least a portion of at least one route and travel cost information associated with the at least a portion of at least one route are output. 
     In another exemplary embodiment of the invention, a method for providing vehicle range projection is provided. The method includes identifying a starting location of a vehicle and identifying destination locations for the vehicle. Routes are built from the starting location to the destination locations based on routing objectives and travel constraints. At least a portion of at least one route and travel cost information associated with the at least a portion of at least one route are output. 
     In yet another exemplary embodiment of the invention a computer program product for implementing vehicle range projection is provided. The computer program product includes a computer-readable storage medium having instructions embodied thereon, which when executed by a computer, cause the computer to implement a method. The method includes identifying a starting location of a vehicle and identifying destination locations for the vehicle. Routes are built from the starting location to the destination locations based on routing objectives and travel constraints. At least a portion of at least one route and travel cost information associated with the at least a portion of at least one route are output. 
     The above features and advantages and other features and advantages of the invention are readily apparent from the following detailed description of the invention when taken in connection with the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Other features, advantages and details appear, by way of example only, in the following detailed description of embodiments, the detailed description referring to the drawings in which: 
         FIG. 1  is a system upon which vehicle range projection may be implemented in accordance with an exemplary embodiment of the invention; 
         FIG. 2  is a system upon which vehicle range projection may be implemented in accordance with an alternate exemplary embodiment of the invention; 
         FIG. 3  is a flow diagram describing a process for implementing vehicle range projection in accordance with an exemplary embodiment of the invention; and 
         FIG. 4  is a sample output screen produced by a vehicle range projection system in accordance with an exemplary embodiment of the invention. 
     
    
    
     DESCRIPTION OF THE EMBODIMENTS 
     The following description is merely exemplary in nature and is not intended to limit the present disclosure, its application or uses. It should be understood that throughout the drawings, corresponding reference numerals indicate like or corresponding parts and features. 
     In accordance with an exemplary embodiment of the invention, a travel range of a vehicle is determined by taking into consideration both a routing method and a travel constraint. Different routing methods have different routing objectives, for example, to minimize travel time, to minimize travel distance and/or to minimize energy usage (e.g., gasoline and/or electricity). As used herein, the term “travel constraint” refers to vehicle range restrictions such as, but not limited to: a distance (e.g., within three miles); an amount of time (e.g., within three minutes); or an energy usage (e.g., less than 0.3 kwHrs). In accordance with exemplary embodiments, information about the projected travel range of the vehicle is output to a display device in the vehicle and presented, via the display device, to the operator of the vehicle or to a passenger in the vehicle. This projected travel range may then be used, for example, to select one or more points of interest along a route to a destination that meet a specified travel constraint(s). 
     In an embodiment, the vehicle is a limited range powertrain vehicle such as a battery electric vehicle (BEV) or an extended range electric vehicle (EREV), and the travel constraint is an electricity range of the vehicle. In another embodiment, the vehicle is a gasoline powered automobile. 
     In an embodiment, the projected travel range is determined by first replacing a node representing the destination location with a virtual node that corresponds to a distance beyond the reach of the travel constraints. A secondary cost is then accumulated based on the travel constraint(s) as a mapping engine calculates a minimizing route based on the routing objective(s). When the secondary cost exceeds the travel constraint cost, graph node neighbors are prevented from being considered in developing the range projection. A reachable region is highlighted on a display device based on the nodes in the map that can be reached. In this manner, drivers are assisted in selecting POIs based on travel constraints. For example, POIs that are within a time constraint for travel may be displayed on the display device. The use of embodiments of the vehicle range projection as described herein may also result in improved off-cycle electrification of driving due to better understanding of trip feasibility and remaining range. 
     Turning now to  FIG. 1 , a system  100  upon which vehicle range projection may be implemented in an exemplary embodiment will now be described. The system  100  shown in  FIG. 1  is located in a vehicle and includes a processor  102 , range projection logic  114 , a storage device  108 , a display device  104 , and a user input device  112 . The processor  102  may be implemented by any computer processor that is suitable for being located in the vehicle and for performing the vehicle range projection described herein. In an exemplary embodiment, the system  100  is integrated into or is a vehicle control module such as, for example, an infotainment control module or a navigation control module. Though not shown, the system  100  may also include an antenna for communicating with a wireless communication network. 
     The user input device  112  typically includes a keypad or a keyboard for allowing a user to input information. In an embodiment, the display device  104  is a liquid crystal display (LCD) screen that is used to display graphics and text. Although  FIG. 1  illustrates the user input device  112  and the display device  104  as separate components it is to be understood that the user input device  112  and the display device  104  may be a combined unit as well. For example, in an embodiment the display is a touchscreen that detects the presence and location of a user&#39;s touch. 
     In an embodiment, the system  100  is in communication with or includes a global positioning satellite (“GPS”) receiver that is in communication with a satellite (not shown) for providing information regarding a current (or starting) location of the vehicle. Alternatively, the current (or starting) location of the vehicle is determined by obtaining user input. Specifically, the user may input current location information into a keypad or keyboard or touch screen of the user input device  112 . In an embodiment, the range projection logic  114  includes travel constraint logic  106  and a mapping engine and database  110  for providing a vehicle range projection based on both routing objectives and travel constraints as described herein. For example, instead of choosing a destination against which an approximate ‘cost-to-go’ is determined, the cost-to-go to the target from any node is the negative scaled Euclidean distance to the vehicle&#39;s current location. By contrast, in conventional routing approaches, the cost-to-go approximation is done with respect to a single destination. The use of this approximation of the cost-to-go causes the range projection logic  114  to search in every larger area for a route. Additionally, the range projection logic  114  maintains a record of the total cost-to-go to arrive at a node from the vehicle&#39;s current location. When this cost-to-go from the vehicle location to the node if question exceeds the constraint cost, then the all searching from that node is terminated. These two mechanisms (a negative cost approximation to the vehicle&#39;s current location and the termination of searching based on node costs to the vehicle location) enable calculation of the range projection. 
     The range projection logic  114  may be a program that is included with the system  100  in a vehicle at the time of manufacture. Alternatively, the range projection logic  114  is a downloadable application that is saved in the memory of the system  100  after manufacture of the vehicle. 
     As described previously, travel constraints are vehicle range restrictions such as distance or travel time. In an embodiment, a user sets the travel constraints through the user input device  112 . Alternatively a travel constraint is set automatically by the range projection logic  114  based on one or more known vehicle states (e.g., amount of remaining fuel or energy). 
     Turning now to  FIG. 2 , an alternate system  200  upon which vehicle range projection may be implemented in an exemplary embodiment of the invention will now be described. The system  200  includes a host system  202  in communication with a user system  204  over one or more networks  206 . The host system  202  is also in communication, via the network  206 , with a mapping engine and database  208 . 
     As shown in  FIG. 2 , the host system  202  may be implemented by an enterprise for providing vehicle range projection and is configured with range projection logic  210  for performing the vehicle range projection described herein. In one embodiment, the host system  202  is implemented by an application service provider (ASP) to provide vehicle range projection to end users (e.g., vehicle consumers). The host system  202  may be implemented as a high-speed computer processing device (e.g., a mainframe computer) capable of handling a high volume of activities conducted between the host system  202  and the network entities shown in  FIG. 2 . 
     The host system  202  may operate as a web server including a web site for generating subscription accounts to vehicle range projection services and providing information to end users. The host system  202  may also operate as an application server including one or more applications for providing the vehicle range projection described herein. These one or more applications are collectively referred to herein as range projection logic  210 . 
     The networks  206  may be any type of known networks in the art. For example, the networks  206  may be a combination of public (e.g., Internet), private (e.g., local area network, wide area network, virtual private network), and may include wireless and wireline transmission systems (e.g., satellite, cellular network, terrestrial networks, etc.). 
     In an embodiment, the user system  204  is included in a vehicle control module such as, for example, an infotainment control module or a navigation control module. In another embodiment, the user system  204  is a personal digital device such as, but not limited to, a cellular telephone or tablet computer. In an embodiment, the user system  204  includes an input device and a display device, such as those described previously with respect to  FIG. 1 . 
     In an embodiment, the system  200  is in communication with or includes a GPS receiver that is in communication with a satellite (not shown) for providing information regarding a current (or starting) location of the vehicle. Alternatively, the current (or starting) location of the vehicle is determined by obtaining user input. Specifically, the user may input starting location information into the user system  204 . In the embodiment shown in  FIG. 2 , the range projection logic  210  includes travel constraint logic and it interfaces with the mapping engine and database  208  for providing a vehicle range projection based on both routing objectives and travel constraints as described herein. 
     It will be understood that while only a single user system  204  is shown in  FIG. 2  for illustrative purposes, any number of user systems may be employed in realizing the advantages of the exemplary embodiments. 
     The mapping engine and database  208  includes a mapping tool that takes as input a starting location (e.g., address) and a destination location and returns as output one or more routes to follow to get from the starting location to the destination location subject to routing objectives. The mapping engine and database  208  includes a database of maps for generating the routes. The mapping engine and database  208  may be a proprietary tool or a commercial application, such as Google Maps®. 
       FIG. 3  is a flow diagram describing a process for implementing vehicle range projection in accordance with an exemplary embodiment. As indicated above, vehicle range projection enables an operator to receive information about the locations that a vehicle can visit based on a routing method and a travel constraint. In an embodiment, the vehicle is a BEV or an EREV and the travel constraint is the amount of charge left in the vehicle. The process depicted in  FIG. 3  is described using the system  100  shown in  FIG. 1  as an example; the process shown in  FIG. 3  may also be implemented by other embodiments, such as the system  200  shown in  FIG. 2 . 
     At step  302  in  FIG. 3 , the system  100  identifies a starting location that corresponds to the current location of the vehicle when it is received via a GPS receiver. Alternatively, the starting location may be received from a user of the system  100  via the user input device  112 . 
     At step  304 , destination locations are identified by the system  100  using the mapping engine and database  110 . In an embodiment, an A* routing algorithm used by the mapping engine and database  110  is modified to route to locations farthest away from the origin (i.e., the starting location) by using a routing heuristic which is equal to the negative of a scaled Euclidean distance to the origin. This ensures that each routing decision chooses the point which produces travel away from the origin as efficiently as possible. In addition to the Euclidean distance, other metrics, such as Manhattan distances, p-norms, or similar measures of distance may be applied. 
     At step  306 , routes are built toward the destination locations by the system  100  using the travel constraint logic  106  and the mapping engine and database  110  components of the range projection logic  114 . In an embodiment, while developing the network of routed connects, a minimum of two costs are maintained. One cost corresponds to the routing cost and the other cost corresponds to the travel constraint cost. The routing algorithm in the mapping engine is prohibited from selecting neighboring nodes if the travel constraint is exceeded by the route. The routing algorithm terminates when all reachable points are searched. Using this approach, the cost to travel to the origin from each routed node is known. In this manner, the route is calculated using multiple costs which are used for independent purposes: routing and constraint evaluation. 
     A modified A* algorithm, written in pseudo code that is utilized by an exemplary embodiment to perform step  306  follows: 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 function A*(start,goal) 
               
               
                   
                 // The set of nodes already evaluated. 
               
               
                   
                 closedset := the empty set 
               
               
                   
                 // The set of tentative nodes to be evaluated. 
               
               
                   
                 openset := set containing the initial node 
               
               
                   
                 // The map of navigated nodes. 
               
               
                   
                 came_from := the empty map 
               
               
                   
                 // Distance from start along optimal path. 
               
               
                   
                 c_score[start] := 0 
               
               
                   
                 g_score[start] := 0 
               
               
                   
                 h_score[start] := heuristic_estimate_of_distance(start, goal) 
               
               
                   
                 // Estimated total distance from start to goal through y. 
               
               
                   
                 f_score[start] := h_score[start] 
               
               
                   
                 while openset is not empty 
               
               
                   
                  x := the node in openset having the lowest f_score[ ] value 
               
               
                   
                  if x = goal 
               
               
                   
                   return reconstruct_path(came_from, came_from[goal]) 
               
               
                   
                  remove x from openset 
               
               
                   
                  add x to closedset 
               
               
                   
                  for each y in constrained_neighbor_nodes(x,c_score[x]) 
               
               
                   
                   if y in closedset 
               
               
                   
                    continue 
               
               
                   
                   tentative_g_score := g_score[x] + dist_between(x,y) 
               
               
                   
                    if y not in openset 
               
               
                   
                    add y to openset 
               
               
                   
                    tentative_is_better := true 
               
               
                   
                   else if tentative_g_score &lt; g_score[y] 
               
               
                   
                    tentative_is_better := true 
               
               
                   
                   else 
               
               
                   
                    tentative_is_better := false 
               
               
                   
                   if tentative_is_better = true 
               
               
                   
                    came_from[y] := x 
               
               
                   
                     g_score[y] := tentative_g_score 
               
               
                   
                    h_score[y] := heuristic_estimate_of_distance(y, goal) 
               
               
                   
                    f_score[y] := g_score[y] + h_score[y] 
               
               
                   
                    c_score[y] := c_cost(x,y)+c_score[x] 
               
               
                   
                    Update(openset,y) 
               
               
                   
                  return failure 
               
               
                   
                 function reconstruct_path(came_from, current_node) 
               
               
                   
                  if came_from[current_node] is set 
               
               
                   
                   p = reconstruct_path(came_from, came_from[current_node]) 
               
               
                   
                   return (p + current_node) 
               
               
                   
                  else 
               
               
                   
                   return current_node 
               
               
                   
                 function constrained_neighbor_nodes(x,c_score) 
               
               
                   
                  neighbor_set := empty set 
               
               
                   
                  foreach y in neighbor_nodes(x) 
               
               
                   
                    if c_score + c_cost(x,y)&lt;threshold 
               
               
                   
                     add y to neighbor_set 
               
               
                   
                  return neighbor_set 
               
               
                   
                 function heuristic_estimate_of_distance(y,goal) 
               
               
                   
                  return −1*(Euclidean distance between y and goal) *scaling_factor 
               
               
                   
                   
               
            
           
         
       
     
     At step  308 , the range projection is output to the display device  104 . In an embodiment, all nodes within a region are added to a list. For “reachable” nodes, the travel cost to reach these nodes is assigned to the nodes. For “unreachable” nodes, a high value which exceeds the maximum travel cost is assigned to the node. In an embodiment, the map is partitioned into Voronoi cells and only cells with travel costs less than the travel constraint are considered. Depending on the display purpose either a filled area is displayed or an exterior perimeter is displayed. In an embodiment, the perimeter curvature is filtered. In an embodiment, cells within the perimeter are colored according to travel costs. 
     In an embodiment, the range projection is output, by the system  100 , to the display device  104  at step  308  using the following sub-steps to mark (e.g., color) the cells according to travel costs:
         1. Let R be the set of all reachable nodes on the map from the origin when routes per one criteria are subject to a constraint criteria.   2. Let d_max be the maximum distance from the origin to a reachable node in R.   3. Let C be collection of points on the perimeter of a circle which has a radius greater then d_max by some positive epsilon — 1.   4. Let S be the set of all nodes within C.   5. Let c be the travel constraint cost associated with each node in R; if a node is not in R, then assign a value equal to the maximum travel constraint cost in R plus some positive epsilon — 2. Let c[n] indicate the constraint cost for node n.   6. Let V be the Voronoi cells defined by C+S. Let V[n] indicate the Voronoi cell associated with node n.   7. Let M be a color mapping which defines an RGBA value which spans the range of c. (Red, Green, Blue, and Alpha (transparency))   8. For each node in S: assign a color to the Voronoi cell using the color mapping: V[n].color:=M[c[n]]   9. Render the Voronoi cells onto a surface with coordinate which match node coordinates.   10. Filter this surface using a low pass filter to blend the RGB components.   11. Render the filtered surface onto a display with map information.       

       FIG. 4  is a sample output screen  400  produced by the system  100  in accordance with an exemplary embodiment. As shown in  FIG. 4 , there is a starting location node  402 , a first region  404 , a second region  406 , a third region  408 , and a fourth region  410 . In an embodiment, the first region  404  includes nodes having a first travel cost, the second region  406  includes nodes having a second travel cost that is greater than the first travel cost, the third region  408  includes nodes having a third travel cost that is greater than the second travel cost, and the fourth region  410  includes nodes having a fourth travel cost that is greater than the third travel cost. Though shown in black and white in  FIG. 4 , the display may be in color, with each color denoting a different travel constraint. Any manner of delineating the different travel costs may be used by embodiments when displaying the vehicle range projection. 
     One method to improve the execution time of the range projection is to use ‘step-gates’. A step-gate is implemented by first classifying all roads into categories. Generally, the more lanes or faster a road is, the higher its classification will be. Step-gate logic will only allow a node to consider routes which connect nodes to equal or higher classes of roads. This can be implemented by adding additional logic to the range projection logic  114 , where feasible neighboring nodes are only admitted when the based on the road classifications. 
     Technical effects include the ability to take into account both routing objectives and travel constraints when projecting a travel range for a vehicle. 
     As described above, the invention may be embodied in the form of computer implemented processes and apparatuses for practicing those processes. Embodiments of the invention may also be embodied in the form of computer program code containing instructions embodied in tangible media, such as floppy diskettes, CD-ROMs, hard drives, or any other computer readable storage medium, wherein, when the computer program code is loaded into and executed by a computer, the computer becomes an apparatus for practicing the invention. An embodiment of the invention can also be embodied in the form of computer program code, for example, whether stored in a storage medium, loaded into and/or executed by a computer, or transmitted over some transmission medium, such as over electrical wiring or cabling, through fiber optics, or via electromagnetic radiation, wherein, when the computer program code is loaded into and executed by a computer, the computer becomes an apparatus for practicing the invention. When implemented on a general-purpose microprocessor, the computer program code segments configure the microprocessor to create specific logic circuits. 
     While the invention has been described with reference to exemplary embodiments, it will be understood by those skilled in the art that various changes may be made and equivalents may be substituted for elements thereof without departing from the scope of the invention. In addition, many modifications may be made to adapt a particular situation or material to the teachings of the invention without departing from the essential scope thereof. Therefore, it is intended that the invention not be limited to the particular embodiments disclosed, but that the invention will include all embodiments falling within the scope of the present application.