SAT vs CSP: a commentary

arXiv.org Artificial Intelligence

In 2000, I published a relatively comprehensive study of mappings between propositional satisfiability (SAT) and constraint satisfaction problems (CSPs) [Wal00]. I analysed four different mappings of SAT problems into CSPs, and two of CSPs into SAT problems. For each mapping, I compared the impact of achieving arc-consistency on the CSP with unit propagation on the corresponding SAT problems, and lifted these results to CSP algorithms that maintain (some level of ) arc-consistency during search like FC and MAC, and to the Davis- Putnam procedure (which performs unit propagation at each search node). These results helped provide some insight into the relationship between propositional satisfiability and constraint satisfaction that set the scene for an important and valuable body of work that followed. I discuss here what prompted the paper, and what followed.


Extending GENET to Solve Fuzzy Constraint Satisfaction Problems

AAAI Conferences

Despite much research that has been done on constraint satisfaction problems (CSP's), the framework is sometimes inflexible and the results are not very satisfactory when applied to real-life problems. With the incorporation of the concept of fuzziness, fuzzy constraint satisfaction problems (FCSP's) have been exploited. FCSP's model real-life problems better by allowing individual constraints to be either fully or partially satisfied. GENET, which has been shown to be efficient and effective in solving certain traditional CSP's, is extended to handle FCSP's. Through transforming FCSP's into 0 1 integer programming problems, we display the equivalence between the underlying working mechanism of fuzzy GENET and the discrete Lagrangian method. Simulator of fuzzy GENET for single-processor machines is implemented. Benchmarking results confirm its feasibility in tackling CSP's and flexibility in dealing with over-constrained problems.


Constraint-Based Agents

AAAI Conferences

The following paper defines a framework for constraint.based The underlying dynamic realtime environment demands special properties of constralnt-based agents, such as dynamic adaptation and real-time behavior. Underlying models and algorithms have to ensure these features. Introduction The increasing availability of distributed information and computation capacities, from client-server solutions to intranets and the internet, raises new opportunities and requirements on computer science. The agent concept can be used to simplify the solution of large problems by distributing them to some collaborating problem solving units.


Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems Makoto Yokoo

AAAI Conferences

A constraint satisfaction problem (CSP) is a general framework that can formalize various problems in AI, and many theoretical and experimental studies have been performed (Mackworth 1992). In (¥okoo et al. 1992), a distributed constraint satisfaction problem (distributed CSP) is formalized as a CSP in which variables and constraints are distributed among multipie automated agents. Various application problems in DAI which are concerned with finding a consistent combination of agent actions (e.g., distributed resource allocation problems (Conry et al. 1991), distributed scheduling problems (Sycara et al. 1991), distributed interpretation tasks (Mason & Johnson 1989) and multi-agent truth maintenance tasks (Huhns Bridgeland 1991)) can be formalized as distributed CSPs. Therefore, we can consider a distributed CSP as a general framework for DAI, and distributed algorithms for solving distributed CSPs as an important infrastructure in DAI. It must be noted that although algorithms for solving distributed CSPs seem to be similar to parallel/distributed processing methods for solving CSPs (Collin, Dechter, & Katz 1991; Zhang & Mackworth 1991), research motivations are fundamentally different.


Inconsistency and Redundancy Do Not Imply Irrelevance

AAAI Conferences

Relevant information reduces algorithmic effort. In constraint satisfaction, information that a priori appears relevant may prove to be just the opposite. This is likely to prove to be a tricky task. We illustrate the potential pitfalls here in the domain of constraint satisfaction. First, we present what we hope will be a plausible, if crude, definition of what it means for information to be relevant to an algorithm.