Optimal Solution Stability in Real Time Optimization
Adrian Petcu and Boi Faltings

Abstract

We define the distributed, real-time combinatorial optimization problem. We propose a general, semantically well-defined notion of solution stability in such systems, based on the cost of change from an already implemented so-lution to the new one. This approach allows maximum flexibility in specifying these costs through the use of stability constraints. We present the first mecha-nism for combinatorial optimization that guarantees optimal solution stability in dynamic environments, based on this notion of solution stability. In contrast to current approaches which solve sequences of static CSPs, our mechanism has a lot more flexibility by allowing for a much finergrained vision of time: each variable of interest can be assigned its own commitment deadlines, allowing for a continuous, real-time optimization process. We show the efficiency of this approach with experimental results from the dis-tributed meeting scheduling domain. We describe an algorithm for the distributed case, but its reduction to a centralized system is straightforward.