Solving and learning a tractable class of soft temporal problems: theoretical and experimental results

Often we need to work in scenarios where events happen over time and preferences are associated with event distances and durations. Soft temporal constraints allow one to describe in a natural way problems arising in such scenarios. In general, solving soft temporal problems requires exponential time in the worst case, but there are interesting subclasses of problems which are polynomially solvable. In this paper we identify one of such subclasses, that is, simple fuzzy temporal problems with semi-convex preference functions, giving tractability results. Moreover, we describe two solvers for this class of soft temporal problems, and we show some experimental results. The random generator used to build the problems on which tests are performed is also described. We also compare the two solvers highlighting the tradeoff between performance and robustness. Sometimes, however, temporal local preferences are difficult to set, and it may be easier instead to associate preferences to some complete solutions of the problem. To model everything in a uniform way via local preferences only, and also to take advantage of the existing constraint solvers which exploit only local preferences, we show that machine learning techniques can be useful in this respect. In particular, we present a learning module based on a gradient descent technique which induces local temporal preferences from global ones. We also show the behavior of the learning module on randomly-generated examples.