Using Topological Stages of Closeness 

Wuersch, M. (1), Caduff, D. (2)

1 Intelligent Spatial Technologies
PO Box 3857
Portland, ME 04104, USA
This email address is being protected from spam bots, you need Javascript enabled to view it This email address is being protected from spam bots, you need Javascript enabled to view it

2 Department of Geography, University of Zurich - Irchel
Winterthurerstr. 190, CH-8057 Zurich, Switzerland
This email address is being protected from spam bots, you need Javascript enabled to view it  

5th International Workshop on Web and Wireless Geographical Information Systems 2005, Lecture Notes in Computer Science, Vol. LNCS 3633, Springer, pp. 31-41, Lausanne, Switzerland 

ABSTRACT. In pedestrian navigation, navigators are free to choose any passable way. Because of this characteristic, accurate route instructions are important when navigating from waypoint to waypoint. In this paper, a theoretical framework is described for dealing with position uncertainty in pedestrian guiding systems. Stages of closeness are defined based on the topological relation between the navigator and a waypoint. These stages of closeness allow for refining route instructions and, therefore, leading to more accurate navigation and increased efficiency of the system.

Introduction

Routes for car navigation are confined to street networks and any instruction given to navigators is always with reference to the underlying network. The ride from Boston to New York, for instance, takes place on the different types of street networks. This system has many constraints associated with it (e.g., lanes, entrances, exits, etc.) and rules (e.g, speed limits, one ways, etc). These rules and constraints, together with the street network provide a forgiving system with regard to user and data inaccuracies. As long as route instructions are not given too late, user location and data inaccuracies do not deter drivers from their chosen route.

Pedestrian navigation, however, is not confined to a network of streets, but in-cludes all passable areas, such as walkways, squares, and open areas, within or out-side buildings. The property of being a decision point is not specific to junctions anymore, but becomes a property associated with the actual position of the pedestrian as pedestrians are free to choose their own path, get on and off street networks any-where and anytime (with exceptions of bridges, walls, etc), take shortcuts, or cross squares. Hence, we define a path for pedestrians as consisting of waypoints. Way-points differ from traditional decision points, such as junctions, as they are not part of the street network, but demarcate points that the navigator passes, independent of the underlying structure (i.e., street, square, walkway). For the sake of simplicity, we confine the extent of this paper to the description of the route in terms of route in-structions for a given path, and not to the generation of the route itself. An example of such a route is illustrated in Figure 1.

Figure 1. Example of a tour indicating the way between start (A) and destination (B) and pass-ing by several attractions along the route. The path consists of waypoints that are not necessar-ily attached to the underlying route network.

Because of the complexity of pedestrian navigation, it is important to provide route instructions at each point along the way. Examples of applications that require this kind of route instructions are GPS-based tourist guides that describe routes with at-tractions, such as sightseeing tours or museum guides. Such route instructions are preferably given ‘just in time’, that is, not too late, but also not too early. In cases where instructions are given too early, navigators might choose the wrong path, while late instructions may result in overshooting, both cases requiring extra instructions and corrections.

The goal of this paper is to provide route instructions that are more accurate under consideration of inaccuracies of the navigator’s position and the location of the way-point. A qualitative measure of how close a navigator is to the next waypoint is de-fined. Based on this qualitative measure, the route instructions are refined, resulting in more accurate and more intuitive navigation. For example, Figure 2a shows a tourist navigating along a chosen route from one waypoint to the other. Because of an inac-curate location determining method, the next waypoint is selected before the user actually gets to it. Figure 2b shows a visual instruction given at the user’s location. If no other instructions are given, the user most likely will turn left without actually reaching the waypoint across the street. Figure 2c shows a refined visual instruction given at the same location. This instruction represents the current situation more accu-rately. It combines instructions on how to reach the next waypoint as well as how to continue when that waypoint is reached, i.e., go straight and then turn left.

Figure 2. (a) An example of a tourist navigating along a route; (b) simple route instruction; (c) refined route instruction.