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.