TP 1 : IA et Logique

D’une énigme logique…

L’Énigme d’Einstein est une énigme, souvent attribuée à Einstein bien que cela soit peut probable, consistant à retrouver des informations sur des personnes à partir d’indications partielles sur leur situation. Ce genre d’énigmes, connues sous le nom de Zebra Puzzle en anglais, était très populaire comme jeux de logique dans différents magazines. C’est une bonne illustration de ce qu’on pourrait attendre d’une Intelligence Artificielle : quelles connaissances peut-on inférer d’un ensemble de faits connus ?

Dans cette section, on va s’intéresser à une version simplifiée de l’énigme d’Einstein et essayer d’inférer une méthode générale pour modéliser et résoudre ce genre de problème. L’énigme est la suivante (source, en anglais):

… à la logique propositionnelle

Formaliser la logique

La logique propositionnelle est un système formel permettant de modéliser des relations logiques entre des propositions et de formaliser ainsi de nombreux raisonnements. On écrit des formules propositionnelles en combinant des propositions atomiques, à qui on donne des noms (x,y ou plus explicitement voitureEstVerte) avec différents connecteurs. Chaque proposition atomique peut être soit vraie soit fausse. Une fois leurs valeurs fixées, on peut en déduire si une proposition donnée est vraie ou fausse. Par exemple, x OU y est vraie dès lors que soit x soit y est vrai. On peut représenter comme s’interprète chaque connecteur via une table de vérité. Voici celles des connecteurs les plus courants :

On peut ensuite combiner ces différents connecteurs pour former des formules plus complexes :

Étant donnée une formule propositionnelle F, on peut se demander différentes choses : est-ce que F est vraie quelque soit les valeurs données à ses propositions atomiques ? Est-ce qu’il existe une assignation des propositions atomiques à vrai/faux où F devient vrai ? C’est ce deuxième cas qui nous intéressera ici. On peut ainsi voir F comme une équation dont les inconnues sont les propositions atomiques et on cherche une solution à cette équation.

Traduire vers la logique propositionnelle

On veut modéliser l’énigme précédente en logique propositionnelle. Pour cela, on va introduire des propositions atomiques de la forme suivante :

• P_Ian_1 : L’enfant prénommé Ian vit dans la maison 1. (P comme Prénom)
• N_Quinn_3 : La famille Quinn vit dans la maison 3. (N comme Nom)
• G_Skateboard_4 : L’enfant de la maison 4 a reçu un skateboard. (G comme Gift).
• C_Rose_2 : La maison 2 est rose (C comme Couleur).

On suppose qu’on a toutes les propositions atomiques précédentes pour toutes les valeurs possibles. Par exemple, on a aussi P_Ian_2, P_Ian_3, P_Ian_4, P_Patrick_1, P_Patrick_2…

On se pose la question suivante : existe-t-il une façon d’assigner à vrai / faux les propositions atomique afin de respecter toutes les indications qui nous sont données dans l’énoncé ?

Pour cela, on va traduire chacune des indications de l’énoncé comme une formule exprimant des contraintes sur les propositions atomiques. L’ensemble de ces propositions formera donc une “équation” dont les inconnues sont les propositions atomiques. Résoudre cette équation donnera une solution au problème !

Par exemple, la proposition suivante exprime le fait que la maison 3 a une couleur : C_Bleue_3 OU C_Rose_3 OU C_Blanche_3 OU C_Verte_3. En effet, cette proposition exprime le fait que la maison 3 est soit blanche, soit rose, soit verte, soit bleue.

On va essayer d’exprimer ce que l’on sait du problème avec des propositions construites à partir des propositions atomiques. On cherchera ainsi à attribuer des valeurs de vérité à chaque proposition atomique afin que les informations qui nous ont été données soient toutes satisfaites. On peut voir ces informations comme une base de connaissances. Notre problème devient donc un problème d’inférence : on essaie d’inférer de nouvelles connaissances depuis celles qui nous sont données.

Le script solve.py contient un début de formalisation du problème en logique propositionnelle. Une liste indications est déjà remplie en parti. La ième valeur de cette liste contient une formalisation de la ième indication du problème.

On dispose des fonctions suivantes :

• VAR(s: str): construit une proposition atomique dont le nom est s
• ET(l: Formula list): construit une formule propositionnelle qui est le ET d’une liste l de formules
• OU(l: Formula list): construit une formule propositionnelle qui est le OU d’une liste l de formules
• NON(f: Formula): construit une formule propositionnelle qui est la négation d’une formule f
• SIALORS(f1: Formula, f2: Formula): construit une formule propositionnelle SI f1 ALORS f2.

Les 4 premières indications sont un peu particulières et permettent d’assurer qu’il y a exactement une variable qui sera mise à vraie pour les couleurs, prénoms, noms et cadeaux comme on l’a fait dans les questions 7 et 8. L’écriture des toutes ces contraintes étant un peu fastidieuse, elles ont été générées automatiquement et vous sont données (vous pouvez voir le code dans logic.py).

Une hypothèse centrale en informatique est qu’on ne pourra pas, en théorie, trouver d’algorithme vraiment plus efficace que la méthode de la force brute. Cette hypothèse n’a jamais été prouvée formellement mais elle est étayée par de nombreuses observations. Cette hypothèse est connue sous le nom de P ≠ NP. Il existe cependant des outils spécialisés pour trouver des solutions à des formules propositionnelles qui sont bien plus performant que la méthode de force brute en pratique. Ces outils sont connus sous le nom de SAT Solvers. Pour des raisons techniques, ces outils ne peuvent accepter en entrée qu’une forme très spéciale de formule propositionnelle. Le script solve.py utilise un tel outil pour résoudre notre problème de logique :

Solution n°1 trouvée!
Assignation des variables:
['-C_Rose_1', '-C_Rose_2', '-C_Rose_3', 'C_Rose_4', '-C_Blanc_1', '-C_Blanc_2', 'C_Blanc_3', '-C_Blanc_4', '-C_Bleu_1', 'C_Bleu_2', '-C_Bleu_3', '-C_Bleu_4', 'C_Vert_1', '-C_Vert_2', '-C_Vert_3', '-C_Vert_4', '-P_Ian_1', '-P_Ian_2', '-P_Ian_3', 'P_Ian_4', '-P_Patrick_1', '-P_Patrick_2', 'P_Patrick_3', '-P_Patrick_4', 'P_Ulysses_1', '-P_Ulysses_2', '-P_Ulysses_3', '-P_Ulysses_4', '-P_Wyatt_1', 'P_Wyatt_2', '-P_Wyatt_3', '-P_Wyatt_4', '-N_Quinn_1', 'N_Quinn_2', '-N_Quinn_3', '-N_Quinn_4', 'N_Young_1', '-N_Young_2', '-N_Young_3', '-N_Young_4', '-N_Jackson_1', '-N_Jackson_2', 'N_Jackson_3', '-N_Jackson_4', '-N_King_1', '-N_King_2', '-N_King_3', 'N_King_4', '-G_Skateboard_1', 'G_Skateboard_2', '-G_Skateboard_3', '-G_Skateboard_4', '-G_Puzzle_1', '-G_Puzzle_2', '-G_Puzzle_3', 'G_Puzzle_4', '-G_Robot_1', '-G_Robot_2', 'G_Robot_3', '-G_Robot_4', 'G_Kit_1', '-G_Kit_2', '-G_Kit_3', '-G_Kit_4']
******************************************************************************************
Interprétation : 

-------------------------------------------------------
Maison1     Maison2     Maison3     Maison4
-------------------------------------------------------
Vert        Bleu        Blanc       Rose
Ulysses     Wyatt       Patrick     Ian
Young       Quinn       Jackson     King
Kit         Skate       Robot       Puzzle
==========================================================================================

Aller plus loin : les limites de la logique propositionnelle

Nous avons vu dans ce TP qu’on pouvait utiliser la logique propositionnelle pour modéliser des connaissances que l’on a sur un problème. Cela permet ensuite d’inférer de nouvelles connaissances en raisonnant sur cette base de connaissances. Cette approche a cependant de nombreuses limites que nous tentons ici de lister.

Complexité inhérente de la résolution

Malgré l’existence d’outils efficaces en pratique sur de nombreux problèmes, inférer de nouvelles connaissances depuis une base de connaissances est un processus très coûteux. Du point de vue de la théorie de la complexité, qui s’intéresse à classifier formellement les problèmes informatiques selon leur difficulté de résolution sur un ordinateur, ce problème se situe dans des niveaux de difficulté pour lesquels on soupçonne qu’il n’existe pas d’algorithmes efficaces. Ainsi, pour certains problèmes, même si leur formalisation en logique propositionnelle n’est pas trop difficile, on n’arrivera pas pour autant à les résoudre automatiquement dans un temps raisonnable.

Complexité et correction de la modélisation

Cela est partiellement illustré dans ce TP : modéliser un problème concret en logique propositionnelle est fastidieux. Par exemple, pour exprimer que deux maisons sont voisines, on doit envisager tous les cas possibles en utilisant un OU. De plus, il est assez facile de commettre des erreurs dans l’encodage qui seront très difficiles à détecter. Cela peut être partiellement résolu en introduisant des logiques un peu plus riches ou en proposant un langage logique de plus haut niveau à l’utilisateur.

Par exemple, on pourrait envisager d’ajouter un peu d’arithmétique dans la modélisation logique, permettant par exemple d’exprimer que le numéro de la maison de Wyatt est égale au numéro de la maison d’Ulysses plus un. On pourrait aussi ajouter des quantifications pour exprimer qu’on veut qu’une condition soit vraie “pour toutes les maisons”. Une autre solution serait de proposer des connecteurs plus complexes à l’utilisateur, par exemple, EXACTEMENTUN(f1,f2…,fn) qui sera vrai seulement si exactement une formule propositionnelle parmi f1,…,fn est vraie. Le problème principal de ces approches est que plus la logique ou son langage est riche, plus il est complexe d’y inférer des nouvelles connaissances.

Ces approches sont bien entendu étudiées et comprises mais force est de constater qu’en pratique, on se ramène souvent (parfois de manière automatique) à la logique propositionnelle pour résoudre les problèmes d’inférence en pratique.

Limite de la modélisation

Une dernière limitation de la logique propositionnelle est son inhabilité à exprimer des connaissances et des raisonnements qu’on utilise cependant souvent en pratique. Par exemple, en pratique, on raisonne parfois avec des faits dont on n’est pas vraiment certain de leur véracité, ou nous avons certaines croyances que nous mettons parfois à jour en fonction de différentes observations. Cette dynamique est difficile à représenter en logique propositionnelle. D’autres logiques permettent de modéliser ce genre de chose, par exemple, la logique modale qui permet de raisonner dans l’incertain, la logique floue qui permet de raisonner avec des degrés de vérité etc.

Afin de vous familiariser avec ces problèmes, voici une énigme classique qui montre bien qu’on a parfois besoin de modéliser des évolutions dynamiques des connaissances.