Planification automatique

La planification classique s’adresse aux environnements complètement observables, déterministes, statiques et mono-agents, et son apport est représentationnel plutôt qu’algorithmique. Un état est une conjonction de fluents instanciés, positifs et sans symboles de fonction. Sous l’hypothèse du monde clos, tout fluent non mentionné est faux, si bien que la négation n’a jamais à être écrite, et sous l’hypothèse des noms uniques, des constantes distinctes désignent des objets distincts. L’effet est qu’un état peut se lire indifféremment comme une formule logique avec laquelle raisonner ou comme un ensemble que l’on manipule, et la plupart des algorithmes de planification retiennent la seconde lecture.

Les actions sont données sous forme de schémas en PDDL, le Planning Domain Definition Language, descendant de STRIPS. Un schéma nomme l’action, énumère ses variables, puis donne une précondition et un effet. Les littéraux positifs de l’effet forment la liste d’ajout et les littéraux niés la liste de suppression, de sorte qu’appliquer une action instanciée à un état tient en une seule expression ensembliste : retirer la liste de suppression, puis ajouter la liste d’ajout. Tout le reste persiste par défaut. Voilà comment la planification classique traite le problème du cadre - non en prouvant ce qui reste inchangé, mais en restreignant l’attention aux domaines où la plupart des actions laissent la plupart des choses tranquilles, pour ne décrire alors que le changement.

Un schéma est une représentation relevée, qui hisse le raisonnement de la logique propositionnelle vers un fragment restreint de la logique du premier ordre. Là où un agent propositionnel réclamait une formule par orientation, par pas de temps et par lieu, un unique schéma les couvre toutes. L’économie est réelle, mais l’instanciation coûte cher : un schéma se développe sur le domaine de chacun de ses arguments, si bien qu’une action de vol avec dix avions et cinq aéroports fournit à elle seule deux cents actions instanciées. Un peu de soin s’impose aussi vis-à-vis des instances parasites, comme voler d’un aéroport vers lui-même, qu’une précondition d’inégalité vient exclure.

Un but s’écrit comme une précondition, c’est-à-dire comme une conjonction de littéraux dont les variables se lisent existentiellement, et un état l’atteint lorsqu’il l’implique. Cela achève un problème de recherche : état initial, actions applicables, fonction de résultat, test de but. La recherche en avant dans cet espace est complète mais fort mal informée, car l’instanciation produit quantité d’actions sans rapport avec le but visé. La recherche en arrière depuis le but ne considère que les actions pertinentes et branche donc moins, mais ses nœuds sont des ensembles d’états plutôt que des états. L’avantage décisif de la représentation est qu’une heuristique peut être extraite en modifiant les schémas eux-mêmes.

Le problème de la roue de secours part de At(Flat, Axle) ∧ At(Spare, Trunk) avec le but At(Spare, Axle). Une recherche en avant en largeur d’abord renvoie un plan en trois étapes : retirer le pneu crevé de l’essieu, sortir la roue de secours du coffre, monter la roue de secours sur l’essieu.

Le pneu crevé doit être retiré d’abord parce que PutOn porte la précondition négative ¬At(Flat, Axle). Sans elle, le raccourci en deux étapes serait légal, ce qui montre les préconditions négatives faire un travail que les listes d’ajouts et de retraits ne peuvent accomplir seules.

Le domaine du fret aérien, avec deux cargaisons, deux avions et deux aéroports, développe trois schémas en vingt actions instanciées, et son plan optimal compte six étapes : charger les deux cargaisons, faire voler chaque avion vers l’autre aéroport, décharger les deux cargaisons.