The Interaction Component

 

  

Figure 2: The route request window.

When started, the Route Advisor client locates the servers it needs and displays a route request screen, like the one pictured in Figure 2. In the current implementation, the user specifies origin and destination in a postal address style, and identifies him/herself for the purpose of loading the user model. An in-car implementation could simplify this screen by providing the current location as a default starting point, and the most frequent car driver as a default user identity. The driver could select a destination from a list of that driver's most common destinations.

   

Figure 3: Initially, the user is presented two alternative routes. The best route according to the current user-model is highlighted.

[The route selection window.]

[The map window.]

After requesting a route, the main interaction window appears, as displayed in Figure 3(a). It provides a list of current route options and two menus, ``Route'' and ``Modify.'' The current routes are presented in terms of five attributes: total time, total distance, number of turns, number of intersections, and total time on highways. Initially the agent presents two routes to the user. The first route uses the current preference model as the weight vector for the routing cost function. The second uses novel weights in an attempt to explore new directions in the space of preference models.

Presenting at least two route options forces the user to make a choice and provide some feedback to the agent. The turn directions for the selected route are shown in the field below the route list and the map displays the selected route, as in Figure 3(b). Clicking ``Select'' indicates that the highlighted route is satisfactory and terminates the window. The route advisor assumes that the highlighted route is preferable to the alternative routes and updates the user model. Clicking ``Cancel'' terminates the window but does not update the model.

The ``Modify'' menu lets the user generate a new route that is faster, shorter, has fewer turns, has fewer intersections, or has less highway time than the selected route. The implicit assumption is that the driver is willing to accept routes that are somewhat worse on other attributes if he or she can find one that is better on the selected attribute. This approach to navigating through the space of possible solutions is similar to ``tweaking'' in Burke et al.'s FINDME systems [8]. In that system, the user can navigate a database of apartments for rent by asking for an apartment that is either cheaper, bigger, nicer, or safer than the one currently displayed.

The Adaptive Route Advisor searches for new routes that satisfy the improvement request by modifying the weights it places on attributes, increasing the weight of the selected attribute, and decreasing the other weights. Since slight changes in the weight vector may result in the same route, the system continues modifying the weights until the resulting route is significantly different. For example, Figure 4(a) shows a shorter route added to the route list. If the user is unsatisfied with all listed routes, the ``Route'' menu lets the user generate an entirely new route as different as possible from all those displayed. The route advisor does this by adding a ``penalty'' in the cost function to all segments used by one of the displayed routes.

   

Figure 4: The user generated the third route by selecting the first route and choosing ``Shorter'' from the ``Modify'' menu.

[The route selection window.]

[The map window.]

The interface described above simultaneously and seamlessly fulfills two functions in the Adaptive Route Advisor. First, it lets the users easily find routes they like by giving them choices and letting them interactively modify the routes proposed. Second, it unobtrusively collects the information the learning algorithm needs to refine the user model and adapt to a particular driver.