An initial investigation into searching to satisfy soft temporal constraints

When using Simple Temporal Networks, it may be that not all constraints must be met, rather that they should be met if possible with some degree of preference. To express this, a utility value is added to represent the importance of some temporal constraints. Various search procedures are looked at to try to maximise the total utility whilst still maintaining consistency. It is found that a greedy approach with hill-climbing works well where these soft constraints interact closely and that a greedy start to the hill-climbing is better than a random start.