R167  
Robust Solutions in Unstable Optimization Problems
Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, and Rina Dechter

Abstract
We consider constraint optimization problems where costs (or preferences) are all given,
but some are tagged as possibly unstable, and provided with a range of alternative values.
We also allow for some uncontrollable variables, whose value cannot be decided by the
agent in charge of taking the decisions, but will be decided by Nature or by some other
agent. These two forms of uncertainty are often found in many scheduling and planning
scenarios. For such problems, we define several notions of desirable solutions. Such
notions take into account not only the optimality of the solutions, but also their degree
of robustness (of the optimality status, or of the cost) w.r.t. the uncertainty present
in the problem. We provide an algorithm to find solutions accordingly to the considered
notions of optimality, and we study the properties of these algorithms. For the
uncontrollable variables, we propose to adopt a variant of classical variable elimination,
where we act pessimistically rather than optimistically.
[pdf] 