Bart Peintner, Martha E. Pollack
We present a simple greedy algorithm and a novel complete algorithm for finding utilitarian optimal solutions to Simple Temporal Problems with Preferences. Unlike previous algorithms, ours does not restrict preference functions to be convex. We present experimental results showing that (1) a single iteration of the greedy algorithm produces high-quality solutions, (2) multiple iterations, bounded by the square of the number of constraints, produce near-optimal solutions, and (3) our complete, memory-boundable algorithm has compelling anytime properties and outperforms a branch-andbound algorithm.
Content Area: 6. Constraint Satisfaction and Satisfiability
Subjects: 3.6 Temporal Reasoning; 15.2 Constraint Satisfaction
Submitted: May 9, 2005