Exemple du robot

Il s'agit de programmer un petit robot: on dispose d'un plan de travail comportant trois emplacements (1, 2 et 3), et de trois cubes (a, b et c) empilés sur les emplacements. Notre petit robot sait prendre un cube au sommet d'une pile pour le déposer au sommet d'une autre pile. Par exemple, lorsque le robot reçoit l'instruction déplace(b,3,1), il prend le cube b qui est au sommet de la pile à l'emplacement numéro 3 pour le déposer au sommet de la pile à l'emplacement numéro 1. Il s'agit maintenant de programmer le robot (i.e., d'indiquer au robot une suite d'actions à effectuer) pour passer d'un état initial à un état final donnés.

Formalisation du problème :

• S est l'ensemble des configurations possibles du plan de travail,

• est l'état initial suivant:

  

• F contient l'unique état final suivant:

  

• T est la fonction de transition définie par

  

Remarques:

• On peut généraliser le problème à N cubes sur M emplacements.