Artificial Intelligence has matured to the point that it is proving useful in many real-world applications. Planning and scheduling in dynamic environments is one such domain. Imagine a robot navigating through a university full of students trying to get from one class to another. As the robot’s environment changes, new constraints are added and removed. In these domains, it is of utmost importance to be able to determine and resolve conflicts that may arise. One typical formulation for these temporal reasoning problems is temporal constraint satisfaction.
Mouhoub studies the applicability of systematic versus nonsystematic search methods for solving dynamic temporal constraint satisfaction problems (DTCSP). He uses a derivative of Allen’s temporal logic to transform the TCSP into a binary CSP (finite domain variables with binary constraints). Constraints are added to the TCSP to form a dynamic TCSP (no constraints are removed in his study). He then compares a systematic method consisting of a combination of path and arc consistency with dynamic backtracking, a min-conflicts random walk search method, and a genetic algorithm on a set of randomly generated TCSPs ranging between 20 and 400 variables with domains of up to 100 values. He shows that the backtracking method is best for smaller problems, and the nonsystematic methods perform better on the larger problems, though he recognizes that they degrade quickly as the problem size grows beyond 100 variables. Both nonsystematic methods perform at about the same rate.
The main contribution of this paper is the presentation of the study. The author presents the problem clearly and elegantly, and then proceeds to describe each technique in detail. The main flaw of the paper is that the author seems unaware of the body of work that focuses on maintaining bounds rather than exact solutions for DTCSPs [1,2]. Exact solutions tend to be brittle, while flexible schedules tend to absorb change more easily, so the state-of-the-art research suggests using these flexible schedules instead.
