19

Click here to load reader

Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

Embed Size (px)

DESCRIPTION

Ce papier explique en détail et de manière pédagogique comment résoudre des problèmes en intelligence artificielle à l'aide du langage Prolog. Les classiques du loup, chèvre et chou, et de la tour de Hanoï sont expliqués en détail. On décrit comment appliquer l'approche "general problem solver" en Prolog

Citation preview

Page 1: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

RESOLUTION DE PROBLEMES EN INTELLIGENCE ARTIFICIELLE

L’APPROCHE « GENERAL PROBLEM SOLVER » EN PROLOG

Jean Rohmer

[email protected]

ESILV

ECOLE SUPERIEURE D’INGENIEURS LEONARD DE VINCI

PARIS LA DEFENSE

COURS INTELLIGENCE ARTIFICIELLE DE 3 ème Année

Mars 2013

Avertissement : cet article est à vocation pédagogique. Dans ce but, certaines solutions sont d’abord

proposées sous des formes incomplètes, simplifiées (et donc parfois inexactes). Mais que les puristes

se rassurent, tout s’arrange à la fin, et la rigueur scientifique est sauve…

Sur l’histoire de l’approche « General Problem Solver », commencer par :

http://en.wikipedia.org/wiki/General_Problem_Solver

Il n’est pas nécessaire de connaître Prolog pour le lire. C’est au contraire une occasion de découvrir

Prolog en même temps que la notion de « general problem solver ».

---------------------------------------

La description d’un problème, la recherche d’une solution, peuvent être vues comme le passage

d’une situation de départ à une situation d’arrivée, à travers la réalisation d’un certain nombre

d’actions, qui chacune aboutit à une nouvelle situation.

Par exemple, si votre problème est d’aller de Paris au Camping de la Plage à Ajaccio, vous partez de

la situation initiale « je suis à Paris », et suite à un certain nombre d’actions (prendre un train,

prendre un ferry, faire du stop, conduire une voiture, prendre un bus, …) vous vous retrouvez dans la

situation finale « je suis au Camping de la Plage à Ajaccio ».

Vous allez passer par une suite de situations et une suite d’actions qui vont alterner. Voilà une

solution possible :

� Situation initiale: je suis à Paris

� Action A1 : je prends le TGV Paris-Lyon

� Situation S1 : je suis à Lyon

� Action A2: je fais du stop jusqu’à Marseille

� Situation S2: je suis à Marseille

Page 2: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

� Action A3: je prends un ferry

� Situation S3: je suis à Ajaccio

� Action A4: je prends un bus

� Situation finale: je suis au Camping de la Plage à Ajaccio

Pour résoudre votre problème, vous avez accompli une suite de 4 actions :

[TGV Paris-Lyon, je fais du stop jusqu’à Marseille, je prends un ferry, je prends un bus]

Vous êtes passés par 5 situations successives [Situation de départ, S1, S2, S3, situation finale]

Et il y a beaucoup d’autres solutions possibles, compte-tenu de tous les modes de transport

disponibles.

On a résolu le problème en le décomposant en une suite d’étapes élémentaires, plus simples. Une

étape est caractérisée par trois choses : la situation initiale, l’action, la situation d’arrivée.

NB : Pour rendre une machine capable de résoudre automatiquement un problème, il faut lui

communiquer des connaissances dans un langage formel, plus précis que le langage naturel. Prolog

est un tel langage formel, qui, par certains aspects, ressemble au langage des mathématiques.

Dans ce qui suit, nous écrirons donc en bleu des formules –obéissant à certaines règles- en

utilisant l’essentiel du langage Prolog, mais sans entrer dans le détail du langage.

Nous allons donc résoudre des problèmes en Prolog, mais sans faire un cours de Prolog. En fait, à la

fin de cet article, vous aurez non seulement résolu des problèmes, mais aussi découvert et compris

l’essentiel du langage Prolog. Ceci vous aidera à apprendre plus vite Prolog, sans vous en dispenser.

Attendez l’énoncé des programmes Prolog complets (en rouge) pour avoir un code correct

exécutable.

Commençons par exprimer qu’une étape permet de passer d’une situation à une autre suite à une

action.

Etape(je suis à Marseille, je prends un ferry, je suis à Ajaccio)

Si on connaît toutes les étapes possibles, la solution est une suite d’étapes, telle que le point

d’arrivée de l’une d’elles est le point de départ de la suivante, et telle que la première étape parte de

la situation de départ, et la dernière étape arrive à la situation finale:

Etape(situation initiale, A1, S1), Etape(S1,A2,S2) …. Etape (Sn-1,An,situation finale)

La solution est un itinéraire possible composé d’une suite d’étapes.

Posons-nous un autre problème : je suis en terminale S (c’est ma situation initiale) et je veux devenir

Ingénieur (c’est ma situation finale). Là aussi, j’ai à ma disposition un certain nombre d’étapes :

Etape(je suis candidat au concours d’entrée , je réussis le concours, je suis admis ).

Etape(je suis admis à une école, je choisis cette école, je suis étudiant à cette école)

Page 3: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

Il faut bien distinguer les situations et les actions. Une action –on pourrait dire aussi parfois un

évènement- est ce qui fait passer d’une situation à une autre.

Dans notre voyage vers le camping, les étapes étaient de vraies étapes de voyageur, mais dans notre

parcours scolaire, on peut aussi parler d’étapes.

Quel que soit le problème à résoudre, on va chercher à construire une solution comme une suite

d’étapes qui chacune nous fait passer d’une situation à une autre qui nous rapproche de l’objectif

final.

On décrira une solution comme ça :

Solution(situation initiale, situation finale, suite des actions)

Exemple :

Solution(je suis à Paris, je suis au Camping, [TGV Paris-Lyon, Auto Stop, Ferry, Autobus]).

Comment construire une solution ?

Supposons que l’on connaisse toutes les étapes possibles, et que je veuille passer de la situation

initiale SI à la situation finale SF.

Le cas le plus simple est celui où je peux aller de SI à SF en une seule étape. On va dire ça ainsi:

Solution(SI,SF,[A]) :- Etape(SI,A,SF).

Qui va se lire comme :

Si j’ai une étape directe de SI à SF avec l’action A alors j’ai une solution pour aller de SI à SF par la

suite d’actions [A] (uns suite d’actions qui ne contient qu’une action).

C’est le :- qui exprime que la formule à gauche du :- est vraie si la formule à droite est vraie.

NB : on voit qu’on décrit une suite en mettant ses éléments entre crochets, séparés par des virgules :

• [A,B,C] est une suite de 3 éléments

• [A] est une suite d’un seul élément

• [] est une suite qui est vide : elle ne contient aucun élément

On peut lire ça aussi comme :

Pour avoir une solution qui permet de passer de SI à SF par la suite d’action [A], il suffit qu’il existe

une étape directe qui passe de SI à SF par l’action A :

Pour avoir ce qui est à gauche du :- ,il suffit d’avoir ce qui est à droite.

Page 4: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

Mais en général, il nous faudra plus d’une étape pour atteindre la situation finale, et on ne sait pas

combien à l’avance, cela dépend des étapes à notre disposition.

Pour résoudre ça, on va « saucissonner » la solution, la décomposer, on va procéder pas à pas, en

nous disant que pour partir de la situation initiale vers la situation finale, on va commencer par

chercher une étape qui nous mène de la solution initiale à une solution intermédiaire. Puis une fois

arrivés à ce point intermédiaire, on se repose le problème de trouver une solution qui nous mène à la

situation finale.

Autrement dit, si je veux voyager de SI à SF, je peux commencer par

une étape de SI à Premier_Arret, puis voyager de Premier_Arret à SF.

Ce qui peut s’exprimer ainsi :

Solution(SI, SF, [Premiere_Action|Actions_Restantes]) :-

etape(SI, Premiere_Action, Premier_Arret),

Solution(Premier_Arret, SF, Actions_Restantes).

On dit qu’une solution peut toujours être vue comme une première étape suivie d’une solution

couvrant le reste du chemin.

Un voyage, c’est une première étape, suivie d’un autre voyage.

A noter l’usage de la barre verticale | dans :

[ Premiere_Action | Actions_Restantes ]

Ceci représente la suite constituée de l’élément Premiere_Action ajouté à la suite Actions_Restantes.

(la barre verticale « saucissonne » les suites en isolant leur premier élément).

Sachant qu’on a aussi dit que, dans le cas le plus simple, une étape peut être un voyage à elle toute

seule :

Solution(SI,SF,[A]) :- Etape(SI,A,SF).

(Ceci est une version simplifiée de « solution », la version finale est donnée plus loin dans le code

source en rouge)

Voilà donc comment il faut procéder pour résoudre un problème :

1) Décrire toutes les étapes faisant passer d’une situation à une autre via une action

2) Construire une solution comme une suite d’étapes

Et nous avons expliqué comment construire de longues solutions en les « saucissonnant » :

une première étape qui part du début, suivie d’une solution qui arrive à la fin.

Page 5: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

Pour résoudre un problème donné, il nous suffit donc de décrire, d’énumérer toutes les étapes

possibles, la construction de la solution étant toujours la même –une suite d’étapes- quelles que

soient ces étapes.

Comment décrire les étapes pour un problème donné.

Il y a deux grands cas de figure :

A) Celui où il est possible de faire la liste complète de toutes les étapes : c’est le cas si on

dispose des horaires de trains, de bus, de lignes aériennes.

C’est aussi le cas si on connaît les conditions d’admission à toutes les écoles et leurs règlements

pédagogiques

Faire l’inventaire de toutes les étapes, ça veut dire deux choses : établir la liste de toutes les

situations et établir toutes les actions qui peuvent faire passer d’une situation à une autre

B) Mais dans la vie courante, il y a des problèmes trop complexes pour faire l’inventaire de

toutes les situations et de toutes les étapes possibles.

Par exemple, si on veut résoudre un problème en terme de jeux, (jeux de cartes, jeux d’échec,

tactiques sportives, situations dans des jeux video) : le nombre des situations est astronomique, et se

mesure avec des nombres à plusieurs dizaines de chiffres.

Il n’est plus question d’énumérer à la main. Il va falloir explique à la machine quelles sont les étapes

possibles à partir d’une situation donnée, en donnant des règles générales. En quelque sorte donner

les règles du jeu. (De même que l’on ne décrit pas le jeu d’échecs en faisant la liste de toutes les

situations, mais en donnant des règles générales de comportement des pièces).

Nous allons maintenant traiter deux cas célèbres : le paysan, le loup, la chèvre et le chou, et les tours

de Hanoï.

Le paysan, le loup, la chèvre et le chou

Un paysan est sur la rive gauche d’une rivière, avec un loup, une chèvre, et un chou.

Il dispose d’une barque

Son problème est de faire passer tout le monde (loup, chèvre, chou) ainsi que lui-même sur la rive

droite, en faisant des allers et retour sur les deux rives.

Les contraintes sont les suivantes :

Dans la barque, le paysan peut avoir au plus un passager (loup, chèvre ou chou).

Si le loup et la chèvre se trouvent sur une même rive sans le paysan, le loup mange la chèvre.

Page 6: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

Si la chèvre et le chou se trouvent sur une même rive sans le paysan, la chèvre mange le chou.

Pour donner des règles générales décrivant les étapes possibles, il faut :

� Décider comment définir la situation à un instant donné

� Décider ce que c’est qu’une action, comment la définir, et comment une action fait passe d’une

situation « avant » à une situation « après »

Comment définir la situation.

A un instant donné, les quatre interlocuteurs sont répartis entre trois lieux :

� La rive gauche

� La rive droite

� La barque

Donc on pourrait décrire la situation en disant qui est où, en représentant trois ensembles

correspondant à ces trois lieux.

Mais on peut faire plus simple : une fois la barque partie d’une rive, elle arrive forcément sur l’autre

rive pour décharger ses passagers. On peut donc se contenter de considérer les situations une fois la

barque accostée à une rive, après une traversée, au moment où la barque est vide.

Ensuite, pour connaître l’état du système, il suffit de savoir ce qu’il y a sur une seule rive, puisque on

sait que les autres sont nécessairement sur l’autre rive.

Décidons donc que la situation va être décrite par les présences sur la rive gauche.

Donc le problème à résoudre est :

� Situation initiale : tout le monde sur la rive gauche

� Situation finale : personne sur la rive gauche

Maintenant il faut définir ce qu’est une action : c’est une traversée ; elle est donc définie par le

contenu de la barque.

Ce qu’il faut exprimer maintenant, c’est la notion d’étape, donc dans notre cas :

� Une certaine situation sur la rive gauche avant la traversée

� Une traversée

� La situation sur la rive gauche après la traversée (on parle de cette même rive gauche puisque

c’est elle que nous avons choisi pour représenter la situation)

Il faut distinguer deux types d’étapes :

-celles où la barque quitte la rive gauche (on appellera ce cas « aller »)

-celles où la barque revient sur la rive gauche (on appellera ce cas « retour »)

Cas Aller :

Les passagers de la barque quittent la rive gauche et vont sur la rive droite

Page 7: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

Etape(RG1,Passagers,RG2)

Attention : RG1, ce n’est pas la rive de départ, et RG2 ce n’est pas la rive d’arrivée. RG1

c’est la situation de la rive gauche avant l’action, et RG2 la situation de la rive gauche

après l’action, les déplacements de la barque se faisant de rive à rive dans les deux sens.

Il faut dire que RG2 c’est : RG1 moins les Passagers

Cas Retour :

Les passagers de la barque viennent s’ajouter sur la rive gauche

Etape(RG1,Passagers,RG2)

Il faut dire que RG2 c’est RG1 plus les Passagers

Il nous faut donc définir une sorte d’opération faisant la somme entre des ensembles :

Somme(E1,E2,E3) qui signifiera que les éléments de E3 sont la somme de ceux de E1 et de ceux de

E2

Dans le cas aller, on aura donc :

Somme(RG2,Passagers,RG1) : RG2 diminue par rapport à RG1

Et dans le cas retour :

Somme(RG1,Passager,RG2) : RG2 augmente par rapport à RG1

Donc à l’aller, on définit l’étape ainsi :

Etape(RG1,Passagers,RG2) :- somme(RG2, Passagers, RG1)

Et au retour :

Etape(RG1,Passagers,RG2) :-somme(RG1, Passagers, RG2)

Il faut imposer aussi les contraintes sur la composition d’une rive (personne ne mange personne) et

sur la composition des passagers.

A l’aller :

Le paysan quitte la rive gauche, il faut imposer qu’il laisse une rive paisible

Etape(RG1,Passagers,RG2) :- somme(RG2, Passagers, RG1),

bonnerive(RG2),

bonnebarque(Passagers).

Ce n’est pas la peine de dire que la rive RG1 est bonne, on en est sûr puisque le paysan y était.

Page 8: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

Au retour :

Le paysan revient sur la rive gauche, et abandonne la rive droite, qu’il doit laisser dans un état

paisible. Il faut donc savoir qui est présent sur cette rive. Ce sont ceux qui ne sont pas dans RG2, ce

qu’on peut exprimer comme

Somme(RG2,Rive_Droite,Tous_les_Quatre), bonnerive(Rive_Droite)

On exprime ainsi que la Rive_Droite est le complément de la rive gauche, pour réunir tout le

monde.

Finalement, voilà la définition d’une étape de retour :

Etape(RG1,Passagers,RG2) :- somme(RG1, Passagers, RG2),

bonnebarque(Passagers),

Somme(RG2,Rive_Droite,Tous_les_Quatre),

bonnerive(Rive_Droite).

Nous avons choisi des représentations de la situation et de l’action ; nous avons expliqué comment

une action changeait la situation, et nous avons imposé les contraintes sur la nature des passagers et

la composition d’une rive paisible.

Il nous reste à définir en détail les contraintes : somme, bonnebarque, bonnerive.

Elles opèrent toutes sur des ensembles contenant tout ou partie de nos quatre « individus » : paysan,

loup, chèvre et chou. De même, notre situation sur la rive gauche est représentée par un ensemble.

Une manière bien connue de représenter des sous- ensembles est la « fonction caractéristique »,

qui dit, pour chaque élément possible, s’il appartient ou non au sous-ensemble.

Ici , l’ensemble total est paysan, loup, chèvre, chou

On représente un sous-ensemble par un 0 si l’élément est absent et un 1 si il est présent.

On fixe l’ordre : « paysan, loup, chèvre, chou ».

• L’ensemble complet est représenté par : [1,1,1,1] (ce que nous avons appelé plus haut

« Tous_les_quatre »)

• L’ensemble vide par : [0,0,0,0]

• Le sous-ensemble loup, chou par : [ 0,1,0,1]

Définition des bonnes barques.

Elles contiennent toujours le paysan, et au plus un passager.

Page 9: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

Donc on a :

Bonnebarque([1,0,0,0]).

Bonnebarque([1,0,0,1]).

Bonnebarque([1,0,1,0]).

Bonnebarque([1,1,0,0]).

Définition des bonnes rives

Une rive est paisible si le paysan est présent.

Si le paysan est absent, une rive est paisible :

� Si elle ne contient qu’un seul autre élément ou aucun élément

� Si seuls le loup et le chou sont présents (le loup ne mange pas le chou, ni le chou le loup)

On va écrire :

Bonnerive[1, _,_,_]

Le caractère « _ » signifiant que la valeur à cet endroit n’a pas d’importance, sorte de joker : il suffit

que le paysan soit là, le reste n’a pas d’importance

Bonnerive[0,0,0,0]

Bonnerive[0,0,0,1]

Bonnerive[0,0,1,0]

Bonnerive[0,1,0,0]

Bonnerive[0,1,0,1]

Définition de la somme

Il s’agit de dire que somme(E1,E2,E3) signifie que l’ensemble E3 est la réunion des ensembles E1 et

E2.

Exemple : somme([0,0,1,0],[1,0,0,1],[1,0,1,1])

Le travail s’effectue élément par élément, selon la règle suivante

somme(0,0,0)

somme(0,1,1)

somme(1,0,1)

Page 10: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

NB : le cas somme(1,1,1) ne se présente jamais ici car un élément n’est jamais dans deux ensembles

à la fois.

D’où :

Somme([X1,X2,X3,X4],[Y1,Y2,Y3,Y4],[Z1,Z2,Z3,Z4]) :-

Somme(X1,Y1,Z1), Somme(X2,Y2,Z2), Somme(X3,Y3,Z3),Somme(X4,Y4,Z4)

Pour distinguer entre les deux cas que nous avons vus plus haut (celui où la barque quitte la rive

gauche, et celui où elle y revient), on va pouvoir procéder ainsi :

Etape(RG1,Passagers,RG2) :- RG1 = [1,_,_,_],

somme(RG2, Passagers, RG1),

bonnerive(RG2),

bonnebarque(Passagers).

Etape(RG1,Passagers,RG2) :- RG1= [0,_,_,_],

somme(RG1, Passagers, RG2),

bonnebarque(Passagers),

Somme(RG2,Rive_Droite,Tous_les_Quatre),

bonnerive(Rive_Droite).

Les ajouts de RG1 = [1,_,_,_] et RG1 = [0,_,_,_] permettent de distinguer les cas aller et

retour.

Finalement, avec ces conventions, pour résoudre notre problème, il suffira de l’exprimer ainsi :

Solution([1,1,1,1], [0 ,0,0,0], Liste_Actions).

afin de trouver toutes les listes d’actions qui permettent de passer à :

Situation = [1,1,1,1] : tout le monde sur la rive gauche

à

Situation = [0,0,0,0] : personne sur la rive gauche

Page 11: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

Voilà le programme Prolog complet qui correspond à cette approche.

etape(RG1,P,RG2):-RG1 = [1,_,_,_], bonnebarque(P), somme(RG2,P,RG1), bonnerive(RG2).

etape(RG1,P,RG2):- RG1 = [0,_,_,_],

bonnebarque(P),somme(RG1,P,RG2),somme(RG2,RIVE_DROITE,[1,1,1,1]),bonnerive(RIVE_

DROITE).

somme([X1,Y1,Z1,T1],[X2,Y2,Z2,T2],[X3,Y3,Z3,T3]):-

somme(X1,X2,X3),somme(Y1,Y2,Y3),somme(Z1,Z2,Z3),somme(T1,T2,T3).

somme(0,0,0).

somme(0,1,1).

somme(1,0,1).

bonnebarque([1,0,0,0]).

bonnebarque([1,1,0,0]).

bonnebarque([1,0,1,0]).

bonnebarque([1,0,0,1]).

bonnerive([1,_,_,_]).

bonnerive([0,1,0,1]).

bonnerive([0,0,0,0]).

bonnerive([0,1,0,0]).

bonnerive([0,0,1,0]).

bonnerive([0,0,0,1]).

nonmember(_,[]).

nonmember(X, [Y|Ys]):-X \= Y,nonmember(X,Ys).

solution(A,B,[ACT],_):-etape(A,ACT,B).

solution(A,B,[ACT|L],Deja):-etape(A,ACT,C),nonmember(C,Deja),solution(C,B,L,[C|Deja]).

solution(A,B,L):-solution(A,B,L,[A]).

Page 12: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

On voit dans ce code que « solution » a été modifiée par rapport à la version donnée plus haut. La

première version partirait dans des boucles infinies si une action nous ramenant dans une situation

déjà visitée (par exemple des aller-retour à l’infini avec le même passager).

Avant de se diriger vers une nouvelle étape, il faut savoir par quelles situations où on est déjà passé,

et vérifier que l’on n’y retourne pas. D’où une version de « situation » avec un 4 ème paramètre, qui

contient la suite des situations rencontrées (appelée Déjà). Si la situation C n’est pas déjà rencontrée

(usage de « nonmember », bien connue en Prolog), alors on peut continuer, et on ajoute C à Déjà,

par [C|Deja].

Vous pouvez l’exécuter par exemple avec le logiciel libre SWI Prolog.

Les tours de Hanoï

Le problème est bien expliqué dans Wikipedia : http://fr.wikipedia.org/wiki/Tours_de_Hano%C3%AF

« Le problème des tours de Hanoï est un jeu de réflexion imaginé par le mathématicien français

Édouard Lucas, et consistant à déplacer des disques de diamètres différents d'une tour de « départ »

à une tour d'« arrivée » en passant par une tour « intermédiaire », et ceci en un minimum de coups,

tout en respectant les règles suivantes :

on ne peut déplacer plus d'un disque à la fois,

on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.

On suppose que cette dernière règle est également respectée dans la configuration de départ. »

On aborde habituellement ce problème dans les cours de programmation, pour illustrer la notion

d’algorithme récursif, et pour trouver le meilleur algorithme de résolution du problème.

Mais ici notre démarche est toute autre : on ne veut pas trouver le meilleur algorithme pour

résoudre le problème, on est plus paresseux : on veut juste décrire les étapes possibles d’une

situation à une autre, et laisser la machine trouver des solutions.

Comment définir la situation :

Page 13: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

C’est bien évidemment la composition de chaque tour, c’est à dire l’empilement des disques.

Appelons nos tours t1, t2, t3

Appelons nos disques 1, 2, 3, 4 …

1 est le plus petit, puis 2, puis 3 …

Par exemple, avec trois disques, la situation de départ est la suivante :

t1 = [1, 2, 3]

t2 = [] (vide)

t 3 = []

et la situation d’arrivée est :

t1 = []

t2 = [1, 2, 3]

t3 = []

etape(S1, A, S2) signifie :

Partant de la situation S1, je fais l’action A et je me retrouve dans la situation S2.

Comment définir une action

Qu’est-ce qu’une action ? C’est le déplacement d’un sommet d’une tour à une autre.

Elle se représente naturellement par le nom de la tour de départ et le nom de la tour d’arrivée, par

exemple : [t1, t3]

La forme générale d’une étape est donc :

etape( S1, [T1,T2], S2)

Les contraintes pour qu’une étape soit possible sont :

• il doit y avoir au moins un disque sur la tour T1, soir D1.

• il faut que D1 soit plus petit que le sommet D2 de T2 (ou que T2 soit vide).

Pour passer de S1 à S2, il faut changer la composition des tours : enlever un élément à T1, en rajouter

un à T2.

Comment représenter la situation

La situation globale est complètement décrite par la situation de chaque tour.

La situation d’une tour est la suite des disques qui la composent.

On peut le formuler ainsi :

Page 14: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

[t1, [ 2, 3]] : dans la tour T1, il y a 2 en sommet , puis 3 en-dessous

La situation globale est donc la suite des situations des tours.

Exemple : situation de départ :

[ [t1, [1,2,3]] , [t2, [ ]] , [t3, [ ]] ]

Exemple : situation d’arrivée :

[ [t1, [ ]] , [t2, [1, 2, 3]] , [t3, [ ]] ]

Comment passer d’une situation à une autre

On doit enlever le sommet de la tour T1 et l’ajouter à la tour T2.

Donc dans la description de la situation de départ S1, il faut remplacer la description de la tour T1

par un contenu plus petit (le sommet en moins). Ceci nous conduira à une nouvelle situation S3.

Puis il faut remplacer dans S3 le contenu de T2 par un contenu plus grand (un sommet en plus), ce

qui nous conduira à S2.

On voit que pour passer de S1 à S2, on passe par une situation intermédiaire, S3, qui correspond au

moment où on a enlevé le sommet de T1 sans encore l’avoir mis dans T2.

On va utiliser une opération « remplacer », qui, dans une suite, remplace un élément par un autre.

Remplacer( S1,X1,X2,S2)

Signifiera que la suite S2 est la suite S1 dans laquelle tous les X1 ont été remplacés par X2.

Exemple :

Remplacer([10, 20, 30, 20, 40,] 20, 200, [10, 200, 30, 200, 40])

Etape(S1, [T1,T2],S2) peut alors être réalisée par deux remplace successifs :

Remplacer(S1,[T1,[D1|L1],[T1,L1],S3)

qui enlève le sommet de T1

Puis

Remplacer(S3,[T2,L2],[T2,[D1|L2]],S2)

Qui ajoute un sommet à T2

Commentaires.

On voit apparaître la notation :

[D1|L1]

Page 15: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

La barre verticale permet de décrire la structure d’une suite comme composée d’un premier

élément suivi du reste de la suite.

S = [P |S1] signifiera que P est le premier élément de S et S1 le reste de la suite.

suite = [ premier élément de la suite | reste de la suite ]

Exemples :

S = [1,2,3,4]

S = [P | S1] donne P = 1 et S1 = [2,3,4]

A noter que P est un élément, et S1 une suite

S =[3]

S = [P | S1] donne P = 3 et S1 = [ ] (la suite vide)

Donc

Remplacer(S1,[T1,[D1|L1],[T1,L1],S3)

Signifie bien : je cherche dans S1 la description de la tour T1 ; soit D1 son sommet, et L1 le reste de la

liste, et je vais remplacer cette description par juste L1, pour obtenir la situation intermédiaire S3

De même

Remplacer(S3,[T2,L2],[T2,[D1|L2]],S2)

Signifie : je cherche dans S3 la description de la tout T2, soit L2 son contenu, je la remplace en

ajoutant D1 en tête de L2, pour obtenir la situation S2

Voilà donc la formule pour l’étape des tours de Hanoï

Etape(S1, [T1,T2], S2) :-

Remplacer(S1,[T1,[D1|L1],[T1,L1],S3)

Remplacer(S3,[T2,L2],[T2,[D1|L2]],S2).

Il nous manque la contrainte qui dit que dans une tour un disque ne peut pas être au-dessus d’un

disque plus petit.

Cela revient à vérifier que la composition de T2, à laquelle on vient d’ajouter D1, est valide.

Deux cas sont à considérer :

Page 16: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

A) T2 était vide avant, et contient maintenant juste un disque. Et c’est une situation valide, que

l’on formulera comme :

Tour_Valide([X]) (toute suite d’un seul élément est valide)

B) T2 contient après au moins deux éléments, et il faut que le plus haut soit inférieur celui en

dessous :

Tour_Valide([S1| [S2 | L]]) :- S1 < S2

S1 est le premier élément de la suite, et S2 le premier élément de la liste moins S1.

D’où la formule finale pour l’étape des tours de Hanoï :

Etape(S1, [T1,T2], S2) :-

Remplacer(S1,[T1,[D1|L1],[T1,L1],S3)

Remplacer(S3,[T2,L2],[T2,[D1|L2]],S2)

Tour_Valide([D1|L2]).

On trouvera plus loin dans le programme Prolog complet la formule de « remplacer ».

Finalement, avec ces conventions de représentation, le problème des tours de Hanoï s’exprimera

ainsi :

Solution([[t1,[1,2,3]],[t2,[]],[t3,[]]], [[t1,[]],[t2,[1,2,3]],[t3,[]]), Liste_Actions).

NB : Il y a 2808 solutions …

Ceux qui ont déjà étudié la programmation des tours de Hanoï de manière classique ont été surpris :

elle ne donne qu’une seule solution.

Car la solution classique est la programmation d’un algorithme, qui est imaginé et construit par

une intelligence humaine. C’est l’intelligence humaine qui comprend qu’il existe un algorithme

récursif permettant de déplacer N disques de la tour A à la tour B en :

--déplaçant N-1 disques de la tour A à la Tour C

--puis en déplaçant le sommet de A à B

--puis en déplaçant N-1 disques de C à B

Dans notre cas, nous n’avons pas eu besoin d’imaginer et de construire un algorithme, nous avons

juste décrit les contraintes du problème : on ne peut que déplacer un sommet d’une tour qui n’est

pas vide que vers une tour vide ou dont le sommet est plus grand que le disque déplacé.

Page 17: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

Or l’énoncé de ces contraintes ne figure même pas dans l’algorithme ! C’est bien la preuve que

l’intelligence est restée dans la tête humaine, et pas du tout dans la machine.

Dans notre solution, les contraintes sont données à la machine, et c’est la machine qui s’en

débrouille. On est passé d’une intelligence humaine à une intelligence artificielle, de nature très

différente.

Il faut noter que la machine trouve 2808 solutions (2808 suites de déplacements d’une tour à une

autre), alors que l’algorithme ne donne que la plus courte de ces suites.

A ce sujet il faut faire les remarques fondamentales suivantes :

� L’algorithme est apparemment « optimal »

� Mais qu’est-ce qui vous prouve que l’algorithme respecte les contraintes, puisqu’elles ne

figurent pas dans son texte ? L’intelligence humaine a peut-être trouvé un algorithme optimal,

mais encore faudrait-il le prouver formellement ! Ce qui n’est en général jamais fait …

� Les 2807 solutions non optimales que l’on trouve s’égarent en quelque sorte du chemin

optimal, prennent le chemin des écoliers … Mais supposons que le monde des tours ne soit

pas parfait, qu’à certains moments une tour soit « défaillante », qu’un déplacement d’une tour

à l’autre soit interdit … alors l’algorithme devient inutile, et nos solutions pourront peut-être

trouver « à tâtons » un détour, une suite de mouvements qui nous tirera d’affaire. La solution

algorithmique est aveugle, purement automatique. Dit autrement, elle ne s’applique que dans

un monde idéal loin de la complexité potentielle de la réalité

� Plus généralement, il y a peu de problèmes dans le monde réel qui soient suffisamment

« carrés » pour qu’un algorithme existe pour les résoudre. (De même qu’il y a peu d’équations

qui soient solubles purement mathématiquement). L’approche que nous avons programmée

s’oppose à la notion d’algorithme : les contraintes d’un problème sont communiquées à la

machine qui va chercher elle-même des solutions.

Ceci caractérise bien la démarche « intelligence artificielle » par opposition à la démarche

algorithmique. En Intelligence artificielle, l’important devient la représentation de connaissances

/ contraintes qui caractérisent un problème.

Voilà le programme Prolog complet qui correspond à notre approche.

Il peut être appelé avec la commande :

hanoi_debut(E1),hanoi_fin(E2),solution(E1,E2,X),imprime(X).

etape(E1,[T1,T2],E2):-tour(T1),tour(T2),T1 \=T2,remplacer(E1,[T1,[S1|L1]],[T1,L1],E3),

remplacer(E3,[T2,L2],[T2,[S1|L2]],E2),tour_valide([S1|L2]).

(les « tour » au début servent à générer les étapes pour toutes les combinaisons de tours

différentes possibles)

tour_valide([_]).

Page 18: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls

tour_valide([S1|[S2|_]]):-number(S1),number(S2),S1<S2.

(on vérifie que S1et S2 sont bien des entiers avant de les comparer, sinon SWI Prolog a des

problèmes pour une raison qu’un lecteur pourra peut-être m’indiquer …)

remplacer([],_,_,[]).

remplacer([X|L],X,X1,[X1|L1]):-remplacer(L,X,X1,L1).

remplacer([Y|L],X,X1,[Y|L1]):-Y \=X,remplacer(L,X,X1,L1).

(la fonction remplacer est générale : remplacer X par X1 dans une liste)

tour(t1).

tour(t2).

tour(t3).

hanoi_debut([[t1,[1,2,3]],[t2,[]],[t3,[]]]).

hanoi_fin([[t1,[]],[t2,[1,2,3]],[t3,[]]]).

nonmember(_,[]).

nonmember(X, [Y|Ys]):-X \= Y,nonmember(X,Ys).

solution(A,B,[ACT],_):-etape(A,ACT,B).

solution(A,B,[ACT|L],Deja):-etape(A,ACT,C),nonmember(C,Deja),solution(C,B,L,[C|Deja]).

solution(A,B,L):-solution(A,B,L,[A]).

imprime([]).

imprime([X|L]):-print(X),imprime(L).

------------------------------------------

Merci aux lecteurs de nous faire suivre toutes leurs questions ou remarques pouvant améliorer cet

article.

[email protected]

[email protected]

Page 19: Intelligence Artificielle: résolution de problèmes en Prolog ou Prolog pour les nuls