Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints
The Interval Algebra (IA) and a subset of the Region Connection Calculus (RCC),namely RCC-8,are the dominant Artificial Intelligence approaches for representing and reasoning about qualitative temporal and topological relations respectively.Such qualitative information can be formulated as a Qualitative Constraint Network (QCN).In this paper,we focus on the minimal labeling problem (MLP) and we propose an algorithm to efficiently derive all the feasible base relations of a QCN.Our algorithm considers chordal QCNs and a new form of partial consistency which we define as mG-consistency.Further,the proposed algorithm uses tractable subclasses of relations having a specific patchwork property for which -consistency implies the consistency of the input QCN.Experimentations with QCNs of IA and RCC-8 show the importance and efficiency of this new approach.
Nouhad Amaneddine Jean-Fran(c)ois Condotta Michael Sioutis
Arab Open University Université Lille-Nord de France CRIL-CNRS,Lens,France Université Pierre et Marie Curie Paris,France
国际会议
北京
英文
696-702
2013-08-01（万方平台首次上网日期，不代表论文的发表时间）