Anytime, Complete Algorithm for Finding Utilitarian Optimal Solutions to STPPs

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

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.