Field of the Invention

The present invention relates to a method and device for predicting the range of a vehicle, for example, an electric motor vehicle.

Background of the Invention

With the advent of electric and hybrid vehicles, it is increasingly important for the driver of a vehicle to know how far it is possible to travel in the vehicle given the amount of energy left in the vehicle. The amount of energy remaining to power the vehicle will be a function of the amount of fuel and/or battery charge remaining in the vehicle. Conventional techniques use a standardised measure of energy consumption based on a test cycle known as a‘Reference Drive Cycle’ to define an expected range based on fuel (for combustion engines) or power consumption e.g. miles per gallon or miles per kWh of charge. For example, in Europe the NEDC (New European Driving Cycle) and more recently WLTP (Worldwide Harmonised Light Vehicle Test Procedure) drive cycles are used, while in the US, it is the Environmental protection agency (EPA) Federal test procedure that is used as a reference for fuel and energy consumption. Predicting the range using these measures isn’t very accurate, however, because the reference drive cycles make assumptions as the vehicle travelling at constant speeds or making predetermined speed changes considered typical of on-road driving. Thus, it doesn’t take into account real world driving conditions that may depend on the route being taken or other driving conditions and/or behaviours. Even taking into account past driving behaviour does not necessarily improve the accuracy because it is not a good predictor of future driving conditions which on which future driving behaviour is heavily dependent.

Alternatively, a route specific measure of range may be calculated based on predicting a target destination and corresponding route that a driver will take from a current location. In other words, the vehicle navigation system selects a probable destination based on a driving history. If the predicted route is correct, the measure of range may have reasonable accuracy. This is because it can take into account features of the route being travelled such as road speed limits, terrain (e.g. topology), and traffic when determining the range. However, due to the inherent difficulty and complexities of route prediction, the destination and/or route predicted by such a system will often be wrong and further it cannot easily predict new destinations or routes taken by a driver. If the route predicted is incorrect then the range prediction is likely to be highly inaccurate. In fact, it has been found that determining the range using such route prediction systems is often even less accurate than using a simple ‘Reference Drive Cycle’ based calculation. Further, route prediction algorithms are necessarily complex requiring significant processing by a navigation system. Of course, a user may merely specify a destination and route via a navigation system and the range be predicted from a specified route but this gives no improvement in range prediction accuracy when the route and/or destination is unspecified or to be determined.

Summary of the Invention

The present invention provides a method of predicting the range of a vehicle comprising: obtaining a plurality of distance values each corresponding to a distance of a route on a road network, each route being from a current location of a vehicle to a destination point determined to be in range of the vehicle; and determining a predicted range of the vehicle using the obtained distance values.

A surprisingly robust and accurate prediction of range can, thus, be made simply from using distance values of routes determined using conventional route prediction algorithms. Such route determinations are typical made by navigation systems in the process of generating a range plot (sometimes known as a‘spider plot’,‘range plot’, ‘range on map’, or‘spider graph’) having vertices that indicate destinations reachable by the vehicle from its present location given the amount of energy remaining. The distances to each destination point form a useful dataset from which to determine the range. For example, by determining a simple average of the distance values obtained, a good measure of range can be provided for very little additional computational overhead if the potential routes have already been determined. It is possible that some destination points indicate a point where a route or road on the road network terminates, and accordingly the vehicles energy would not be fully expended. Thus, in order to generate a meaningful average it is preferable that at least two distance values from those obtained correspond to destinations along a route of the road network at which a vehicle is predicted to have no remaining energy available.

The destination points may be determined for a range plot that provides a visual representation of the destinations within range of the vehicle on a route map. Accordingly, the range prediction calculation usefully repurposes data that is already being generated for the purpose of visually representing the range on a map image. This is particularly efficient as no additional or separate route detection is required to get the destination points and the distance data for each destination may be simply provided and processed to generate the range prediction value.

Additionally, the method may include generating a request to a vehicle navigation system for the plurality of distance values and receiving the plurality of distance values from the system. Many vehicles incorporate satellite navigation systems that have route map data and algorithms for generating route data. Accordingly, it is an efficient use of resources to request such a navigation system to generate the distance values for the range prediction.

Generating the request may include sending at least one of: location data indicating a current vehicle position, energy data indicating remaining amount of energy, and energy usage and/or efficiency data associated with the vehicle.

The energy usage and efficiency data may be generated at the time of or immediately prior to making the request. Alternatively, the data may be pre-recorded and stored in a memory for retrieval when needed. In embodiments, the navigation system is hosted on a remote server and the request is transmitted to the remote server and the distances are received from the navigation system in a data transmission from the remote server.

In embodiments, each destination point is determined based on a current position of the vehicle, a road network map, and an available amount of energy of the vehicle, and takes into account one or more of ¾ Vehicle efficiency data, ¾ Terrain data (e.g. topology), iu) regenerative braking data, _*9 road speed data, Ό Live traffic data, vi) weather data, and vii) auxiliary systems usage data. Accordingly, possible destinations may be accurately determined

Optionally, in determining the destination points, a digital road map around a current location of the vehicle is partitioned into regions and a driving route is determined for a predicted destination in one or more of the regions. The regions may be radial sectors of the route map formed around the current vehicle location which provides a simple and effective way to partition the map.

A direction of travel of the vehicle may be determined and the direction used to determine how the obtained distances are used in determining the predicted range.

For example, at least one of a duration of time travelled in a direction and a distance travelled in a particular direction may be used in determining how the obtained distances are used in determining the predicted range. For example, if it is determined that the vehicle is travelling in a particular direction (or road) for at least a predetermined amount of time then that might indicate that they intend to continue in that direction. Accordingly destinations that are within regions in an angular range about that direction are more likely to be the target destination of the driver. Accordingly, distances associated with those regions can be more heavily weighted and destinations outside that range may be omitted or have their weighting reduced. Alternatively or additionally a vehicle driving history may be used to determine how the obtained distances are used in determining the predicted range. Thus, if the driving history indicates that some routes are used frequently or infrequently that information can be used to determine how distance values associated with such routes or destinations is used in determining the predicted range. For example, distances associated with infrequently used routes may be given a low weighting or omitted altogether from the calculation. The vehicle driving history may be associated to a driver profile, thus a bespoke driving history can be used that more accurately reflects the probability of taking certain routes resulting in better use of the obtained destination values in making the range prediction.

Alternatively or additionally terrain information (e.g. including the topology or geography of a region) may be used to determine how the obtained distances are used in determining the predicted range. For example, where there is a mountainous region, coast, or region with water features such as lakes or rivers the use of destination points about those features may be adapted. For example, destinations near a coastal region may be indicative of an early termination of a route without expending all the energy of the vehicle and the weighting or use of those values adjusted accordingly. Destinations in a mountainous or hilly region may be less likely to be taken by the driver and accordingly the weighting of distances associated with those destinations may be reduced or those values omitted altogether on the grounds that they are unrepresentative.

As mentioned, determining how the obtained distances are used based on the above factors may comprises at least one of applying a weighting to one or more obtained distances and determining which of the obtained distances are used in determining the range prediction. Various examples of how this might advantageously be done in practice are already mentioned above.

Alternatively or additionally, one or more distance values that are determined to be below a threshold value are omitted from consideration altogether when determining the average distance value. This allows obviously invalid or unrepresentative distance values to be excluded from the range prediction determination to avoid the result being skewed by erroneous or unrepresentative values. Such distances may correspond, for example, to a route that terminates at a dead end before all the energy of the vehicle is consumed or correspond to null values obtained for region of the map where there are no roads.

Obtaining the distance values may comprise sending a request to an off-vehicle navigation data server and receiving the distances in a wireless data transmission from the off-vehicle navigation data server sent in response to the request. This is advantageous in that it permits the computationally intensive task of multiple parallel route calculations to be performed remotely by a conventional navigation data provider and the resulting range prediction calculation performed on-board the vehicle. Alternatively, both the determination of the distance values and the range prediction value may be performed remotely and the range value alone transmitted to the vehicle.

In an advantageous embodiment, the distance values are repeatedly obtained and the predicted range repeatedly calculated, for example, while the vehicle is in motion. This allows the range prediction to be updated in accordance with up-to-date information on the location, and other properties of the vehicle.

In an embodiment, the frequency of which the distances are obtained and the predicted range calculated depends on the amount of energy remaining. For example, if the amount of energy available drops below a threshold then the frequency may be increased. The reason is that the exact range available becomes more critical as the energy in the vehicle is depleted. This is in some sense counterintuitive, and thus surprisingly advantageous, because calculating the predicted range more frequently uses more energy. However, the present inventors have recognised that the additional spend of energy is relatively small and disproportionately worthwhile in giving the driver an accurate read on the range remaining at the most critical moments. This should allow them to safely reach a charge point (or refuel) before the vehicle is empty of energy without the risk of overestimating the range due an inaccurate estimate of the range.

Using the distance values to determine the predicted range of the vehicle may comprise determining an average of the obtained distance values. The average may be calculated by calculating an arithmetic mean, median or mode of the set of obtained distance values. Taking a simple average of the distance values gives an accurate range estimate with very little processing required of the obtained distance values.

Further, a distribution (e.g. a histogram) of the distance values may be obtained and the predicted range determined based on features of the distribution. This is advantageous because it allows the statistics of the distribution to be taken into account in calculating the average thereby providing a potentially more accurate range prediction than a simple arithmetic averaging operation. For example, end values further than a predetermined distance from a centre value or peak value of the distribution may be excluded, on the basis that these are outliers and not likely to provide useful range data. Additionally, a distance value corresponding to a peak in the distribution may be taken as or used as the basis for the predicted range. In instances where the distribution has multiple peaks these may be identified and the predicted range based on an average of values corresponding to those peaks in the distribution. This can occur when the environment around the vehicle differs depending on the direction travelled by the vehicle resulting in two peaks in the distribution. Thus, a better representative value for the predicted range can be obtained by looking at the values at both peaks and, for example, taking an arithmetic average of the peak values.

Alternatively, the distance values can be used to determine the predicted range by determining respective energy consumption rates corresponding to the obtained distances; using the energy consumption rates to determine a representative energy consumption rate; and determining the predicted range using the representative energy consumption rate and the energy available to the vehicle. This is advantageous because it means that distance values that correspond to destinations which result in the car battery (or fuel tank) not being completely emptied can still be taken into account and provide information to refine the determination of the predicted range of the vehicle. Thus, it is more likely that a large set of distance values can be used in the determination resulting in a better prediction of the range. For example, determining the representative energy consumption rate may comprise determining an average from the obtained energy consumption rates. The average is one an arithmetic mean, median or mode of the obtained set of energy consumption rates.

Alternatively, the representative energy consumption rate may be determined based on features of a distribution (e.g. histogram) generated from the obtained energy consumption rates (in a similar manner to the distribution of distance values mentioned above). Optionally, energy consumption rate values further than a predetermined distance from a central value or a peak value of the distribution are excluded from consideration in determining the representative energy consumption rate. The representative energy consumption rate may be based on an energy consumption rate that corresponds to a peak in the distribution. Where multiple peaks are identified in the distribution, the determined representative energy consumption rate may be based on an average of energy consumption rate values corresponding to those peaks

In embodiments, a weighting to be applied to one or more of the energy consumption rates that correspond to the obtained distances is determined based on one or more of the factors already mentioned above in relation to how the distance values may be used. In other embodiments, which of the obtained energy consumption rates are used in determining the predicted range is determined based on one or more of the factors mentioned above already in relation to the distance values. The weightings and/or selective use of the determined energy consumption rates allow further refinement of the values such that a better prediction can be made.

The method may further comprise selecting a target destination; determining a route to the target destination; calculating the energy remaining to the vehicle at the target destination; and calculating a total predicted range a sum of the range predicted using the plurality of distance values and the route distance to the target destination , wherein the plurality of distance values obtained each correspond to a distance from the target destination of the vehicle to a further destination point determined as being in range of the vehicle given the energy remaining at the target destination. This is advantageous because it allows the full predicted range of the vehicle to be more accurately determined when an initial target destination is known and has been selected e.g. by a user indicating that they wish to navigate there using the vehicle navigation system.

In another aspect of the invention, there is provided a computer program which upon execution causes a method according to any preceding claim to be performed. The computer program may comprise processor executable instructions and be provided on a carrier that is transitory or a non-transitory computer (or other machine) readable medium. For example, the computer program may be executable by a control unit in a motor vehicle, said control unit having a processor and a memory.

In a further aspect of the invention, there is provided a device configured to perform the method according to any of the aspects set out above. In another aspect there is provided a device comprising one or more processors and a memory, the memory storing processor executable code which upon execution by the one or more processors causes a method as set out in any of the above mentioned aspects or embodiments to be performed.

In yet another aspect of the invention there is provided a motor vehicle comprising such a device. The motor vehicle may be an electric vehicle (EV) or plug-in hybrid electric vehicle (PHEV) and the amount of energy available to the vehicle is based on an amount of charge remaining in the vehicle battery. Additionally, the motor vehicle may be a passenger vehicle.

In a further aspect of the invention there is provided a vehicle navigation system comprising: a vehicle navigation device including wireless communication means operable to generate a data transmission via a network, said transmission comprising a request for a range prediction value; and a server arranged to, upon receipt of the request, perform a method according to any of the above mentioned aspects and embodiments, and to transmit, via the network, to the vehicle navigation device the predicted range.

In a yet further aspect of the invention, there is provided a vehicle navigation system comprising a vehicle navigation device including wireless communication means operable to generate a data transmission on a network comprising a request for route data from a server; and a server arranged to, upon receipt of the request, obtain and send to the vehicle route data via the network including a plurality of distance values each corresponding to a distance from a current location of a vehicle to a destination point, each distance being a distance along a route of a road network to a respective destination determined to be in range of the vehicle, wherein the vehicle navigation device is operable to receive, via the network, data including the plurality of distance values and determine a predicted range of the vehicle using the received distance values.

Brief Description of the Drawings

In order that the present invention may be more readily understood, embodiments of the invention will now be described, by way of example, with reference to the accompanying drawings, in which:

Figure 1 is an illustration of a vehicle with a navigation system;

Figure 2 is a block diagram showing components of a range prediction device;

Figure 3 is a flow chart showing a method for predicting the range of the vehicle using destination points;

Figure 4 is a flow chart showing a method for determining possible routes; Figures 5a and 5b show a route map partitioned to determine destination points and a resulting range diagram from determined destination points;

Figure 6 shows a distribution of distance values used to determine a predicted range value for a vehicle;

Figures 7a, 7b, 7c and 7d show example route maps with terrain for which distance values may be weighted or omitted;

Figure 8a shows a route map where a corresponding energy consumption rate is determined for each radial sector;

Figure 8b shows a flowchart in which energy consumption rates based on distances to predicted destinations are used in determining the predicted range;

Figures 9a and 9b show the radial partitioning of a route map when the energy remaining is above and below a threshold value respectively; and

Figure 10 is a block diagram of a range prediction system according to a further embodiment, the system including a vehicle and remote server in communication with the vehicle.

Detailed Description of the Invention

A motor vehicle 1 is shown in Figure 1 having a navigation system 2 in communication with a GNSS satellite system 3 via a transceiver 4. The GNSS (Global Navigation Satellite System) includes GLONASS, Galileo, Beidou and other satellite systems including the American GPS system. The transceiver 4 sends and receives location data from the GNSS system 3 which returns latitude, longitude, altitude and time data that is usable by the navigation system to determine when the vehicle is located in a digital route map. The vehicle has a battery pack 5 and a circuit (not shown) for measuring the remaining charge in the vehicle battery that is available. In addition, the transceiver 4 is in communication with a communications network 6 (e.g. the internet) that is in turn in communication with a data centre 7. The data centre may provide navigation data such as route information, weather data, or traffic data in response to requests received from the vehicle navigation system 2 via the transceiver 4 and communications network 6. In other words, the vehicle shown is a connected vehicle. A block diagram showing components of the navigation system 2 is shown in Figure 2.

The navigation system 2 includes a navigation data module 201 which stores data used for navigation functions performed by a processing unit 200. The processing unit 200 may receive input from, the navigation data module 201, a user interface 202 and a GNSS unit 203 that provides location data 203 a indicating the current coordinates of the vehicle in latitude and longitude (for example) as determined by the GNSS system. Control of what data a user wishes the system to generate and display may be provided via the user interface 202 by user input and resulting control data (not shown) sent to instruct the processing unit. In addition, the output of the processing unit 200 may be provided to a display 204 which is capable of displaying a visual representation of the route data e.g. as an overlay on a digital route map.

A vehicle efficiency database 206 is provided that stores and provides historical efficiency data 206a for the vehicle showing, for example, the average miles per kilowatt hour for the vehicle. Such data can provide a useful starting point as an estimate of the range of the vehicle that is arguably superior to using manufacturer specifications based on a reference drive cycle because it is based on real energy usage.

Further, a driver profile database 208 is provided that includes data relating to usage of the vehicle by different drivers. Such information may include, average energy consumption from usage of auxiliary systems such as air conditioning or infotainment that impact the overall energy consumption of the vehicle. Additionally, profile information might include historical data on preferred routes taken by a particular driver. For example, if a driver profile indicates that the driver is more likely to prefer travelling on motorway routes or A-roads than back roads and the route prediction algorithm may choose routes that reflect this.

In addition, an auxiliary systems module 211 is provided that monitors the HVAC and other energy consuming auxiliary systems of the vehicle. For example, the current or recent use of air conditioning, lighting, communications, infotainment or other electrical systems or vehicle functions that consume energy. The auxiliary systems module 211 outputs auxiliary data 211a which is data giving a snapshot of the auxiliary systems usage that can be used by the route determination unit.

The navigation data module 201 includes a road network database 207 and a traffic module 209. The road network database 207 stores a digital road map of the route network that includes speed limits and historical road speeds for roads and topological information. This route data 207a may be provided to the route determination unit 205. Finally, a traffic module 209 is provided that provides live or historical traffic data 209a to the route determination unit 205 for roads on the road network. If live traffic information is required this may be obtained wirelessly over the communications network 6 via transceiver 4 (not shown) from any live traffic data feed.

The processing unit 200 includes a route determination unit 205 which is capable of determining possible routes that can be taken by the vehicle from its current location to respective destination points on the road network. Each determined route to a destination point defines a distance that the vehicle can travel before running out of energy (i.e. battery charge). The route determination unit 205 receives the location of the vehicle from the GNSS module 203 as location data 203a and a route map with details of the road network as map data 206a from the road network database (storage means) 206 in the navigation data module 201. It is also capable of receiving the efficiency data 206a, route data 207a, behaviour data 208a, and traffic data 209a. This data is used in determining the possible routes to destinations that empty the remaining charge in the vehicle by simulating the energy consumption of the vehicle. The route determination unit 205 provides route data 205a, which includes a set of distance values corresponding to the destination points determined, to the range prediction unit 210.

The range prediction unit 210 is operable to utilise the distance values to generate a prediction of the range remaining in the vehicle for the given charge remaining in the vehicles battery. The range prediction unit 210 provides display data 210a to the navigation system display 210, the display data includes date for a visualisation of the destination points and the value of the predicted range. For example, the destination points may be visualised by the display as a range-on-map plot and the predicted range value displayed either separately or in an overlay on the navigation system display. Other ways of visualising the data are also possible, as will be appreciated by those skilled in the art of navigation display systems.

A process of determining a range prediction value will now be described with reference to Figure 3 which shows method steps performed by the processing unit 200 of the navigation device 2 in determining the vehicle range. The process begins with obtaining at S301 with obtaining the vehicle’s current location. This may be performed using the GNSS module 203 and the location data 203a may comprise latitude and longitude values or other position data capable of locating the vehicle. The remaining charge is then obtained from the vehicle control systems (S302). The remaining charge may be monitored, for example, by a vehicle control unit of the vehicle connected to the powertrain (not shown). At step S303, the route determination unit 205 determines possible destinations based on the vehicles current location and remaining charge. Once these possible destinations are determined the distances to each destination on the road network are obtained (S304) which are to be used in the range prediction. At S305 those distances are used to determine a range prediction value, for example, by calculating an average of the obtained values. This process will be explained in more detail together with the destination determination at S303 below. Finally, at S306, a check is performed to see if the predicted range R _pr ed should be refreshed or recalculated. For example, it might be that this is recalculated regularly at predetermined time intervals or only upon request by a user via the user input device 202

Determination of possible destinations

The process at S303 will now be explained in more detail with reference to Figures 4, 5a and 5b. In a first step S401 a simple reference measure R _ref of expected range is determined in accordance with a reference drive cycle and the remaining charge in the vehicle (obtained in S302). As explained above this range value is likely to be inaccurate as it is based on average road conditions and speed of a vehicle. Often the reference drive cycle for a vehicle is reported by a vehicle manufacturer and this value can be used to determine R _ref . If it were to be assumed that the vehicle were to travel along typical terrain radially outward in a straight line from its current location then all possible destinations would be indicated by a circle with radius R _ref with the current vehicle location at the centre. In practice, of course, vehicles are bound to follow existing roads in a road network. To this end, at step S402, a digital map of the road network is partitioned into radial segments with the vehicle at the centre. This is shown in Figure 5a where the road map about the circle 501 having radius R _ref is partitioned in 12 radial segments (or sectors) 502 each of equal angle Q, where in this embodiment Q = 30 degrees.

In this embodiment, the radial sectors are evenly spaced around 360 degrees but this is not essential and other angular separations could be used. Starting with a first radial sector n a predicted destination point D _n is determined at the distance R _ref that coincides with a point on the road network. In effect each sector can be swept through its angular range until a suitable point is found. Where more than one suitable point is found, various criteria might be used to determine which one to use. In the simplest case the first such point found is used. In the event that there is no point coincident with the road network at the distance R _ref , that sector can either be omitted and no destination point calculated or the distance R _ref incrementally decreased or increase until a coincident point is found on the road network to use as a predicted destination point D _n . In this embodiment, if a point on the road network can still not be found then that sector may be marked as void or invalid and no distance value is returned.

A route to the destination point D _n is then determined at S404. This may be performed using known pathfmding algorithms in the art and the digital route map. Such a route could be obtained to take into account various criteria (shortest distance, most use of motorways/highways, quickest route etc).

As the actual distance along the road network to the selected point will be greater than the distance R _ref as the crow flies (because of the requirement to stick to the road network) then the car will be unlikely to reach the destination point D _n. Accordingly, therefore, we simulate travelling along the route to reach the point at the distance R _ref in order to make a determination of where the car will actually run out of charge on the route to destination point D _n. In other words the distance along the road network travelling to D _n at which the vehicle runs out of charge. In the event that the car has not run out of energy by that point, then the car is assumed to continue along the current road until the energy is consumed. This may be possible for example, where the actual route is downhill, on energy efficient roads follows a straight line to the destination or has otherwise favourable properties for energy efficient driving.

In step S405 the route on the road network is segmented by into k straight line segments ki-k _n. For example, in Figure 5a the route 503 is divided into five linear segments ki-ks. Next in S406, the energy requirement for each segment and the determined route is calculated. For example, the total energy consumed (i.e. work performed) in following a route consisting of N linear road segments might be calculated using the following relationship:

Where Fx(k) is the tractive force load for segment k, S _k is the length of a road segment k. The term W _aux (k) represents energy losses due to use of auxiliary systems in the vehicle and other energy losses in traversing the road segment k. This might be based on the average use of such systems according to a driver profile data or vehicle efficiency data. Such auxiliary systems might include air conditioning, lighting, or infotainment. In addition, energy recovered via regenerative braking effects might also be taken into account with this term.

The tractive force FT can be calculated a weighted sum of at least the following terms:

F _T = F _R + F _H + F _A + G

Where FR is rolling resistance force, FH is a component associated with climbing a gradient (i.e. hill), FA is aerodynamic drag and G is a term representing all other forces e.g. driver dependent effects such as acceleration and deceleration. The FR, FH, and FA components will be a function of the vehicle and the road properties which can be derived from the route data and vehicle efficiency data. The catch-all force term G may be influenced by driver behaviours according to a driver profile and/or traffic on the road as per the traffic data.

The energy requirements calculated for the road segments can then be used to determine how far on the route the vehicle may travel before the vehicles energy is expended. This waypoint of the road segment at which the energy would be expended is the actual destination point reachable by the vehicle and the distance d _n to that point is the sum of the distance of the road segments to that location.

In the next step S408, it is determined if this is the last radial sector to be considered i.e. if n<N. If the answer is ‘no’ then the process passed to step S409 where n is incremented by one so as to move on to the next radial sector and then the steps S403 to S408 are repeated. If the answer is‘yes’ then the process is complete and a set of distance values each representing a distance driven along the road network at which the amount of charge left in the vehicle is zero, is passed as an output and the process continues at S305. For example, the output values may be tabulated as follows

*If the battery charge is greater than 0% at this distance it should be flagged as invalid e.g. a dead end road

** If there are no roads in a segment it should be flagged as invalid i.e. as having no data. We are only interest in drivable routes that resulted in the battery reaching 0%, anything else should be flagged as invalid. Computationally, this could be represented by -1 or null.

The tabulated values may be visualised on a display as a bounded area 504 as shown in Figure 5b. This is a so-called spider graph or range on map plot in which the‘Distance to empty’ values are vertices of the plot. Providing such a visualisation as an overlay on a map displayed by a vehicle navigation system gives an occupant of the vehicle an easy and quick visual indication of which destinations might be in range of the vehicle. However, such a display is optional in the case of the present embodiment. As will be explained below, what is important here is how the distance to empty values are utilised in generated the predicted range. Nevertheless, as can be seen, where the destination points and distances have already been calculated by a navigation system for the purpose of generating such a spider graph or range plot, then the present invention provides a useful way to use that data to additionally provide a reasonable prediction of the range of the vehicle until it is empty of charge (or fuel). The above model is purely exemplary and it will be understood that any other simulation model for energy consumption known to those skilled in the art might be used which takes into account the properties of a particular road segment and the vehicle characteristics. To be clear, the present invention is not predicated upon the use of any particular routing algorithm. Similar algorithms are known for use in generating conventional range or spider diagrams, for example. As will be explained below the present invention is instead concerned with how the destination data is used subsequent to its determination. For example, in an embodiment an average is taken of the distances associated with each of the destinations determined according to the route prediction algorithm. Of course the better the route prediction and energy consumption simulation is then the better result will be achieved by the presently described method. However, the advantages of a better range prediction will be obtained with any conventional route prediction algorithm that can determine possible routes and distance along those routes to empty or to route termination. For example, if enough computational resource is available to the navigation system, then a brute force technique may be used to evaluate each and every route from the cars current position to find a destination in each radial sector. For example, if the route determination were to be performed off-car in the cloud or by another connected remote resource then such a brute force technique might be preferred as the system would not be limited the processing power of the vehicle.

Range prediction determination

The step S305 in Figure 3 of determining a range prediction value R _pred using the obtained distances di-d _n will now be described in more detail according to various embodiments.

In a simple embodiment, an arithmetic mean is taken of the obtained distances values giving a simple and efficient measure of predicted range. Other arithmetic operations may be performed on the set of distances i.e. the median or the mode. In calculating the average, values from the set of distances that are considered to be invalid values for the purpose of predicting the range of the vehicle may be removed from the set and thereby omitted from the calculation.

In another embodiment, a histogram is constructed from the obtained distances and the histogram processed in order to determine a suitable prediction value representative of an average or likely range.

This is shown qualitatively in Figure 6a where the distribution approximates a bell or Gaussian curve 601. The bin sizes for the distances on the x-axis may be configured according to the number of distances obtained in order to construct a meaningful distribution. The distance value of the bin corresponding to a peak in the histogram can be used as indicative of an average value of the distance achievable by the vehicle until the charge in the battery is expended. Where the bin contains a range of distances the value corresponding to the midpoint of the range of distances may be used, or alternatively the value at the beginning or end of the range. That value is then used as a prediction of the range remaining. In more complex distributions such as that shown in Figure 6b multiple peaks 602, 603 may be derived from the histogram. In that case, values corresponding to more than one peak in the distribution may be used to determine the range prediction value. For example, an average such as the arithmetic mean of distance values corresponding to the peaks in the distributions may be determined and that value used as the predicted range of the vehicle.

In another embodiment a weighted average of the distance values is calculated.

, where w _n is a weighting coefficient for the i-th region, and d _n is the distance to the destination point determined possible for that region at which the vehicle battery is predicted to reach 0% charge. The distance values may be weighted in accordance with various factors relating to the route they represent that may make that distance more or less relevant. Various examples of scenarios in which the obtained distances might be weighted or omitted are considered in Figures 7a to 7d, described below.

Figure 7a shows an example, in which terrain to one side of the vehicle is impassable and no roads exist. Specifically, in the example shown, the vehicle is travelling on a coastal road such that the area to the East of the vehicle 701 in sectors 2 to 6 consist almost entirely of ocean and no roads. These sectors are, thus, rendered invalid and no distance values returned. This may be done, for example, by associating a weighting coefficient of zero to those sectors or by flagging them as invalid such that no distance is calculated. In one embodiment, in order to maintain the resolution of the range prediction calculation the remaining valid radial sectors may be further subdivided and a distance value determined and returned for each. Thus, the number of distance points and accuracy of the calculation may be maintained within the bounds of the expected computational burden.

Figure 7b shows an example whereby the vehicle is surrounded by differing types of terrain. Specifically, there is a passable rural but mountainous region 702 to the North, a largely urban region 703 to the South and transitional regions 704a, 704b the East and West. The distance values obtained for the destinations in the mountainous region 702 (sectors 12, 1, 2 and 3) may be weighted lower with weighting value Wi to reduce their influence on the average. This would be on the basis of an underlying assumption that it is more likely that the driver will be driving away from such terrain that towards it. Accordingly, distances to destination points in those regions should be less influential to the average calculated. Alternatively, those distances can be omitted altogether, and an arithmetic mean or other average calculated from the remaining values. Similarly, the urban region might be weighted highly in sectors 5 to 9 by weighting value W3. This would represent an underlying assumption that the likelihood of the driver wanting to drive in the city is high. The transitional regions 704a, 704b in sectors 4 and 10 might be weighted somewhere between the two extremes with weighting value W2 as they have a mix of terrain types. The weighting applied might be predetermined based on terrain type or it might be adapted based on short or long term historical driver behaviour, e.g. based on a driver profile. For example, if the driver behaviour indicates that the driver typically avoids urban driving and frequently drives cross country through mountainous regions then the conventional weighting assumptions might be reversed. Other factors than the terrain that affect route choice may be applied when determining appropriate weightings.

Alternatively or additionally, the scheme of Figure 7c may also be applied. The area surrounding the vehicle is the same as in Figure 7b; however, in this example the angular portioning of the sectors about the vehicle for which distance values are calculated is adapted based on the terrain. For example, for the rural and mountainous region to the north, it is assumed that this is an unlikely destination so the angular size of the partitions in this region is increase such that only two radial sectors 1 and 2 are provided. The angular size for the urban regions (i.e. sectors 4 to 13) is substantially smaller so that more distances are captured for this area. This is based on the underlying assumption that urban driving is more likely and thus to get an improved accuracy for the distance more distances in the urban region should be captured than for the mountainous region. The size of the partitioning for the transitional regions (i.e. sectors 3 and 14) is somewhere between the two. As with the weighting values, the underlying assumptions on which the portioning is based can be predetermined or based on driving behaviours or histories, e.g. those stored or updated with a driver profile. The underlying assumptions could be reversed such that the driver behaviours indicate that cross country driving is more likely than urban driving in which case the portioning sizes for the mountainous and urban areas would effectively be reversed.

A combination of weightings and adaptive portioning may be used in order to further improve the accuracy of the range prediction. The partitioning and weightings may advantageously be adapted on the fly as the vehicle moves such that an optimal set of distance values is obtained for each range prediction.

Figure 7d shows another example, in which the directivity of the vehicle is used to weight and/or omit from consideration the data points used. In the example, shown the vehicle has travelled from point A to its current location at point B to the north along road 705. Thus, an underlying assumption is made that the vehicle is more likely than not to continue travelling in this direction. Based on that assumption, the radial sectors 5 to 8 are designated as being unlikely destinations. Accordingly, the distance values obtained for those radial sectors may be weighted lowly or omitted altogether. Alternatively or additionally, the sectors 5 to 8 may be adapted such that they are consolidated into fewer sectors and accordingly fewer distance values are determined for this region of the map. Conversely, the weighting and/or number of distance values obtained may be increased in the direction in which the vehicle is travelling. For example, sectors 1 and 2 can be heavily weighted and/or adapted such that they are subdivided into further radial sectors to reflect their increased importance to the range prediction.

Other weighting schemes are possible to those mentioned above. For example, the points may be weighted according to how often the driver has frequented a particular route, road, or destination in the past (based on a driver profile, for example).

Range prediction based on energy consumption rate

In the above embodiments, the range is derived directly from analysis of the distance values to empty for a number of predicted destinations. However, this has the disadvantage that where a particular destination is where a road terminates and the vehicle still has some energy remaining, the distance is discarded from the analysis. This can be disadvantageous because there are situations where this would result in too few distance values being available for an accurate measure of range to be made purely from the distance to empty values. For example, consider the situation where the vehicle is on an island and the vehicle is fully charged. This could result no route from the vehicle in any of the radial sectors resulting the vehicle being empty of charge. Thus, if these distances were to be discarded then it would not be possible to calculate a range prediction value according to the method of the above embodiments. Further, consider also the case where the vehicle is near to the coast. If the driver actually intends to drive in the direction of the coast in a sector where the route distance has been declared invalid the accuracy of the range result could be reduced. Specifically, the accuracy could be less because we are ignoring the data from the roads and terrain where the driver would actually like to travel and instead basing it on an analysis solely of routes not of interest to the driver. This is particularly exacerbated if the vehicle has only a short range due to lack of remaining charge. Accordingly, it would be advantageous if the distance data from routes that do not result in emptying the charge could also be taken into account.

This can be achieved if the analysis is modified so that each distance value is used to generate a corresponding measure of energy usage per distance unit e.g. kW/km. The resulting energy consumption rates are then utilised to generate the predicted range. In particular, a single representative energy consumption rate is determined and multiplied by the remaining charge to generate a distance value that can be used as the predicted range.

An example of a situation where this embodiment is of particular use is shown in Figure 8a. In this simplified example, there are 8 radial sectors as numerically labelled. A coastal region to the East of the vehicle is depicted in sectors 1 to 3. The distances to the labelled destination points D1 to D3 will not result in the vehicle battery being fully discharged upon reaching the predicted destination. Sectors 4-5 and 7-8 have routes to destinations which will fully expend the charge remaining in the battery. Sector 6 is impassable due to a mountainous region having no roads. An alternative method for predicting the range, by using the distance values to generate corresponding energy consumption rates, will now be described with reference to the steps of the flowchart shown in Figure 8b.

In a first step S801, having determined the distance travelled along a route to a predicted destination, we estimate the amount of energy remaining in the battery at the destination point. This is done for each sector so that there is a respective energy remaining value determined corresponding to each distance. Then in step S802, having determined an estimate of the energy in kWh remaining in the battery corresponding to each distance value (i.e. by following the route to the predicted destination) it is possible to calculate an energy consumption rate kWh/km for each distance value (i.e. each radial sector). In particular, the following formula may be used: EC = (SE-RE)/DT where EC is the energy consumption rate in kWh/km, SE is the starting energy contained in the vehicle battery in kWh, DT is the distance travelled in km to the predicted destination, and RE is the predicted remaining energy in kWh after the vehicle has travelled to a respective destination.

The estimated energy remaining RE can be determined in S801 from the simulation method already mentioned above or other method that can estimate the energy consumption when driving along particular road segments taking into account the vehicle and road characteristics. Using the above formula we can calculate an estimated energy consumption rate kWh/km for each sector (S802). For example, if we assume SE = 40 kWh then for radial sector 4 the energy consumption rate is given by (40- 0)/l 54 = 0.26 kWh/km. For radial sector 1, where only some of the starting energy is consumed by completing the route to the predicted destination Dl, the calculation is (40-20.1)/71 = 0.28 kWh/km. Radial sector 6 is invalid due to the mountain and no roads and thus returns a null value and cannot be used to predict the range. Tabulating the results for the example shown in Figure 8a gives the following:

To get the predicted range we determine a representative energy consumption rate in kWh/km (S803). The representative value can be calculated as a simple arithmetic average of the energy consumption rates for the different sectors. To determine the predicted range we can simply multiply that representative rate by the starting energy in the battery (S804). In other words:

PR SE/AC

Where PR is predicted range in km, AC is average (or more generally, representative) consumption rate, and SE is starting energy. For example, if a simple mean of the energy consumption rates is calculated then AC= (0.28+0.3+0.23+0.26+0.25+0.27+0.284)/7 = kWh/km and thus the predicted range PR = SE/AC = 40 /0.268= 149.3km

The representative consumption rate AC may be determined from the energy consumption rates determined for the radial sectors using any of the methods already mentioned above (either alone or in combination) where the distance values are used to predict the range directly. For example, a histogram may be constructed but the bins will be for the energy consumption rate EC in kWh/km rather than distance values DT in km and the peaks in the distribution used to determine a representative average energy consumption rate AC in kWh/km for the vehicle as currently located. The representative value could be based on one or more peak energy consumption rates identified in the histogram, for example.

Predicted range when a target destination is pre-selected

One situation that may arise is when a user selects via the navigation system (e.g. user input device 202) a particular target destination that the user wishes to navigate to. The navigation system will determine a best route by conventional methods. It is then possible to determine how much charge will be used to reach that destination by simulating the energy consumption along the route to the selected destination. The distance to the target destination will also be known. However, this only gives a prediction of the remaining charge in the battery, rather than a total predicted range from the current location taking into account the distance to the known target destination. In such a case, any of the already described methods above that use a plurality of distance values for possible routes to predict the range may be performed taking into account the target destination. This is done by taking the remaining charge at the target destination as the starting point for performing the range calculation as per the above methods. In other words, the already described methods as per Figure 3, are performed by using the target destination as the initial‘vehicle location’ obtained in S301 and the calculated remaining charge upon reaching the target destination as the value for the‘remaining charge’ obtained in S302. The above processes will generate a number of further possible destinations (S303) that can be travelled from the target destination and corresponding distances (S304). A predicted range from the target destination may therefore be calculated by the above methods using those distances (S305). The total predicted range of the vehicle will be the sum of the distance to the selected target destination and the predicted range calculated based on the remaining charge upon reaching the target. Thus, an accurate total predicted range can be calculated.

Dynamic range prediction accuracy adjustment

In an embodiment, the resolution i.e. number of distances and/or frequency at which the distances are obtained is adapted based upon the amount of charge remaining in the battery. The present inventors have recognised that it is actually preferable to increase the accuracy of the range prediction calculation when the amount of energy remaining is low. In other words, as the amount of energy available decreases the accuracy of the prediction should increase. This may be considered counter-intuitive because in order to improve the accuracy the number of distance calculations or the frequency of their calculation increases which is computationally more intensive. That additional computational burden of course is detrimental to the power consumption causing the battery charge to be consumed more rapidly than it otherwise might. Nevertheless, the benefit of more accurate range prediction at the moment when the vehicle might need to be taken to a charging station has been found to outweigh the relatively modest increase in energy consumption from the additional processing burden.

Figures 9a and 9b show an example of this principle. In figure 9a the amount of energy remaining in the battery is greater than a threshold value ET and in figure 9b the amount of energy is less than the threshold ET. AS shown in the Figure 8b the number of radial sectors is doubled such that each extends through an angle of 15 degrees. Accordingly, double the distance values may be calculated and a more refined average value calculated for the range prediction.

In other embodiments, additionally or alternatively, the frequency at which the distance values are obtained is increased when the amount of energy stored in the battery falls below the threshold value ET. For example, the frequency at which the values are obtained may be once every 20 seconds above the threshold and increase to once every five seconds when below the threshold. Other time values are of course possible and can be fine-tuned to the particular energy and computational requirements of the navigation system and vehicle.

In a further embodiment, the process operates with a second threshold E _T 2 representing a critical level below which the range prediction processing is ceased in order to save energy. The principle applied is that it is useful to have high accuracy when the battery is low but below a certain level of remaining range the range prediction value will cease to be meaningful. For example, the range prediction may only have an accuracy of less than a few kilometres and accordingly if the amount of energy remaining indicates a range of only km remaining then there is no useful purpose is continuing to expend energy to estimate it. Accordingly, if the energy level is so low that it would be unable to travel further than a few km then the range prediction updates should cease and the last calculated value presented or a warning that the range is less than one kilometre presented. In that way, crucial energy is not wasted in refreshing the range prediction which might be better used in getting the vehicle to a suitable charging point or destination. Alternatively, rather than cease altogether, the distance values are obtained with a frequency that is less than when the energy remaining is above the threshold. Thus, the energy consumption is reduced but a range prediction value is still regularly updated albeit with a relatively long up-date period.

In another embodiment, rather than hard edged thresholds, the frequency and/or resolution of the angular sectors may be incrementally increased as the charge in the battery decreases. Optionally, this is done until the charge level reaches the second threshold and behaves as described above thereafter.

Alternatively or additionally, a data type usable in the determination of the destination points (e.g. auxiliary usage, traffic data, driver profile data, vehicle efficiency data, terrain data). For example, the adjustment may be to omit use of that data in determining one or more of the destination points when the amount of energy remaining is at or above the threshold. For example, to simplify the calculation one or more of efficiency, behaviour and auxiliary data types may be omitted as a variable from the determination of the destinations (e.g. from use in the route finding algorithm for determining the destinations and routes). For example, data that is deemed to have only a small effect on accuracy when the energy remaining is low may be omitted or replaced by a constant in any calculation.

Remote server

Figure 10 shows another embodiment in which the distance values are obtained in a data transmission from a data service provided by a navigation systems provider. In particular, a system is shown that includes a remote server 1001 and a vehicle navigation system 1002. The remote server 1001 has a data unit 1003 which includes road network database 1003-1 and live traffic data module 1003-2. These function in a similar manner to the road network database 207 and traffic module 209 of the device shown in Figure 2. Map and traffic data 1003-la, 1003-2a are provided from the road network database 1003-1 and the traffic module 1003-2 respectively to a route determination unit 1004. In addition, a transceiver 1005 is connected to the route determination unit 1004. The remote server 1001 is adapted to receive data transmissions from the vehicle navigation system 1002 and to transmit distance and other route information data 1004a determined by the route determination unit 1004 to the vehicle navigation system 1002 via communications network 1006.

The vehicle navigation system 1002 includes a transceiver 1007 in communication with a range prediction unit 1008. The range prediction unit 1008 is operable to generate a request to the remote server for routes and associated distance values to be determined and to use the distance values received from the remote server in response to calculate a prediction of the range of the vehicle. The range prediction unit 1008 is also coupled to a vehicle information unit 1009 that includes a vehicle efficiency database 1009-1, a driver profile database 1009-2, and an auxiliary systems module 1009-3. These provide efficiency behaviour, and auxiliary data 1009- la, 1009-2a, 1009-3 a, respectively which have the same properties as the respective data in the Figure 2 embodiment already described above. A GNSS module 1010 is also provided for obtaining the vehicle location data which is provided to the range prediction unit 908. In generating the request to the remote server, the range prediction unit collates the location, efficiency, behaviour and auxiliary data 1010a, 1009- la, 1009-2a, 1009-3 a into a data packet 1011 and sends this as a data transmission via the transceiver 1007 and communications network 1006 to the remote server 1001.

The route determination unit 1004 obtains the location, efficiency, behaviour and auxiliary data 1010a, 1009-la, 1009-2a, 1009-3a from the data packet 1011 from the data transmission and uses that together with the map data 1003- la and traffic data 1003 -2a to generate routes and associated distances to destinations about the vehicle that would empty the vehicle of charge or otherwise terminate before all the vehicle charge had been consumed. The determined route data 1004a is then transmitted back to the vehicle navigation system 1002 and received by the range prediction unit 1008 for use in determination the predicted range. Display 1012a generated by the range prediction unit 1008 based on the predicted range and a visualisation of the route data is provided to a display 1012. Control of what to display and how it should be displayed may be provided via user interface controls 1013 and resulting control data (not shown) sent to instruct the range prediction unit 1008.

In this embodiment the vehicle efficiency database, driver profile database and auxiliary systems module 1009-1, 1009-2, 1009-3 are provided on the vehicle side in the vehicle information unit 1009. However, it is also possible that these are provided on the remote server and kept up to date by period data transmissions from the vehicle. Alternatively, in the case of vehicle efficiency data 1009- la, this could be based on predetermined manufacturer specifications or historical usage, thus obviating the need for its provision at the vehicle side.

In the above embodiment traffic data, driver behaviour data, terrain data and efficiency data may all be used by the route prediction algorithm. In a simpler embodiment, however, the only inputs to the route prediction algorithm are the vehicle energy efficiency (that is updated in the vehicle between journeys) and the vehicle location as obtained via the GNSS. This is obviously not as accurate but as the vehicle efficiency data is based on real use rather than manufacturer data, a reasonable degree of accuracy can be obtained when obtaining the possible distances for the amount of energy remaining.

The motor vehicle described above is an electric vehicle (EV) and we have referred to energy remaining in the vehicle throughout. Energy in the context of an EV refers to remaining battery charge. However, the invention is not limited to electric vehicles and may be equally applied to conventional internal combustion engine (ICE) vehicles or plug-in hybrid (PHEV) vehicles that utilise vehicle navigation systems. The energy remaining in such vehicles may be calculated by conventional means known to those skilled in the art and utilised in determining possible routes according to any of the processes described herewith.

The above embodiments have been described in terms of apparatus having discrete functional modules. As will be appreciated, the functionality of those modules may be embodied by hardware or software. For example, a microcontroller, electronic control unit or one or more processors arranged to execute corresponding software modules. Alternatively, aspects may be embodied on an ASIC (application specific integrated circuit), SoC (system on chip), FPGA (fully programmable gate array) or other configurable logic array. The above is of course a non-exclusive list and any circuit type on which the processes described above can be embodied could equally be used. Further, the invention could be implemented on a distributed system such as a cloud computing platform, with different elements across the distributed system performing different aspects of the described processes. A computer program for performing the above described process may be embodied on a carrier that is computer readable such as a physical medium e.g. computer disc, DVD, Blu Ray (RTM), solid state memory, hard disk, or as a data signal that may be distributed over a network e.g. as an internet software download or a firmware update for a connected device with reconfigurable hardware.