Robustness, Stability, Recoverability and Reliability in Dynamic Constraint Satisfaction Problems

Abstract

Many real-world problems in Artificial Intelligence (AI) as well as in other areas of computer science and engineering can be efficiently modeled and solved using constraint programming techniques. In many real-world scenarios the problem is partially known, imprecise and dynamic, so that some effects of actions are undesired and/or several un-foreseen incidences or changes can occur. Whereas expressivity, efficiency, and optimality have been the typical goals in the area, several is-sues regarding robustness appear with a clear relevance in dynamic constraint satisfaction problems (DCSPs). However, there is still no a clear and common definition of robustness-related concepts in CSPs. In this paper, we propose two clearly differentiated definitions for robustness and stability in CSP solutions. We also introduce the concepts of recoverability and reliability which arise in temporal DCSPs. All these definitions are based on related well-known concepts addressed in engineering and other related areas.