A Qualitative Trajectory Calculus to Reason about Moving Point Objects

A Qualitative Trajectory Calculus to Reason about Moving Point Objects

Matthias Delafontaine (Ghent University, Belgium), Seyed Hossein Chavoshi (Ghent University, Belgium), Anthony G. Cohn (University of Leeds, UK) and Nico Van de Weghe (Ghent University, Belgium)
DOI: 10.4018/978-1-61692-868-1.ch004


A number of qualitative calculi have been developed in order to reason about space and time. A recent trend has been the emergence of integrated spatiotemporal calculi in order to deal with dynamic phenomena such as motion. In 2004, Van de Weghe introduced the Qualitative Trajectory Calculus (QTC) as a qualitative calculus to represent and reason about moving objects. This chapter presents a general overview of the principal theoretical aspects of QTC, focusing on the two most fundamental types of QTC. It shows how QTC deals with important reasoning concepts and how calculus can be employed in order to represent raw moving object data.
Chapter Preview


In Artificial Intelligence, several qualitative calculi exist to reason about either spatial or temporal information, the most well-known being Allen’s Interval Calculus (Allen, 1983), which has about 1200 citations in the ISI Web of Science by the time of writing. According to Wolter and Zakharyaschev (2000), an apparent and natural step is to combine both spatial and temporal formalisms in order to reason about spatiotemporal phenomena. A crucial and fundamental phenomenon at this cross-pollination of space and time is motion. Note that motion is an inherently spatiotemporal phenomenon (Peuquet, 2001). Dealing with motion is essential to spatial and geographical information systems, where an evolution from static to dynamic formalisms and representations has been made. A specific type of motion is associated with moving objects, i.e. objects whose position moves through space in time.

In the past decade, the modelling of moving objects has been a hot topic in fields such as GIScience, Artificial Intelligence and Information Systems (Bitterlich, Sack, Sester, & Weibel, 2008). In qualitative reasoning, however, considerable work has focused on the formalisation of motion, or moving objects in particular. Some examples are Muller (2002), Ibrahim (2007), Hallot and Billen (2008), and Kurata and Egenhofer (2009). These approaches have in common that they rely on topological models such as the Region Connection Calculus (Randell, Cui, & Cohn, 1992) or the 9-Intersection model (Egenhofer & Franzosa, 1991). However, a general shortfall of topological models is their inability to further differentiate between disjoint relations. This makes their applicability to represent and reason about continuously moving objects questionable, as in many cases moving objects remain disjoint for most of the time. For instance, cars in a traffic situation are usually disjoint, apart from the exceptional case of an accident.

In order to overcome this inability, the Qualitative Trajectory Calculus (QTC), was proposed by Van de Weghe (2004). QTC provides a qualitative framework to represent and reason about moving objects which enables the differentiation of groups of disconnected objects. The development of QTC has been inspired by some major qualitative calculi: the Region Connection Calculus (Randell, et al., 1992), the temporal Semi-Interval Calculus (Freksa, 1992a), and the spatial Double Cross Calculus (Freksa, 1992b; Zimmerman & Freksa, 1996).

Complete Chapter List

Search this Book: