Implémentation
Choix liés à la planification
Le processus de création d’un scénario par DIRECTOR repose sur la génération d’un domaine de planification à partir des modèles de domaine et d’activité, sur la génération d’un problème de planification à partir des objectifs scénaristiques, et sur l’utilisation d’un moteur de planification afin de générer les plans qui correspondront aux étapes du scénario. Pour implémenter ce processus, nous nous sommes basés sur l’utilisation du langage PDDL et d’un moteur de planification capable d’interpréter ce langage.
Représentation en PDDL
Les connaissances utilisées pour la planification des scénarios sont représentées en PDDL. PDDL (Planning Domain Definition Language) est un langage de représentation de tâches de planification basé sur le Lisp. Ce langage a été proposé dans le cadre de la compétition de planification IPC (International Planning Competition) dans le but de permettre l’échange des domaines et la comparaison des résultats des différents moteurs. Il en existe à ce jour différentes versions : – PDDL1.2 [McDermott et al., 1998] , la première version de PDDL, permet de représenter des problèmes de planification classiques, de manière très proche du STRIPS [Fikes and Nilsson, 1971] ; – PDDL2.1 [Fox and Long, 2003] étend cette première version avec la représentation des problèmes de planification numérique et temporelle ; – PDDL2.2 [Edelkamp and Hoffmann, 2004] introduit les axiomes, ou prédicats dérivés, qui permettent d’inférer directement certains faits à partir d’autres faits ; – PDDL3.0 [Gerevini and Long, 2005] y ajoute la représentation de préférences, et de contraintes sur l’occurrence ou l’ordonnancement de certaines situations ; – PDDL3.1 [Kovacs, 2011], la dernière version en date, permet de considérer des fonctions pouvant renvoyer n’importe quel type d’objet, et non plus seulement des booléens ou des nombres. En PDDL, une tâche de planification est composée d’un domaine et d’un problème. Le domaine est constitué de : – la définition des types d’objets considérés, – l’ensemble des constantes, – la définition des prédicats, – l’ensemble des opérateurs de planification (aussi appelés actions PDDL). Dans notre cas, il s’agit des cinq types d’opérateurs : actions, comportements, commitments, happenings et contraintes d’occurrence. Le problème est constitué de : – l’ensemble des objets, – les faits constituant l’état initial, – la spécification du but. Le langage PDDL permet de représenter de nombreux types de problèmes, mais tous les types de problèmes ne peuvent pas être traités par tous les moteurs de planification. PDDL définit donc un certain nombre de prérequis, qui doivent être déclarés dans le domaine pour s’assurer que le moteur utilisé a la capacité de traiter la tâche de planification. Les tâches de planification créées par DIRECTOR possèdent les prérequis suivants : – s : les opérateurs de planification doivent pouvoir ajouter et supprimer des faits à l’état du monde ; – : les objets doivent pouvoir être typés, de manière à reproduire la hiérarchie de concepts définie dans le modèle du domaine, et de permettre ainsi d’appliquer les comportements sur les objets du type associé ; – : le moteur de planification doit pouvoir prendre en compte des buts disjonctifs pour l’algorithme de complétion des trames scénaristiques à partir des points clés ; – : le nombre d’instances d’un type d’objet donné n’est pas fixé dans le domaine, et donc n’est pas connu lors de la génération des opérateurs. Il est donc nécessaire de pouvoir exprimer à la fois la quantification universelle (∀) et la quantification existentielle (∃) pour représenter certains comportements complexes, à la fois au niveau des préconditions (par exemple, un bras de chargement ne peut être verrouillé que s’il existe une vanne à laquelle il est branché) et des effets (par exemple, l’arrêt d’un programmateur entraine l’arrêt de toutes les pompes auxquelles il est relié). Ces prérequis correspondent à des tâches de planification classiques, et se retrouvent dans les tâches de type ADL [Pednault, 1989], une extension de STRIPS incluant l’ensemble de ces prérequis, ainsi que la définition d’effets conditionnels dans les opérateurs. Les actions ADL peuvent exprimer des effets à l’aide du prédicat ♥♦t pour signaler le retrait d’un fait, plutôt que d’avoir deux listes d’ajout et de retrait séparées comme c’est le cas dans STRIPS. Le choix du moteur de planification intégré dans l’implémentation de DIRECTOR est guidé par ces prérequis. 8.1.2 Choix du moteur de planification A partir de ces prérequis, nous avons étudié un ensemble de moteurs de planification parmi les plus populaires, en les sélectionnant d’une part pour la disponibilité de leur code source, et d’autre part pour leur succès dans les différentes compétitions de planification. Le tableau 8.1 présente les différents moteurs de planification envisagés. Nous avons considéré ici uniquement des moteurs de planification classique, et nous avons notamment laissé de côté les moteurs comme TLPlan [Bacchus and Kabanza, 1998] ou SHOP [Nau et al., 1999] qui utilisent des informations dépendantes du domaine pour guider la recherche. De plus, nous n’avons pas étudié les moteurs trop anciens pour supporter le PDDL, comme Prodigy [Veloso et al., 1995] ou Graphplan [Blum and Furst, 1997]. Cependant, étant donné le grand nombre de moteurs de planification existants, cette liste est tout de même loin d’être exhaustive.
Télécharger le document complet
