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 driver preferences from driver route choices. We have implemented a perceptron-style training algorithm [6], which we call differential perceptron, that processes a sequence of interactions with the planner and produces a weight vector that attempts to model the preferences expressed. In this way, as the driver uses the interface, it adapts itself to the user's 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).$$

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. Although the system can update the perceptron on-line after each new training example, the experiment described in the next section trains on a fixed set of examples.

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 be the lowest cost route 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.