Your travelling habits often follow certain patterns. The most common is your daily commute between home and workplace but there is a basis for assuming what your likely next destination will be in many other situations as well. The prediction is, of course, done based on your past travelling records. The basic idea is that your GPS navigation system is able to figure out where you might be going based on your current location, weekday, time of day and a couple of other parameters.
As mentioned above, a typical example which first pops to mind is your daily commute. This is the easiest pattern to recognize. However, it is often interrupted with things like workouts on Tuesdays or beer with colleagues on Fridays. Maybe you going to these locations depends on what you did earlier in a day – did you do your workout in the morning? Did you leave your child at kindergarten before work? For another example, imagine it's evening and you went to visit your friends for the first time. When you get in your car afterwards, what is your likely next destination? Although you never took this particular route before (as far as your GPS navigation is concerned), it makes most sense to assume you are going to the place you go to every night – home. All of these examples are complex patterns which we wanted our AI to be able to recognize.
There are a handful of possible uses for such system. For starters, if you wish to use turn-by-turn navigation you don't have to type in your destination, so that's convenient. But the field in which it has the widest possible usage is Advanced driver-assistance systems (ADAS). These are electronic systems that help the vehicle driver while driving or during parking. The examples of ADAS are anti-lock braking system (ABS), adaptive cruise control, electronic stability control, parking sensors, lane departure warning system etc. Using the information about your likely next destination, the GPS navigation system can predict your most probable path. Using this, the infotainment system in your car can alert you about congestions up ahead without you actively turning turn-by-turn navigation on. Or it can tell you that bad weather is expected on your route. Furthermore, imagine a scenario in which cars are connected to the internet and certain car sensor readings are shared online. You could be warned about excessive ABS usage on part of your route, which may be the result of icy roads or oil spillage. You can also be warned about speed bumps or potholes.
During the course of creating such AI model, we constructed a list of conditions it should comply with. Needless to say, not all of the conditions were obvious from the start.
First, we had to precisely define what should be regarded as a trip's destination. If you stop along the way to leave your child at a soccer practice or to fill your car, does that count as an interim stop or the end of the trip? What about if you get stuck in traffic for a certain period? After careful consideration, we decided to regard the trip as being finished if you turn the engine off for more than 3 minutes.
Next, chances are good that, for most places you visit, you don't have a dedicated parking spot, so the exact parking location varies. In order to learn what the likely next destination is, the system must be able to figure out these parking locations actually correspond to the same destination. This is why all past trip destinations are first clustered. The most common and well known clustering methods did not suit our needs here. The need of many of them to define the number of clusters beforehand was ridiculous for this purpose. Also, the situation in which two locations a couple of kilometers apart end up in the same cluster does not make sense. DBSCAN seemed like a good idea, since one of the parameters is the distance in which to consider neighbors. However, this can also result in such situations that a neighbor of a neighbor of a neighbor ends up very far away, but is in fact a part of the same cluster. So we had to come up with a new method which would work logically for our specific purpose. We ended up using a heavily modified version of k-nearest neighbors algorithm. One destination clustering example is shown below. Of course, if you prefer, you can manually enter your points of interest, like home or work, and we'll use that location instead.
Another aspect to keep in mind is the recency of past trips. The trip you did yesterday is more relevant than the one from 6 months ago. As a result, it should be possible, for example, to change the system's information about your workplace if you change jobs. However, it shouldn't be too jumpy – you could be attending a conference at a different location for a couple of days but we wouldn't want the navigation system to change preferences immediately. It should change after a certain time, though, maybe after a couple of weeks. The key was finding the sweet spot. We performed the accuracy tests on a number of vehicles to fine tune this parameter.
It would be beneficial if the AI model could not only tell the most likely destination, but instead output a list of destinations, sorted from most to least probable. That way the GPS navigation system could show the user top 3 or 5 most likely destinations to choose from. If turn-by-turn navigation to a specific location is not activated, the system will alert you as if you’re driving to your most likely destination. If during a trip a significant divergence is noticed from the most probable path, the system will switch to the next destination that is still probable due to the course of trip so far. This means that if you’re actually going to a location that the system initially thought as second most likely, once it realizes you are not travelling in the direction of the most likely location, the system will switch to your actual destination and start alerting you what’s up ahead with that in mind.
To sum up all the prerequisites, the likely destination model should:
- Be able to handle complex circumstances and driving patterns
- Be able to recognize which locations belong to the same final destination
- Take trip recency into account
- Be able to give a list of ranked destinations as a result
- Be able to switch to the next most likely destination while driving
We then used machine learning to create AI model that finds patterns and figures out where you might be going based on your trips' history. Of course, we were interested in maximizing the model accuracy. We defined it as a percentage of destinations guessed by the model. However, it was important to simulate conditions in which the model would be used. For each trip, we would create a model that learned about all the trips preceding it. In other words, we would pretend that we have data only up to a point before the trip we wish to evaluate. Then, we would compare the real trip destination to the predicted one based on the knowledge before that point. This way, we created a testing procedure where the data on which we test the model is completely independent from the data on which the model is made.
Regarding the AI model accuracy measurement, there are a couple of things that need to be emphasized. First, predicting destination from past behavior means that the model will do a good job anticipating your next destination if that is something you normally or even sometimes do. If you break your record of going straight home after work one day to grab a drink – the model won't anticipate it because it has never recorded you going there. But, if you do it a few times, it will quickly become one of most likely destinations under similar conditions. Furthermore, there are situations when it’s absolutely ok for the model to make an incorrect prediction. For each of us, there are situations when we don’t follow our usual routine in similar circumstances. In such cases, it is natural for the model to expect us to do what we usually do. We just aren't following our usual pattern. And finally, in terms of accuracy, there is no one single number that should be regarded as satisfactory. Some drivers rarely diverge from their patterns, while others have almost none. For example, someone using his vehicle for a delivery service – in that case some locations might repeat, but most of them are impossible to anticipate. In the first case, anything below 8 out of 10 correctly guessed destinations might be low, while in the second 4 out of 10 might be a huge success. This is why there was a lot of manual checkup to make sure destination predictions make sense in the context of each driver. It is also for these reasons that trips to completely new destinations were excluded from evaluation. We wanted to measure the proportion of correctly guessed destinations out of ones that the model had at least a theoretical chance of guessing right.
The prediction accuracy we obtained on a mixed collection of vehicles was 61%. However, the accuracy varied a lot between vehicles, ranging from 41% to 76%. When testing the proportion of cases where the true destination was among the top 3 most likely destinations, the accuracy rose to 73%. In this case, the accuracy range was between 52% and 92%. But, what is most important is that the manual inspection showed the AI model always made sensible predictions, and wrong guesses stemmed either from driver behaving against his patterns or absence of notable patterns to begin with.
