This Bayes net demonstrates how to solve constraint satisfaction problems (CSPs)
using Bayes nets. 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.
A map consisting of some of the countries in western continental Europe is to be
colored so that no two bordering countries have the same color. In a map coloring
problem, four colors is enough, so we have chosen red, green, blue and yellow.
In this CSP the variables are the color of each country, and the constraints are that
bordering countries must have different values.
The constraints are represented by the R nodes. If you look at their relation table,
you will see that they are "True" only when the two nodes they are between have
different values. Each has a finding of "True" entered, to indicate that the constraint
is satisfied.
If you compile the above network, the solution is represented by the nonzero beliefs.
The problem is under-constrained so there are lots of solutions. Say we want Luxembourg
to be red, and Germany green. If you enter those as findings, you will see how choices
for the rest of the countries become reduced (you can't make a choice with a zero belief).
Yellow is still a possiblity for Netherlands, France and Italy. Say we make Netherlands
yellow. Then we see that Italy can't be yellow, and France must be yellow.
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 contrains. Binary constraints will have two parents, ternary
constraints will have three, and so on. Each constraint will be a True/False node,
whose relation 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 are possible. Instead of giving the constraint node a finding, you can
add a utility node which is a child of the contraint 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).
You can see that belief/decision networks are powerful and practical way to represent
CSPs, allowing for Nary constraints, soft constraints, meta constraints, easily changing
constraint sets, other probabilistic relations, etc.
Some tips: Often contraints are the same, so copy and paste a lot during construction.
If you have a large network it is a good idea to label each constraint node with a
keyword (e.g. put "$constraint" in its comment). Then you can select all the constraint
nodes using Edit->Find All. If you invert that selection with Shift+Ctrl+A, you can
then do Network->Remove Findings to remove all the findings except constraints.
This Bayes net designed by Norsys Software Corp. |