Related Work

Wayfinding can be categorized in planning a route and following a route. The two main research areas are: 1) research that aims at shedding light on the question of how humans actually find their way (Arthur & Passini, 1992; Hollands, Patla, & Vickers, 2002; Iachini &Logie,2003; Werner, Krieg-Brückner, Mallot, Schweizer, & Freksa, 1997), and 2) research that aims at supporting humans in the activity of finding the way (Haklay, O’Sullivan, Thurstain-Goodwin, & Schelhorn, 2001; Kray, Laakso, Elting, & Coors, 2003; Tversky & Lee, 1999). The research topics in the second cate-gory include analysis of the characteristics of good route instructions in general (Lovelace, Hegarty, & Montello, 1999), specific aspects of car navigation systems (Burnett, 1998), and investigations on how to provide route instructions to pedestrians (Altai, 2001; May, Ross, Bayer, & Tarkiainen, 2003).

Another emerging aspect of route instructions is the uncertainty derived from dif-ferent sources, i.e., data, sensors, etc. The first model that attempts to consider uncer-tainty in the navigation process is Chown’s PLAN model (1999), which is basically an extension of Kuiper’s TOUR model (1979). Busquets (2003) uses fuzzy set theory to model imprecision in robot navigation, which allows improving the robot’s naviga-tion. Finally, Duckham, Kulik, and Worboys (2003) address the problem of delivering Location-based Services to an agent under imprecision.

The approach followed in this paper complements research on supporting humans and other agents in following a route under constraints. However, unlike most re-search in this field, we do not assume an underlying street network that can be refer-enced, but rather assume a series of waypoints that define a path. The path may follow segments of streets or walkways, but may also cross these. This assumption requires a different approach to describing routes and a different handling of uncertainty, which we will explain in the following sections.