A Personalised Routing Algorithm

Modelling "Familiarity" in Proposing A to B Routes


`Would you tell me, please, which way I ought to go from here?'
`That depends a good deal on where you want to get to,' said the Cat.
`I don't much care where--' said Alice.
`Then it doesn't matter which way you go,' said the Cat.
`--so long as I get somewhere,' Alice added as an explanation.
`Oh, you're sure to do that,' said the Cat, `if you only walk long enough.'

- Lewis Carol, Alice in Wonderland



Research Context

In our everyday life we often find ourselves navigating from place A to place B, increasingly using mobile applications to assist this navigation (Schmid 2010, Savage 2011, Zandbergen and Barbeau 2011). Efficiency is mostly related to the shortest route (Mooney and Winstanley 2006, Lloyd 2010), however this might not necessarily be the preferred route (Golledge 1999). People like to take advantage of places they know, as this requires less cognitive energy and therefore feels easier (Golledge et al. 1990, Lovelace and Hegarty 1999, Papinski, Scott et al. 2009, Pahlavani and Delavar 2014). This research paper addresses the question why the preferred route pedestrians take to get from A to B is not necessarily the shortest route. The assumption is tested that the concept of familiarity affects route choice decisions.

The aim is to improve navigational solutions for pedestrians in urban environments by taking into account familiarity of their environment, creating a quantitative measure for familiarity and incorporating this in Dijkstra’s Shortest Path algorithm efficiently. This involves two objectives:

Quantitative shape comparison measures, such as the Discrete Fréchet Distance, were used to explore the differences between routes in more depth. Participants were asked to draw on paper maps the routes they would take from origin to destination, as a method of validation for the use of the Familiarity Index as a prediction for route choice. The research concludes that it is possible to quantify and implement familiarity as an edge weight and that a simulation on the basis of this concept is accurate to a certain extent.

Methodology

As the locational awareness and accuracy of our mobile devices continues to improve (Schmid and Richter 2006, Savage 2011), it fuels a trend in research analysing and extraction of locational data for the creation of (spatial) user profiles that can be used in Location Based Services (Papinski, Scott et al. 2009, Schmid 2010, Zandbergen and Barbeau 2011, Pahlavani and Delavar 2014). GPS trajectories were extracted from mobile phones from ten participants to create spatial user profiles. The following research questions are answered:

GPS trajectory data was used to quantify familiarity based on a revisit day count and built a Familiarity Index (Dijkstra 1959, Corley and Moon 1985).




As a validation of the predictive possibilities of the model, participants were asked to draw routes on paper maps. They were also interviewed for reasons as to why route choices were made. Interview outcomes were used to qualitatively assess the model predictions. The quality of the predicted routes is quantitatively assessed by comparing:

Implementation Environment

OpenStreetMaps data was used as input street network. The Network Analyst extension available in ESRI’s ArcGIS 10.1 was used for solving shortest path problems. The extension makes use of Dijkstra’s Shortest Path algorithm. MATLAB was used to make Discrete Fréchet Distance calculations.

Key Findings

From the results the following key conclusions can be drawn:

  1. People travel 15% longer than the Shortest Path: All participants travelled longer routes than the route calculated by Dijkstra’s Algorithm based on distance only.

  2. People do not do what they say they would do: The trajectories between what people have drawn on the paper maps and the results from their GPS trajectories do not correspond. This might be due to lacking GPS point observations or errors in recording them, or it could be caused by too few days of recording (how many days do you have to track someone on average to get a good enough basis for familiarity of a place?), but it also shows that people do not do what they say they would do.

  3. Familiarity can be quantified and incorporated as an edge weight for Dijkstra’s algorithm: By gathering GPS data from mobile phones familiarity can be quantified and successfully incorporated as an edge weight in an Open Street Maps road network using the Familiarity Index, to be solved with Dijkstra’s Shortest Path algorithm. This can be seen from both the quantitative and the qualitative results conducted for this research. People are willing to travel longer routes to navigate through familiar space. Qualitative results suggest this is related to the comfort of a familiar environment and less cognitive energy that is required to navigate through this known space.

Want to take this research further? Some suggestions:

The “time” aspect of familiarity has not been incorporated in the current Familiarity Index, due to a lack of empirical research in what the effect of time is on spatial familiarity of a person – how long does it take for a person to forget a place? Or parts of a place or route? Familiarity decays or strengthens over time. The GPS date and time stamps do include valuable time information and this could be explored and used.

Furthermore, it would be interesting to look at possibilities of reducing the amount of navigational information based on a person’s familiarity, giving people instructions like “walk to the top of the mound (because the system knows that you are familiar with this place), from there take the street sloping down on your right hand side”. This involves more research in familiarity in semantics and potentially looking into the value that specific “places” have for people and their familiarity of a place. The role a web map (for example on a mobile phone) and the type of information and instructions shown on the map will have to be explored, a good starting point for this would be the research by Smith (2010).

Key References

Supervisor: William Mackaness

Golledge, R. G. (1999). Wayfinding Behaviour: Cognitive Mapping and Other Spatial Processes. Baltimore, Maryland, U.S.A., The Johns Hopkins University Press.

Lloyd, C. D. (2010). Spatial Data Analysis: An Introduction for GIS users. Oxford, Oxford University Press.

Lovelace, K. L. and M. Hegarty (1999). Elements of Good Route Directions in Familiar and Unfamiliar Environments. Spatial Information Theory: Cognitive and Computational Foundations of Geographic Information Science. D. M. M. C. Freska. Berlin, Springer: 65 - 82

Mooney, P. and A. Winstanley (2006). "An evolutionary algorithm for multicriteria path optimization problems." International Journal of Geographical Information Science 20(4): 401-423.

Pahlavani, P. and M. R. Delavar (2014). "Multi- Criteria Route Planning Based on a Driver’s Preferences in Multi- Criteria Route Selection." Transportation Research Part C: Emerging Technologies 40: 14-35.

Papinski, D., et al. (2009). "Exploring the Route Choice Decision- Making Process: A Comparison of Planned and Observed Routes Obtained using Person- Based GPS." Transportation Research Part F: Traffic Psychology and Behaviour 12(4): 347-358.

Savage, S., et al. (2011). I'm Feeling LoCo: A Location Based Context Aware Recommendataion System. Intenrational Symposium on Location- Based Services, Vienna, Springer.

Schmid, F. (2010). Personal Wayfinding Assistance. Dissertation zur Erlangung des Grades eines Doktors der Ingenieurwissenschaften. Bremen, Universitat Bremen.

Schmid, F. and K.-F. Richter (2006). "Extracting Places from Locational Data Streams." UbiGIS 2006 - Second International Workshop on Ubiquitous Geographical Information Services.

Zandbergen, P. A. and S. J. Barbeau (2011). "Positional Accuracy of Assisted GPS Data from High-Sensitivity GPS-enabled Mobile Phones." Journal of Navigation 64(03): 381-399.