Anytime, Complete Algorithm for Finding Utilitarian Optimal Solutions to STPPs

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.

Authors

• Bart Peintner Martha E. Pollack

Keywords

No keywords are indexed for this paper.