Artificial Intelligence - Chapter 6 with Java
MINES Saint-Etienne

Table of Contents

Introduction

The goal of this tutorial is to understand how to (i) model constraint satisfaction problems and (ii) how to implement the solving algorithms as described in AIMA. We take inspiration here from the algorithm provided by AIMA-Java Project. The slides containing the pseudocode are available here.

Modeling CSPs

As to focus one the CSP modeling and the implementation of search algorithms, we provide here some reusable code.

The CSP class

The first important structure we use is the CSP class. To define a particular problem to solve, you must extend this class. 

package fr.emse.ai.csp.core;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Hashtable;
import java.util.List;

public class CSP {

    private List<Variable> variables;
    private List<Domain> domains;
    private List<Constraint> constraints;

    private Hashtable<Variable, Integer> varIndexHash;
    private Hashtable<Variable, List<Constraint>> cnet;

    public CSP() {
        variables = new ArrayList<Variable>();
        domains = new ArrayList<Domain>();
        constraints = new ArrayList<Constraint>();
        varIndexHash = new Hashtable<Variable, Integer>();
        cnet = new Hashtable<Variable, List<Constraint>>();
    }

    public CSP(List<Variable> vars) {
        this();
        for (Variable v : vars)
            addVariable(v);
    }

    protected void addVariable(Variable var) {
        if (!varIndexHash.containsKey(var)) {
            Domain emptyDomain = new Domain(Collections.emptyList());
            variables.add(var);
            domains.add(emptyDomain);
            varIndexHash.put(var, variables.size() - 1);
            cnet.put(var, new ArrayList<Constraint>());
        } else {
            throw new IllegalArgumentException("Variable with same name already exists.");
        }
    }

    public List<Variable> getVariables() {
        return Collections.unmodifiableList(variables);
    }

    public int indexOf(Variable var) {
        return varIndexHash.get(var);
    }

    public Domain getDomain(Variable var) {
        return domains.get(varIndexHash.get(var));
    }

    public void setDomain(Variable var, Domain domain) {
        domains.set(indexOf(var), domain);
    }

    public void removeValueFromDomain(Variable var, Object value) {
        Domain currDomain = getDomain(var);
        List<Object> values = new ArrayList<Object>(currDomain.size());
        for (Object v : currDomain)
            if (!v.equals(value))
                values.add(v);
        setDomain(var, new Domain(values));
    }

    public void addConstraint(Constraint constraint) {
        constraints.add(constraint);
        for (Variable var : constraint.getScope())
            cnet.get(var).add(constraint);
    }

    public List<Constraint> getConstraints() {
        return constraints;
    }

    public List<Constraint> getConstraints(Variable var) {
        return cnet.get(var);
    }

    public Variable getNeighbor(Variable var, Constraint constraint) {
        List<Variable> scope = constraint.getScope();
        if (scope.size() == 2) {
            if (var.equals(scope.get(0)))
                return scope.get(1);
            else if (var.equals(scope.get(1)))
                return scope.get(0);
        }
        return null;
    }

    public CSP copyDomains() {
        CSP result = new CSP();
        result.variables = variables;
        result.domains = new ArrayList<Domain>(domains.size());
        result.domains.addAll(domains);
        result.constraints = constraints;
        result.varIndexHash = varIndexHash;
        result.cnet = cnet;
        return result;
    }
}

This class implements the structure of a CSP, i.e. a set of variables, a set of domains and a set of constraints (and some util methods), as stated in AIMA chapter 6. The variables are defined using the Variable class. In short, a variable is only defined by its name (a String): 

package fr.emse.ai.csp.core;

public class Variable {
    private String name;

    public Variable(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public String toString() {
        return name;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null)
            return false;
        if (obj.getClass() == getClass())
            return this.name.equals(((Variable) obj).name);
        return false;
    }

    @Override
    public int hashCode() {
        return name.hashCode();
    }
}

To define constraints, we need to implement the Constraint interface: 

package fr.emse.ai.csp.core;

import java.util.List;

public interface Constraint {
    List<Variable> getScope();    
    boolean isSatisfiedWith(Assignment assignment);
}

It has only two methods:

  • getScope() which returns the set of variables in the scope of this constraint,
  • isSatisfiedWith() which returns true if the constraint is satisfied for a given assignment.

An Assignment assigns values to some or all variables of a CSP. This class allows to check if the assignment is consistent with some constraints, if it is complete (all variables are assigned), or if it is solution for a given CSP. 

package fr.emse.ai.csp.core;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Hashtable;
import java.util.List;

public class Assignment {

    List<Variable> variables;
    Hashtable<Variable, Object> variableToValue;

    public Assignment() {
        variables = new ArrayList<Variable>();
        variableToValue = new Hashtable<Variable, Object>();
    }

    public List<Variable> getVariables() {
        return Collections.unmodifiableList(variables);
    }

    public Object getAssignment(Variable var) {
        return variableToValue.get(var);
    }

    public void setAssignment(Variable var, Object value) {
        if (!variableToValue.containsKey(var))
            variables.add(var);
        variableToValue.put(var, value);
    }

    public void removeAssignment(Variable var) {
        if (hasAssignmentFor(var)) {
            variables.remove(var);
            variableToValue.remove(var);
        }
    }

    public boolean hasAssignmentFor(Variable var) {
        return variableToValue.get(var) != null;
    }

    public boolean isConsistent(List<Constraint> constraints) {
        for (Constraint cons : constraints)
            if (!cons.isSatisfiedWith(this))
                return false;
        return true;
    }

   public boolean isComplete(List<Variable> vars) {
        for (Variable var : vars) {
            if (!hasAssignmentFor(var))
                return false;
        }
        return true;
    }

    public boolean isComplete(Variable[] vars) {
        for (Variable var : vars) {
            if (!hasAssignmentFor(var))
                return false;
        }
        return true;
    }

    public boolean isSolution(CSP csp) {
        return isConsistent(csp.getConstraints())
                && isComplete(csp.getVariables());
    }

    public Assignment copy() {
        Assignment copy = new Assignment();
        for (Variable var : variables) {
            copy.setAssignment(var, variableToValue.get(var));
        }
        return copy;
    }

    @Override
    public String toString() {
        boolean comma = false;
        StringBuffer result = new StringBuffer("{");
        for (Variable var : variables) {
            if (comma)
                result.append(", ");
            result.append(var + "=" + variableToValue.get(var));
            comma = true;
        }
        result.append("}");
        return result.toString();
    }
}

Variables takes their values within domains. To define them, we need to implement the Domain class, which is a subclass of Iterable (see http://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html): 

package fr.emse.ai.csp.core;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import fr.emse.ai.util.ArrayIterator;

public class Domain implements Iterable<Object> {

    private Object[] values;

    public Domain(List<?> values) {
        this.values = new Object[values.size()];
        for (int i = 0; i < values.size(); i++)
            this.values[i] = values.get(i);
    }

    public Domain(Object[] values) {
        this.values = new Object[values.length];
        for (int i = 0; i < values.length; i++)
            this.values[i] = values[i];
    }

    public int size() {
        return values.length;
    }

    public Object get(int index) {
        return values[index];
    }

    public boolean isEmpty() {
        return values.length == 0;
    }

    public boolean contains(Object value) {
        for (Object v : values)
            if (v.equals(value))
                return true;
        return false;
    }

    @Override
    public Iterator<Object> iterator() {
        return new ArrayIterator<Object>(values);
    }

     public List<Object> asList() {
        List<Object> result = new ArrayList<Object>();
        for (Object value : values)
            result.add(value);
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Domain) {
            Domain d = (Domain) obj;
            if (d.size() != values.length)
                return false;
            else
                for (int i = 0; i < values.length; i++)
                    if (!values[i].equals(d.values[i]))
                        return false;
        }
        return true;
    }

    @Override
    public int hashCode() {
        int hash = 9; // arbitrary seed value
        int multiplier = 13; // arbitrary multiplier value
        for (int i = 0; i < values.length; i++)
            hash = hash * multiplier + values[i].hashCode();
        return hash;
    }

    @Override
    public String toString() {
        StringBuffer result = new StringBuffer("{");
        boolean comma = false;
        for (Object value : values) {
            if (comma)
                result.append(", ");
            result.append(value.toString());
            comma = true;
        }
        result.append("}");
        return result.toString();
    }
}

An example of CSP modeling

To be more concrete, let's take an example of a simple CSP, the graph coloring problem of Australia (see Chapter 6): 

package fr.emse.ai.csp.australia;


import fr.emse.ai.csp.core.CSP;
import fr.emse.ai.csp.core.Domain;
import fr.emse.ai.csp.core.NotEqualConstraint;
import fr.emse.ai.csp.core.Variable;

public class MapCSP extends CSP {
    public static final Variable NSW = new Variable("NSW");
    public static final Variable NT = new Variable("NT");
    public static final Variable Q = new Variable("Q");
    public static final Variable SA = new Variable("SA");
    public static final Variable T = new Variable("T");
    public static final Variable V = new Variable("V");
    public static final Variable WA = new Variable("WA");
    public static final String RED = "RED";
    public static final String GREEN = "GREEN";
    public static final String BLUE = "BLUE";

    public MapCSP() {
        addVariable(NSW);
        addVariable(WA);
        addVariable(NT);
        addVariable(Q);
        addVariable(SA);
        addVariable(V);
        addVariable(T);

        Domain colors = new Domain(new Object[]{RED, GREEN, BLUE});

        for (Variable var : getVariables())
            setDomain(var, colors);

        addConstraint(new NotEqualConstraint(WA, NT));
        addConstraint(new NotEqualConstraint(WA, SA));
        addConstraint(new NotEqualConstraint(NT, SA));
        addConstraint(new NotEqualConstraint(NT, Q));
        addConstraint(new NotEqualConstraint(SA, Q));
        addConstraint(new NotEqualConstraint(SA, NSW));
        addConstraint(new NotEqualConstraint(SA, V));
        addConstraint(new NotEqualConstraint(Q, NSW));
        addConstraint(new NotEqualConstraint(NSW, V));
    }
}

This problem has a fixed number of variables (one for each state) and non-equality constraints between neighboring states. All the variable have the same domain (red, green, blue). Constraints are defined using a NotEqualConstraint (which implements the Constraint interface) which holds true iff the values of the two constrained variables are different: 

package fr.emse.ai.csp.core;

import java.util.ArrayList;
import java.util.List;

public class NotEqualConstraint implements Constraint {

    private Variable var1;
    private Variable var2;
    private List<Variable> scope;

    public NotEqualConstraint(Variable var1, Variable var2) {
        this.var1 = var1;
        this.var2 = var2;
        scope = new ArrayList<Variable>(2);
        scope.add(var1);
        scope.add(var2);
    }

    @Override
    public List<Variable> getScope() {
        return scope;
    }

    @Override
    public boolean isSatisfiedWith(Assignment assignment) {
        Object value1 = assignment.getAssignment(var1);
        return value1 == null || !value1.equals(assignment.getAssignment(var2));
    }
}

Look carefully at this example.

Modeling CSPs: Exercises

Exercise 1

Download the provided code and import it in a new project. Model and implement the 4-queens problem using this framework. (Hint: you will require to define a specific Constraint subclass)

Exercise 2

Model and implement the n-queens problem using this framework. (Hint: you will require to specify a constructor with an integer parameter to set the size)

Solving algorithms

Solving CSP requires implementing the algorithms we taught in class.

The SolutionStrategy abstract class

To code a CSP solver, one should extend the SolutionStrategy abstract class. It essentially defines a solve() method that returns an assignment for a given CSP. It also provides some util methods to trace step-by-step the solving process, using the CSPStateListener interface (see provided code). 

package fr.emse.ai.csp.core;

import java.util.ArrayList;
import java.util.List;

public abstract class SolutionStrategy {
    List<CSPStateListener> listeners = new ArrayList<CSPStateListener>();

    public void addCSPStateListener(CSPStateListener listener) {
        listeners.add(listener);
    }

    public void removeCSPStateListener(CSPStateListener listener) {
        listeners.remove(listener);
    }

    protected void fireStateChanged(CSP csp) {
        for (CSPStateListener listener : listeners)
            listener.stateChanged(csp.copyDomains());
    }

    protected void fireStateChanged(Assignment assignment, CSP csp) {
        for (CSPStateListener listener : listeners)
            listener.stateChanged(assignment.copy(), csp.copyDomains());
    }

    public abstract Assignment solve(CSP csp);
}

An example of solution strategy, as presented in AIMA chapter 6, is backtracking algorithm. You can note that when an assignment is done, the fireStateChanged(assignment, csp) method is triggered, so that another class listening to this one can trace, step-by-step, the solving process (investigate this technique by yourself). 

package fr.emse.ai.csp.core;

public class BacktrackingStrategy extends SolutionStrategy {

    public Assignment solve(CSP csp) {
        return recursiveBackTrackingSearch(csp, new Assignment());
    }

    private Assignment recursiveBackTrackingSearch(CSP csp,
                                                   Assignment assignment) {
        Assignment result = null;
        if (assignment.isComplete(csp.getVariables())) {
            result = assignment;
        } else {
            Variable var = selectUnassignedVariable(assignment, csp);
            for (Object value : orderDomainValues(var, assignment, csp)) {
                assignment.setAssignment(var, value);
                fireStateChanged(assignment, csp);
                if (assignment.isConsistent(csp.getConstraints(var))) {
                    DomainRestoreInfo info = inference(var, assignment, csp);
                    if (!info.isEmpty())
                        fireStateChanged(csp);
                    if (!info.isEmptyDomainFound()) {
                        result = recursiveBackTrackingSearch(csp, assignment);
                        if (result != null)
                            break;
                    }
                    info.restoreDomains(csp);
                }
                assignment.removeAssignment(var);
            }
        }
        return result;
    }

    protected Variable selectUnassignedVariable(Assignment assignment, CSP csp) {
        for (Variable var : csp.getVariables()) {
            if (!(assignment.hasAssignmentFor(var)))
                return var;
        }
        return null;
    }

    protected Iterable<?> orderDomainValues(Variable var,
                                            Assignment assignment, CSP csp) {
        return csp.getDomain(var);
    }

    protected DomainRestoreInfo inference(Variable var, Assignment assignment,
                                          CSP csp) {
        return new DomainRestoreInfo().compactify();
    }
}

To solve a CSP, you only have to call the solve() method. For instance, to solve the map coloring problem, you can code: 

MapCSP map = new MapCSP();
BacktrackingStrategy bts = new BacktrackingStrategy();
bts.addCSPStateListener(new CSPStateListener() {
    @Override
    public void stateChanged(Assignment assignment, CSP csp) {
        System.out.println("Assignment evolved : " + assignment);
    }

    @Override
    public void stateChanged(CSP csp) {
        System.out.println("CSP evolved : " + csp);
    }
});
double start = System.currentTimeMillis();
Assignment sol = bts.solve(map);
double end = System.currentTimeMillis();
System.out.println(sol);
System.out.println("Time to solve = " + (end - start));

which will return: 

Assignment evolved : {NSW=RED}
Assignment evolved : {NSW=RED, WA=RED}
Assignment evolved : {NSW=RED, WA=RED, NT=RED}
Assignment evolved : {NSW=RED, WA=RED, NT=GREEN}
Assignment evolved : {NSW=RED, WA=RED, NT=GREEN, Q=RED}
Assignment evolved : {NSW=RED, WA=RED, NT=GREEN, Q=GREEN}
Assignment evolved : {NSW=RED, WA=RED, NT=GREEN, Q=BLUE}
Assignment evolved : {NSW=RED, WA=RED, NT=GREEN, Q=BLUE, SA=RED}
Assignment evolved : {NSW=RED, WA=RED, NT=GREEN, Q=BLUE, SA=GREEN}
Assignment evolved : {NSW=RED, WA=RED, NT=GREEN, Q=BLUE, SA=BLUE}
Assignment evolved : {NSW=RED, WA=RED, NT=BLUE}
Assignment evolved : {NSW=RED, WA=RED, NT=BLUE, Q=RED}
Assignment evolved : {NSW=RED, WA=RED, NT=BLUE, Q=GREEN}
Assignment evolved : {NSW=RED, WA=RED, NT=BLUE, Q=GREEN, SA=RED}
Assignment evolved : {NSW=RED, WA=RED, NT=BLUE, Q=GREEN, SA=GREEN}
Assignment evolved : {NSW=RED, WA=RED, NT=BLUE, Q=GREEN, SA=BLUE}
Assignment evolved : {NSW=RED, WA=RED, NT=BLUE, Q=BLUE}
Assignment evolved : {NSW=RED, WA=GREEN}
Assignment evolved : {NSW=RED, WA=GREEN, NT=RED}
Assignment evolved : {NSW=RED, WA=GREEN, NT=RED, Q=RED}
Assignment evolved : {NSW=RED, WA=GREEN, NT=RED, Q=GREEN}
Assignment evolved : {NSW=RED, WA=GREEN, NT=RED, Q=GREEN, SA=RED}
Assignment evolved : {NSW=RED, WA=GREEN, NT=RED, Q=GREEN, SA=GREEN}
Assignment evolved : {NSW=RED, WA=GREEN, NT=RED, Q=GREEN, SA=BLUE}
Assignment evolved : {NSW=RED, WA=GREEN, NT=RED, Q=GREEN, SA=BLUE, V=RED}
Assignment evolved : {NSW=RED, WA=GREEN, NT=RED, Q=GREEN, SA=BLUE, V=GREEN}
Assignment evolved : {NSW=RED, WA=GREEN, NT=RED, Q=GREEN, SA=BLUE, V=GREEN, T=RED}
{NSW=RED, WA=GREEN, NT=RED, Q=GREEN, SA=BLUE, V=GREEN, T=RED}
Time to solve = 6.0

Other algorithms are provided (MinConflictsStrategy to solve CSP and AC3Strategy to reduce domains). Inspect carefully the provided code so that you can use all these classes.

Solving CSPs: Exercises

Exercise 3

Compare backtracking and min-conflict heuristic performances on the n-queens problem, with increasing values for n.

Exercise 4

Use AC-3 algorithm to reduce domains, and compare again the algorithms performances.

Exercise 5

Implement the (i) Minimum remaining values, the (ii) Degree and the (iii) least constraining value heuristics. Check again the performances of our algorithms.

Author: Gauthier Picard

Created: 2019-04-10 Wed 08:00

Validate