Constraint Satisfaction Methods for Qualitative Spatial and Temporal Reasoning
Dr Jochen Renz (National ICT Australia, Sydney)
CSL SEMINAR SERIESDATE: 2005-08-29
TIME: 15:40:00 - 16:25:00
LOCATION: RSISE Seminar Room, ground floor, building 115, cnr. North and Daley Roads, ANU
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
Knowledge about space and time is an essential part of intelligent systems. Qualitative spatial and temporal representation and reasoning tries to represent spatial and temporal information similar to how humans appear to communicate and conceptualise this information. Namely, by specifying qualitative relationships between spatial and temporal entities.
Reasoning within this framework is essentially a constraint satisfaction problem where relations constrain possible instantiations of variables over spatial and temporal entities. Therefore, constraint satisfaction methods such as backtracking and path-consistency are typically used for solving spatial and temporal reasoning problems but also for analysing computational properties of these problems. However, there is one major difference between standard constraint satisfaction problems and spatial and temporal ones: Spatial and temporal constraint satisfaction problems usually have infinite domains, ie there is an infinite number of spatial/temporal entities that can be assigned to the variables. This makes it impossible in many cases to verify correctness of the main reasoning steps and might lead to wrong results.
In the past fifteen years researchers have tried to come up with criteria for the applicability of constraint satisfaction methods to spatial and temporal reasoning, but without success. In this talk I present a general solution to this problem. I will introduce a new concept "closure under constraints" which turns out to be a general criterion of whether constraint satisfaction methods can be applied to spatial and temporal reasoning problems. I will analyse the effects of this criterion on the commonly used methods and give a roadmap of how spatial and temporal calculi should be properly defined and analysed. As a side effect it turns out that several results in the literature are wrong.
BIO:
Dr Jochen Renz is a researcher at the Knowledge Representation and Reasoning Program of NICTA Kensington. He commenced his academic career as a researcher at the Foundations of Artificial Intelligence group at the University of Freiburg, Germany, where he worked within the interdisciplinary DFG priority program on Spatial Cognition. After finishing his PhD, Dr Renz held a postdoctoral position at the WITAS group of the University of Linkoping, Sweden, working on the Unmanned Aerial Vehicle project. He was rewarded a two-year Marie Curie Postdoctoral Fellowship of the European Commission which he spent at the Database and Artificial Intelligence group at the Technical University of Vienna, Austria. After his Habilitation at TU Vienna he joined the NICTA KRR program. Dr Renz's research background is in Artificial Intelligence. In particular, in the fields of qualitative spatial and temporal reasoning, computational complexity, constraint satisfaction, efficient algorithms and cognitive aspects. He solved some of the long-standing open problems in qualitative spatial and temporal reasoning and also published a book on this topic. He is currently working on different applications of spatial and temporal reasoning such as bioinformatics, traffic management, and cell-phone localisation.
