Chapter 7 : Using Constraint nodes

To conclude this tutorial, we describe in this chapter the use of the Constraint nodes.

These discrete nodes have the following characteristics:

1. They are logical nodes (two modalities, False and True)
2. They are always observed at the True value
3. It’s impossible to associate monitor to them, to rename their modalities or to add them modalities, and to tag them.

As their name indicates it, these nodes are used to express a constraint that must hold between their parents. To illustrate the use of this type of nodes, we are interested in modeling of a well-known problem in Artificial Intelligence, the map coloring problem. In this problem, the constraints to be respected are to color a geographical map with a limited number of colors while not affecting the same color to two neighbor elements. We choose the map of Australia that has seven territories and that requires three colors. We thus need a variable by territory.

To improve the readability of the graph, it is possible to change the background image of BayesiaLab (thanks to the contextual menu associated to the worksheet), to set for example an image of a map of Australia.

Each of these variables has three modalities, one for each color. Their corresponding conditional probability tables are all identical to the one describe below :

It then remains us to express the constraint that neighbor territories must have different colors. We must then associate a Constraint node between each neighbor territories. The creation of a Constraint node is carried out either by switching to the Constraint node creation mode , or thanks to the shortcut "C". All these Constraint nodes having the same probability table (as the one illustrated below), it is possible to exploit the functions of node copy and of arc moving. Then, we just have to define a first Constraint node and to fill its probability table.

Once this first Constraint node defined, we just have to copy it (Ctrl + "C"), to left click where we want to place the copy, to paste the node (Ctrl + "V", a copy of the node is then pasted with the two initial arcs), and finally to move the arcs that were copied to make them correspond to the desired parents (Shift + selection and drag of arc). The probability tables are then preserved.

We obtain then the following Bayesian network:

The use of this Bayesian network is then easy. We just have to monitor the set of nodes:

and then to observe (choose) a color for a territory. The constraints are then propagated to the set of unobserved variables.