Eugene C. Freuder

AAAI Conference 2024 Conference Paper

Conversational Modeling for Constraint Satisfaction

• Eugene C. Freuder

Many problems, from Sudoku to factory scheduling, can be regarded as constraint satisfaction problems. A key component of real world problem solving is a conversation between a constraint programming expert and a problem domain expert to specify the problem to be solved. This presentation argues that the time is ripe for progress in automating the constraint programmer side of this conversation and suggests promising avenues for this pursuit.

AAAI Conference 2019 Conference Paper

Relating the Structure of a Problem and Its Explanation

• Eugene C. Freuder

As AI becomes more ubiquitous there is increasing interest in computers being able to provide explanations for their conclusions. This paper proposes exploring the relationship between the structure of a problem and its explanation. The nature of this challenge is introduced through a series of simple constraint satisfaction problems.

IJCAI Conference 2009 Conference Paper

• Richard J. Wallace
• Diarmuid Grimes
• Eugene C. Freuder

This paper presents a new analysis of dynamic constraint satisfaction problems (DCSPs) with finite domans and a new approach to solving them. We first show that even very small changes in a CSP, in the form of addition of constraints or changes in constraint relations, can have profound effects on search performance. These effects are reflected in the amenability of the problem to different forms of heuristic action as well as overall quality of search. In addition, classical DCSP methods perform poorly on these problems because there are sometimes no solutions similar to the original one found. We then show that the same changes do not markedly affect the locations of the major sources of contention in the problem. A technique for iterated sampling that performs a careful assessment of this property and uses the information during subsequent search, performs well even when it only uses information based on the original problem in the DCSP sequence. The result is a new approach to solving DCSPs that is based on a robust strategy for ordering variables rather than on robust solutions.

AIJ Journal 2008 Journal Article

Properties of tree convex constraints

• Yuanlin Zhang
• Eugene C. Freuder

It is known that a tree convex network is globally consistent if it is path consistent. However, if a tree convex network is not path consistent, enforcing path consistency on it may not make it globally consistent. In this paper, we investigate the properties of some tree convex constraints under intersection and composition. As a result, we identify a sub-class of tree convex networks that are locally chain convex and strictly union closed. This class of problems can be made globally consistent by arc and path consistency and thus is tractable. Interestingly, we also find that some scene labeling problems can be modeled by tree convex constraints in a natural and meaningful way.

IJCAI Conference 2007 Conference Paper

• Chavalit Likitvivatanavong
• Yuanlin Zhang
• Scott Shannon
• James Bowen
• Eugene C. Freuder

Enforcing arc consistency (AC) during search has proven to be a very effective method in solving Constraint Satisfaction Problems and it has been widely-used in many Constraint Programming systems. Although much effort has been made to design efficient standalone AC algorithms, there is no systematic study on how to efficiently enforce AC during search, as far as we know. The significance of the latter is clear given the fact that AC will be enforced millions of times in solving hard problems. In this paper, we propose a framework for enforcing AC during search (ACS) and complexity measurements of ACS algorithms. Based on this framework, several ACS algorithms are designed to take advantage of the residual data left in the data structures by the previous invocation(s) of ACS. The algorithms vary in the worst-case time and space complexity and other complexity measurements. Empirical study shows that some of the new ACS algorithms perform better than the conventional implementation of AC algorithms in a search procedure.

AAAI Conference 2006 Conference Paper

Constraints: The Ties that Bind

• Eugene C. Freuder

Constraints can serve as a unifying force in artificial intelligence.

AIJ Journal 2005 Journal Article

Constraint-based reasoning and privacy/efficiency tradeoffs in multi-agent problem solving

• Richard J. Wallace
• Eugene C. Freuder

Because of privacy concerns, agents may not want to reveal information that could be of use in problem solving. As a result, there are potentially important tradeoffs between maintaining privacy and enhancing search efficiency in these situations. In this work we show how quantitative assessments of privacy loss can be made within the framework of distributed constraint satisfaction. We also show how agents can make inferences about other agents' problems or subproblems from communications that carry no explicit private information. This can be done using constraint-based reasoning in a framework consisting of an ordinary CSP, which is only partly known, and a system of “shadow CSPs” that represent various forms of possibilistic knowledge. This kind of reasoning in combination with arc consistency processing can speed up search under conditions of limited communication, at the same time potentially undermining privacy. These effects are demonstrated in a simplified meeting scheduling problem where agents propose meetings consistent with their existing schedules while responding to other proposals by accepting or rejecting them. In this situation, we demonstrate some of the conditions under which privacy/efficiency tradeoffs emerge, as well as complications that arise when agents can reason effectively under conditions of partial ignorance.

ECAI Conference 2004 Conference Paper

Adversarial Constraint Satisfaction by Game-Tree Search

• Kenneth N. Brown
• James Little 0002
• Páidí Creed
• Eugene C. Freuder

AAAI Conference 2004 Conference Paper

Tractable Tree Convex Constraint Networks

• Yuanlin Zhang
• Eugene C. Freuder

A binary constraint network is tree convex if we can construct a tree for the domain of the variables so that for any constraint, no matter what value one variable takes, all the values allowed for the other variable form a subtree of the constructed tree. It is known that a tree convex network is globally consistent if it is path consistent. However, if a tree convex network is not path consistent, enforcing path consistency on it may not make it globally consistent. In this paper, we identify a subclass of tree convex networks which are locally chain convex and union closed. This class of problems can be made globally consistent by path consistency and thus is tractable. More interestingly, we also find that some scene labeling problems can be modeled by tree convex constraints in a natural and meaningful way.

AIJ Journal 2002 Journal Article

On forward checking for non-binary constraint satisfaction

• Christian Bessière
• Pedro Meseguer
• Eugene C. Freuder
• Javier Larrosa

Solving non-binary constraint satisfaction problems, a crucial challenge today, can be tackled in two different ways: translating the non-binary problem into an equivalent binary one, or extending binary search algorithms to solve directly the original problem. The latter option raises some issues when we want to extend definitions written for the binary case. This paper focuses on the well-known forward checking algorithm, and shows that it can be generalized to several non-binary versions, all fitting its binary definition. The classical non-binary version, proposed by Van Hentenryck, is only one of these generalizations.

ECAI Conference 2000 Conference Paper

Dispatchability Conditions for Schedules with Consumable Resources

• Richard J. Wallace
• Eugene C. Freuder

ICAPS Conference 2000 Conference Paper

Dispatchable Execution of Schedules Involving Consumable Resources

• Richard J. Wallace
• Eugene C. Freuder

Earlier work on scheduling by autonomous systems has demonstratedthat schedules in the form of simple temporal networks, with intervals of values for possible event-times, can bc maxle"dispatchable~, i. e. executable incrementally in real time with guarantees against failure due to unfortunate cvcnt-time selections. In this work wc show how the property of dispatchabi]ity can be extended to networks that include constraints for consumableresources. Wefirst determine conditions under which a componentof thc network composedof resource constraints associated with a single sequenceof activities that use a resource (’~bout") will support dispatchability. Then we show howto handle interactions betwcenresource and temporal subnetworksto insure dispatchability and howto handle sequences of bouts interspersed with resource release. The results demonstrate that flexible handling of resource use can be safely extended to the execution layer to provide more effective deployment of consumableresource. s.

AIJ Journal 1999 Journal Article

Using constraint metaknowledge to reduce arc consistency computation

• Christian Bessiére
• Eugene C. Freuder
• Jean-Charles Regin

Constraint satisfaction problems are widely used in artificial intelligence. They involve finding values for problem variables subject to constraints that specify which combinations of values are consistent. Knowledge about properties of the constraints can permit inferences that reduce the cost of consistency checking. In particular, such inferences can be used to reduce the number of constraint checks required in establishing arc consistency, a fundamental constraint-based reasoning technique. A general AC-Inference algorithm schema is presented and various forms of inference discussed. A specific algorithm, AC-7, is presented, which takes advantage of a simple property common to all binary constraints to eliminate constraint checks that other arc consistency algorithms perform. The effectiveness of this approach is demonstrated analytically, and experimentally.

AAAI Conference 1997 Conference Paper

Interchangeability Supports Abstraction and Reformulation for Multi-Dimensional Constraint Satisfaction

• Eugene C. Freuder

Interchangeability provides a principled approach to abstraction and reformulation of constraint satisfaction problems. Values are interchangeable if exchanging one for the other in any solution produces another solution. Abstracting a problem by simplifying the constraints can increase interchangeability. Multi-dimensional constraint satisfaction problems can provide natural opportunities for this abstraction process. Multidimensional problems may involve vectors of values, or conjunctive constraints. Utilizing the interchangeability can permit more efficient solutions of the abstracted problem. These solutions can be expanded into smaller reformulations of the original problem. Solving abstracted and then reformulated problems can be considerably more efficient than solving the original problems. We provide data that demonstrates the potential of this abstraction/reformulation process for multi-dimensional problems, and illuminates how its utility can depend on natural problem parameters.

AAAI Conference 1996 Conference Paper

Neighborhood Inverse Consistency Preprocessing

• Eugene C. Freuder

Constraint satisfaction consistency preprocessing methods are used to reduce search effort. Time and especially space costs limit the amount of preprocessing that will be cost effective. A new form of consistency preprocessing, neighborhood inverse consistency, can achieve more problem pruning than the usual arc consistency preprocessing in a cost effective manner. There are two basic ideas: 1) Common forms of consistency enforcement basically operate by identifying and remembering solutions to subproblems for which a consistent value cannot be found for some additional problem variable. The space required for this memory can quickly become prohibitive. Inverse consistency basically operates by removing values for variables that are not consistent with any solution to some subproblem involving additional variables. The space requirement is at worst linear. 2) Typically consistency preprocessing achieves some level of consistency uniformly throughout the problem. A subproblem solution will be tested against each additional variable that constrains any subproblem variable. Neighborhood consistency focuses attention on the subproblem formed by the variables that are all constrained by the value in question. By targeting highly relevant subproblems we hope to “shim the cream”, obtaining a high payoff for a limited cost. Key Ideas

IJCAI Conference 1995 Conference Paper

Extracting Constraint Satisfaction Subproblems

• Eugene C. Freuder
• Paul D. Hubbe

Given a subproblem, S, of a constraint satisfaction problem, we can decompose the problem into a set of disjoint subproblems one of which will be S. This decomposition permits exploitation of problem-specific metaknowledge, a priori or acquired knowledge, about S. If we know that S is unsolvable, for example, the decomposition permits us to extract and then discard S, restricting the search for a solution to the remaining subproblems. A variety of potential uses for the decomposition method are discussed. A specific method that dynamically discards failed subproblems during forward checking search is described, and its utility demonstrated experimentally.

IJCAI Conference 1995 Conference Paper

Generalizing Inconsistency Learning for Constraint Satisfaction

• Eugene C. Freuder
• Richard J. Wallace

Constraint satisfaction problems, where values are sought for problem variables subject to restrictions on which combinations of values are acceptable, have many applications in artificial intelligence. Conventional learning methods acquire individual tuples of inconsistent values. These learning experiences can be generalized. We propose a model of generalized learning, based on inconsistency preserving mappings, which is sufficiently focused so as to be computationally cost effective. Rather than recording an individual inconsistency that led to a failure, and looking for that specific inconsistency to recur, we observe the context of a failure, and then look for a related context in which to apply our experience opportunistically. As a result we leverage our learning power. This model is implemented, extended and evaluated using two simple but important classes of constraint problems.

IJCAI Conference 1995 Conference Paper

Using Inference to Reduce Arc Consistency Computation

• Christian Bessiere
• Eugene C. Freuder
• Jean-Charles Rtgin

Constraint satisfaction problems are widely used in artificial intelligence. They involve finding values for problem variables subject to constraints that specify which combinations of values are consistent. Knowledge about properties of the constraints can permit inferences that reduce the cost of consistency checking. In particular, such inferences can be used to reduce the number of constraint checks required in establishing arc consistency, a fundamental constraint-based reasoning technique. A general AC-Inference schema is presented and various forms of inference discussed. A specific algorithm, AC-7, is presented, which takes advantage of a simple property common to all binary constraints to eliminate constraint checks that other arc consistency algorithms perform. The effectiveness of this approach is demonstrated analytically, and experimentally on real-world problems.

ECAI Conference 1994 Conference Paper

Contradicting Conventional Wisdom in Constraint Satisfaction

• Daniel Sabin
• Eugene C. Freuder

AIJ Journal 1993 Journal Article

The complexity of constraint satisfaction revisited

• Alan K. Mackworth
• Eugene C. Freuder

This paper is a retrospective account of some of the developments leading up to, and ensuing from, the analysis of the complexity of some polynomial network consistency algorithms for constraint satisfaction problems.

IJCAI Conference 1993 Conference Paper

Using Inferred Disjunctive Constraints To Decompose Constraint Satisfaction Problems

• Eugene C. Freuder
• Paul D. Hubhe

Constraint satisfaction problems involve finding values for problem variables that satisfy constraints on what combinations of values are permitted. They have applications in many areas of artificial intelligence, from planning to natural language understanding. A new method is proposed for decomposing constraint satisfaction problems using inferred disjunctive constraints. The decomposition reduces the size of the problem. Some solutions may be lost in the process, but not all. The decomposition supports an algorithm that exhibits superior performance. Analytical and experimental evidence suggests that the algorithm can take advantage of local weak spots in globally hard problems.

ECAI Conference 1992 Conference Paper

Interchangeability Preprocessing Can Improve Forward Checking Search

• Brent W. Benson Jr.
• Eugene C. Freuder

AIJ Journal 1992 Journal Article

Introduction to the special volume on constraint-based reasoning

• Eugene C. Freuder
• Alan K. Mackworth

AIJ Journal 1992 Journal Article

Partial constraint satisfaction

• Eugene C. Freuder
• Richard J. Wallace

A constraint satisfaction problem involves finding values for variables subject to constraints on which combinations of values are allowed. In some cases it may be impossible or impractical to solve these problems completely. We may seek to partially solve the problem, in particular by satisfying a maximal number of constraints. Standard backtracking and local consistency techniques for solving constraint satisfaction problems can be adapted to cope with, and take advantage of, the differences between partial and complete constraint satisfaction. Extensive experimentation on maximal satisfaction problems illuminates the relative and absolute effectiveness of these methods. A general model of partial constraint satisfaction is proposed.

AAAI Conference 1991 Conference Paper

Eliminating Interchangeable Values in Constraint Satisfaction Problems

• Eugene C. Freuder

Constraint satisfaction problems (CSPs) involve finding values for variables subject to constraints on which combinations of values are permitted. This paper develops a concept of intndrangcabilityof CSP values. Fully interchangeable values can be substituted for one another in solutions to the problem. Removing all but one of a set of fully interchangeable values can simplify the search space for the problem without effectively losing solutions. Refinements of the interchangeability concept extend its applicability. Basic properties of interchangeablity and complexity parameters are established. A hierarchy of local interchangeability is defined that permits recognition of some interchangeable values with polynomial time local computation. Computing local interchangeability at any level in this hierarchy to remove values before backtrack search is guaranteed to be cost effective for some CSPs. Several forms of weak interchangeability are defined that permit eliminating values without losing all solutions. Interchangeability can be introduced by grouping values or variables, and can be recalculated dynamically during search. The idea of interchangeability can be abstracted to encompass any means of recovering the solutions involving one value from the solutions involving another.

AAAI Conference 1990 Conference Paper

Complexity of K-Tree Structured Constraint Satisfaction Problems

• Eugene C. Freuder

Trees have played a key role in the study of constraint satisfaction problems because problems with tree structure can be solved efficiently. It is shown here that a family of generalized trees, k-trees, can offer increasing representational complexity for constraint satisfaction problems, while maintaining a bound on computational complexity linear in the number of variables and exponential in k. Additional results are obtained for larger classes of graphs known as partial k-trees. These methods may be helpful even when the original problem does not have k-tree or partial k-tree structure. Specific tradeoffs are suggested between representational power and computational complexity.

IJCAI Conference 1989 Conference Paper

Partial Constraint Satisfaction

• Eugene C. Freuder

A constraint satisfaction problem involves finding values for variables subject to constraints on which combinations of values are allowed. In some cases it may be impossible or impractical to solve these problems completely. We may seek to partially solve the problem in an "optimal" or "sufficient" sense. A formal model is presented for defining and studying such partial constraint satisfaction problems. The basic components of this model are a constraint satisfaction problem, a problem space, and a metric on that space. Algorithms for solving partial constraint satisfaction problems are discussed. A specific branch and bound algorithm is described. Some initial experimental experience with this algorithm is presented.

IJCAI Conference 1985 Conference Paper

Taking Advantage of Stable Sets of Variables in Constraint Satisfaction Problems

• Eugene C. Freuder
• Michael J. Quinn

AIJ Journal 1985 Journal Article

The complexity of some polynomial network consistency algorithms for constraint satisfaction problems

• Alan K. Mackworth
• Eugene C. Freuder

Constraint satisfaction problems play a central role in artificial intelligence. A class of network consistency algorithms for eliminating local inconsistencies in such problems has previously been described. We analyze the time complexity of several node, arc and path consistency algorithms and prove that arc consistency is achievable in time linear in the number of binary constraints. The Waltz filtering algorithm is a special case of the arc consistency algorithm. In the edge labelling computational vision application the constraint graph is planar and so the time complexity is linear in the number of variables.

AAAI Conference 1980 Conference Paper

Information Needed to Label a Scene

• Eugene C. Freuder

AIJ Journal 1980 Journal Article

On the knowledge required to label a picture graph

• Eugene C. Freuder

I analyze the information content of scene labels and provide a measure for the complexity of line drawings. The Huffman-Clowes label set is found to contain surprisingly little additional information as compared to more basic label sets. The complexity of a line drawing is measured in terms of the amount of local labeling required to determine global labeling. A bound is obtained on the number of lines which must be labeled before a full labeling of a line drawing is uniquely determined. Methods are provided for obtaining subsets of lines whose labeling is sufficient to imply the labeling of the remaining lines. I present an algorithm which combines local sensory probing with knowledge of labeling constraints to proceed directly to a labeling analysis of a given scene.