‘Personalization for Route Guidance’ is a research effort conducted at the Computational Learning Laboratory, Stanford, CA. which aims to develop an adaptive route advisor that develops a model of a driver's preferences over time. Imagine a driving assistance system which learns your driving habits and route preferences to suggest better driving routes for you. That’s exactly what this system is trying to achieve!!!
The system comprises of a routing algorithm which is used to determine a route between two points on a map, taking into consideration the users preferences. The system works by first calculating multiple routes to help the user reach his destination. These routes are then presented to the user and he is asked to choose one of them. Based on the user’s choice, the different routes are rated and the cumulative understanding from these ratings is then used to build a user model for that user which can be used to predict which routes the user might like in the future.
Inner workings:
The system contains a map, which is composed of geographic locations (starting and destination locations) and routes connecting them. These routes are composed of roads also called edges.
The routing algorithm attempts to find the shortest path from a starting point to a destination point on this planner map using the Dijkstra’s shortest path algorithm. The route or path is traced along edges in the map. Each edge is weighted, and the algorithm attempts at determining the route with edges having the least weight.
So how does the algorithm go about doing this? Well let’s first understand the concept of weights in this system.
Each route is treated as a vector, and this vector is composed of individual edges. Each route will be multiplied by a global weight vector to determine its cost, this weight being derived from the collective values of attributes of each of the edges. Attributes are estimated total time, total distance, number of turns and number of intersection.
Now once the user selects a destination, the system throws up multiple alternatives to the user. Each alternative route has a weight associated with it. When the user makes a selection, that route’s cost is calculated to make sure it’s the lowest of all the alternatives. If not, the weight vector is modified to reflect the user’s preferences. This change in weight vector is added to the value of global weight vector.
What we get at the end of the day is a weight vector that tries to predict the users route preferences. To determine if a user likes a route or not, we take his global weight vector and multiply it with a route vector to determine its cost. If it’s low, we have a winner!!!
Testing the system:
The research group decided to test this system on a sample data set. Their results show that route preferences change widely across people. People are willing to sacrifice on a range of attributes of a route to achieve their goal, which can be different for different people.
Kicking the personalization aspect up a notch!!!
The research group has plans to use GPS to determine certain attributes of a driver which might be otherwise difficult to determine because of the impersonal nature of the route descriptors. Example: determine the speeds a user takes on edges of a particular type. The familiarity of a route is also being worked into the system. The more familiar a user is with a route, the higher is the preference. But this preference might be overridden by other attributes as time taken to complete route, and is a very subjective in nature.
What this project has managed to do is to prove that it is possible to derive a cost function that predicts driver preferences. Thus the cost function acts as a user model, generating routes that will satisfy the user’s needs. Better street descriptions and detailed user feedback (not the binary yes/no response used now) can help the system construct a better cost function. The group is also looking at other inductive methods to adapt the user model, such as regression over preference rankings, neural networks and principle component analysis which will help is refining the user model to a point where its predictions hit exceptional accuracy levels.
Links:
Project Homepage (get project literature here)
No comments:
Post a Comment