Adaptive presentation of itineraries in navigation systems by means of semantic models Daniel Muenter & Tim Hussein University of Duisburg-Essen Lotharstr. 65, 47057 Duisburg, Germany {daniel.muenter, tim.hussein}@uni-due.de ABSTRACT area, and, on the other hand, more detailed, while driving In this paper, we introduce a technique for adaptive presen- through unknown territory. tation of itineraries in navigation systems based on seman- tic models. We enrich waypoints with semantic information In this paper, we introduce a concept to enhance the presen- and display only those waypoints to the driver that he is re- tation of the route by adapting it to the driver and his pref- ally interested in, hiding information that will most probably erences and experience. For that purpose, we use semanti- be distracting. cally enriched models of the itineraries. In the end, the user should only see and hear necessary and helpful information instead of every single detail. Besides automated adaptation, Author Keywords the user has always the option to adjust the level of detail of Model-driven UI Generation, Navigation Support the presentation manually. ACM Classification Keywords RELATED WORK D.1.2 Software: Programming Techniques—Automatic Pro- Even if not focused on the particular problem depicted in gramming the introduction, research has been conducted, in order to enhance presentation of itineraries. INTRODUCTION Navigation systems are widespread tools in automobiles. Ac- A generalization technique that is geared to hand-drawn route cording to recent german studies [5], the percentage of pre- descriptions and tries to solve the visibility problem of minor installed navigation systems increased from less than 6% to parts of an itinerary on a constant scale factor, is presented 18% within the last six years (in Germany). The percentage by Agrawala and Stolte [1]. They assume that humans de- of mobile navigation systems even rose from 1% to almost scribe routes in a different way than systems. People always 31% in the same period. With regard to usability [7] and relate to their own knowledge of the environment in a route traffic routing [3, 11], constant progress has been made dur- description. ing the last years. However, there is room for improvement In addition, humans are mainly interested in information about in many ways. the main waypoints and not the connections between them. Usually, the presentation of the itinerary is very detailed – They rather neglect the length of individual roads and instead even if the driver knows parts of the route very well. This is raise their visibility or specific route characteristics (e.g. a often distracting and annoying. Presentation techniques that big building or a roundabout) that they consider to be rele- take the users knowledge and driving behavior into account vant to the navigation process [9]. can improve the user experience considerably. In [6], Klippel et. al. propose a formal characterization of Present solutions aim at optimizing routes without taking the route knowledge, that allows for communicating informa- driver’s personal knowledge, experience, and preferences into tion on how to reach a destination (even if a specific route account and, thus, are not personalized. However, incorpo- is not known). Therefore, changes of granularity in route ration of personal information could improve presentation directions resulting from combining elementary route infor- of routes significantly. On the one hand, instructions should mation into higher-order elements (so called spatial chunk- be rather short and abstract, if the user knows the particular ing) are discussed. The authors of that paper also point out, that if environ- mental features are taken into account for structuring route knowledge, a coarser perspective on the required way-finding action than simple turn-by-turn directions can be provided. Variable granularity in route directions is also focused in [10]. However, while these approaches attempt to improve the route guidance by structuring route knowledge, they dis- regard the individual needs of the user. 1 Copyright is held by the author/owner(s) SEMAIS'11, Feb 13 2011, Palo Alto, CA, USA Most users have at least some knowledge of the vicinity they a classification of each route point on the nature and type live. Although most people are familiar with their hometown of geographical conditions. This means that a place can ei- or parts of it, they receive detailed route instructions from ther be characterized as town, city, region or even a country their device. A personalized granularity in route directions and the connection between two places as a street, road or regarding the special knowledge of a user about the routing motorway. This hierarchical distinction enables later filter- environment could lead to a more intelligent navigation sys- ing to distinguish the different levels of abstraction. For the tem. transformation every route object provided by online web services like Google Maps1 can be used. Such a comprehension of the user’s knowledge about several parts of the route has been largely neglected by device man- If a user has sufficient knowledge about the environment in ufacturers and suppliers of relevant web services, so far. The a particular area, only a few instructions, limited to the issue fact that such navigators would need an extended learning of the next motorway link and the direction of the nearest phase to provide customized assistance, is mostly seen as a town, may be appropriate, while in areas less or not at all major drawback. familiar, a detailed route guidance without any abstraction will be a better choice. To address this problem, Richter and Tomko present an ap- proach to generate adaptive route directions generated through For enriching semantic itinerary models with further infor- a dialog-based knowledge recognition process [9]. There- mation, geo-services such as LinkedGeoData.org2 can be fore, the way-finder by default is presented with with desti- used. Those services provide comprehensive background nation descriptions, assuming that the environment is known, knowledge related to spatial features of the ways, structures and can request more detailed directions using a provided and landscapes around the waypoints of an itinerary [2]. dialog facility, if the currently presented information is not adequate. Other services that provide additional information for route enhancement are, for instance, OpenStreetMap3 , GeoNames4 , We argue that a system could automatically provide user spe- or Topocoding5 , which enables us to add the related altitude cific route directions based on a learning process that primar- value to each waypoint. Figure 1 shows such a semantic ily is supported by a dialog-driven approach. Therefore, we route representation enhanced with additional information. act on the dialogue suggestion by Richter and Tomko, which in a first step can enhance the learning process to solve the "Koloniestraße" "Bissingheimer Str" cold start problem of completely unknown user preferences "Turn left at ..." "Keep right at the.." and also avoids the user from unnecessary interactions while label label residential residential ins ins driving. tru tru pe pe c c ty tio tio ty n n hasSuccessor Waypoint Waypoint ITINERARIES AS SEMANTIC MODELS loc ate ate d In lo ng loc lon dIn de itu e In order to personalize the route descriptions, we need a de- ud git de latitu tit ud la e altitude altitu tailed and machine-readable model of the route in order to City de 51.416 6.790 51.409 6.799 adapt it to the user’s knowledge and preferences. Thus, we label have to encode all information that may be helpful to decide 36 m / 118 ft 39 m / 128 ft whether a particular part of the route should be displayed in Duisburg detail, only briefly, or not at all. Figure 1. Semantic route representation enriched with additional in- Itineraries usually are described by a set of waypoints, which formation. represent positions between origin and target location. The idea is now to semantically enhance the waypoints in order An itinerary that has been semantically enriched in that way, to use the semantic information for filtering. finally, facilitates the applications of particular “views” on the route. This mechanism can be used to show or hide cer- We therefore propose a layer model where each layer repre- tain waypoints and create an optimal presentation based on sents a degree of granularity in the route presentation. The the users’ preferences and experiences. lowest layer contains the default route directions including all details of the itinerary, as known from conventional sys- The navigation system could, for instance, only display promi- tems. All upcoming layers show, depending on the level of nent waypoints such as freeways (if the user already has ba- abstraction, only certain parts of the route and provide the sic knowledge of the area). In this case, the directive could related routing instructions. simply be “Head for Freeway 1”, whereas other users would receive a set of detailed instructions leading the driver to the To achieve this goal, we transform the route description into particular freeway. a semantic model, which allows us to characterize each way- 1 http://maps.google.com/ point on the basis of its properties comprehensively. In ad- 2 http://linkedgeodata.org/ 3 dition to the general information of an itinerary, such as lo- http://wiki.openstreetmap.org/ 4 cation coordinates, street name and driving instructions, a http://www.geonames.org/ 5 semantic description includes further information, such as http://www.topocoding.com/ 2 Copyright is held by the author/owner(s) SEMAIS'11, Feb 13 2011, Palo Alto, CA, USA The use of semantic models has different advantages com- The layered model now allows us to switch between the pared to traditional ways routes are displayed in navigation levels-of-detail, such as zooming in or zooming out details systems: of the route presentation. We provide means of manually and automatically switching between the degree of detail as • Standardization: As information comes from various sources, well as choosing the granularity based on user profiles. each with their own formats and specifications, we need a standard to cover all these information. Semantic models Manual Adjustment are flexible enough to import all information provided by A simple way of adjusting the presentation could be by in- the original sources and make them accessible in a unified teracting with the driver. Initially the user should be able to way (e.g. via SPARQL). convey known regions dialogue based at the beginning of the guiding process, where the route has been calculated. There- • Extensibility: The characteristics of semantic models men- fore, he can check the known parts of the itinerary step by tioned in the last paragraph allow integration of new infor- step. Such a procedure is necessary on each guidance where mation sources as well, regardless of their format. no part has been marked as well known, yet. This approach • Ease of data processing: If the models are encoded in is similar to the dialog-driven process described by Richter a standardized language like RDF or OWL, they can be et. al. [9]. queried using the SPARQL Protocol and RDF Query Lan- guage (SPARQL). The significant deviation in our approach is that we use the dialogue initially to customize the whole route guidance on • Additional services: The use of standardized semantic mod- the users individual needs, while Richter provides abstract els lays ground for future services apart from classical instructions by default and requires user interactions at any navigation. Recommender systems that incorporate se- time the user needs more detailed ones. Nevertheless, that mantic data [4], could for instance find filling stations kind of interaction facility we will provide additionally. The with attractive bargains or popular restaurants on the way. user can use a simple widget such as a slider or a turning Ideas for realizing such value-added services have been knob, which he can set up or adjust the level of detail manu- introduced in a german publication written by some of the ally. authors [8]. This functionality is available at each stage of the guidance LAYERS OF DETAIL process to allow the user to react appropriately in any situ- As an intermediate step towards a personalized presenta- ation depending on his individual perception. The opportu- Wenn Sie alle auf dem Bildschirm sichtbaren tion, we create a layered model based on the semantic route, nity to interact with the system at any Details time anzeigen alsoverwenden möchten, enhances Sie the so that the distinct layers reflect a particular level-of-detail. satisfaction, thus, the acceptance of Drucken den Link the automated process neben der Karte. The bottom layer contains all waypoints, whereas the level- can be improved. Figure 3 shows an example of such an in- of-detail decreases on each layer (see Figure 2). SPARQL teraction widget. The user interface provides two buttons for queries can be used as a filtering technique in order to show changing the level of detail. If the user pushes the “More” or hide certain waypoints for each layer. button he receives more details of the itinerary presented on the screen and as driving instructions. A push on the “Less” button on the other hand causes a higher level of abstraction. Figure 2. Particular “views” on the route of a semantically enriched itinerary. Each layer can be seen as a “view” on the itinerary show- ing or hiding certain details. The base-layer corresponds to Take the A3 motorway More Less the way traditional navigators would display a route; it sim- ply contains every single waypoint. If a higher level of ab- straction is selected (either automatically or by hand), the Figure 3. Interaction widget for manually adjust the level of detail. navigator hides certain waypoints and only displays more prominent ones. If the adaptation process is supposed to be User Profiles automatically instead, the level of detail can be adjusted rule- For more sophisticated adaptation effects, dedicated user pro- based or by other means. files cam be maintained to keep track of the user’s knowl- edge and preferences. The system keeps track of all places ADAPTIVE ROUTE GENERATION and routes the user has marked as well known. It then can 3 Copyright is held by the author/owner(s) SEMAIS'11, Feb 13 2011, Palo Alto, CA, USA provide recommendation for the levels of detail on new cal- could a learning system look like that recognizes frequently culated itineraries. In this way, a user knowledge model used route parts or repeatedly visited places? evolves from the users interaction in a step by step man- ner. Figure 4 shows a schematic example of a map repre- REFERENCES senting the users area knowledge, where the dark regions are 1. M. Agrawala and C. Stolte. Rendering effective route assumed as well known and the lighter ones as unfamiliar. maps: improving usability through generalization. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, SIGGRAPH ’01, pages 241–249, New York, NY, USA, 2001. ACM. 2. S. Auer, J. Lehmann, and S. Hellmann. LinkedGeoData: Adding a spatial dimension to the Web of Data. The Semantic Web-ISWC 2009, pages 731–746, 2009. 3. J. Hu, I. Kaparias, and M. Bell. Spatial econometrics models for congestion prediction with in-vehicle route guidance. Intelligent Transport Systems, IET, 3(2):159 –167, 2009. well known area partially known area 4. T. Hussein, T. Linder, W. Gaulke, and J. Ziegler. unknown area Context-aware recommendations on rails. In Workshop on Context-Aware Recommender Systems (CARS-2009) Figure 4. Schematic representation of a users individual area knowl- in conjunction with the 3rd ACM Conference on edge. Dark areas represent well known areas while bright regions are Recommender Systems (ACM RecSys 2009), New York, less known. NY, USA, 2009. Automatic Adjustment 5. Institut für Demoskopie Allensbach. ACTA 2010 - In order to automatically switch between the levels of detail, Innovationen treiben die Märkte. Presentation, October knowledge about the user is necessary. On the one hand, 2010. the system could incorporate information explicitly entered 6. A. Klippel, S. Hansen, K. Richter, and S. Winter. Urban by the user or, alternatively, keep track of his itineraries, in granularities—a data structure for cognitively order to “learn” such a profile. The first case requires user ergonomic route directions. GeoInformatica, interaction, for instance by tagging certain areas on a map as 13(2):223–247, 2009. “well-known” or selecting them from a list of areas. 7. T. Kujala. Efficiency of visual time-sharing behavior: If the system should learn and update the profile automati- the effects of menu structure on poi search tasks while cally based on the driver’s routes, it has to keep track of the driving. In AutomotiveUI ’09: Proceedings of the 1st waypoints on these routes and autonomously mark them as International Conference on Automotive User “rather known” or “well-known”. The level of detail then is Interfaces and Interactive Vehicular Applications, based on the supposed degree of familiarity with the partic- pages 63–70, New York, NY, USA, 2009. ACM. ular route section. 8. D. Münter, T. Hussein, and W. Gaulke. Combining explicit profile information with learning, of course, Kontextabhängige empfehlung von services zur is an opportunity as well. intelligente navigationsunterstützung. In Proceedings of the 1st German Workshop on Human Service Interaction, 2010. DISCUSSION In this paper we presented an approach for enriching the 9. K. Richter, M. Tomko, and S. Winter. A dialog-driven waypoints of itineraries with semantic information, enabling process of generating route directions. Computers, a route guiding system to provide an adaptive user interface. Environment and Urban Systems, 32(3):233–245, 2008. If a driver already knows parts of the itinerary very well, the 10. T. Tenbrink and S. Winter. Variable granularity in route system presents the route by adapting it to the drivers pref- directions. Spatial Cognition & Computation, erences and experience. 9(1):64–93, 2009. During the workshop, we would like to discuss, among other 11. J. Yoon, B. Noble, and M. Liu. Surface street traffic issues, the following questions: What would be better? Tag- estimation. In MobiSys ’07: Proceedings of the 5th ging a route object with semantic information vs. converting international conference on Mobile systems, the whole route as a semantic model? What could be alter- applications and services, pages 220–232, New York, natives for interactive definition of already known waypoints NY, USA, 2007. ACM. (e.g. marking them at the route planning process). How 4 Copyright is held by the author/owner(s) SEMAIS'11, Feb 13 2011, Palo Alto, CA, USA