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. Ex x ≠ 2.
• Binary Constraint - Constraint that involves pairs of variables. Ex x ≠ y.
• 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.
• Node Consistency - When all values of a single variable's domain will satisfy said variable's unary constraints.
• Arc Consistency - When all values of a single variable's domain will satisfy said variable's binary constraints.

Solution Formats

Backtracking Search - Naive Solution

One of the most naive possible solutions. 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.

Constant Propagation

A much more efficient form of Backtracking Search, which actually accounts for constraints.

Rather than blindly trying all possibilities in the depth-first search tree, it accounts for the constraints at each step, and skips trying states which it can easily tell will fail constraint checks.

For example, when doing color assignment, if "red" is assigned to a region, then it skips attempting states which include red for adjacent neighbors, as these will guaranteed fail and waste computations to check.

Often, this is done by treating each variable as a nodes in a graph, and binary constraints are graph connections. As states are traversed, connections are gradually removed for invalid neighboring states.

This process can then take advantage of:

• Minimum Remaining Values (MRV) - Putting preference on variables which have the fewest remaining legal values, in order to quickly eliminate/evaluate the most restrictive state spaces.
• Degree Heuristic Elimination - When choosing the first variable to examine, starting with the variable that has the most constraints on remaining variables. Doing so tends to significantly reduce branching factor on future choices.
• Least Constraining Value Heuristic - Once a variable has been examined, choosing the value that eliminates the fewest choices from neighboring variables.

Note: Combining the above, we select a variable to examine by finding the most restrictive one. But then choose that variable's value by selecting the least restrictive one.

In this way, we use variable selection to minimize overall nodes in the search tree. But then we use value selection to check for the most likely outcomes first.

Linear Programming

This is mathematically one a much more efficient (but much more complex) solution. It's particularly useful when dealing with very large problems or problems that span many dimensions of variables.

See Linear Programming.