Le problème

Récapitulons le problème. Bob doit concevoir des circuits. Ces circuits doivent conduire un signal d’une source aux antennes situées sur un panneau cartésien 2D discrets de dimensions finies. La tâche est de tracer les lignes de conduction, que j’appellerai chemins, sur le panneau. Voici les règles:

1. Un chemin est une séquence de segments de droite dont les points limites doivent correspondre à des cases du panneau discret.
2. Il doit y avoir un chemin entre la source et chacune des antennes.
3. Un chemin ne peut pas sortir des dimensions du panneau.
4. Un chemin ne peut pas passer sur la source ou un antenne, sauf pour ses points limites (début et fin).
5. Un chemin ne peut pas passer sur certaines cases nulles identifiées au départ.
6. Bien qu’un chemin peut se séparer en multiples autres chemins (les fourches sont permises), un chemin ne peut pas en croiser un autre.

Durant le CTF, une séquence de tels problèmes de conception de circuit était offerte par un serveur. Il fallait donc solutionner tous les problèmes de la séquence aussi rapidement que possible: après un temps de calcul excessif, la connexion était brisée par le serveur. Si on arrivait à compléter tous les problèmes correctement, on se faisait donner un mot de passe qui débloquait 4 points pour son équipe.

Les leçons apprises lors du CTF

Une approche inadéquate

Comme mentionné plus haut, durant le CTF, j’ai mis en oeuvre une solution qui n’a pas permis de décrocher le mot de passe. En voici l’algorithme de haut niveau:

• Tant qu’on n’a pas trouvé des chemins satisfaisant les conditions ci-haut vers toutes les antennes:
  1. Tracer un chemin de la source à l’antenne qui s’en éloigne le plus.
  2. Pour chacune des autres antennes a:
     1. Pour chaque chemin c déjà tracé sur le panneau:
        1. Tenter de trouver un chemin vers a en fourchant le chemin c. Cela nous fait même considérer une fourche du chemin c à partir de la source, ce qui revient à tracer un tout nouveau chemin.
     2. Si on n’a pas trouvé un chemin vers a, on élimine le dernier chemin trouvé et on reprend. Cela nous ramène une étape en arrière dans la solution.

Cette solution fonctionne plutôt bien… pour les problèmes de petites dimensions. Ainsi, lorsque nous contactions le serveur, il nous était possible de résoudre les trois ou quatre premières instances qui nous étaient envoyées. Cependant, on finissait inévitablement par se prendre un problème de plus grandes dimensions déclenchant des calculs de plusieurs minutes, que nous finissions typiquement par interrompre nous-mêmes. J’ai travaillé fiévreusement à ajouter et ajuster diverses heuristiques de recherche, mais sans succès.

Les humains à la rescousse

Désespérés, nous avons remarqué que bien que la séquence de problème était différente chaque fois que nous contactions le serveur, plusieurs instances étaient récurrentes. Nous avons donc commencé à noter ces instances et à les résoudre à la main, au tableau noir. Nous tabulions les solutions dans un fichier de sorte qu’en recevant une telle instance une seconde fois, nous pouvions sortir la solution de ce fichier, sans la recalculer. Surprenamment, nous étions en mesure d’avancer jusqu’au huitième problème dans la séquence grâce à cette approche.

Dompter la complexité exponentielle

Je sentais déjà en programmant la solution esquissée ci-haut qu’il était possible de se frapper à une importante difficulté avec ce genre de problème: la taille de l’espace d’états, auquel la solution appartient, est une fonction exponentielle de la taille du problème. Spécifiquement à ce problème de conception de circuits, le nombre de chemins possibles de longueur n croît exponentiellement avec n. Cela signifie que l’espace des états qu’on explore avec l’approche de backtracking que j’ai adoptée est lui aussi de taille exponentielle. En gros, on cherche une aiguille de taille atomique dans une botte de foin grosse comme l’univers.

Dans une telle situation, l’atteinte d’une solution dépend entièrement des heuristiques de recherche: où on cherche en premier, quelle information sur la solution on injecte dans la recherche… Ces heuristiques ne sont pas des propriétés garanties quant à la solution, mais plutôt des règles de pouce, des approximations qui s’avèrent plus souvent qu’autrement. Les heuristiques mises en oeuvre ci-haut étaient pauvres: la meilleure information sur la solution mise en oeuvre consiste en ce que les chemins composant la solution soient issues de la fourche d’un ou deux chemins de base partant de la source. En supposant aussi peu sur la solution, on s’ouvre à l’exploration d’un très grand espace de possibilités, d’où les temps de calcul excessifs, même sur mon ordinateur personnel plutôt puissant (Mac Book Pro mouture début 2011, Intel Core i7, 16 GB RAM).

On peut néanmoins tirer deux observations de cette approche infructueuse:

1. Le calcul d’un chemin entre deux points, même deux points éloignés, est rapide si on n’en contraint pas la longueur. Il est même simple d’introduire des heuristiques qui favorisent le calcul d’un chemin aussi court que possible.
2. Le calcul de plusieurs chemins de même longueur L est rapide si L est petit. En effet, comme mentionné ci-haut, l’algorithme est en mesure de résoudre le problème si la dimension du panneau n’est pas très grande. Dans ce cas, les chemins devant aller de la source aux antennes sont courts, aussi leur nombre n’excède pas les possibilités de calcul de mon ordinateur.

Ces observations aiguillent la recherche d’une meilleure approche.

Diviser pour régner

Si la solution ci-haut n’est pas vilaine pour régler les problèmes de petite dimension, il est intéressant de voir comment on peut réduire un problème de grande dimension à un autre plus petit. L’observation d’un bon nombre d’instances du problème glanées durant le CTF suggère que souvent, les antennes se retrouvent entassées dans une petite région R du panneau, éloignée de la source. Dans ce genre de situation, l’approche ci-haut tenterait de calculer plusieurs longs chemins, ce qui prend trop de temps. Par contre, si la source appartenait à la petite région qui englobe toutes les antennes, on pourrait ignorer tout le reste du panneau et le problème deviendrait effectivement de petite taille.

Il est donc possible de résoudre, par l’approche ci-haut, le problème de joindre toutes les antennes à un point de rencontre M qui appartiendrait à R (où R est l’ensemble des cases de la plus petite région rectangulaire du panneau qui contient toutes les antennes). Cela fait, il ne reste qu’à calculer un chemin de longueur arbitraire entre la source et M. En résumé, au lieu de résoudre un seul gros problème, on le divise en deux plus petits:

1. trouver tous les petits chemins de même longueur allant de M à chacune des antennes;
2. trouver un chemin de longueur arbitraire allant de la source à M.

Les deux observations ci-haut suggèrent que ces deux sous-problèmes peuvent être calculés en temps convenable. Le seul cas problématique est que la solution au sous-problème (1) élève des contraintes qui rendrait impossible la résolution du sous-problème (2). Heureusement, il existe typiquement plusieurs solutions au sous-problème (1): l’approche de résolution trouvera vraisemblablement d’abord les solutions basées sur les chemins les plus courts. Si cette solution ne convient pas, il faudra explorer des alternatives à chemins plus longs, jusqu’à une certaine limite.

Le nouvel algorithme

1. Pour chaque point M du panneau qui n’est pas une antenne:
   1. Trouver un chemin de M à l’antenne qui s’en éloigne le plus.
   2. Pour chacune des autres antennes a:
      1. Pour chaque chemin c déjà tracé:
         1. Pour chaque point p du chemin c:
            1. Tenter de trouver un chemin de p à a.
      2. Si on n’a pas trouvé de chemin vers a, on élimine le chemin tracé vers l’antenne considérée précédemment, et on reprend la recherche. On peut reprendre en (1.1) si le tout premier chemin est ainsi éliminé.
   3. Tracer un chemin de la source à M, en évitant de croiser les chemins allant de M aux antennes. Si cette recherche est infructueuse, on reprend la recherche d’une solution au premier sous-problème.

L’heuristique mise en oeuvre est donc qu’une solution consiste en un seul chemin partant de la source, qui fourche en divers points près des antennes. La division du problème est une interprétation de cette heuristique qui permette de réduire la taille des problèmes effectivement considérés.

Heuristiques d’optimisation

En plus de cette heuristique principale, on met en oeuvre diverses heuristiques supplémentaires propres à accélérer le calcul de la solution.

• La longueur des chemins de M aux antennes est contrainte, de manière à éviter les solutions où, M étant mal placé, on crée des chemins excessivement longs de M aux antennes, lesquels empêcheraient toute tentative de trouver le chemin de M à la source. La longueur de ce dernier n’est pas contrainte.
• Les chemins les plus courts sont considérés en premier. Ils tendent à moins encombrer le panneau. Techniquement, on appelle ce genre d’approche avare (greedy).
• Lorsqu’on cherche un chemin d’un point à un objectif dans un panneau encombré de divers obstacles, on maintient en mémoire l’ensemble des points à partir desquels l’atteinte de l’objectif a déjà été évaluée et est impossible. Ainsi, on évite de générer répétitivement un grand ensemble de longs chemins à partir de multiples points de départ intermédiaires qui ne peuvent pas mener à la solution. Cette approche réduit significativement les calculs inutiles suivant une solution intermédiaire inadéquate.

Visualisation

Afin d’assister l’implantation de l’algorithme, j’ai mis en oeuvre des outils pour visualiser le panneau décrivant le problème, ainsi qu’une solution, c’est-à-dire le panneau auquel on superpose des chemins calculés. Ces outils de visualisation sont basés sur matplotlib. Les figures ci-bas présentent un exemple de l’utilisation de ces outils.

L’outil de visualisation peut par ailleurs être utilisé durant le calcul de la solution pour observer les états explorés et l’ordre dans lequel ils sont générés. Comme il s’agit d’un outil de déboguage, j’ai simplement mis la ligne qui rafraîchit l’affichage à chaque étape en commentaire. Il est à noter que je n’ai utilisé ce système de visualisation que sur ipython, lancé en mode pylab. Je n’ai aucune idée si ça fonctionne bien avec Python ordinaire.

Conclusion

La page du projet présente les temps de calcul du nouvel algorithme contre chacun des 81 problèmes distincts que j’ai sauvegardés du CTF. La plupart des solutions sont trouvées en moins de 100 millisecondes; dans le pire cas considéré, la solution est trouvée en moins de 7 secondes. Je suis convaincu que ces performances auraient été suffisantes pour résoudre tous les problèmes d’une séquence et mériter à mon équipe quatre points de plus.

C’est en retard, mais je suis quand même très fier. J’avais peur de ce genre de problème d’intelligence artificielle, mais ayant appris beaucoup et ayant eu tellement de plaisir en le résolvant, ce ne sera plus le cas. Je retiens qu’il est important de bien réfléchir aux heuristiques guidant la recherche avec backtracking: la qualité de ces heuristiques a un impact crucial sur la performance, au point où l’exploration d’un espace d’états exponentiel devient réalisable en un temps acceptable.