Open constraint programming

doi:10.1016/j.artint.2004.10.005

Return

Open constraint programming

2005-01-01

PRE

Boi Faltings

Santiago Macho-Gonzalez

DOI：10.1016/j.artint.2004.10.005

Original

Original request for help

Save

Abstract

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.

Keywords:

constraint satisfaction

multi-agent systems

distributed AI

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.