v-vi Constraint satisfaction is a simple but powerful idea. If we can pose our world knowledge as
a set of local constraints on the values assigned to variables in global solutions to a problem, then when we satisfy those
constraints we solve the problem... For an optimist, a constraint specifies the possible; for a pessimist, equivalently,
the impossible... These restricted, modular knowledge representations are natural to humans... The lesson is that constraint-based
systems are tools that let us make computation more transparent, efficient and reliable - in short, more useful...
The power of making the implicit constraints explicit is that they can, in turn, control the search for global solutions,
quickly terminating impossible partial solutions or sub-problems and avoiding thrashing search behavior. This can
make the search vastly more efficient, sometimes even making apparently intractable problems tractable... One reason
these algorithms are so practical is that we can easily tradeoff the degree of consistency, and thus the level of explicitness,
with the work required to compute it.
xvii A constraint is a restriction on a space of possibilities; it is a piece of knowledge
that narrows the scope of this space. Because constraints arise naturally in most areas of human endeavor, they are the most
general means for formulating regularities that govern our computational, physical, biological, and social worlds... Although
observable in diverse disciplines; they all share one feature in common: they identify the impossible, narrow down the realm
of possibilities, and thus permit us to focus more effectively on the possible.
Formulating problems in terms of constraints has proven useful for modeling fundamental cognitive
activities... as well as having application for engineering tasks... Formulating problems in terms of constraints enables
a natural, declarative formulation of what must be satisfied, without having to say how it should be
satisfied... This book focuses on the fundamental tools and principles that underlie reasoning with constraints
p.1 We regularly encounter constraint in our day-to-day lives... And we regularly engage in solving
constraint satisfaction problems... But consider the complexity encountered when the number of constraints to be
satisfied, and the variables involved, begin to grow... As the complexity of the problem grows, we turn to computers to help
us find an acceptable solution. Computer scientists have devised language to model constraint satisfaction problems
and have developed methods for solving them. The language of constraints is used to model simple cognitive tasks
p.2 every constraint problem must include variables: objects or items that can take on a variety
of values... The second component to every constraint problem is the set of constraints themselves. Constraints are
rules that impose a limitation on the values that a variable, or a combination of variables, may be assigned... A
model that includes variables, their domains, and constraints is called a constraint network, also called
a constraint problem.
p.29 Graph concepts play a central role in capturing the structure of a constraint problem and in its solution
process... A constraint network can be represented by a graph called a primal constraint graph or just a
constraint graph, where each node represents a variable and the arcs connect all nodes whose variables are
included in a constraint scope of the problem. the absence of an arc between two nodes indicates that there is no direct constraint
- one that is specified in the input - between the corresponding variables.
p.51 Knowledge of what is possible is the beginning of happiness. George
Santayana, Little Essays
p.52 In general, the more explicit and tight (but equivalent) constraint networks are, the more
restricted the search space of all partial solutions will be, and consequently, any search becomes more efficient.
p.85 How do we explain how people perform so well on tasks that are theoretically intractable [ JLJ - Difficult
to alleviate, remedy, or cure]? One explanation is to assume that intelligent behavior is actually grounded in approximation
methods that are based on idealized, easy-to-solve models. In other words, we assume people intuitively transform
hard tasks into a series of more manageable, simple tasks, which, taken together, approximate the original task...
Following this line of reasoning, one approach in artificial intelligence is to imitate the assumed human reasoning
process and find ways to idealize (i.e., simplify) the task environment. These simplifications can then be
used to provide either approximate solutions or heuristic advice to guide the search toward an exact solution of the original
problem.
p.117 No matter how much we reason about a problem, after some consideration we are left
with choices, and the only way to proceed is trial and error or guessing and testing... That is,
we must search the space of possible choices.
p.194 The breakout method or constraint weighting can also significantly improve the performance
of a local search. The guiding cost function is a weighted sum of the violated constraints
p.245 Everything should be made as simple as possible, but not one bit simpler. Albert Einstein (attributed)
