Any time, complete algorithm for finding utilitarian optimal solutions to STPPs
Bart Peintner, Martha E. Pollack · 2005
We present a simple greedy algorithm and a novel complete algorithm for finding utilitarian optimal solutions to Simple Temporal Problems with Preferences. Unlike previous algo-rithms, ours does not restrict preference functions to be con-vex. We present experimental results showing that (1) a sin-gle 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 com-pelling anytime properties and outperforms a branch-and-bound algorithm.