Constraints

Adversarial Search

Search Strategy that incorporates opponent’s objectives into their own - used in competitive multi-agent environments

Minimax

A decision rule that minimises loss by maximising an adversary’s gains

1) Evaluate all the moves you can make
2) For each move, assume the opponents plays optimally to counter it
3) Among these worse case scenarios, pick the move that results in the maximum possible gain in the worse case

Constraint

A proposition that defines some restriction on one or more variables.
Constraint is satisfied if the proposition is true.

Linear programming

Minimising constraint problems where the objective is a linear function and the constraints can be represented as linear inequalities.
i.e. Minimising 30A + 55B
Subject to -10A -12B <= -80
and 5A + 2B <= 20

Constraint Satisfaction Problem (CSP)

A problem where values for a set of variables must be found while satisfying a given set of constraints.

Assignment

All nodes have been assigned a value

State

Some (partial) assignment of the CSP.

State space

The set of all possible assignments of nodes

Domain

The set of all possible values a variable can be assigned

Partial assignment

Where only some variables have an assigned value

Consistent

A (partial) assignment is consistent if all assigned values satisfy the constraints.

Complete

An assignment is complete if all values satisfy the constraints.

*NOTE* a complete assignment is always consistent, but a consistent assignment is not always complete

Backtracking for CPS’s

An algorithm that incrementally assigns values to variables while ensuring constraints are satisfied.
If conflict arises, it backtracks by undoing the last assignment and trying a different value.

Heuristics for selecting unassigned variables in CSP’s

Minimum remaining value (MRV):
Select the variable with the smallest domain

…. if two variables have equally small domains

Degree
Select the variable with the highest number of constraints (may be the node with the most connections)

Heuristics for Domain Ordering

Choose the value that eliminates the fewest options for neighbouring variables

Unary Constraint

A constraint involving only one variable

i.e. A >= 0

Binary constraint

A constraint involving only two variables

i.e. A≠B

Global constraint

A constraint involving more than two variables

Node consistency

When all values in a variables domain satisfy that variables unary constraints

i.e. Domain = {1, 2, 3, 4}
Variable = X
Constraint X > 2
enforcing node consistency…
new domain for X = {3, 4}

reason for enforcing node consistency - Shrinks the domain before the search starts making the CSP easier to solve.

Arc consistency

When all values in a variables domain satisfy that variables binary constraints

Constraint propagation

An approach that reduces the number of values a variable can take by propagating constraints through the factor graph

*Node and Arc consistency are both examples of constraint propagation*

Hard constraints

A constraint that must be satisfied in order for a CSP to be solved

Soft constraints

A constraint that may be partially satisfied in order for a CSP to be solved

AC-3 (Arc Consistency - 3)

AC-3 is an algorithm used in CSP’s to enforce Arc consistency. It is built around 2 main functions:

.revise(f, A, B) - Ensures A is arc consistent with B by removing values from A’s domain if they do not satisfy f(A, B)
.AC3(csp) - The main loop which iterates over all constraints and applies ‘revise‘ until no more changes occur.