The increasing availability of mobile networks and devices motivate the development of new paradigms of interaction between users, and between a user and the surrounding environment. When the position of a user is known, location-aware applications can adapt their behaviour accordingly to that position. This usual behaviour of location-aware applications can be enhanced in order to turn these applications pro-active, providing services that can be helpful to the user before he/she asks for them. For this kind of behaviour, location-aware applications need to anticipate the user’s position, predicting where the user is going to be in the future. This chapter discusses the prediction of movement in space by looking at the topological constraints existing in the geographical space in which the user is moving. The obtained results show that the topological distance can be used as an alternative or as a complement to the geometrical distance normally used in map-matching techniques.
TopIntroduction
The modelling of the conceptual relationships that exist between spatial objects plays an important role in new application areas based on geographic information. One of these emerging areas is related to context-aware applications. Within this class of applications, the location-aware applications are those that are able to adapt their behaviour accordingly to the location of the user (Dey, 2001). A key aspect of context-aware applications is the easy access to the geographic context of their users. One simple way of describing that context is to describe the place where the mobile user is at in a particular instant of time. The most usual and elementary form of geographic context is therefore the current position of the user, described as a pair of geographic coordinates, or the location, described as an address or other symbolic reference.
The information about the user location is used by these applications to make available a wide range of services that are, hopefully, useful to the users. The services that are provided depend upon the user location and the geographic context in which the user is mapped by the location-aware application. Actions can only be started, e.g. making a specific service available, after the identification of the geographic context where a user can be located. Another potential contribution to the identification of the location of a user is through the use of predictive models to estimate future movements of a person (Ashbrook & Starner, 2003). Several studies have been carried out in order to predict the next user’s location, based on the actual user’s location or the previous available locations of the user (Ashbrook & Starner, 2003; Laasonen, 2005; Marmasse & Schmandt, 2002). The most common approaches used to estimate the user’s position in a mobile environment follow quantitative approaches, in which the previous positions of the user and the estimation of his/her moving velocity, for example, are used as input. There are also other approaches in which the user’s previous behaviour is used to predict the most probable next location. Relaying on user’s current position and past behaviour for prediction processes requires the collection of data over a certain period of time, in order to establish his/her movement pattern. Besides the fact the user needs to be tracked, and privacy issues can arise, some learning time is also required. Moreover, systems trained for a certain geographic region may not perform well while the user is visiting a new region for the first time.
Instead of creating a history of the user to predict his/her next position, this work addresses the prediction of such position by resorting to the topological constraints present in the geographical context in which the user is located. Our aim is to focus on the prediction of the near future positions of cars, and on their use in applications that need to reserve resources or request data for future tasks. Examples include the reservation of network bandwidth in the wireless networks that are expected to be deployed along highways and other roads in the near future, and automatic traffic lights control for emergency vehicles (Yang & Wang, 2007).
Two approaches are discussed in this Chapter. The first approach uses the traditional geometric distance in a predictive model that allocates the user to a specific road segment in a road network. The second one uses the concept of topological distance, following a qualitative approach, in the allocation process. In this last approach, the topological spatial relations that exist between a spatially extended point (representing the uncertainty on the position of a mobile user) and a line (representing objects in which movement in space is possible) are identified (Santos & Moreira, 2007; Santos & Moreira, 2009a). Afterwards, and for the prediction task, two conceptual neighbourhood graphs are identified (Santos & Moreira, 2009b): one following the snapshot model, and a second one following the smooth-transition model (Egenhofer & Al-Taha, 1992). A subset of this smooth-transition model is used in this work.