Sokoban, gardien d'entrepôt en français, est un jeu vidéo de réflexion originaire du Japon et datant du début des années 80. Selon des sources diversesSoHistory (Pas d'année); WikiSokoban (Pas d'année), il a été créé par Hiroyuki Imabayashi et édité par Thinking Rabbit qui en détient aujourd'hui tous les droits. Le jeu doit sa popularité à des règles très simples mais qui permettent néanmoins une très grande complexité. De fait, certains niveaux sont très difficiles à résoudre par l'homme et même par la machine.

La Figure 3.2 correspond à la représentation d'un niveau de Sokoban.

Dans ce document, la référence à l'une des positions de l'aire de jeu se fera toujours à l'aide du croisement entre la ligne et la colonne de la position concernée (i.e. la position du pousseur est I12 sur la Figure 3.2).

Etant donné le niveau représenté sur la Figure 3.3, la liste des états intermédiaires qui mènent à la solution optimale, en terme de mouvements et de poussées, est visible sur la Figure 3.4. Il y a plusieurs façons de représenter une solution. Celle adoptée dans ce document consiste à se placer du point de vue du pousseur et d'indiquer ses directions successives par des lettres minuscules s'il ne pousse pas de caisse ou majuscules s'il en pousse une. Si plusieurs mouvements ont lieu dans la même direction. La lettre est préfixée par son nombre d'occurences. Dans notre exemple, la solution est Ld2l2urDldR et s'établit en 11 mouvements et 3 poussées.

Il a été démontré en 1995 par Dorit Dor et Uri ZwickDor et Zwick (Pas d'année) que le problème de décision correspondant au Sokoban était NP-difficile. C'est-à-dire que Sokoban fait partie de la classe des problèmes décidables par une machine de Turing non déterministe en temps polynomial.

Deux ans plus tard, en 1997, des travaux réalisés par Joseph CulbersonCulberson (Pas d'année) ont démontré que le problème de décision était PSPACE-complet. Il appartient donc à la classe PSPACE et est PSPACE-difficile. C'est-à-dire qu'il est au moins aussi difficile que tous les problèmes de la classe PSPACE qui représente les problèmes décidables par une machine de Turing déterministe en espace polynomial par rapport à la taille de sa donnée.

Sokoban est un problème de type Single-Agent. C'est-à-dire qu'un seul agent peut faire évoluer le jeu en permettant le passage d'un état à un autre. Dans le Sokoban, celui-ci est le pousseur. Ce type de problème n'est pas nouveau et des méthodes existent déjà pour transiter d'un état à un autre afin d'atteindre un état solution. Ces méthodes impliquent un arbre de recherche comme nous le verrons dans la Section 4.1.

Les méthodes existantes sont cependant très générales et peu efficaces dans le cas du Sokoban. En effet, elles devront être adaptées aux particularités de ce problème précis sans quoi nous n'obtiendrons que peu de résultats. La Section 4.2 détaille comment des études menées par différentes Universités ont déjà grandement amélioré les méthodes existantes.

Les méthodes Single-Agent et certaines des améliorations propres au Sokoban seront intégrées dans ce mémoire. Devant la quantité de techniques qui existent, un choix a dû être effectué pour sélectionner celles qui semblaient les plus prometteuses. De plus, certaines évolutions et alternatives seront proposées. Les décisions prises quant à ces techniques sont détaillées dans la Section 4.3.

Afin de limiter la taille de l'arbre de recherche, ce ne sont pas les mouvements du pousseur qui sont pris en compte mais les poussées des caisses. Les transitions entre un état et ses fils correspondent donc chaque fois à une succession de mouvements suivie d'une poussée comme indiqué sur la Figure 4.1. Cette couche d'abstraction nous permet d'arriver plus vite à un état solution mais ne nous garantit pas l'obtention de la solution optimale en terme de mouvements, seulement celle en terme de poussées.

La position exacte du pousseur importe peu. Tant qu'il reste dans un ensemble de positions atteignables sans la moindre poussée, les futures poussées possibles à partir de cet état seront les mêmes. En généralisant la position du pousseur de la sorte, nous évitons de multiplier dans notre arbre les états qui ont des descendances identiques. Nous réduisons ainsi les branches potentielles à explorer. La Figure 4.2 montre bien qu'un seul état généralisé correspond simultanément à plusieurs états sans perdre d'information et donc l'optimalité de la solution.

Depuis l'apparition de Sokoban, celui-ci a été le sujet de nombreuses recherches qui ont conduit à la conception de solveurs. L'efficacité de ces solveurs est à chaque fois mise à l'épreuve sur le même ensemble de 90 niveaux. Cet ensemble regroupe les 50 niveaux de la première version de SokobanOriginalHighScore (Pas d'année) ainsi que 40 niveaux postérieursExtraHighScore (Pas d'année) dont la paternité semble appartenir à Joseph L Traub.

Le solveur Rolling Stone est certainement celui qui est le plus documenté à ce jour. Il provient de l'Université d'Alberta, Canada. Des recherches y ont été faites entre 1997 et 2001 et il en résulte une Thèse écrite par Andreas JunghannsJunghanns (1999) et de nombreuses publications d'articles sur des méthodes testées et plus ou moins efficaces. L'utilisation d'une méthode intelligente de parcours de l'arbre de recherche (IDA*) permet d'assurer l'optimalité de la solution en terme de poussées d'un niveau. De plus, de nombreuses méthodes de détection de deadlocks et de pénalités sont utilisées et réduisent considérablement la taille de l'arbre de recherche.

Le solveur Talking Stone est plus récent et date de 2006. Il a été créé par François Van Lishout à l'Université de Liège, Belgique, dans le cadre d'un DEA en Sciences AppliquéesVan Lishout (2006). Une nouvelle approche Multi-Agent est utilisée dans le but de faire interagir les éléments principaux du jeu – les caisses – entre-eux avec un objectif commun. F. Van Lishout est parvenu à trouver un algorithme permettant de résoudre les niveaux lorsque ceux-ci appartiennent à une certaine sous-classe prédéfinie. L'idée principale est qu'un niveau appartient à cette sous-classe si on peut trouver une association caisses-goals permettant de mettre, tour à tour, chaque caisse sur son goal. Cette méthode a cependant très vite montré ses limites car un seul niveau a ainsi pu être résolu.

Un autre solveur est apparu l'année suivante à Liège, toujours en Scheme et reprenant les principes de base de Talking Stone. Il a été créé par Jean-Noël Demaret dans le cadre de sa Deuxième LicenceDemaret (2007) et reprend l'approche Multi-Agent en l'améliorant et en insérant des optimisations propres au Sokoban. Il concrétise l'intérêt de l'approche de Talking Stone en résolvant 54 niveaux tout en laissant une légère marge de progression.

Le solveur Sokoban Automatic Solver est certainement celui qui est le plus puissant à ce jour. Il est toujours en développement et sa première version semble dater de 2003. Malheureusement, il est non documenté et son code n'est pas disponible. Il est créé par le Japonais Ken'ichiro Takahashi et la version 7.2.2 de janvier 2008Takahashi (Pas d'année) permet de résoudre 86 des 90 problèmes proposés, ce qui est réellement impressionnant. Les solutions trouvées ne sont pas optimales ce qui laisse supposer qu'il utilise des heuristiques très précises pour réduire la taille de l'arbre de recherche.

Une zone est une technique qui consiste à représenter un ensemble de positions dans le niveau. Le concept de zone est apparu très tôt dans l'élaboration de notre solveur. Initialement prévu pour alléger l'espace de stockage de l'arbre de recherche, en utilisant des bits pour stocker les positions des caisses, il a très vite montré son efficacité dans bon nombre de situations. Il permet, entre autres, de trouver toutes les caisses que le pousseur peut déplacer dans un état en seulement quelques opérations sur des entiers. Étant donné que ces optimisations concernent les aspects les plus élémentaires d'un solveur, et donc les plus courants, elles s'avèrent très efficaces dans la pratique. Le concept de zone sera développé dans la Section 5.5.

Concrètement, un deadlock est un état dont on peut affirmer, par l'une ou l'autre méthode (cf. Chapitre 8), qu'il ne mènera pas à une solution. En d'autres mots, cet état est la racine d'un sous-arbre de l'arbre de recherche qu'il faut éviter de créer, au risque de faire croître inutilement la taille de l'arbre et augmenter le temps de résolution du problème.

Un certain nombre de techniques efficaces ont été implémentées à partir de méthodes décrites dans la Section 4.2. Nous avons ajouté à celles-ci une nouvelle méthode permettant d'étendre la notion de deadlock à celle de deadlock zone. Cette méthode découle d'observations effectuées lors de l'utilisation du solveur sur certains niveaux et est décrite dans la Section 8.2.2.

Dans les précédentes recherches de la Section 4.2, il semble n'y avoir eu que quelques cas de pré-traitement, notamment dans le cadre de l'utilisation de Deadlock Tables dans Junghanns (1999). Peut-être étaient-ils passés sous silence mais utilisés dans la pratique. Peut-être également que l'une des contraintes était de pouvoir recalculer les informations utiles à la volée. Quoi qu'il en soit, nous pensons que ces techniques sont intéressantes car facultatives et persistantes. Facultatives car il est possible d'utiliser le solveur sans utiliser de pré-traitement ni de post-traitement. Persistantes car une fois un traitement effectué, il peut être chargé instantanément lors d'une prochaine utilisation du solveur et être utilisé tel quel ou complété.

Le fonctionnement principal du solveur est détaillé dans l'Algorithme 1. L'implémentation proposée, bien que de haut niveau et très simplifiée, présente les mécanismes les plus importants d'un tel programme. Pour pouvoir créer l'arbre de recherche, on utilise une liste d'attente, dont le fonctionnement sera décrit dans la Section 5.4.

Les différentes données contenues dans un état, qu'elles soient relatives aux caisses ou au pousseur, ne sont rien de plus que des ensembles contenant des positions. Les représentations peuvent donc être faites à l'aide d'un même outil. Cet outil, la zone, permet de gérer facilement différents ensembles de positions (cf. Section 5.5).

Comme nous l'avons signalé dans la Section 4.1, la structure d'un état ne doit pas contenir d'information relative aux positions des goals et des murs. Celles-ci sont stockées au début de la résolution d'un niveau et ne sont plus recalculées par la suite.

La Figure 5.1 représente la structure d'un état tel qu'il est stocké en mémoire. Les croix représentent les positions qui sont utilisées respectivement par les caisses et par le pousseur. La zone du pousseur comprend également les caisses voisines de son champ d'action. Nous verrons dans la section 5.5 pourquoi nous procédons de la sorte.

Un nœud est un élément qui englobe un état et qui lui permet de se greffer sur un arbre de recherche existant. Il donne à l'état la possibilité d'interagir avec les autres états présents dans l'arbre de recherche. Comme on peut le voir sur la Figure 5.2, le nœud contient un état ainsi que des références vers son nœud père et ses nœuds fils.

Dans d'autres cas de constructions plus complexes, une contrainte impose que la liste reste triée. Chaque nœud possède alors un certain coût et la liste doit conserver un ordre prédéfini. Pour cela, l'insertion doit veiller à positionner les nouveaux éléments aux endroits adéquats. Les listes doublement chaînées auraient pu fonctionner dans un tel cas mais avec une complexité qui aurait été désastreuse en cas d'insertion triée ($O\left(n\right)$ où $n$ est le nombre d'éléments dans la liste). Nous avons donc opté pour une structure plus efficace : le tas (cf. Section 6.3.1).

Les zones ne peuvent représenter que les positions qui se situent à l'intérieur d'un niveau par rapport aux murs. En d'autres mots, les positions sur lesquelles le pousseur et les caisses peuvent évoluer. La Figure 5.3 représente l'ensemble des positions $$\{w_1,w_2,\dots ,w_{23}\}$$qui sont représentées par une zone sur ce niveau. Comme illustré, les positions sont numérotées ligne par ligne, en partant du coin supérieur gauche.

Tout l'intérêt d'une zone est de pouvoir être représentée par un nombre binaire. Dans l'exemple de la Figure 5.3, nous voyons qu'une zone est définie par 23 positions. Ces positions peuvent toutes être représentées par un bit. Le bit $i$ vaudra 1 si la position $w_i$ est comprise dans l'ensemble et $0$ si elle ne l'est pas.

Nous avons donc réduit la représentation d'un ensemble de positions à une simple valeur entière. Ceci s'avère très économique pour la consommation de mémoire car chaque état ne contiendra que deux zones (cf. Section 5.2) et donc seulement 2 valeurs entières par tranche de 32 positions dans le niveau.

Pour éviter ce problème, deux tables de traduction $Tra{d}_{a\to r}$ et $Tra{d}_{r\to a}$ sont créées. Celles-ci ont la propriété d'associer une position relative à chaque position absolue et vice versa tel qu'illustré sur la Figure 5.4. Dans le cas où aucune position relative ne correspond à une position absolue, la table de traduction retournera $-1$ pour bien indiquer l'impossibilité. C'est le cas de $Tra{d}_{a\to r}\left[A1\right]$ qui retournera $-1$ pour bien montrer l'impossibilité de représenter cette position par la méthode relative.

Tester si un état est solution consiste à comparer la zone des caisses de l'état avec la zone des goals calculée une fois pour toutes à l'initialisation de la résolution. C'est-à-dire une unique comparaison entre les entiers qui représentent les deux zones ce qui, sur la Figure 5.3, donne simplement $200704\stackrel{?}{=}4719616\Rightarrow faux$. Dans le cas où il y a plus de goals que de caisses, il faudra utiliser l'inclusion telle que décrite plus loin dans cette section.

Il suffit, comme la Figure 5.5 le montre, de rechercher l'intersection entre les deux zones. Concrètement, cela consiste à appliquer une opération binaire ET entre les représentations de la zone du pousseur et de la zone des caisses. On obtient ainsi une nouvelle zone contenant la position des caisses que le pousseur peut atteindre. On pourra ainsi travailler directement sur un sous-ensemble de caisses, ce qui diminuera la quantité de calculs nécessaires lors de la création des états fils d'un nœud de l'arbre de recherche.

Le fait que ce soit la zone du pousseur de l'état B qui doit être contenue dans celle de l'état A va à l'encontre d'une première intuition. Il faut cependant prendre en compte, comme représenté sur la Figure 5.6, que moins un état possède de caisses, plus la zone du pousseur sera grande. Dans un état sans caisses, la zone du pousseur représenterait toutes les positions de celui-ci.

À l'aide des zones, tester si $z_A\subseteq z_B$, où $z_A$ et $z_B$ sont des zones d'un même niveau, est assez simple. Il suffit d'appliquer $z_C=z_A\cap z_B$ à la manière de la Figure 5.5 et ensuite de tester la condition $z_C\stackrel{?}{=}{z}_A$. Si la condition est vérifiée, alors $z_A\subseteq z_B$, sinon $z_A⊈z_B$. Un tel test est donc très rapide car il ne concerne que des opérations élémentaires portant sur des entiers. À chaque opération sur un entier, ce sont 32 positions qui sont testées à la fois.

Il est parfois nécessaire, entre autres pour la détection des deadlocks à une caisse (cf. Section 8.1), de tester si l'intersection entre deux zones est vide ou non.

Ces problèmes de duplications de sous-arbres et de situations redondantes (cf. Figure 5.7) sont très préoccupants dans un contexte où nous essayons justement de limiter les calculs nécessaires, et donc la taille de l'arbre de recherche, pour trouver une solution.

Le fonctionnement d'une table de hachage est très simple. Il consiste en l'utilisation d'un tableau $T$ de taille $n$ dont toutes les cellules correspondent à des listes chaînées. Posons $e$ un nouvel état et $h\left(x\right)$ une fonction de hachage permettant d'obtenir un nombre naturel à partir d'un état. Un nouvel état $e$ sera ajouté au début de la liste chaînée correspondant à la cellule $T\left[h\left(e\right)modn\right]$. Si la fonction de hachage et la taille de la table sont définies afin de répartir uniformément les états, chaque liste chaînée ne contiendra en moyenne que quelques éléments. Ceci permettra de conserver une complexité moyenne en $O\left(1\right)$ pour l'ajout, la suppression ou la recherche d'un état. La Figure 5.8 schématise la manière dont les nœuds de l'arbre de recherche sont ajoutés à la table de hachage.

La fonction de hachage doit avant tout veiller à répartir uniformément les états dans la table. Elle a été implémentée de manière intuitive et son efficacité a ensuite été testée. Notre méthode consiste à additionner tous les entiers utilisés pour représenter un état (cf. Section 5.5) sur lesquels un $modulo\left(n\right)$, où $n$ correspond à la taille de la table, est à chaque fois appliqué. Un dernier $modulo\left(n\right)$ est ensuite appliqué au total obtenu.

La table de hachage a été testée de manière intensive (cf. Tableau 5.1 et Figure 5.9) avec la création d'un arbre de recherche contenant environ 4250000 nœuds. Les résultats attendus correspondent à une moyenne de 5 éléments par liste chaînée. Les résultats obtenus sont assez concluants car 65% des listes contiennent jusqu'à 5 éléments, 90% des listes contiennent jusqu'à 10 éléments et 99% des listes possèdent 20 éléments ou moins. Sans être exceptionnels, ces résultats ne justifient pas la recherche d'une meilleure fonction de hachage.

Nous avons vu dans la Section 4.1 que la résolution d'un problème de Sokoban nécessitait la construction d'un arbre de recherche. Le moment est venu de décrire les différentes façons de construire cet arbre. Chacune des méthodes proposées possède ses avantages et inconvénients et diffère essentiellement des autres par l'ordre dans lequel les nœuds dans la liste d'attente seront placés dans l'arbre de recherche.

Pour illustrer ces différents parcours, nous allons utiliser l'arbre de recherche de la Figure 6.1.

Le parcours en largeur utilise une liste d'attente FIFO (First In, First Out), c'est-à-dire une file, pour traiter les nœuds en attente. De cette façon, les nœuds arrivés en premier dans la liste d'attente seront placés en priorité dans l'arbre de recherche. Étant donné que l'Algorithme 1 utilise toujours le premier nœud de la liste pour le placer dans l'arbre de recherche, la fonction ajouteDansListe(noeud) va insérer chaque nouveau nœud à la fin de la liste chaînée tel qu'illustré sur la Figure 6.2.

Le parcours en largeur explore en priorité les nœuds les plus hauts de l'arbre de recherche. Du fait que dans notre solveur, chaque saut d'un nœud à un autre corresponde à une seule poussée, nous pouvons en déduire que l'optimalité en terme de poussées de la solution sera atteinte. Sur la Figure 6.1, nous pouvons voir deux nœuds qui contiennent des états solutions. L'une des deux solutions est optimale avec 2 poussées (nœud 8) et l'autre ne l'est pas avec 3 poussées (nœud 12). Avec le parcours en largeur, la solution qui sera trouvée la première sera bien celle qui est optimale.

Le parcours en profondeur utilise une liste d'attente LIFO (Last In, First Out), c'est-à-dire une pile, pour traiter les nœuds en attente. De cette façon, les nœuds arrivés en dernier dans la liste d'attente seront placés en priorité dans l'arbre de recherche, privilégiant ainsi les nœuds plus profonds. Étant donné que l'Algorithme 1 utilise toujours le premier nœud de la liste pour le placer dans l'arbre de recherche, la fonction ajouteDansListe(noeud) va insérer chaque nouveau nœud au début de la liste chaînée tel qu'illustré sur la Figure 6.3.

Le parcours en profondeur explore en priorité les nœuds les plus profonds de l'arbre de recherche. Certains nœuds situés au niveau $p$ seront ainsi explorés avant que tous les nœuds situés au niveau $p-1$ ne le soient. Une solution non-optimale pourrait donc être trouvée avant la solution optimale. Une telle situation est illustrée avec la Figure 6.1. Si un parcours en profondeur était appliqué sur l'arbre de recherche, le premier nœud solution trouvé serait le 12. Le problème est qu'un autre nœud non exploré, le 8, contient une meilleure solution.

Si l'arbre binaire contient $p$ niveaux, alors celui-ci doit être complet sur ses $p-1$ premiers niveaux et le dernier doit être rempli de gauche à droite. Un des aspects les plus pratiques d'un tas est qu'il peut être stocké dans un tableau T tel qu'illustré sur la Figure 6.4. L'arbre binaire correspondant au tas doit respecter un certain ordre dans ses éléments : si A et B sont deux nœuds de l'arbre binaire tels que A est le père de B, alors $cout\left(A\right)$$\le cout\left(B\right)$.

Lors du parcours, il a été prévu dans la Section 5.6 de rejeter un état si celui-ci est déjà présent dans l'arbre de recherche. Dans le cas du parcours A*, afin de garder l'optimalité des solutions, il ne suffit plus de rejeter tous les doublons. En effet, deux états identiques peuvent se trouver à deux profondeurs différentes de l'arbre de recherche et possèder deux valeurs différentes pour $g\left(n\right)$ où $n$ est le nœud contenant l'état. Si le nœud dont la valeur est la plus petite, et donc la meilleure, est traité en deuxième lors du parcours, il sera considéré comme doublon et rejeté à tort. Le risque est que ce nœud mène justement à la solution optimale, qui sera alors perdue.

Le tas est organisé de façon à ce que les nœuds les plus prometteurs soient prioritaires. La méthode simple consiste à placer en tête de liste ceux pour lesquels le coût $f\left(n\right)$ est le plus petit. Il est cependant possible d'affiner ce résultat. En cas d'égalité pour les valeurs de $f\left(n\right)$, une deuxième condition portant sur les valeurs de $h\left(n\right)$ est ajoutée. Pour deux valeurs égales de $f\left(n\right)$, la plus petite valeur de $h\left(n\right)$ sera prioritaire tel qu'illustré sur la Figure 6.5.

La Figure 6.5 représente les différentes structures qui interviennent lors d'un parcours A*. Pour une lecture plus facile, la liste d'attente n'est pas représentée sous la forme d'un tas mais sous celle d'une liste chaînée triée. On voit que le parcours se dirige assez facilement vers le nœud solution 15 en évitant les autres nœuds dont le coût $f\left(n\right)$ est plus élevé. Si aucune solution en 5 poussées n'était possible, le prochain nœud traité serait le premier de la liste d'attente et donc celui qui est le plus prometteur en 6 poussées.

La Figure 6.6 montre différentes itérations du parcours A*. Nous pouvons y voir que la solution optimale sera toujours trouvée la première (lors de l'itération pour laquelle $f_{max}=10$). Des solutions moins bonnes pourraient être trouvées lors d'itérations suivantes.

Nous avons remarqué que l'évolution du coût a tendance à évoluer par pas de 2. En effet, si le pousseur est placé du mauvais côté pour pousser une caisse, il va d'abord devoir la pousser une première fois, la contourner, puis la repousser une deuxième fois (cf. Figure 6.7). L'estimation du coût est ainsi faussée de 2 poussées. Pour ne pas inutilement incrémenter la limite par pas de 1 si on peut progresser plus rapidement, nous allons garder en mémoire le nœud rejeté dont le coût est le plus petit. Par exemple si la limite actuelle est de 10 et qu'à la fin de l'itération, le coût le plus petit qui a été rejeté est 12, nous pourrons commencer l'itération suivante à 12.

Comme nous le verrons dans le Chapitre 10, le temps de calcul de l'estimation des caisses n'est pas un problème majeur. Ceci est lié au fait que le calcul n'est réalisé qu'une seule fois par niveau. Par la suite, les résultats seront réutilisables à l'infini. Il est donc préférable d'utiliser les méthodes les plus précises même si elles s'avèrent souvent plus lentes.

Chaque état contient des caisses sur des emplacements différents. Celles-ci peuvent potentiellement occuper toutes les positions internes d'un niveau (cf. Figure 5.3). Nous allons construire une matrice $M$ carrée $N\times N$, où $N$ est le nombre de positions internes, et dans laquelle la cellule $M_{i,j}$ où $1\le i,j\le N$ contiendra le nombre de poussées requises pour déplacer une caisse située sur la position $i$ vers la position $j$. Cette matrice $M$ sera aussi appelée la table des estimations.

En théorie, nous n'avons besoin que des estimations des caisses vers les différents goals. Dans la pratique il est intéressant de généraliser pour trouver les estimations des caisses vers toutes les positions. Ces informations nous seront utiles dans la suite pour, par exemple, le calcul des macro-poussées (cf. Section 12.1). De plus, avec l'algorithme de Dijkstra, connaître les estimations des caisses vers les goals ou vers l'ensemble des autres positions nécessite, à peu de choses près, la même quantité de calculs.

La taxi-distance, aussi appelée Distance de Manhattan, doit son nom à la distance que doivent effectuer les taxis de Manhattan pour joindre deux points dans la ville. Étant donné la structure de Manhattan qui est composée de quartiers rectangulaires et alignés, la distance réellement parcourue par un taxi correspondra à notre définition et non à la distance euclidienne. La Figure 7.1 montre que, quel que soit le chemin emprunté par le taxi dans Manhattan, la longueur totale vaudra 8 longueurs de blocs et correspondra à la taxi-distance.

La Figure 7.2 représente la taxi-distance entre la caisse se situant sur la position F5 et l'ensemble des autres positions joignables.

La Figure 7.3 représente le graphe connexe utilisé pour calculer l'estimation de la caisse F5 ainsi que le niveau qui comprend les estimations obtenues de la sorte. Sachant que chaque arc du graphe possède un poids unitaire, il est facile d'y appliquer directement l'algorithme de Dijkstra. L'objectif est de trouver le chemin minimal permettant de pousser la caisse $s_0$ vers les trois goals $s_1,s_2$ et $s_3$, et par la même occasion, les chemins minimaux de la caisse vers toutes les autres positions.

À titre d'exemple, sur la Figure 7.3, après une poussée de E4 vers D4, le pousseur se trouvera sur la position E4. Par la suite, il n'aura pas la possibilité de déplacer la caisse sur la position D5, contrairement à ce qui est indiqué dans le graphe.

Dans le but de réutiliser des fonctionnalités qui ont déjà été implémentées, cette méthode passe par la création d'un niveau temporaire comprenant une seule caisse et un seul goal. Sur ce niveau, un parcours en largeur sera appliqué tel qu'il a été décrit dans la Section 6.1. Celui-ci permet de trouver la solution optimale d'un niveau. Le nombre de poussées de la solution optimale servira donc d'estimation pour déplacer une caisse de la position $i$ vers la position $j$.

La Figure 7.4 représente le graphe connexe amélioré obtenu en procédant comme indiqué. Pour une meilleure lisibilité, les sommets qui correspondent à une même position sont entourés par des cercles plus clairs. Ceux-ci ne sont pas à prendre en considération dans le graphe connexe. Même si le graphe connexe semble peu lisible à première vue, il est possible de transiter d'un sommet à l'autre en partant de $s_0$ pour arriver à l'un des goals. L'important est de remarquer que le chemin emprunté sera plus long que sur la Figure 7.3 car les contraintes imposées par la position du pousseur ne permettent pas toujours le déplacement voulu.

La Figure 7.5 représente un nœud ainsi que la matrice $O$ correspondante. Pour être fidèle à la réalité, la matrice $M$ utilisée pour créer la matrice $O$ a été générée à l'aide de la méthode de la Section 7.1.3 impliquant Dijkstra et le graphe amélioré. L'intersection entre la ligne $c_2$ et la colonne $g{}_3$ contient l'estimation requise pour positionner la caisse $c_2$ sur le goal $g_3$.

L'application de cette méthode sur notre exemple (cf. Figure 7.5) conduit à associer :

Cette méthode ne conserve pas la propriété d'admissibilité car il existe des états pour lesquels $h\left(n\right)>h^{*}\left(n\right)$. L'un de ces états est illustré sur la Figure 7.6. Dans celui-ci, $h^{*}\left(n\right)=9$ et $h\left(n\right)=11$. Ceci est dû au fait que, pour minimiser l'estimation totale, il est plus intéressant de déplacer la caisse $c_1$ vers le goal le plus éloigné ($g_2$) que vers le goal le plus proche ($g_1$).

Pour que la méthode puisse donner des résultats admissibles, il faut qu'elle soit capable de trouver une association entre les caisses et les goals, à l'aide de la matrice $O$, de manière à minimiser l'estimation totale. La matrice $O$, qui contient les estimations des caisses vers chacun des goals, peut être représentée dans un graphe biparti tel qu'illustré sur la Figure 7.7. Chaque arête du graphe biparti possède un poids. L'arête qui relie la caisse $i$ au goal $j$ possède le poids relatif à la position $O_{i,j}$ de la matrice.

Remarquons que nous obtenons là un problème typique d'assignation dans un graphe biparti complet pondéré. Le but est de trouver la couverture de poids minimum (minimum weighted bipartite matching) permettant de pousser chaque caisse sur son goal. Pour cette opération, un algorithme se présente à nous : la méthode Hongroise. Gardons à l'esprit que cet algorithme est en $O\left(n³\right)$ où $n$ représente le nombre de caissesFrank (Pas d'année). La puissance demandée pour ce traitement, à chaque nœud de l'arbre de recherche, représente une partie très gourmante de notre solveur.

Pour ne pas devoir réimplémenter la méthode Hongroise à partir de rien, une version C++ existanteWeaver (Pas d'année), déjà déboguée et optimisée, a été intégrée à notre solveur. Nos données ont été adaptées pour correspondre aux contraintes des fonctions existantes.

Trois méthodes ont été présentées pour calculer l'estimation d'une caisse et trois méthodes ont été présentées pour calculer l'estimation totale. En théorie il y a donc neuf possibilités d'associations entre ces méthodes comme illustré sur la Figure 7.8. Dans la pratique, on peut directement éliminer la méthode de la Section 7.2.2 du goal le plus proche avec réservation car elle ne respecte pas la propriété d'admissibilité du parcours A*. Si une solution est trouvée, il ne sera donc pas possible d'affirmer que celle-ci est optimale.

Des six associations restantes possibles et qui sont admissibles, il est préférable de prendre celle qui maximise l'estimation de manière à être le plus proche de la valeur $h^{*}\left(n\right)$. Comme le démontre la Figure 7.9, c'est l'algorithme de Dijkstra avec graphe amélioré qui majore le plus l'estimation d'une caisse vers chacune des positions. C'est donc la méthode qui s'avère la plus efficace. Rien d'étonnant à cela, c'est la méthode qui prend en compte le plus de contraintes, dont la position du pousseur.

Un exemple de deadlock en coin est illustré sur la Figure 8.2. Selon les règles du jeu, il parait clair que la caisse située sur la position absolue D2 ne pourra pas rejoindre l'un des goals.

Pour détecter les positions qui provoquent des deadlocks en coin, nous parcourons toutes les positions internes d'un niveau afin de tester si elles sont bornées par des murs, sur deux côtés consécutifs, de manière à former un coin. Si tel est le cas, nous enregistrons une zone ne comprenant que les positions concernées comme illustré à l'aide de croix sur la Figure 8.2. La zone sera utilisée par la suite afin de rejeter de l'arbre de recherche tous les états qui ont une caisse sur l'une des croix.

Un exemple de deadlock en ligne est illustré sur la Figure 8.3. Selon les règles du jeu, il parait clair que la caisse située sur la position absolue C2 ne pourra pas s'écarter du mur pour rejoindre l'un des goals.

Une fois tous les deadlocks en ligne trouvés, nous enregistrons une zone ne comprenant que les positions concernées comme illustré à l'aide de croix sur la Figure 8.4. La zone sera utilisée par la suite afin de rejeter de l'arbre de recherche tous les états qui ont une caisse sur l'une des croix.

Grâce à l'utilisation des zones, les deadlocks à une caisse sont rapidement évincés de l'arbre de recherche. L'idée consiste à créer une zone $z_{deadlock}$ comprenant toutes les positions pour lesquelles l'état sera déclaré comme un deadlock si une caisse s'y trouve. Une telle zone est illustrée sur la Figure 8.5.

La caisse qui vient d'être poussée sur la position absolue H9 de la Figure 8.6 provoque un deadlock en carré avec les trois autres positions G8, G9 et H8.

Le deadlock en Z est décliné en 4 versions qui sont représentées sur la Figure 8.7.

La méthode de la deadlock zone a été conçue en regardant le solveur s'exécuter sur certains niveaux. Il apparaissait régulièrement que certaines caisses n'évoluaient plus dans l'un des sous-arbres de l'arbre de recherche, alors que toutes les autres caisses continuaient de bouger. En analysant la situation, le phénomène était compréhensible car, peu importe la façon dont il aurait été possible de pousser l'une des caisses bloquées, elle introduisait toujours un deadlock. L'état courant n'était donc pas reconnu comme un deadlock mais il n'était pas possible de dégager l'une des caisses bloquées sans en provoquer un. La Figure 8.8 montre cette situation par les deux caisses bloquées situées sur les positions absolues C3 et D3. Il n'est pas possible de bouger l'une de ces caisses sans provoquer de deadlock en coin.

La méthode proposée a donc pour objectif de découvrir les sous-ensembles de caisses qui ne provoquent pas directement de deadlock mais qui ne peuvent pas être poussées sans en provoquer un. De manière générale, les caisses qui sont bloquées entourent, avec des murs, un certain nombre de positions vides. Le fonctionnement de la méthode consiste à détecter des positions vides dont les caisses limitrophes sont toutes bloquées. On appellera ces positions et ces caisses bloquées une deadlock zone. La Figure 8.9 indique trois de ces deadlock zones.

De manière générale, la méthode de la deadlock zone est assez coûteuse mais permet de détecter des situations de deadlock éventuellement provoquées par un grand nombre de caisses (cf. Figure 8.10). Cette méthode vérifie, pour chaque état, que celui-ci ne contient pas une deadlock zone. Si un état en contient une, alors il est rejeté de l'arbre de recherche.

L'aspect le plus intéressant de cette méthode est qu'elle est récursive. En effet, lorsqu'on teste si une caisse est bloquée, on teste ses déplacements possibles et on regarde si ceux-ci provoquent, ou non, un deadlock. Toutes les techniques de détection de deadlock, y compris celle de la deadlock zone, sont donc à nouveau appliquées sur l'état induit par la poussée de la caisse. Cette capacité à fonctionner récursivement permet d'anticiper des situations de deadlock plusieurs poussées avant qu'elles ne se produisent (cf. Figure 8.11).

Rappelons-nous la définition d'un deadlock : “un deadlock est un état de l'arbre de recherche à partir duquel il est impossible de trouver un état solution”. Un deadlock est souvent provoqué par un sous-état de l'état testé. Il dépend donc des positions des caisses et de celle du pousseur. On peut d'ailleurs remarquer sur la Figure 8.12 qu'un deadlock ne serait pas détecté si le pousseur occupait la position D12.

Nous verrons que la recherche passive de deadlocks est un cas particulier de la recherche passive de pénalités. La Section 9.2.1 décrit plus en profondeur la technique employée pour créer les états à 1, 2 ou 3 caisses.

Comme la recherche passive, la recherche active de deadlocks est un cas particulier de la recherche active de pénalités. La Section 9.2.2 explique comment créer des sous-états à tester à partir d'un état de l'arbre de recherche.

Les techniques développées dans le Chapitre 7 permettent d'obtenir une estimation $h\left(n\right)$ en fonction des positions des caisses et des goals dans le nœud. Rien dans ces techniques ne permet de mettre en évidence le surcoût occasionné lorsque plusieurs caisses se gênent mutuellement.

Le cas d'un sous-état contenant des caisses qui se gênent mutuellement, illustré sur la Figure 9.1, n'est pourtant pas rare. À partir des méthodes d'estimation décrites précédemment, on obtient pour ce sous-état $h\left(n\right)=20$. Dans les faits cependant, on voit directement que la caisse située sur la position absolue H9 ne pourra pas être atteinte par le pousseur sans qu'il ne commence par pousser la caisse située en H6 vers le bas. Ce mouvement supplémentaire donnera au final $h^{*}\left(n\right)=22$. La différence entre l'estimation et le coût réel est donc de 2.

Cette différence entre coût estimé et coût réel du sous-état, que nous appellerons pénalité d'un sous-état, devra s'appliquer dans tous les états dans lesquels ce sous-état est inclus. La pénalité déduite d'un état $e$ comprend l'application des pénalités (cf. Section 9.4) de tous les sous-états $s{}_1,s{}_2,\dots ,s{}_n$ tels que $s{}_1\in e,s{}_2\in e,\dots ,s{}_n\in e$. Contrairement à la pénalité d'un sous-état, la pénalité déduite d'un état n'est pas toujours la différence exacte entre le coût estimé et le coût réel, ce n'est qu'une meilleure approche de la valeur $h^{*}\left(n\right)$

Cette technique est une généralisation de celle des deadlocks méthodiques (cf. Section 8.2.3). En effet, un sous-état qui provoque un deadlock peut être considéré comme un sous-état dont la pénalité est infinie. L'état qui comprend ce sous-état aura alors une pénalité déduite infinie et une valeur $h\left(n\right)=\infty$. Le coût du nœud contenant l'état va alors provoquer son rejet de l'arbre de recherche.

La zone des caisses de chaque état sera ainsi créée à partir des positions des caisses obtenues par ce procédé. Il faut ensuite chercher toutes les zones du pousseur possibles à partir de chaque zone des caisses. Pour chaque couple possible ($z_{caisses}$, $z_{pousseur}$) tel qu'illustré sur la Figure 9.2, un état sera créé et testé. La position du pousseur dans le niveau transmis au solveur bestPushes n'a que peu d'importance tant qu'elle se situe bien dans la zone du pousseur trouvée. Dans notre exemple, le pousseur se situe chaque fois sur la première position relative à la zone du pousseur à tester.

Il serait trop optimiste de tester dans un temps raisonnable tous les sous-états pouvant être formés à partir des caisses présentes dans l'état. Nous allons devoir utiliser des techniques pour obtenir en un temps minimum les sous-états qui ont le plus de chances de mener à des pénalités. La méthode employée s'inspire fortement de celle des Pattern Search développée par Andreas JunghannsJunghanns (1999).

Pour illustrer cette méthode, nous avons repris l'exemple présenté dansJunghanns (1999) La Figure 9.3 correspond à une poussée. La recherche active va s'appliquer sur la caisse qui vient d'être poussée en créant plusieurs sous-états qui sont susceptibles de provoquer des pénalités comme illustré sur la Figure 9.4.

Le chemin des caisses récupéré à partir de la solution du sous-état représenté en haut à gauche de la Figure 9.4 passe par les positions absolues C6, C5, C4, C3. On ajoute donc la caisse située sur la position C5 dans le sous-état suivant. Pour le troisième sous-état représenté, on utilise le chemin du pousseur car aucune caisse ne se trouve plus sur le chemin des caisses.

Sur l'exemple de la Figure 9.5, on remarque que la différence entre le coût réel et le coût estimé est de 1. Une pénalité de 1 devrait donc être assignée à ce sous-état. Cependant, il existe un sous-ensemble de goals pour lequel l'estimation correspond bien au coût réel. Dans ce cas, la pénalité n'est pas validée car elle va majorer $h^{*}\left(n\right)$ si la solution comprend les trois caisses positionnées sur les goals F14, F15 et K14.

Il peut arriver qu'un sous-état pénalisé contienne plus de caisses que nécessaire pour que la pénalité s'applique (cf. 4ème état de la Figure 9.4). Il faut donc trouver le sous-état pénalisé minimum, c'est-à-dire le sous-état qui comprend le moins de caisses tout en provoquant la même pénalité. Pour y arriver, pour chaque état de $c$ caisses qui est validé, nous allons tester les pénalités de tous les sous-états de $n-1$ caisses. Par récursivité, tous les sous-états qui provoquent une pénalité seront trouvés.

La méthode utilisée consiste à classer tous les sous-états pénalisés en fonction du nombre de caisses qu'ils contiennent en utilisant une liste par nombre de caisses. Ensuite, chaque liste sera triée par ordre décroissant de pénalité pour obtenir une organisation comme celle illustrée sur la Figure 9.6.