Représenter les actions en PDDL

La recherche traitait un état comme une boîte noire dont on pouvait seulement tester s’il était but. La logique savait regarder à l’intérieur d’un état, mais devait raisonner sur des énoncés clos, et s’y noyait. La planification emprunte la voie médiane : un état est une collection de variables, et c’est cette structure qui rend possibles des heuristiques automatiques.

Les états comme ensembles de fluents

Un état est une conjonction de fluents, c’est-à-dire d’atomes clos et sans symbole de fonction. Pour le problème de la roue de secours, l’état initial est

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

Trois restrictions rendent tout cela traitable, et non pas seulement expressif.

• Clos. $\mathrm{At}(x, y)$ n’est pas un fluent d’état : il contient une variable.
• Positif. $\neg \mathrm{Poor}$ est interdit. Sous l’hypothèse du monde clos, tout fluent non mentionné est faux : la négation est donc gratuite et implicite plutôt qu’écrite noir sur blanc.
• Sans symbole de fonction. $\mathrm{At}(\mathrm{Father}(\mathit{Fred}), \mathit{Sydney})$ est exclu ; l’hypothèse des noms uniques fait alors de constantes distinctes des objets distincts.

Le bénéfice, c’est qu’un état se lit de deux façons à la fois : comme une conjonction logique sur laquelle raisonner, ou comme un ensemble de fluents à manipuler par des opérations ensemblistes. La plupart des algorithmes de planification retiennent la seconde lecture, et c’est pourquoi le code ci-dessous est si court.

Les actions comme schémas

Le problème du cadre est la difficulté de dire ce qui reste inchangé quand quelque chose change. La planification classique le contourne en se concentrant sur des problèmes où la plupart des actions laissent la plupart des choses tranquilles, puis en décrivant une action uniquement par ce qui change. Tout ce qui n’est pas mentionné persiste.

Un schéma d’action est une description à variables qui représente de nombreuses actions instanciées :

$$\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}$$

L’effet se scinde en une liste d’ajout, les littéraux positifs, et une liste de suppression, les littéraux niés. Appliquer une action instanciée $a$ à un état $s$ tient alors en une ligne d’arithmétique ensembliste :

$$\mathrm{Result}(s, a) = (s \setminus \mathrm{Del}(a)) \cup \mathrm{Add}(a) ,$$

et $a$ est applicable dès que $\mathrm{Precond}(a) \subseteq s$.

Cette mise en variables fait toute l’économie de la représentation. Dans le monde du wumpus, l’agent logique avait besoin d’un énoncé distinct pour avancer, et cela pour chacune des quatre orientations, $T$ pas de temps et $n^2$ emplacements. Un seul schéma remplace les $4Tn^2$ énoncés.

Instanciation et dénombrement

Un schéma est une promesse ; un planificateur travaille sur les actions instanciées qu’il déploie. Le domaine du fret aérien compte trois schémas et, avec deux cargaisons, deux avions et deux aéroports, ils se déploient en vingt actions instanciées.

Remarquez le garde-fou. Sans lui, le schéma produit aussi $\mathrm{Fly}(P_1, JFK, JFK)$, dont l’effet serait $\neg\mathrm{At}(P_1, JFK) \wedge \mathrm{At}(P_1, JFK)$ - une contradiction. Le remède est une précondition d’inégalité exigeant que les deux aéroports diffèrent.

L’instanciation passe par ailleurs très mal à l’échelle, et c’est justement pourquoi l’on garde les schémas aussi longtemps que possible. Avec dix avions et cinq aéroports, $\mathrm{Fly}$ donne à lui seul $10 \times 5 \times 4 = 200$ actions instanciées, et le compte croît comme le produit de tous les domaines figurant dans le schéma.

Bougez les trois domaines ci-dessous et regardez le produit. Avec deux de chaque, ce sont les vingt actions ci-dessus ; poussez à dix avions et cinq aéroports et Fly contribue à elle seule deux cents, avant tout autre schéma. Load et Unload croissent avec le fret et Fly non, car un schéma ne se développe que sur les arguments qu’il mentionne effectivement.

La garde mérite d’être désactivée une fois. Sans la précondition d’inégalité, le schéma produit un Fly(p, a, a) par avion et par aéroport, et la figure les compte. Ce n’est pas un détail de propreté : sans elle, le schéma décrit des actions dont l’effet affirme et nie à la fois que l’avion est là où il est.

Un but est une précondition

Un but s’écrit comme une précondition : une conjonction de littéraux, éventuellement à variables, lues existentiellement. Ainsi $\mathrm{At}(p, \mathit{SFO}) \wedge \mathrm{Plane}(p)$ signifie qu’un avion se trouve à San Francisco. Un état satisfait un but lorsqu’il l’implique, ce qui, sous l’hypothèse du monde clos, se réduit à un test d’inclusion sur les littéraux positifs.

Ce n’est pas une logique affaiblie, c’est un fragment choisi. Chaque restriction - clos, positif, sans symbole de fonction, réduit aux effets - existe pour que la structure d’une action reste ouverte à l’inspection. La leçon suivante transforme cette structure en recherche, et celle d’après en heuristiques dérivées automatiquement des schémas eux-mêmes. Rien de tout cela n’est possible lorsqu’un état est un atome.

Avant le quiz

Sachez dire ce qu’est une représentation factorisée et ce qu’elle apporte, énumérer les trois restrictions pesant sur les fluents d’état et le rôle de l’hypothèse du monde clos, écrire un schéma d’action et l’appliquer comme une opération ensembliste, compter les actions instanciées qu’un schéma déploie, et expliquer pourquoi une précondition d’inégalité est parfois nécessaire.