This paper presents SAFEWAY, a case-based recommender system to propose and explain the safest route between two points taking the user context into account. The novelty of this work is twofold. First, it considers safety as the main goal to optimize during the route calculation, and includes dynamic restrictions from the user context, like geographical, temporal, weather, and past accidents in that route. Secondly, it presents an approach to increase the acceptance of the recommendations by means of graphical explanations about the route safety. The paper describes a version of the SAFEWAY system that works with a memory of cases obtained from the Road Safety dataset that includes road accidents in GB since 1979.
Today, navigation devices are high-tech products that are available to everyone and have also become an important part of the lives of many people. The arrival of these devices has completely changed the way we move. Most of navigation apps are focused on speed, o ering the user the shortest route between a source and a destination previously de ned by it. But this is not, far from it, the only aspect that they take into account when it comes to providing us with a nal route. As we all know, these devices are able to o er in just a matter of seconds, information in real time about possible incidents that have taken place between the perimeter between the origin and the destination marked, such as tra c jams, accidents or sections with works in the road, thus being able to recalculate the fastest route to reach the destination. In addition, navigator software often is able to warn about xed and mobile radars, based on the reports made by users, and thus avoiding possible penalties for speeding. ? Supported by the UCM (Group 910494) and the Spanish Committee of Economy and Competitiveness (TIN2014-55006-R and TIN2017-87330-R)
In this work, route nding is considered as a recommendation problem and we explore two novel capabilities that can be integrated into navigation software. The rst feature that can be taken into account is the user context. A contextaware recommender system uses not only the static preferences of the user but also the dynamic data about its current state. For example, when recommending the best route there is an static setting of the user preferences including the type of road, points of interest, etc. However, there is other kind of information about the user that changes dynamically and is referred to as the user context. In our domain, the user context may include current location, weather conditions, type of vehicle, tra c state, or any other event along the user route at this speci c time. The user context is a very valuable source of information that can enrich the performance of the recommender system.
The second feature that this paper addresses is the explainability of the results. It is a major requirement of knowledge-based systems to be able to explain their decisions to the user. It is the goal of the of Explainable Arti cial Intelligence (XAI): to create a suite of new or modi ed machine learning techniques that produce explainable models that, when combined with e ective explanation techniques, enable end users to understand, appropriately trust, and e ectively manage the emerging generation of Arti cial Intelligence (AI) systems.
In the route planning domain the user receives a route recommendation, but
it is important to explain the reasons of such choice in order to increase the
acceptance of the recommendation being proposed. There are several ways to
explain a recommendation. The explanations can be shown in di erent ways,
more or less elaborated. The main formats are textual descriptions; schematic
descriptions such as tables, lists, tags, etc.; and several graphic approaches as
charts, like, histograms or tag clouds [
In order to explore the possibilities of explaining context-aware recommender systems we present a case-based system to recommend the safest route between two locations. SAFEWAY includes a memory of past accidents and enhance the route recommendation with information about incidents that took place in similar context restrictions as weather or tra c conditions, time, etc. The paper is structured as follows. Section 2 reviews state-of-the art literature about explanations and context-aware recommender systems. In Section 3, we describe the proposed recommender con guration, description features and the similarity measures. Section 4 describes the visual metaphor to explain the global route safety details and previous accidents and severity in the di erent zones. Section 5 concludes the paper and outlines the lines of future work. 2
There are many works that describe the features of good explanations for
recommender systems [
Contextual information extends the system query with information that is
not included in user preferences[
There are many platforms for route recommendations that we use every day. The most popular one is Google Maps. It recommends up to three routes commonly based on its duration. Explanations in this platforms are very simple, just a short text indicating the shortest or fastest route. It does explain contextual information such as tra c info using colours or icons, but this information is not associated when presenting the recommended route as shown in Figure 1.
Another popular platform is Apple Maps. It follows the explanation scheme of Google Maps but including the tra c conditions,the most relevant context feature of the route, into the recommendation. Figure 2 illustrates its behaviour.
Finally, the most complete application regarding the explanation strategy is Here WeGo. It is the main competitor of the previous approaches and provides real-time information on tra c conditions and incidents. This information is included in the graphical explanation presented to user when proposing a recommended route. As Figure 3 shows it includes contextual tra c conditions into the suggested route and it also shows incidents by means of icons.
If we focus on the inclusion of context information, the most relevant system is Waze. It provides real-time directions that are adjusted on-the- y to account for various types of potential obstacles. Waze uses a collaborative approach were users share their context info to allow the real time recommendation. It uses several icons to report these potential obstacles (Figure 4) and a limited explanation of the route being recommended (Figure 5). 3
SAFEWAY is a case-based recommender system to propose and explain the safest route to the user taking into account her context restrictions. Case-based recommenders use a memory of past cases to perform the recommendation. They can be classi ed as content-based recommenders because they compare the preferences of the user to the description of the stored cases in order to select the best option. In our case we will extend this comparison to include also the dynamic information from the user context.
The memory of cases has been obtained from the Road Safety dataset1. This dataset provides detailed road safety data about the circumstances of personal injury road accidents in GB from 1979, the types of vehicles involved and the consequential casualties. Among many other elds, this dataset includes geographical and temporal information (location, date, time), accident severity,and other context information such as weather conditions. This way, the cases are de ned as a description that contains the location and context information, and a solution that describes the incident severity
CB = fc1; c2; : : : ; ci; : : : ; cng c = < d; s > d = < location; context > s = < severity > (1)
The query of the system is a couple of origin and target coordinates that will be submitted to the Google Maps API in order to obtain the three fastest routes. The query also includes the context information of the user (date,time,weather,...). 1 https://data.gov.uk/dataset/cb7ae6f0-4be6-4935-9277-47e5ce24a11f/road-safetydata
Then, these routes are ranked by our system according to their safety given the restrictions of user context. To do so, the system splits the route according to the con gured precision threshold and obtains the list of way-points of the route. Then every way-point is compared to the incidents in the case base to retrieve past accidents that took place in the corresponding coordinates. This retrieval process uses a similarity function that enables nding incidents within a certain distance and similar conditions. This way, we assume that incidents taking place in a certain distance ( parameter in Equation 6) can also have consequences in the way-point due to the tra c congestion they can generate. An example of this assumption is shown in Figure 6. Concretely, the similarity measure takes into account the location, weather conditions, time, date, and type of vehicle. It is important to note that there are several ways to con gure this similarity metric as explained at the end of this section.
W P i = fwpi1; wpi2; :::; wpimg = split(Ri)
Reti = f< cj ; similaritycj >g where dist(cj :location; wpik:location) < (2) (3) (4) (5)
The retrieval process returns a list of incidents ranked according their similarity to the way-point and the context restrictions of the user (weather, time, date and vehicle). Next, an aggregate measure is computed in order to obtain a value that re ects the global safety of the route. It is obtained as the average of the severity value of every incident found in all the way-points of the route weighted according to the similarity value.
Saf etyi =
X cj :severity cj :similarity (8) where
ci 2 Reti
Once we have detailed the case-based recommendation process we will discuss several alternatives to con gure the similarity function. The similarity function in Equation 7 is used to compare the user context (u:context) to the context of the incident (c:context). When de ning this metric we realized that there are di erent valid approaches and our system must allow the user to choose the one that best ts their requirements.
Next we will discuss these alternatives to compute the context's similarity: Date comparison . When comparing dates there are several approaches. We can use just the numerical distance according to the day of the month or de ne a more sophisticated metric. For example, we can retrieve accidents
parameter to take into account incidents that took place the same day of the week, or even accidents in working days or weekends.
Time comparison . There are also several alternatives to compare times. We can use the numerical di erence or generate categorical values like `morning', `afternoon', etc. It is also possible to de ne time zones like `peak hour tra c'. 4
Current research in Explainable Arti cial Intelligence points out the relevance of explanations in order to increase the user's acceptance of the solution. Therefore, SAFEWAY uses a visual metaphor to give the user the details of the route regarding its safety. This metaphor is shown in Figure 7 where numerical markers show the similarity between the context of the past incident to the current user's context. Additionally, the colour of the car icon re ects the severity of the incident. The explanation of the severity of the whole route is complemented by the use of grouping of incidents in a similar location. This allows the user to get a global view of the route, that is later extended when the user zooms for details.
The following example shows how the visual metaphor servers to choose the safest route. Figure 8 (top-left) shows the three routes proposed by Google Map from Camden Town to St. Paul's Cathedral in London. There are three recommended alternatives (22 min, 20 min and 18 min), being recommended the fastest one (18 min). However, the remaining screen-shots in Figure 8 show the sames routes but ordered according to the SAFEWAY's algorithm.
The safest one is shown in the top-right corner (green alternative) and the most dangerous in the bottom-right corner (red alternative). We can observe that the fastest route (18 min) that is recommended by Google Maps is clearly the most dangerous. On the other hand, the slowest alternative is proposed as the safest one.
The visual markers explained in Figure 7 allow to understand the recommendation. As we can observe, the safest route (Figure 8 top-right) contains only one accident that is not very similar to the user context and its severity is low. In the opposite way, the most dangerous alternative (Figure 8 bottom-right) contains many accidents. 5
In this paper we have described SAFEWAY, a case-based system for the recommendation of safe routes. It explores two major ideas. The rst one is the importance of the user context to de ne the dynamic restrictions during the trip. Secondly, it presents an approach to increase the acceptance of the recommendations by means of graphical explanations. SAFEWAY bases its results in the routes suggested by the Google Maps API and a memory of past accidents that took place in similar context restrictions as weather or tra c conditions, time, etc. The system includes visual indications to explain the route security of the recommended route. The system is a prototype and as an immediate future work we need to evaluate the recommendation performance to measure the impact of the di erent parameters of the algorithm such as the distance threshold ( ). It is also necessary to evaluate the di erent similarity approaches with real users in order to validate our hypothesis about how explanations increase the user's acceptance of the solution.
Fig. 8. Alternatives recommended by SAFEWAY. Top-left shows the three alternatives returned by Google Maps API (18 min, 20 min and 22 min). However, the fastest alternative according to Google Maps (18min) is the most dangerous according to SAFEWAY and therefore recommended last (bottom-right). The slowest alternative (22 min) is the safest and recommended rst (top-right), whereas the remaining alternative (20 min) is recommended as the second option (bottom-left). 20. Verbert, K., Manouselis, N., Ochoa, X., Wolpers, M., Drachsler, H., Bosnic, I., Duval, E.: Context-Aware Recommender Systems for Learning: A Survey and Future Challenges. IEEE Transactions on Learning Technologies 5(4), 318{335 (oct 2012). https://doi.org/10.1109/TLT.2012.11, http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6189308 21. Woerndl, W., Huebner, J., Bader, R., Gallego-Vico, D.: A model for proactivity in mobile, context-aware recommender systems. In: Proceedings of the fth ACM conference on Recommender systems - RecSys '11. p. 273. ACM Press, New York, New York, USA (oct 2011). https://doi.org/10.1145/2043932.2043981, http://dl.acm.org/citation.cfm?id=2043932.2043981 22. Woerndl, W., Schueller, C., Wojtech, R.: A Hybrid Recommender System for Context-aware Recommendations of Mobile Applications. In: 2007 IEEE 23rd International Conference on Data Engineering Workshop. pp. 871{878. IEEE (apr 2007). https://doi.org/10.1109/ICDEW.2007.4401078, http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=4401078 23. Zanker, M., Ninaus, D.: Knowledgeable explanations for recommender systems. In: Web Intelligence and Intelligent Agent Technology (WI-IAT), 2010 IEEE/WIC/ACM International Conference on. vol. 1, pp. 657{660. IEEE (2010)