La planification classique : schémas, relaxations et graphes

La recherche résoudra un problème de planification, pourvu qu’on lui donne une heuristique. La question intéressante est de savoir d’où vient l’heuristique, et la réponse se révèle être une thèse sur la représentation plutôt que sur les algorithmes.

A. Ce qu’achète un état factorisé

Un agent de résolution de problèmes traite un état comme un atome. Il ne peut rien en faire d’autre que tester s’il est un but, si bien que toute heuristique doit lui être fournie de l’extérieur. Un agent logique, lui, peut regarder à l’intérieur d’un état, mais il raisonne avec des phrases closes et s’y noie : dans le monde du wumpus, avancer réclamait une phrase distincte pour chacune des quatre orientations, $T$ pas de temps et $n^2$ localisations.

La planification prend la voie moyenne. Un état est une collection de variables - une conjonction de fluents clos, positifs et sans symbole de fonction :

$$\mathrm{At}(\mathit{Flat}, \mathit{Axle}) \wedge \mathrm{At}(\mathit{Spare}, \mathit{Trunk}) .$$

Sous l’hypothèse du monde clos, tout ce qui n’est pas mentionné est faux : la négation n’a donc jamais à être écrite. L’état se lit alors de deux façons à la fois, comme une phrase logique ou comme un ensemble, et presque tous les algorithmes retiennent la seconde.

Les actions sont des schémas, qui ne décrivent que ce qui change :

$$\begin{array}{l} \mathrm{Action}(\mathrm{Fly}(p, \mathit{from}, \mathit{to}), \\ \quad \textsc{Precond}: \mathrm{At}(p, \mathit{from}) \wedge \mathrm{Plane}(p) \wedge \mathrm{Airport}(\mathit{from}) \wedge \mathrm{Airport}(\mathit{to}) \\ \quad \textsc{Effect}: \neg\mathrm{At}(p, \mathit{from}) \wedge \mathrm{At}(p, \mathit{to})) \end{array}$$

Les littéraux positifs forment la liste d’ajout, les littéraux niés la liste de suppression, et appliquer une action tient en une seule expression ensembliste : $\mathrm{Result}(s, a) = (s \setminus \mathrm{Del}(a)) \cup \mathrm{Add}(a)$. Le problème du cadre n’est pas tant résolu qu’écarté : l’attention se restreint aux domaines où la plupart des actions laissent la plupart des choses intactes, et la persistance devient le comportement par défaut.

B. Le coût de l’instanciation

Un schéma est compact ; ses instances ne le sont pas. Avec deux cargaisons, deux avions et deux aéroports, trois schémas de fret aérien se déploient en vingt actions closes, et le seul schéma de vol, avec dix avions et cinq aéroports, en donne $10 \times 5 \times 4 = 200$.

La garde de la dernière compréhension n’est pas de la coquetterie. Sans elle, le schéma produit $\mathrm{Fly}(P_1, JFK, JFK)$, dont l’effet est $\neg\mathrm{At}(P_1, JFK) \wedge \mathrm{At}(P_1, JFK)$, une contradiction ; le correctif de principe est une précondition d’inégalité.

Voilà pourquoi la recherche en avant peine. Elle est complète et, à coûts uniformes, optimale, mais elle envisagera de faire voler un avion vide entre deux aéroports hors sujet aussi volontiers que de charger la bonne cargaison. La recherche en arrière depuis le but ne considère que les actions pertinentes, régressant un but en $(g \setminus \mathrm{Add}(a)) \cup \mathrm{Precond}(a)$, et branche bien moins - mais ses nœuds sont des ensembles d’états plutôt que des états, ce qui exige de l’unification et rend les bonnes heuristiques plus difficiles à définir.

C. Des heuristiques par suppression

C’est ici que la représentation paie. Une heuristique est le coût d’un problème plus facile, et les schémas peuvent tout simplement être édités.

Ignorer les préconditions retire toute précondition, rendant chaque action applicable partout. Il ne reste qu’à couvrir les littéraux de but non satisfaits avec le moins de listes d’ajout possible. C’est de là que viennent les heuristiques classiques du taquin : dans le taquin à huit cases, abandonner $\mathrm{Blank}(s_2) \wedge \mathrm{Adjacent}(s_1, s_2)$ donne le nombre de tuiles mal placées, et abandonner $\mathrm{Blank}(s_2)$ seul donne la distance de Manhattan. Les deux tombent mécaniquement.

Ignorer les listes de suppression retire tout effet négatif. Plus rien ne peut défaire quoi que ce soit, le progrès est donc monotone et l’escalade de colline trouve un plan relâché approché en temps polynomial.

Sur le fret aérien, les deux annoncent 2 à l’état initial contre un coût réel de 6 (le chiffre sans listes de suppression compte les couches du problème relâché, comme le fait un graphe de planification ; le plus court plan relâché compte lui-même 5 actions) :

Les marges sont faibles parce que le problème est petit. Ce qui compte, c’est que personne n’a écrit d’heuristique pour le fret aérien.

D. Ce que remarque un graphe de planification

Un graphe de planification alterne niveaux de littéraux et niveaux d’actions, ajoute une action de persistance pour chaque littéral, et se construit en temps polynomial sans aucune recherche. Sa substance, ce sont les liens de mutex, qui enregistrent les paires ne pouvant tenir ensemble : actions aux effets incohérents, actions qui interfèrent, actions aux besoins concurrents, et littéraux dont toute paire de producteurs est mutex.

Prenez le plus petit problème qui fasse voir la chose. Au départ vous avez un gâteau ; vous voulez l’avoir et l’avoir mangé. Manger supprime le fait d’avoir, et cuire exige de ne pas avoir.

Les deux littéraux de but apparaissent dès $S_1$, si bien qu’un raisonnement littéral par littéral conclut qu’une étape suffit. Elle ne suffit pas : en $S_1$ ils sont mutex, car la seule façon d’avoir le gâteau est de le faire persister et la seule façon de l’avoir mangé est de le manger, et manger supprime le fait d’avoir. À $S_2$ le mutex a disparu et le graphe a atteint son palier.

Le coût de niveau d’un littéral est le niveau où il apparaît pour la première fois, ce qui donne trois heuristiques. Le niveau maximal prend le plus grand, la somme des niveaux les additionne, et le niveau d’ensemble attend le premier niveau où tous les littéraux de but apparaissent sans aucun mutex entre eux. Ici elles donnent $1$, $1$ et $2$. Le plan optimal - manger le gâteau, puis en cuire un autre - a pour longueur $2$ : seul le niveau d’ensemble est donc juste, et lui seul a regardé si les buts pouvaient coexister.

Le niveau maximal et le niveau d’ensemble sont admissibles, et le niveau d’ensemble domine. La somme des niveaux traite les sous-buts comme indépendants et peut dépasser la cible, elle est donc inadmissible en général, ce qui ne l’empêche pas d’être la plus utile des trois en pratique.

La figure ci-dessous construit ce graphe au lieu de le recopier : chaque mutex y est calculé à partir des trois conditions sur les actions et des deux sur les littéraux, et c’est pourquoi les comptes tombent d’eux-mêmes sur 0, 4, 3, 3. Regardez la ligne qui joint les deux littéraux du but. Elle est là en S1 et disparue en S2, et cette seule ligne évanouie fait toute la différence entre une heuristique qui répond 1 et la vraie réponse, 2.

Où cela vous laisse

L’approximation ne va que dans un sens. Un littéral absent au niveau $i$ est véritablement inatteignable en $i$ étapes, et c’est ce qui fait des coûts de niveau des bornes inférieures. Un littéral présent, même sans mutex, ne promet rien ; seules les incohérences deux à deux sont calculées, et un conflit à trois passe donc inaperçu. Cette asymétrie est la forme honnête de tout le sujet : la planification classique ne rend pas faciles les problèmes difficiles, elle fait de la description d’un problème quelque chose qu’un solveur peut lire. Le parcours Planification classique construit les schémas, les relaxations et le graphe à la main et en code.