Artificial Intelligence/Constraint Satisfaction

Constraint Satisfaction Problems are types of real-world problems. The solution is a possible end-state which fits a series of constraints.

For possible methods of solution, see Linear Programming.

General Idea

Constraint Satisfaction Problems have a series of variables (Domain, often denoted D), as well as a series of constraints (often denoted C).

The domain can have any values, but only some of these values will match the problem constraints. When all variables are set and all constraints are met, then the resulting end-state is a solution.

These problems tend to have multiple valid solution states. Depending on the problem, sometimes we just want to find "any solution at all", and sometimes we want "the minimum or maximum solution".

The general idea is to solve complex problems fast, by using the constraints to eliminate large portions of search space at once.

Examples are:

Assignment Problems - Ex: In a college, which teachers teach what classes.
Timetable Problems - Ex: In a college, which classes are offered when, and in which rooms.
Scheduling Problems - Ex: For a business, schedule employees such that all required shifts are covered, employees get breaks, and no employee works too many or too few hours at once.
Building/Factory Layout Problems - When designing a business floor plan, given that certain rooms/processes should be within a certain distance of each other, create a layout which optimizes the overall room layout for employee workflow.
Coloring Problem - Color regions such that no neighboring regions share a color.

Terminology

Unary Constraint - Constraint that involves a single variable. Aka {{{1}}}.
Binary Constraint - Constraint that involves pairs of variables. Aka {{{1}}}.
Higher-Order Constraints - Constraints that involve 3 or more variables.
Soft Constraint - A constraint which can be violated for a valid solution. However, violating the constraint comes at a penalty, making the solution not preferable when other valid solutions are present.
Consistent/Legal Assignment - A state in which no constraints are violated.
Partial Assignment - A state in which only some variables are assigned.
Complete Assignment - A state in which every variable is assigned a value. However, constraints may or may not be violated.
Valid Solution - A state that is both consistent and complete.

Solution Formats

Backtracking Search

One of the more naive solution formats. Acts as a basic uninformed search algorithm. Tends to be very computationally inefficient, as it doesn't really take advantage of "eliminating large portions of search state at once".

Generally assigns values one variable at a time. After each assignment, checks if any constraints were violated.

Assigned values are recorded (in-order), and when any constraint is violated, the algorithm reverts in a depth-first search type format.

Example

ToDo: Describe with images (instead of text) for clarity.

Assigning colors to a region. Only two colors to assign. 4 neighboring regions to assign colors to. Regions are:

1 2
3 4

Symbols are as follows:

x = Unassigned
R = Assigned color "red"
B = Assigned color "blue"

Step 0:

x x
x x

Step 1:

R x
x x

Step 2:

R R
x x

Fails constraint. Backtracks to last branch with untested options.

Step 3:

R B
x x

Step 4:

R B
R x

Fails constraint. Backtracks to last branch with untested options.

Step 5:

R B
B x

Step 6:

R B
B R

Valid solution found.

Linear Programming

This is probably mathematically one of the more efficient solutions. Particularly when dealing with very large problems or problems that span many dimensions of variables.

See Linear Programming.