A Polynomial-Time Algorithm for Simple Temporal Problems with Piecewise Constant Domain Preference Functions

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 19

Automated Reasoning

In this paper, we provide a polynomial-time algorithm for solving an important class of metric temporal problems that involve simple temporal constraints between various events (variables) and piecewise constant preference functions over variable domains. We are given a graph G = (X, E) where X = {X0, X1...Xn} is a set of events (X0 is the "beginning of the world" node and is set to 0 by convention) and e = (Xi, Xj) in E, annotated with the bounds [LB(e), UB(e)], is a simple temporal constraint between Xi and Xj indicating that Xj must be scheduled between LB(e) and UB(e) seconds after Xi is scheduled (LB(e) <= UB(e)). A family of stepwise constant preference functions F = {f_Xi(t): R -> R} specifies the preference attached with scheduling Xi at time t. The goal is to find a schedule for all the events such that all the temporal constraints are satisfied and the sum of the preferences is maximized. Our polynomial-time algorithm for solving such problems (which we refer to as extended simple temporal problems (ESTPs)) has important consequences in dealing with limited forms of disjunctions and preferences in metric temporal reasoning that would otherwise require an exponential search space.