Solving Temporal Constraints in Real Time and in a Dynamic Environment

Contents

In this paper we will present a study of different resolution techniques for solving a Constraint Satisfaction Problem (CSP) in the case of temporal constraints. This later problem is called Temporal Constraint Satisfaction Problem (TCSP). We will mainly focus here on solving TCSPs in real time and in a dynamic environment. 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 Satisfaction Problem). The objective function to minimize is the number of temporal constraint violations. The results of the tests we have performed on randomly generated 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 algorithm represents a better compromise between time and space than the other dynamic arc-consistency algorithms.