Constructing the User Model

 

Although weighting each edge attribute creates a flexible cost function for the planner, the space of possible models is a continuum with as many dimensions as there are attributes. It would be difficult and inconvenient for a user to specify his relative preference for each attribute. Instead, our system automatically induces a driver's preferences from his route choices. We have implemented a perceptron-style training algorithm [8], which we call the differential perceptron, that processes a sequence of interactions with the planner and produces a weight vector that models the preferences expressed. In this way, as the driver uses the interface, it adapts itself to his preferences. This is reminiscent of the way in which Hermens and Schlimmer's system for filling out repetitive forms [5] adapts itself to a particular usage pattern and predicts defaults values based on those observed in previous interactions.

We define an interaction with the planner to be the presentation of a set of N generated routes and feedback from the user indicating which route is preferable. This is completely unobtrusive to the user, because he or she evaluates a set of routes and selects one as part of the route advice process. For training, we expand the interaction into N-1 pairs, representing the fact that the selected route is preferable to each of the presented alternatives. These training pairs can be used to improve the user model in a simple manner. If, out of the two routes in a training pair, the route preferred by the current user model is not the one the user selected, the adaption method increases the weights corresponding to the features in the selected route and decreases those corresponding to the features in the other route.

More precisely, the system represents routes with a vector $\vec{x}$containing its measurable attributes. Given an initial weight vector $\vec{w}$, it estimates the cost of a route to be the linear product $c = \vec{w} \cdot \vec{x}$. If route $\vec{x}_1$ is rated better than route $\vec{x}_2$ and the cost of $\vec{x}_1$ is lower than that of $\vec{x}_2$, the weights are consistent and do not need modification. If the cost of $\vec{x}_1$ is higher than that of $\vec{x}_2$, the system applies the differential perceptron update rule to $\vec{w}$, which decreases the cost of $\vec{x}_1$ and increases the cost of $\vec{x}_2$ using

$$\Delta \vec{w} = \eta \vec{x}_2 - \eta \vec{x}_1 = \eta (\vec{x}_2 - \vec{x}_1),$$

where $\eta$ is the learning rate. For each pass through all available training data, the learning algorithm adds  $\Delta \vec{w}$to $\vec{w}$ and continues running through the training data until the weights stop changing or it has performed a maximum number of iterations, which is set to 5,000 in the current system.²

Once the differential perceptron algorithm finds a weight vector that best predicts preferable routes as a weighted sum of attributes, the routing algorithm uses this weight vector in its cost function. Since the routing algorithm is optimal on the cost function, the resulting route is guaranteed to have the lowest cost for that user model among all routes between the same two nodes. In other words, the routes computed are always Pareto optimal, in that there can be routes that are better along each of the dimensions (attributes) independently, but none that can be better simultaneously on all dimensions.