You are here

Mixed constraint satisfaction: a framework for decision problems under incomplete knowledge

TitleMixed constraint satisfaction: a framework for decision problems under incomplete knowledge
Publication TypeConference Paper
Year of Publication1996
AuthorsFargier, H, Lang, J, Schiex, T
Conference NameAAAI'96 - Proceedings of the 13th National Conference on Artificial Intelligence
Date Published08/1996
PublisherAAAI Press
Conference LocationPortland, OR, United States
ISBN Number0-262-51091-X
Keywordsalgorithms, constraint satisfaction, decision problem, framework, imcomplete knowledge, mixed CSP
Abstract

Constraint satisfaction is a powerful tool for representing and solving decision problems with complete knowledge about the world. We extend the CSP framework so as to represent decision problems under incomplete knowledge. The basis of the extension consists in a distinction between controllable and uncontrollable variables -- hence the terminology "mixed CSP" -- and a "solution" gives actually a conditional decision. We study the complexity of deciding the consistency of a mixed CSP. As the problem is generally intractable, we propose an algorithm for finding an approximate solution.

URLhttp://dl.acm.org/citation.cfm?id=1892875.1892901