Chapitre 7 – Utiliser les nœuds Contrainte

Pour clore ce tutorial, nous décrivons dans ce chapitre l’utilisation des nœuds Contrainte.

Ces nœuds sont des nœuds discrets ayant les particularités suivantes ;

1. Ce sont des nœuds logiques (deux modalités: Faux, Vrai)
2. Ce sont des nœuds qui sont toujours observés à la valeur Vrai
3. Il n’est pas possible de leur associer des moniteurs, il n’est pas possible de renommer ou de leur ajouter des états, et il n’est pas possible de les marquer.

Comme leur nom l’indique, ces noeuds servent à exprimer une contrainte entre leurs nœuds parents. Pour illustrer l’utilisation de ce type de nœuds, nous nous intéressons à la modélisation d’un problème bien connu en Intelligence Artificielle, le coloriage d’une carte. Dans cette problématique, les contraintes à respecter sont de colorier une carte géographique avec un nombre limité de couleurs en n’affectant pas la même couleur à deux éléments voisins.

Nous choisissons la carte de l’Australie qui comporte sept régions et qui nécessite trois couleurs. Il nous faut donc une variable par région.

Pour ajouter à la lisibilité du problème, il est possible de changer le fond d’écran du réseau et d’y associer une autre image, celle d’une carte d’Australie par exemple (menu contextuel associé à la feuille de travail).

Chacune de ces variables comporte trois modalités, une pour chaque couleur. Les tables de probabilités de chacune des régions sont toutes identiques à celle illustrée ci-dessous.

Il nous reste alors à exprimer la contrainte de la différence des couleurs entre chaque région voisine. Pour ce faire, nous devons associer des nœuds Contrainte entre chaque région voisine. La création d’un nœud Contrainte s’effectue soit en passant en mode création de nœuds Contrainte , soit grâce au raccourci « C »,  Tous ces nœuds ayant la même table de probabilités (illustrée ci-dessous), il est possible de mettre à profit les fonctions de copie de nœud et de déplacement d’arc. Il s’agit dans ce cas de définir le premier nœud Contrainte, de remplir sa table de probabilités.

Une fois ce premier nœud Contrainte défini, il suffit de le copier (Ctrl + « C »), de cliquer à l’endroit où on désire coller la copie, de coller le nœud (Ctrl + « V », une copie du nœud est alors insérée à l’endroit désiré avec les deux arcs initiaux), et enfin de déplacer les arcs qui ont été copiés pour les faire correspondre aux parents désirés (Maj. + sélection et déplacement d’arc). Les tables de probabilités sont alors conservées.

On obtient alors le réseau suivant :

L’utilisation de ce réseau est alors simple. Il s’agit de monitorer l’ensemble des nœuds :

et d’observer, de choisir, une couleur pour un territoire. Les contraintes sont alors propagées sur l’ensemble des variables non observées.