CSPの新しい展開:分散/動的/不完全CSP
横尾 真, 平山 勝敏
人工知能学会誌, Vol.12, No.3, 1997.


The conventional Constraint Satisfaction Problem (CSP) framework assumes that a given problem is solved by a single agent that has all knowledge of the problem, the environment is static, i.e., a given problem will not change over time, and a solution must satisfy all of given constraints completely. In this survey, we describe several extensions of the CSP framework, i.e., a distributed CSP in which multiple agents are involved, a dynamic CSP in which the problem is changed dynamically, and a partial CSP in which the goal is to find an incomplete but acceptable solution. For each extension, we show the problem formalization, example/application problems, and available techniques/algorithms.