Belief and decision networks are powerful and practical way to represent constraint satisfaction problems (CSPs), allowing for Nary constraints, soft constraints, meta constraints, easily changing constraint sets, other probabilistic relations, etc. A CSP consists of a number of variables, and some constraints between them. The goal is to find values for the variables that satisfy all the constraints.
To solve general CSPs, you will make each of the variables a node with uniform probabilities (unless you want to express some bias). Each constraint will also be a node, whose parents are the variables it constrains. Binary constraints will have two parents, ternary constraints will have three, and so on. Each constraint will be a True/False node, whose CPT table indicates "True" when the constraint is satisfied. Then it is given a finding of "True".
If not all the constraint nodes can be given findings of True before Netica complains that an inconsistent finding has been entered, then the CSP does not have a solution. You can turn constraints on and off by entering and removing their findings. Sets of constraints can be saved in a case file. A constraint can be made to depend on other variables by giving it additional parents.
Soft Constraints: Soft constraints are possible. Instead of giving the constraint node a finding, you can add a utility node which is a child of the constraint node, indicating the desirability of having the constraint satisfied. Then make the primary variable nodes into decision nodes to find the optimal decision (i.e. the best assignment of values to get the highest utility).
Tutorial: For a demonstration on how to solve CSPs using Bayes nets, open the net called Europe Map Coloring.dne, from the Examples folder that came with your Netica download.
Tips:
• Often constraints are the same, so copy and paste a lot during construction.
• You may want to add some constraint nodes to the Window → Node Palette.
• If you have a large network it is a good idea to put all the constraint nodes in a node-set called "Constraint". Then you can select all the constraint nodes using Edit → Select Nodes → In NodeSet. If you invert that selection with Ctrl+Shift+A, you can then do Network → Remove Findings to remove all the findings except constraints.
Home > Special Topics > Constraint Satisfaction Problems