An Approach to Pathfinding for Real-World Situations

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.