Planification avec préférences basée sur la théorie
MAUT couplée à une intégrale de Choquet

Extension du pouvoir expressif du langage PDDL3

Cette section présente un formalisme original pour la planification avec préférences. Déjà mentionné dans la section 1.2.3 sous l’appellation pddl3/maut, celui-ci généralise la notion de préférence utilisée en pddl3 par l’introduction de préférences floues. L’extension proposée élargit le périmètre des problèmes de planification avec préférences qu’il est possible de modéliser et de résoudre. Pour réaliser cette généralisation, les préférences pddl sont encodées en tant que critères maut (cf. section 3.1.1) et la fonction objectif pddl est définie à l’aide d’une intégrale de Choquet (cf. section 3.1.2). Les modifications à apporter au langage pddl pour prendre en compte ces changements sont présentés dans la section 3.1.3.

Préférences PDDL3 et critères MAUT

Trois types de préférences ont été introduites dans la section 1.2.1 à savoir les préférences numériques, finales et de trajectoire. De plus, il a été expliqué dans la section 2.2 qu’un critère maut est modélisé par un attribut auquel est associée une fonction d’utilité partielle. Cette dernière représente les préférences du décideur par rapport aux valeurs de l’attribut. Cette section explique comment des critères maut peuvent être utilisés pour représenter les préférences d’un problème de planification. Le cas des préférences numériques est le plus simple puisque ces dernières définissent intrinsèquement l’attribut à considérer. Il ne reste donc qu’à définir la fonction d’utilité partielle de l’attribut. Celle-ci peut être construite manuellement ou à l’aide de la méthode présentée dans la section 2.4.2. Par exemple, dans le problème Rovers [42], le décideur peut avoir envie de raisonner sur la quantité d’énergie consommée par le robot N1 comme mentionné dans la section 1.1.2. La variable numérique e1 associée à la consommation d’énergie du robot N1 constitue naturellement l’attribut de cette préférence. Le décideur peut être complètement satisfait (respectivement totalement insatisfait) si 40 unités d’énergie (respectivement 100 unités) sont consommées lors de la mission. Par ailleurs, sa satisfaction n’évolue pas nécessairement linéairement et il peut fortement préférer une consommation de 80 unités par rapport à une de 100 unités mais ne préférer que modérément une consommation de 40 unités par rapport à une de 60 unités. Ces informations préférentielles peuvent être utilisées pour construire une fonction d’utilité partielle uEC : [0, 120] → [0, 1] représentant les choix du décideur comme illustré sur la figure 3.1. En conséquence, la préférence numérique du décideur quant à la consommation d’énergie du robot N1 peut être définie par l’attribut e1 et la fonction d’utilité partielle uEC. Ainsi, si dans un plan x, le robot N1 consomme 60 unités d’énergie au cours de sa mission alors l’utilité de la préférence dans ce plan est uEC(60) = 0.8. Ceci s’interprète comme une grande satisfaction du décideur quant à la consommation d’énergie du robot N1 dans x. 

Fonction objectif PDDL et intégrale de Choquet

Une fois que des préférences ont été spécifiées, il faut se munir d’un mécanisme permettant de calculer la qualité (appelée utilité dans la terminologie maut) des plans solutions. En pddl3, un coût de violation est associé à chaque préférence puis une fonction objectif est définie à partir de ces derniers. Dans le cas de l’extension pddl3/maut, la fonction objectif est construite à l’aide d’une fonction d’agrégation comme le suggère la définition 2.2. L’agrégation des préférences est plus simple et plus intuitive dans le formalisme pddl3/maut puisque le modèle maut impose la commensurabilité des différents critères considérés (c.-à-d. la possibilité de les comparer par le biais d’une unité adéquate). En effet, il est relativement facile de comparer plusieurs préférences entre elles puisque ces dernières sont toutes définies en utilisant une fonction d’utilité partielle à valeur sur l’échelle de satisfaction commune ξ. Les problèmes qui mettent en oeuvre beaucoup de préférences numériques peuvent donc être encodés sans difficulté avec le formalisme maut. Ce propos est illustré une fois de plus à l’aide du problème Rovers. Si les robots peuvent être endommagés lorsqu’ils prélèvent un échantillon, le décideur peut introduire un critère qui modélise le risque d’endommagement des équipements des robots. L’espace de définition associé à ce risque est l’ensemble discret ΩR = {Très faible, Faible, Modéré, Elevé, Très élevé}.Sans commensurabilité, il est impossible de déterminer si une amélioration sur le critère de consommation d’énergie (par exemple consommer 50 unités plutôt que 70) est préférée à une amélioration sur le critère de risque (par exemple passer d’un risque Elevé à un risque Modéré). En conséquence, construire une fonction objectif qui agrège les préférences du décideur relatives à la consommation d’énergie du robot N1, le risque de casse de ses équipements et la préférence de trajectoire preference (always (N1 L1)) est difficile en pddl3. Ceci explique notamment pourquoi tous les problèmes de planification avec préférences proposés lors des compétitions IPC n’utilisent au plus qu’une seule préférence numérique. En revanche, lorsque les préférences sont représentées par des critères maut, il est plus facile de les agréger puisqu’elles sont toutes commensurables entre elles. En effet, la notion d’utilité modélise la même quantité quelque soit la préférence considérée à savoir la satisfaction du décideur. Ainsi, le formalisme pddl3/maut permet de représenter des problèmes avec un grand nombre de préférences numériques. Bien que la fonction objectif pddl puisse être quelconque, les problèmes de référence utilisent généralement une somme pondérée. L’opérateur d’agrégation retenu dans le cadre de cette étude est l’intégrale de Choquet 2-additive. Celle-ci généralise la somme pondérée en permettant au décideur de représenter des interactions entre paires de critères. A titre d’illustration, un décideur peut être prêt à accepter une grande consommation d’énergie pour un robot si le risque d’endommagement de ses équipements est faible. Dans ce cas, les deux critères sont substituables et leur indice d’interaction est négatif (cf. section 2.3.3). Le langage pddl3/maut permet donc de représenter plus finement la complexité intrinsèque des préférences du décideur. L’extension pddl3/maut améliore le pouvoir expressif du modèle de préférences considéré mais complexifie également la réalisation de ce dernier. Ceci est notamment dû au fait que les décideurs doivent définir une fonction de capacité. Toutefois, la construction de la capacité peut être automatisée et outillée comme expliqué dans la section 2.4.2. Ainsi, la réalisation d’un modèle de préférences pddl3/mcda peut être considérée plus simple que celle d’un modèle de préférences pddl3. En effet, il est plus intuitif pour les décideurs de comparer des alternatives de solutions entre elles (pddl3/maut) que de définir les paramètres mathématiques d’une somme pondérée (pddl3).

Langage formel pour l’extension PDDL3/MAUT 

Cette section présente les éléments syntaxiques et sémantiques à considérer pour étendre le langage pddl3 à l’aide du formalisme maut. Syntaxe de l’extension PDDL3/MAUT Le pouvoir expressif du pddl étant très vaste, peu de planificateurs implémentent l’ensemble des fonctionnalités supportées par ce dernier. Les exigences (nommées requirement) sont des sous-ensembles cohérents du langage pddl qui ont été introduits afin de préciser les fonctionnalités qu’un planificateur peut mettre en œuvre. Par exemple, pour raisonner sur les expressions numériques et les préférences présentées respectivement dans les sections 1.1.3 et 1.2.3, il faut être capable de prendre en charge les éléments des exigences numeric-fluents et preferences. Les modifications liées à l’extension pddl3/maut sont accessibles par l’intermédiaire de l’exigence maut-preferences qui elle-même s’appuie sur les exigences numeric-fluents et preferences. La description bnf [4] qui spécifie l’exigence maut-preferences est présentée sur la figure 3.2. Cette dernière s’appuie sur la description bnf du pddl qui est proposée dans [63]. Sans surprise, les deux éléments principaux de l’exigence maut-preferences sont les concepts de critères maut () et d’intégrale de Choquet (). Les critères maut peuvent décrire des préférences finales ou des préférences de trajectoires (), des préférences numériques () ou encore des préférences non élémentaires (). Il convient de remarquer que d’un point de vue sémantique, les préférences finales s’interprètent sur une trajectoire (cf. définitions 1.23 et 1.24) ce qui justifie qu’elles soient représentées par un critère de type . L’intégrale de Choquet est quant à elle spécifiée à l’aide d’une capacité représentée par sa transformation de Möbius (). La description proposée permet d’utiliser une intégrale de Choquet quelconque mais cette étude se limite au cas des intégrales de Choquet 2-additives.