Constrained Based Systems
Individual Study during the PhD Programme
1. First-Order Predicate Logic
1.1 First-Order
Predicate Logic Syntax
1.2 First-Order
Predicate Logic Semantics
1.3 Inference Rules
in First-Order Predicate Logic
2. Constrained Satisfaction Problem
2.1 Constrained Satisfaction
Problem Definition
2.2 Constrained
Satisfaction Problem Instances
2.3 Constrained
Satisfaction as a State Space Search Problem
2.4 Logical Frame of
Constrained Satisfaction Problem
2.5 Problem
Representation as Theorems Proof
2.6 Problem Representation
in Prolog Language
3. Exhaustive and Heuristic Search
3.1 Basic Method -
Backtracking
3.2 Generate and Test
Method
3.4 Heuristic and
Stochastic Algorithms
3.4 Constrained
Optimisation Problem
4. Constraints Propagation
4.1 Constraints
Propagation
4.2 Local Constraints
Propagation
4.3 Node Consistency,
Arch Consistency, Directional Arch Consistency
4.4 Path Consistency,
Directional Path Consistency, Restricted Path Consistency
4.5 K-Consistency,
(i,j)-Consistency, Reverse Consistency
4.6 Constrained
Satisfaction without Backtracking
5. Prospective Techniques for Solving CSP
5.1 Full Look-Ahead
Backtracking Algorithm
5.2 Partial
Look-Ahead Backtracking Algorithm
5.3 Forward Checking
Backtracking Algorithm
6. Retrospective Techniques for Solving CSP
6.1 Backjumping
Algorithm
6.2 Backmarking
Algorithm
6.3 Conflict-Set
Backtracking Algorithm
7. “Soft” Constraints Modelling
7.1 Constraints
Hierarchies
7.2 Partial
Constraints Satisfaction
7.3 CSP based on
Values and Preferences
8. Constraints Programming Languages
8.1 Prolog Language
8.2 Constraints Logic
Programming Languages
8.3 Constraints
Programming based on Rules
9. Constraints Based Application Modelling
9.1 Constraints
Satisfaction used in Picture Interpretation
9.2 Modelling and
Solving Problems using Constraints
9.3 CSP Modelling
Applications
Bibliography
1. Florea A.
M., Artificial Intelligence Elements, Bucharest 1993
2. Florea A.
M., Boangiu A. G., Logic Foundations of Artificial Intelligence, Bucharest 1994
3. Florea A.
M., Dorohonceanu B, Francu C., Prolog Programming, Bucharest 1997
4. Bartak R.,
Constraint propagation and backtracking-based search, 1995
5. Bartak R.,
Theory and practice of constraint propagation, Proceedings of the 3-rd Workshop
on Constraint Programming in Decision and Control, 2001
6. Bartak R.,
Practical constraints: a tutorial on modelling with constraints, Proceedings of
the 4-th Workshop on Constraint Programming in Decision and Control, 7-16, 2003
7. Bartak R.,
Modelling soft constraints: a survey, Neural Network World, 12, 421-431, 2002
8. Bartak R.,
Foundations of constraint programming, ETAPS 2003
9. Bartak R.,
Constraint programming - what is behind ?, Proceedings of the Workshop on
Constraint Programming in Decision and Control, 1999
10. Bartak R.,
Constraint-based scheduling: an introduction for newcomers, Proceedings of 7-th
IFAC Workshop on Intelligent Manufacturing Systems, Elsevier Science, 2003