The results of our initial experiment indicate that it is possible to learn a cost function that predicts driver preferences with reasonable accuracy. More importantly, this cost function serves as a user model for generating routes that will be satisfactory to the driver. The Adaptive Route Advisor can be made more powerful and useful through additional work in five key areas: use of personalized attributes, better street descriptions, use of direct driving feedback, a more effective interface, and better model induction.
One source of error in the experiment was the limited and impersonal nature of the route descriptors. As Haigh and Veloso [4] note, the descriptor set may not represent all factors relevant to a driver. An in-car navigation system is particularly well situated to use personalized attributes, because it can constantly monitor the driver's behavior using traces from a Global Positioning System. In particular, we can assume that the routes a person drives are desirable by that person's true internal cost function3 and use information about familiar routes when planning new ones.
The planner could represent familiarity as a binary visited/not visited value for each edge, or it could try to represent the degree of familiarity as a continuous value. However, with an additional assumption that sequences of familiar edges (subroutes) are more desirable than isolated familiar edges, we have developed a familiarity preprocessor [9] that groups sequences of road edges between commonly used intersections into higher-level links, similar to disjunctive macro-operators. A macro link between two intersections represents all distinct routes the driver has used between these intersections. These macro links are hierarchically organized, with some links recursively incorporating smaller macro links. The largest macro links represent entire trips, such as the drive from home to work. Including these macro links affects the planner in three ways: it uses sequences of familiar edges as primitives, it shortens the edge-by-edge description of the route by summarizing familiar sequences, and it biases the route description toward using familiar segments.
We can improve street descriptions by accessing existing geographic databases and by generating new ones. Current databases provide information about the location and types of businesses, as well as demographic information. In future work, we will generate new geographic databases by collecting and analyzing traces of trips from a Global Positioning System. Analyzing the trajectories of many cars along the same edge provides average speed models for different times of day, the location of traffic controls, and number of lanes. An advantage to the client/server architecture is that clients can serve as a distributed sensor network to sample road conditions and provide dynamic updates to the digital map for more accurate routing. Some possible dynamic attributes include transit time, congestion, and road or lane closures.
Besides interacting with the interface, another form of feedback comes from observing the routes actually driven. If the driver does not take the route the user model predicted, the new route is presumably better than the predicted route, and this will generate a new instance for the personalization module. This type of feedback may include more classification noise than direct feedback because there is no direct evidence that the driver liked his route or even that he or she was not lost. However, if the driver usually follows routes because of his own preferences, the noise should cancel out after sufficient training data. These indirect forms of feedback are less intrusive than that required by our current system, where the user must explicitly select the route he prefers.
The current user interface is tuned to exhibit the functionality of the agent. To deploy the Adaptive Route Advisor in a car, we will need to partly redesign the interface to take into account the limited input and output facilities. For instance, the menu for modifying the routes might be replaced by a panel of buttons that the user can activate through a touch screen. We will also need to evaluate the in-car user interface with drivers to ensure that the capabilities of the route advisor are easily and intuitively available to drivers.
We are also exploring other inductive methods for adapting the user model, such as regression over the preference rankings, multi-layer neural networks, and principal components analysis. A critical property of prospective methods is that the model be able to generate a numeric cost for partial and complete routes. We are also investigating more flexible model representations, such as adjusting the weight vector based on task characteristics. For example, a driver may always want the fastest route to work but prefer a more leisurely drive home. Results from any method could improve with some background knowledge about the domain and more relevant attributes for the street descriptions. We can improve our evaluation by determining the fraction of modeling errors that are due to driver inconsistency, which we can measure by including some redundancy in our experimental tasks. Our final goal is an agent with a flexible, usable interface that accurately adapts itself to its user over time.