Information Technology Reference
In-Depth Information
Chapter 3
Constraint Reasoning
3.1 Introduction
A constraint usually refers to relational expressions which include several
variables and is used to represent conditions which these variables must satisfy.
Constraint representation has been widely applied to various field in artificial
intelligence, including qualitative reasoning, model-based diagnosis, nature
language understanding, scenery analysis, task scheduling, system dispose,
scientific experiment planning, design and analysis of machinery and electronic
apparatus, and so on. Design of constraint satisfaction system is a difficult and
complex task because constraint satisfaction problem is generally a NP problem,
which must be solved by using various strategies and heuristic information. From
the view of knowledge representation, many important problems need studying,
such as representing abstract, default reasoning and so on.
Nonmonotonic
reasoning has enough expressing ability, but it has low reasoning efficiency and
even becomes non-calculated. Furthermore, it is inconvenient for nonmonotonic
reasoning to express heuristic information and meta information. Semantic
network can also represent abstract and default information, however, it does not
have enough problem-solving ability. The constraint representation with abstract
type can remedy deficiencies of both nonmonotonic reasoning and semantic
network in expression. The study on constraint representation and default
reasoning in type hierarchy is very meaningful.
In constraint reasoning, to solve the contradictions between narrowing search
space and controlling reasoning cost, we proposed integrated search algorithm
for constraint satisfaction, and designed appropriate forms of strategy such as
intelligent backtracking, constraint propagation, variable instantiation ordering
etc.. Through combining these strategies organically, the search space can be
107
