Uncertainty in dynamic constraint satisfaction problems

摘要

Many real life problems that can be modeled as Constraint Satisfaction Problems (CSPs) come from uncertain and dynamic environments, so the original solution found might become invalid after changes. Here, we study the problem of finding robust solutions for CSPs under the assumptions that domains are significantly ordered and that changes take the form of restrictions or relaxations at the borders of the solution space of the CSPs.