Navigation device and method for predicting the destination of a trip

• US 8,392,116 B2
• Filed: 03/24/2010
• Issued: 03/05/2013
• Est. Priority Date: 03/24/2010
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Lehmann, Jens, Sommer, David
• Primary Examiner(s): FREJD, RUSSELL WARREN
• Application Number:
  US12/730,973
• Publication Number:
  US 20110238289A1
• Time in Patent Office: 1,077 Days
• Field of Search: 701408-430, 701/450, 701/451, 701/461, 701/468, 701/481, 706/21, 706/25, 706/52, 707/758, 707/736, 707/769, 707/748, 340/994, 3409951-99525
• US Class Current: 701/524
• CPC Class Codes: G01C 21/3438 Rendez-vous, i.e. searching a destination where several users can meet, and the routes to this destination for these users; Ride sharing, i.e. searching a route such that at least two users can share a vehicle for at least part of the route
• CPC Class Codes: G01C 21/3617 using user history, behaviour, conditions or preferences, e.g. predicted or inferred from previous use or current movement

Abstract

A navigation device and computer implemented method for predicting the destination of a trip, the method being executed by a navigation device, the method comprising the steps of: determining starting parameters, the starting parameters comprising at least the starting point, starting time and date of the trip, executing a destination prediction algorithm, the destination prediction algorithm taking the starting parameters as input and predicting a destination, wherein the destination prediction algorithm is generated by using information of a trip history; determining, upon arrival at the predicted or another destination, the actual destination.

Claims

1. A navigation device for predicting a destination of a trip, the navigation device comprising:

a position determination unit for determining the current position of the navigation device;

a clock unit for determining the current time and date;

a computer-readable non-transitory data storage for storing a trip history, the trip history comprising a set of trip data objects, each trip data object representing a past trip and comprising starting parameters and an actual destination of the represented trip, the actual destination being the destination chosen and reached by a user of the navigation device, the starting parameters comprising at least;

a starting time and date of the trip, and

a starting point of the trip;

a learning module for generating a destination prediction algorithm, the destination prediction algorithm being generated by using information of the trip history;

a destination prediction module for predicting the destination of the trip, thereby using the destination prediction algorithm, the destination prediction algorithm being operable to predict the destination of the trip by using the starting parameters of the trip;

wherein the destination prediction algorithm is to calculate prediction scores for corresponding predicted destinations;

wherein the navigation device is to use a value of the highest score among the prediction scores to select a navigation mode among a plurality of navigation modes;

a processor for executing read/write operations on the data storage and for executing instructions of the learning and prediction modules;

a notification device for indicating to a user of the navigation device the route to a destination of a trip.

2. The navigation device according to claim 1, the navigation device further comprising:

an interface for receiving external data, the external data being selected from a group consisting of;

weather data,

traffic data,

traffic jam data,

diversion routes,

data of restaurants, public buildings or shops lying within a specified distance from the current position of the navigation device,

data of hostels, hotels or leisure facilities lying within a specified distance from the current position of the navigation device,

data of gas stations or car repair shops lying within a specified distance from the current position of the navigation device,

trip sharing requests of participants of a trip sharing service lying within a specified distance from the current position of the navigation device, and

the destination and user profile data of participants of a trip sharing service having been determined by said trip sharing service as potential trip accompanies,

wherein the received external data is used as one or multiple additional starting parameters by the destination prediction algorithm.

3. The navigation device according to claim 2, wherein the interface is to receive external data from a trip sharing service, and wherein the navigation device is further operable to send a predicted destination to the trip sharing service via said interface, thereby notifying other users of the existence of a trip to the predicted destination.

4. The navigation device according to claim 1, the navigation device further comprising:

an interface for receiving vehicle data, the vehicle data being selected from the group consisting of

the number of occupied seats in the vehicle,

the position of the occupied seats in the vehicle,

the filling level of the gas tank,

the vehicles oil level,

error messages generated by any of the vehicle'"'"'s components, and

status messages generated by any of the vehicle'"'"'s components,

wherein the received vehicle data is used as one or multiple additional starting parameter by the destination prediction algorithm.

5. The navigation device according to claim 1, the navigation device further comprising an interface for receiving application data, the application data being provided by a software application running on the navigation device, the application data being selected from the group consisting of

calendar event data being received from a calendar application,

data on goods to be sold or bought being received from CRM systems, and

project specific data being received from project management software programs,

wherein the received application data is used as one or multiple additional starting parameters by the destination prediction algorithm.

6. The navigation device according to claim 1, wherein the destination prediction algorithm is implemented as a neural network, wherein the starting parameters and destinations of all trip data objects of the trip history are input data for training the neural network, wherein the neural network as a result of training predicts the destination of a trip by selecting one particular destination from a set of known destinations, the set of known destinations being selected from the group consisting of

destinations having been explicitly entered by the user of the navigation device into the navigation device,

destinations the user of the navigation device chose without entering this data explicitly into the navigation device,

implicit destinations, wherein implicit destinations are locations the navigation device has determined automatically during a trip along a route, and

application derived destinations, an application derived destination being an address derived from an application installed on the navigation device.

7. The navigation device according to claim 1, wherein each type of starting parameter is assigned a weight, wherein for each starting parameter value or value range of a set of current starting parameters and for each known destination a probability value is calculated, the probability value being indicative of the probability that the known destination is the actual destination given said starting parameter value or value range, and wherein an overall probability is calculated for all known destinations by weighting each probability value calculated for a parameter according to the weight assigned to the type of said parameter, and by summing up the weighted probabilities for each known destination.

8. The navigation device according to claim 2, wherein the predicted destination is submitted via the interface for receiving external data to a remote service provider via the interface, wherein the navigation device receives a response from the remote service provider, the content of the response being dependent on the submitted destination, and wherein the notification device further indicates the received response.

9. The navigation device according to claim 1, wherein the notification device does not indicate navigation instructions in case the destination prediction score of the destination prediction algorithm is above a first prediction score threshold.

10. A navigation device for predicting a destination of a trip, the navigation device comprising:

a position determination unit for determining the current position of the navigation device;

a clock unit for determining the current time and date;

a computer-readable non-transitory data storage for storing a trip history, the trip history comprising a set of trip data objects, each trip data object representing a past trip and comprising starting parameters and an actual destination of the represented trip, the actual destination being the destination chosen and reached by a user of the navigation device, the starting parameters comprising at least;

a starting time and date of the trip, and

a starting point of the trip;

a learning module for generating a destination prediction algorithm, the destination prediction algorithm being generated by using information of the trip history;

a destination prediction module for predicting the destination of the trip, thereby using the destination prediction algorithm, the destination prediction algorithm being operable to predict the destination of the trip by using the starting parameters of the trip;

a processor for executing read/write operations on the data storage and for executing instructions of the learning and prediction modules;

a notification device for indicating to a user of the navigation device the route to a destination of a trip;

wherein the destination prediction algorithm is implemented as a neural network, wherein the starting parameters and destinations of all trip data objects of the trip history are input data for training the neural network, wherein the neural network as a result of training predicts the destination of a trip by selecting one particular destination from a set of known destinations, the set of known destinations being selected from the group consisting of

destinations having been explicitly entered by the user of the navigation device into the navigation device,

destinations the user of the navigation device chose without entering this data explicitly into the navigation device,

implicit destinations, wherein implicit destinations are locations the navigation device has determined automatically during a trip along a route, and

application derived destinations, an application derived destination being an address derived from an application installed on the navigation device;

wherein the neural network is implemented as a “

feed-forward back-propagation network,”

wherein weights are assigned to each starting parameter in dependence on its type and wherein the weights of the starting parameters are adapted in each layer of the network by the back-propagation algorithm to minimize a mean squared error value, the mean squared error value being indicative of the prediction accuracy of the destination prediction algorithm.

11. A computer implemented method for predicting the destination of a trip, the method being executed by a navigation device, the method comprising the steps of:

determining, by the position determination unit, the current position of the navigation device as the starting point of the trip, the starting point to be used as a starting parameter;

determining, by the clock unit, the current time and date as the starting time and date of the trip, the starting time and date to be used as starting parameters;

executing a destination prediction algorithm, the destination prediction algorithm taking the starting parameters as input and predicting at least one destination, each predicted destination having assigned a prediction score, the prediction score being derived from the accuracy of the destination prediction algorithm and the probability value of the predicted destination, wherein the destination prediction algorithm is generated by using information of a trip history, the trip history comprising a set of trip data objects, each trip data object in the trip history representing a past trip, each trip data object comprising at least the starting parameters and the actual destination of the past trip, the actual destination being the destination chosen and reached by a user of the navigation device during the past trip represented by said trip data object;

switching, by the navigation device, the mode of operation in dependence on the prediction score value of the predicted destination having assigned the highest prediction score value;

determining an actual destination of the trip; and

storing the actual destination in association with all determined starting parameters in the form of a trip data object in the trip history.

12. The computer implemented method according to claim 11, wherein a repeat is specified, wherein the repeat is executed at least twice, and wherein the actual destination of the trip in the first repeat acts as starting point used in the prediction of the step of executing the destination prediction algorithm of the second repeat, and wherein in step of determining the current time and date as the starting time and date of the trip of the second repeat at least the current time and date is determined as additional starting parameter for the prediction of the destination in the second repeat.

13. The computer implemented method according to claim 11, wherein the destination prediction algorithm is implemented as a neural network, wherein each starting parameter comprises a weight, wherein the weighted starting parameters of all trip data objects of the trip history are used as input for training the neural network, wherein the neural network, as a result of training, predicts the destination of a trip by selecting one particular destination from a set of known destinations, the set of known destinations being selected from the group consisting of

the set of all destinations stored in the trip history, comprising destinations explicitly entered into the navigation system by the user and destinations chosen by the user without explicitly entering them into the navigation device, and

the set of all destinations having been explicitly entered by the user of the navigation device into the navigation device.

14. The computer implemented method according to claim 11, wherein each starting parameter comprises a weight depending on its type, wherein for each type of starting parameter and for each known destination a probability value is calculated, the probability value indicating the probability value that the known destination will be the actual destination given a set of starting parameters, wherein each parameter type is weighted, and wherein an overall probability is calculated for all known destinations by summing up the weighted probabilities for each known destination given the current starting parameters values, wherein the set of known destinations is selected from the group consisting of

destinations having been explicitly entered by the user of the navigation device into the navigation device,

destinations the user of the navigation device chose without entering this data explicitly into the navigation system,

implicit destinations, wherein implicit destinations are locations the navigation device has determined automatically during a trip along a route, and application derived destinations, an application derived destination being an address derived from an application installed on the navigation device.

15. The computer implemented method according to claim 11, further comprising the step of sending, via an interface for receiving external data, the predicted destination to a trip sharing service, thereby notifying other users of the trip sharing service of the existence of a trip to the predicted destination.

16. The computer implemented method according to claim 11, wherein the mode of operation of the navigation device depends on the accuracy of the destination prediction algorithm.

17. A computer implemented method for predicting the destination of a trip, the method being executed by a navigation device, the method comprising the steps of:

determining, by the position determination unit, the current position of the navigation device as the starting point of the trip, the starting point to be used as a starting parameter;

determining, by the clock unit, the current time and date as the starting time and date of the trip, the starting time and date to be used as starting parameters;

executing a destination prediction algorithm, the destination prediction algorithm taking the starting parameters as input and predicting at least one destination, each predicted destination having assigned a prediction score, the prediction score being derived from the accuracy of the destination prediction algorithm and the probability value of the predicted destination, wherein the destination prediction algorithm is generated by using information of a trip history, the trip history comprising a set of trip data objects, each trip data object in the trip history representing a past trip, each trip data object comprising at least the starting parameters and the actual destination of the past trip, the actual destination being the destination chosen and reached by a user of the navigation device during the past trip represented by said trip data object;

determining an actual destination of the trip; and

storing the actual destination in association with all determined starting parameters in the form of a trip data object in the trip history;

wherein the destination prediction algorithm is implemented as a neural network, wherein each starting parameter comprises a weight, wherein the weighted starting parameters of all trip data objects of the trip history are used as input for training the neural network, wherein the neural network, as a result of training, predicts the destination of a trip by selecting one particular destination from a set of known destinations, the set of known destinations being selected from the group consisting of

the set of all destinations stored in the trip history, comprising destinations explicitly entered into the navigation system by the user and destinations chosen by the user without explicitly entering them into the navigation device, and

the set of all destinations having been explicitly entered by the user of the navigation device into the navigation device;

wherein the neural network is implemented as a “

feed-forward back-propagation network,” and

wherein the weights of the starting parameters are adapted in each layer of the network by the back-propagation algorithm to minimize a mean squared error value, the mean squared error value being indicative of the prediction accuracy of the destination prediction algorithm.

18. A data processing system comprising a server and at least a first navigation device, the server hosting a trip sharing service, the first navigation device including

a position determination unit for determining the current position of the navigation device;

a clock unit for determining the current time and date;

a computer-readable non-transitory data storage for storing a trip history, the trip history comprising a set of trip data objects, each trip data object representing a past trip and comprising starting parameters and an actual destination of the represented trip, the actual destination being the destination chosen and reached by a user of the navigation device, the starting parameters comprising at least;

a starting time and date of the trip, and

a starting point of the trip;

a learning module for generating a destination prediction algorithm, the destination prediction algorithm being generated by using information of the trip history;

a destination prediction module for predicting the destination of the trip, thereby using the destination prediction algorithm, the destination prediction algorithm being operable to predict the destination of the trip by using the starting parameters of the trip;

a processor for executing read/write operations on the data storage and for executing instructions of the learning and prediction modules; and

a notification device for indicating to a user of the navigation device the route to a destination of a trip,

the server including;

a processor for executing computer-interpretable instructions;

a network interface for connecting the server to a network;

a web service interface for providing remote access to the program logic of the trip sharing service to the at least one navigation device;

a computer-readable non-transitory storage medium comprising instructions which, when executed by the processor, result in the execution of the trip sharing service, the trip sharing service in operation allocating users with similar user profiles and trip plans as trip accompanies;

wherein the exchanged data is selected from the group consisting of

a request being submitted from the navigation device to the trip sharing service, the request indicating other participants of the trip sharing service, the starting time, starting place and destination of a trip, the destination of the trip being predicted by the destination prediction algorithm, and

a result being returned by the trip sharing service to the navigation device, the result comprising at least contact information of a second user having been assigned to the user of the navigation device by the trip sharing service as trip accompany.

19. The data processing system according to claim 18, wherein planned trips of each user are represented on the server as server-side trip data objects, wherein each server-side trip data object is implemented as a multi dimensional vector, wherein for each newly created server-side trip data object a matching method is executed, wherein the matching method comprises the comparison of a first server-side trip data object with all server-side trip data objects contained in a database of the trip sharing service, thereby determining a matching score for each pair of compared server-side trip data objects, and wherein two users corresponding to the pair of server-side trip data objects reaching the highest matching score are allocated as trip accompanies.