Solving Temporal Constraints in Real Time and in a Dynamic Environment
Malek Mouhoub · 2002
In this paper we will present a study of different res-olution techniques for solving Constraint Satisfaction Problems (CSP) in the case of temporal constraints. This later problem is called Temporal Constraint Sat-isfaction Problem (TCSP). We will mainly focus here on solving TCSPs in real time and in a dynamic en-vironment. Indeed, addressing these two issues is very relevant for many real world applications. Solving a TCSP in real time is an optimization problem that we call MTCSP (Maximal Temporal Constraint Satisfac-tion Problems). The objective function to minimize is the number of temporal constraint violations. The re-sults of the tests we have performed on randomly gen-erated MTCSPs show that the approximation method Min-Conflict-Random-Walk(MCRW) is the algorithm of choice for solving MTCSPs. Comparison study of the different dynamic arc-consistency algorithms for solving dynamic temporal constraint problems in a pre-processing phase demonstrates that the new algorithm we propose and based on a recent arc-consistency al-gorithm represents a better compromise between time and space than the other dynamic arc-consistency al-gorithms.