Open constraint programming

Boi Faltings

doi:10.1016/j.artint.2004.10.005

Open constraint programming

2005-01-01

42

PRE

AI

B

Boi Faltings

S

Santiago Macho-Gonzalez

DOI：10.1016/j.artint.2004.10.005

原文链接

原文求助

摘要

En 中文

Traditionally, constraint satisfaction problems (CSP) have assumed closed-world scenarios where all domains and constraints are fixed from the beginning. With the Internet, many of the traditional CSP applications in resource allocation, scheduling and planning pose themselves in open-world settings, where domains and constraints must be discovered from different sources in a network. To model this scenario, we define open constraint satisfaction problems (OCSP) as CSP where domains and constraints are incrementally discovered through a network. We then extend the concept to open constraint optimization (OCOP). OCSP can be solved without complete knowledge of the variable domains, and we give sound and complete algorithms. We show that OCOP require the additional assumption that variable domains and relations are revealed in non-decreasing order of preference. We present a variety of algorithms for solving OCOP in the possibilistic and weighted model. We compare the algorithms through experiments on randomly generated problems. We show that in certain cases, open constraint programming can require significantly less information than traditional methods where gathering information and solving the CSP are separated. This leads to a reduction in network traffic and server load, and improves privacy in distributed problem solving. (C) 2004 Elsevier B.V. All rights reserved.

Keyword:

constraint satisfaction

multi-agent systems

distributed AI

Open constraint programming

摘要

期刊

机构

引用论文