1. You will be implementing the Generalized Arc Consistency (GAC) algorithm described in Chapter 4 of the textbook. In particular, you will be implementing the while loop shown in Figure 4.3:

http://artint.info/2e/html/ArtInt2e.Ch4.S4.html#Ch4.F3

2. Assignment The provided zip file contains several Java classes. Be sure to familiarize yourself with all of the classes before you begin implementing your solution. The CSPTester class creates a couple of sample CSP problems and runs arc consistency on them. The first CSP example is the same simple example shown in the lecture and the textbook. Because arc consistency hasn't yet been implemented, you will notice that the variable domains do not change after arc consistency runs. Once you have implemented your solution, the variable domains should be appropriately reduced. You can check your solutions by recreating the same problems in AISpace to see that you are getting the right answers. Follow the pseudo-code instructions provided in the GAC() method's comments. You should only implement the GAC() method in the CSP class. Do not edit any other classes. You will submit only your completed CSP class.

Source code

Arc

// DO NOT EDIT THIS FILE

/*

* A simple class representing an Arc,

* a connection between a Variable and a Constraint.

*/

public class Arc

{

// A Constraint and a Variable

private Constraint con;

private Variable var;

// Constructor

public Arc(Constraint c, Variable v)

{

con = c;

var = v;

}

// Getters

public Constraint getConstraint()

{

return con;

}

public Variable getVariable()

{

return var;

}

public String toString()

{

return "Arc: "+con.toString()+" "+var.toString();

}

}

Assignment

// DO NOT EDIT THIS FILE

import java.util.ArrayList;

import java.util.Collections;

import java.util.Hashtable;

import java.util.List;

/**

* An Assignment assigns values to some or all variables of a CSP.

*

*

*/

public class Assignment

{

/**

* List containing all assigned variables. Positions reflect the the order in which

* the variables were assigned to values.

*/

List variables;

/** Maps variables to their assigned values. */

Hashtable variableToValue;

// Constructor

public Assignment() {

variables = new ArrayList();

variableToValue = new Hashtable();

}

// Return all Variables that are assigned values

public List getVariables() {

return Collections.unmodifiableList(variables);

}

// Return the assigned value of a particular Variable

public Object getAssignment(Variable var) {

return variableToValue.get(var);

}

// Assign a value to a particular Variable

public void setAssignment(Variable var, Object value) {

if (!variableToValue.containsKey(var))

variables.add(var);

variableToValue.put(var, value);

}

// Remove assigned value for a particular Variable

public void removeAssignment(Variable var) {

if (hasAssignmentFor(var)) {

variables.remove(var);

variableToValue.remove(var);

}

}

// Check if a Variable has an assigned value

public boolean hasAssignmentFor(Variable var) {

return variableToValue.get(var) != null;

}

}

Constraint

// DO NOT EDIT THIS FILE

import java.util.List;

// A simple interface that any constraint class must implement.

public interface Constraint

{

// check whether particular variable assignments

// satisfy the constraint.

boolean constraintIsSatisfied(Assignment asn);

// return the variables in the constraint's scope

public List getVariables();

// get the ID of the constraint

public String getID();

}

CSP

// ONLY EDIT THE GAC() METHOD BELOW

import java.util.List;

import java.util.ArrayList;

/*

* STUDENT 1 NAME:

* STUDENT 1 NUMBER:

*

*

* STUDENT 2 NAME:

* STUDENT 2 NUMBER

*/

/*

* A class representing a CSP.

* A CSP consists of Constraints and Arcs to the Variables involved.

*/

public class CSP

{

//private Variable[] vars;

private Constraint[] cons;

private ArrayList toDoArcs;

// Constructor

public CSP(Variable[] v, Constraint[] c)

{

//vars = v;

cons = c;

toDoArcs = new ArrayList();

for (Constraint constraint: cons)

{

for (Variable variable: constraint.getVariables())

{

Arc arc = new Arc(constraint, variable);

toDoArcs.add(arc);

}

}

}

/*

* For binary constraints, return the other variable involved

* in Constraint c with Variable v1.

*/

public Variable getOtherVariable(Variable v1, Constraint c)

{

List allConVars = c.getVariables();

if (allConVars.size() == 2) {

if (v1.equals(allConVars.get(0)))

return allConVars.get(1);

else if (v1.equals(allConVars.get(1)))

return allConVars.get(0);

}

return null;

}

/*

* This is the only method you need to implement.

* Follow the provided pseudo-code.

*/

public void GAC()

{

// WHILE toDoArcs is not empty:

// GET an Arc from toDoArcs

// Arc involves some Variable X and Constraint C

// dx is domain of X

// ndx will be new domain of X

// FOR EACH value val in dx:

// boolean satisfied = false;

// create new Assignment

//SET assignment of X to val

//IF C is binary constraint:

// GET other variable O involved in C

// dO is domain of O

// FOR each value val2 in dO:

// SET assignment of O to val2

// IF constraint is satisfied:

// satisfied = true

//break

//ELSE: (is unary constraint)

// IF constraint is satisfied:

// satisfied = true

//IF satisfied:

// ADD val to ndx

// IF size of ndx < size of dx: (values have been removed)

// set domain of v to ndx

// update toDoArcs

// (add Arcs involving other variables involved in other

// constraints with X)

}

}

CSPTester

import java.util.Arrays;

/*

* The driver class.

* Creates a couple of CSPs and runs arc consistency on them.

* Test out both binary and unary constraints.

*/

public class CSPTester

{

public static void main(String[] args)

{

System.out.println("Binary constraint test");

// Three variables, each with the domain {1,2,3,4}

Variable vA = new Variable("A", Arrays.asList(new Object[]{1,2,3,4}));

Variable vB = new Variable("B", Arrays.asList(new Object[]{1,2,3,4}));

Variable vC = new Variable("C", Arrays.asList(new Object[]{1,2,3,4}));

System.out.println("Variable domains before arc consistency");

System.out.println(vA);

System.out.println(vB);

System.out.println(vC);

Variable[] vars = {vA, vB, vC};

// Two less-than constraints (binary constraints).

// Same simple example shown in the lecture and book.

LessThanConstraint c1 = new LessThanConstraint("A

LessThanConstraint c2 = new LessThanConstraint("B

Constraint[] cons = {c1, c2};

// Create a CSP with these Variables and Constraints.

CSP csp = new CSP(vars, cons);

// Run arc consistency algorithm on the CSP.

csp.GAC();

// After running arc consistency, the domains of the variables

// will either be reduced or the same.

System.out.println("Variable domains after arc consistency");

System.out.println(vA);

System.out.println(vB);

System.out.println(vC);

System.out.println();

// Test a unary constraint too

// (constraint involving one variable)

System.out.println("Unary Constraint Test");

// Three variables again

Variable vX = new Variable("X", Arrays.asList(new Object[]{1,2,3,4}));

Variable vY = new Variable("Y", Arrays.asList(new Object[]{1,2,3,4}));

Variable vZ = new Variable("Z", Arrays.asList(new Object[]{1,2,3,4}));

Variable[] vars2 = {vX, vY, vZ};

// Two binary constraints again

LessThanConstraint c4 = new LessThanConstraint("X

LessThanConstraint c5 = new LessThanConstraint("Y

// One unary constraint -

// Says Z has to be less than 4

InvalidUnaryValueConstraint c6 = new InvalidUnaryValueConstraint("Z<4", vZ);

Constraint[] cons2 = {c4, c5, c6};

System.out.println("Variable domains before arc consistency");

System.out.println(vX);

System.out.println(vY);

System.out.println(vZ);

// Create a second CSP.

CSP csp2 = new CSP(vars2, cons2);

// Run arc consistency on it.

csp2.GAC();

// Check the variable domains after running arc consistency.

System.out.println("Variable domains after arc consistency");

System.out.println(vX);

System.out.println(vY);

System.out.println(vZ);

}

}

InvalidUnaryValueConstraint

// DO NOT EDIT THIS FILE

import java.util.ArrayList;

import java.util.List;

/*

* A unary Constraint that says a particular individual Variable cannot have certain values.

*/

public class InvalidUnaryValueConstraint implements Constraint

{

// A single Variable (unary)

private Variable var1;

private List variablesInScope;

private String constraintID;

// Constructor

public InvalidUnaryValueConstraint(String cid, Variable var1)

{

constraintID = cid;

this.var1 = var1;

variablesInScope = new ArrayList(1);

variablesInScope.add(var1);

for (Variable v : variablesInScope)

{

v.addConstraint(this);

}

}

public String getID()

{

return constraintID;

}

public List getVariables()

{

return variablesInScope;

}

/*

* This particular Constraint is only satisfied if the Variable

* has a value less than 4.

*/

public boolean constraintIsSatisfied(Assignment asn)

{

Integer val1 = (Integer) asn.getAssignment(var1);

return (val1 < 4);

}

public String toString()

{

return constraintID;

}

}

LessThanConstraint

// DO NOT EDIT THIS FILE

import java.util.ArrayList;

import java.util.List;

/*

* A binary constraint specifying that one Variable

* has to be less than another Variable.

*/

public class LessThanConstraint implements Constraint

{

// Two variables involved in Constraint

private Variable var1;

private Variable var2;

// Keep track of the Variables involved in the Constraint

private List variablesInScope;

// A simple ID for each Constraint

private String constraintID;

// Constructor takes ID and two Variables

public LessThanConstraint(String cid, Variable var1, Variable var2)

{

constraintID = cid;

this.var1 = var1;

this.var2 = var2;

variablesInScope = new ArrayList(2);

variablesInScope.add(var1);

variablesInScope.add(var2);

for (Variable v: variablesInScope)

{

v.addConstraint(this);

}

}

public String getID()

{

return constraintID;

}

public List getVariables()

{

return variablesInScope;

}

// Given an Assignment of values to Variable,

// check whether this Constraint is satisfied.

// In this case, constraint is only satisfied if

// val1 < val 2.

public boolean constraintIsSatisfied(Assignment asn)

{

Integer val1 = (Integer) asn.getAssignment(var1);

Integer val2 = (Integer) asn.getAssignment(var2);

return val1 < val2;

}

public String toString()

{

return constraintID;

}

}

Variable

// DO NOT EDIT THIS FILE

import java.util.ArrayList;

import java.util.List;

/*

* A simple class representing variables.

* A variable is associated with a domain (values it can take)

* and may be involved with constraints.

*/

public class Variable

{

// simple String ID for a Variable

private String variableID;

// List of values a Variable can take

private List