White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

An Approach to Pathfinding for Real-World Situations

Cook, Sarah (2018) An Approach to Pathfinding for Real-World Situations. PhD thesis, University of Leeds.

Cook_S_Computing_PhD_2018.pdf - Final eThesis - complete (pdf)
Available under License Creative Commons Attribution-Noncommercial-Share Alike 2.0 UK: England & Wales.

Download (45Mb) | Preview


People plan their routes through new environments every day, but what factors influence these wayfinding decisions? In a world increasingly dependent on electronic navigation assistance devices, finding a way of automatically selecting routes suitable for pedestrian travel is an important challenge. With a greater freedom of movement than vehicular transport, and different requirements, an alternative approach should be taken to find an answer for pedestrian journeys than those taken in cars. Although previous research has produced a number of pedestrian route recommendation systems, the majority of these are restricted to a single route type or user group. The aim of this research was to develop an approach to route suggestion which could recommend routes according to the type of journey (everyday, leisure or tourist) a person is making. To achieve this aim, four areas of research were undertaken. Firstly, six experiments containing 450 participants were used to investigate the preference of seven different environment and route attributes (length, turns, decision points, vegetation, land use, dwellings and points of interest) for two attribute categories (simplicity and attractiveness) and three journey types (everyday, leisure and tourist). These empirically determined preferences were then used to find the rank-orders of the attributes, by comparing more of them simultaneously than earlier studies, and found either new rankings (for attractiveness, leisure journeys and tourist journey) or extended those already known (everyday journeys). Using these ranks and previously accepted relationships, an environment model was defined and built based on an annotated graph. This model can be built automatically from OpenStreetMap data, and is therefore simple enough to be applicable to many geographical areas, but it is detailed enough to allow route selection. Algorithms based on an extended version of Dijkstra’s shortest path algorithm were constructed. These used weighted minimum cost functions linked with attribute ranks, to select routes for different journey types. By avoiding the computational complexity of previous approaches, these algorithms could potentially be widely used in a variety of different platforms, and extended for different groups of users. Finally, the routes suggested by the algorithms were compared to participant recommendations for ‘simple’ routes with five start/end points, and for each of the three journey types (everyday, leisure and tourist). These comparisons determined that only length is required to select simple and everyday routes, but that the multi-attribute cost functions developed for leisure and tourist journeys select routes that are similar to those chosen by the participants. This indicates that the algorithms’ routes are appropriate for people to use in leisure and tourist journeys.

Item Type: Thesis (PhD)
Keywords: Pathfinding, pedestrian navigation
Academic Units: The University of Leeds > Faculty of Engineering (Leeds) > School of Computing (Leeds)
Identification Number/EthosID: uk.bl.ethos.736515
Depositing User: Miss Sarah Cook
Date Deposited: 19 Mar 2018 11:04
Last Modified: 25 Jul 2018 09:56
URI: http://etheses.whiterose.ac.uk/id/eprint/19445

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)