Brevet FR3051943A1 — publié le 20171201

Procédé d'aide à la détermination d'un plan respectant des préférences La présente invention concerne un procédé d'aide à la détermination du plan respectant le mieux des préférences. L'invention se rapporte également à un système d'aide à la détermination du plan respectant le mieux des préférences. L'invention concerne aussi un produit programme d'ordinateur associé et un support d'information sur lequel est encodé un tel produit programme d'ordinateur. Dans de nombreux domaines, il est souhaitable de disposer d'outils d'aide à la décision parce que la prise de décision en temps réel avec souvent la prise en compte d'une pluralité de critères est difficile, voire impossible pour un être humain. Par exemple, il est connu du document US 2006/0224426 Al un procédé mis en oeuvre par ordinateur pour manipuler des plans de transport, le procédé comprenant une étape d'accès à une série d'ordres de transport et une étape d'accès à des actions de plan de charge qui peuvent être mis en oeuvre. Le procédé comporte aussi une étape d'identification d'exception de plan relative au plan de transport et une étape d'identification automatique d'une action de plan candidate pour résoudre l'exception de plan. Le procédé met alors à jour de manière sélective les actions de plan de charge en fonction de données issues de l'action de plan candidate identifiée. Toutefois, un tel procédé permet uniquement de gérer une exception et n'est pas adapté pour gérer une pluralité d'exceptions et encore moins des exceptions provenant de décideurs différents pouvant s'interpréter comme des préférences. Il existe donc un besoin pour un procédé d'aide à la détermination de plans, permettant la prise en compte à la fois de contraintes mais également de préférences, notamment en présence d'au moins deux décideurs différents. A cet effet, il est proposé un procédé d'aide à la détermination du plan respectant le mieux des préférences, un plan étant une suite d'actions menant un système d'un état initial à un état final recherché en respectant des contraintes prédéfinies, le procédé étant mis en oeuvre par un ordinateur et comprenant les étapes suivantes : la fourniture de données d'entrées, les données d'entrées comprenant : l'état initial du système, l'état final recherché du système, l'ensemble des actions possibles, et les contraintes, la conversion des données d'entrées en un langage de planification automatique pour obtenir des données converties, la fourniture d'un ensemble de préférences, pour chaque préférence, détermination d'une fonction de score de préférence par analyse de l'évolution de la satisfaction en fonction de la valeur de la préférence correspondante, la détermination d'une fonction de score global à partir des fonctions de score de préférence, la conversion de la fonction de score global en le même langage de planification automatique pour 3051943 2 obtenir une fonction convertie, et la génération d'au moins un plan à partir des données converties et de la fonction convertie.. Suivant un mode de réalisation particulier, le procédé comprend une ou plusieurs des caractéristiques suivantes, prise(s) isolément ou suivant toutes les combinaisons 5 techniquement possibles : - l'ensemble des actions possibles sont menées par plusieurs entités distinctes, l'étape de fourniture des préférences étant menée par au moins deux entités distinctes. - l'ensemble des actions possibles sont menées par plusieurs entités distinctes, au 10 moins une entité fournissant une pluralité de jeux distincts de préférences à l'étape de fourniture, un jeu étant un sous-ensemble de l'ensemble de préférences. - la fonction de score global est obtenue par mise en oeuvre d'un modèle d'utilité multi-attribut utilisant une fonction d'agrégation, la fonction d'agrégation étant une intégrale de Choquet ou une intégrale de Choquet dont la capacité est 2-additive. 15 - le langage de planification automatique comprend des fonctions de gestion de préférences. - une pluralité de plans est générée à l'étape de génération, le procédé comprenant une étape d'affichage de la pluralité de plans et de la valeur de chaque fonction de score de préférence pour chacun des plans de la pluralité de 20 plans. - le procédé étant réitéré au moins une fois, au moins l'un des éléments du groupe constitué des préférences fournies et de la détermination des fonctions de score de préférence étant distincts d'une itération à une autre. Il est également proposé un système d'aide à la détermination du plan respectant 25 le mieux des préférences, un plan étant une suite d'actions menant un système d'un état initial à un état final recherché en respectant des contraintes prédéfinies, le système comprenant au moins un ordinateur et étant propre à recevoir des données d'entrées, les données d'entrées comprenant : l'état initial du système, l'état final recherché du système, l'ensemble des actions possibles, et les contraintes, convertir des données d'entrées en 30 un langage de planification automatique pour obtenir des données converties, recevoir ensemble de préférences, pour chaque préférence, détermination d'une fonction de score de préférence par analyse de l'évolution de la satisfaction en fonction de la valeur de la préférence correspondante, déterminer une fonction de score global à partir des fonctions de score de préférence, convertir la fonction de score global en le même langage de 35 planification automatique pour obtenir une fonction convertie, et générer au moins un plan à partir des données converties et de la fonction convertie. 3051943 3 Il est également proposé un produit programme d'ordinateur comprenant des instructions logicielles qui, lorsqu'elles sont exécutées par un ordinateur, mettent en oeuvre un procédé tel que précédemment décrit. Il est également proposé un support d'information sur lequel est mémorisé un 5 produit programme d'ordinateur tel que précédemment décrit. Les caractéristiques et avantages de l'invention apparaîtront à la lecture de la description qui va suivre, donnée uniquement à titre d'exemple non limitatif, et faite en référence aux dessins annexés, sur lesquels : - la figure 1 est une vue schématique d'un exemple de système permettant la mise 10 en oeuvre d'un procédé d'aide à la détermination du plan respectant le mieux des préférences, et - la figure 2 est un organigramme d'un exemple de mise en oeuvre d'un procédé d'aide à la détermination du plan respectant le mieux des préférences. Un système 10 et un produit programme d'ordinateur 12 sont représentés sur la 15 figure 1. L'interaction du produit programme d'ordinateur 12 avec le système 10 permet de mettre en oeuvre un procédé d'aide à la détermination du plan respectant le mieux des préférences. Le système 10 est un ordinateur. 20 Plus généralement, le système 10 est un calculateur électronique propre à manipuler et/ou transformer des données représentées comme des quantités électroniques ou physiques dans des registres du système 10 et/ou des mémoires en d'autres données similaires correspondant à des données physiques dans des mémoires, des registres ou d'autres types de dispositifs d'affichage, de transmission ou de 25 mémorisation. Le système 10 comporte une unité de traitement de données 14 comprenant un processeur 16, des mémoires 18 et un lecteur 20 de support d'informations. Le système 10 comprend également un clavier 22 et une unité d'affichage 24. Le produit programme d'ordinateur 12 comprend un support lisible 30 d'informations 20. Un support lisible d'informations 20 est un support lisible par le système 10, usuellement par l'unité de traitement d'informations 14. Le support lisible d'informations 20 est un médium adapté à mémoriser des instructions électroniques et capables d'être couplé à un bus d'un système informatique. 3051943 4 A titre d'exemple, le support lisible d'informations 20 est un disque optique, un CD-ROM, un disque magnéto-optique, une mémoire ROM, une mémoire RAM, une mémoire EPROM, une mémoire EEPROM, une carte magnétique ou une carte optique. En variante, le support lisible d'informations 20 fait partie d'un nuage (aussi 5 désigné par le terme anglais « cloud »). Sur le support lisible d'informations 20 est mémorisé le programme comprenant des instructions de programme. Le programme d'ordinateur est chargeable sur l'unité de traitement de données 14 et est adapté pour entraîner la mise en oeuvre d'un procédé d'aide à la détermination du 10 plan respectant le mieux des préférences lorsque le programme d'ordinateur est mis en oeuvre sur le processeur 16. Par l'expression « respectant le mieux », il est entendu « optimisant ». Le fonctionnement du système 10 en interaction avec le produit programme d'ordinateur 12 est maintenant décrit en référence à la figure 2 qui illustre un exemple de 15 mise en oeuvre d'un procédé d'aide à la détermination du plan respectant le mieux des préférences. Le procédé illustré est un procédé d'aide à la détermination du plan respectant le mieux des préférences. Un plan est une suite d'actions menant un système d'un état initial à un état final 20 recherché en respectant des contraintes prédéfinies. Dans le contexte illustré, le plan fait intervenir une pluralité d'entités ou de parties prenantes. Chaque entité ayant le pouvoir d'influer sur le plan adapté (voire de le déterminer) est appelée un décideur. Pour bien montrer l'intérêt du procédé, il est supposé qu'il y a deux décideurs. 25 Les notions de 'plan' et de 'préférence' seront précisées dans la suite de la description. Le procédé comprend une première étape de fourniture 100, une première étape de conversion 102, une deuxième étape de fourniture 104, une première étape de détermination 106, une deuxième étape de détermination 108, une deuxième étape de 30 conversion 110, une étape de génération 112 et une étape d'affichage 114. A la première étape de fourniture 100, il est fourni des données d'entrées. Les données d'entrées comprennent l'état initial So du système, l'état final recherché Sf du système, l'ensemble des actions possibles A et les contraintes C. L'état initial So représente la situation du système avant la mise en oeuvre du plan. 35 Dans l'exemple illustré, au départ, il n'y a pas de navire fabriqué. 3051943 5 Par contre, certaines des parties prenantes disposent déjà d'une partie du matériel permettant de fabriquer le navire. L'état final recherché Sf représente la situation du système à l'issue de la mise en oeuvre du plan. 5 Dans l'exemple, dans l'état final recherché Sf, le navire est fabriqué. L'ensemble des actions possibles A rassemble les actions permettant de passer d'un état du système à un autre état du système. Par exemple, une partie prenante fabrique le gouvernail à partir de matériaux donnés. Par mise en oeuvre de cette action, le système passe ainsi d'un état où le 10 matériau pour fabriquer le gouvernail est disponible à un état dans lequel le gouvernail est fabriqué. Les contraintes C sont des buts à atteindre absolument. Par exemple, il faut que le navire soit livré à une date prédéfinie. Selon un autre exemple, son tonnage ne peut pas dépasser une valeur prédéfinie. 15 Les contraintes C se distinguent des préférences P par leur caractère absolu. La première étape de fourniture 100 est, par exemple, mise en oeuvre au moyen d'un clavier et d'une souris. A titre d'illustration, la première étape de fourniture 100 est mise en oeuvre par les décideurs. 20 Selon un mode de réalisation alternatif, l'ensemble des actions possibles A est établi sur la base d'une description des capacités (opérationnelles) des différentes parties prenantes, dont la mise en oeuvre permet de faire passer le système d'un état à un autre état. Lors de la première étape de conversion 102, les données d'entrée sont 25 converties en un langage de planification automatique. Un langage de planification est un langage formel dédié au domaine de la planification. Plus précisément, un langage de planification est un ensemble formé d'un vocabulaire et d'une grammaire. Le vocabulaire est un ensemble de mots et symboles 30 alors que la grammaire est un ensemble de règles précisant comment construire des formules valides à partir des éléments de base de ce vocabulaire. A titre d'exemple, le langage de planification automatique est un langage PPDL, acronyme de l'anglais « Planning Domain Definition Language » signifiant littéralement « langage de définition de domaine de la planification ». 35 Le langage PDDL propose de représenter un problème de planification à l'aide de deux ensembles de données. Le premier ensemble de données est relatif à la description 3051943 6 du domaine d'étude, soit une description du système et des actions possibles. Le deuxième ensemble de données est relatif à la description du problème à résoudre, soit une description de l'état initial du système et de l'état final recherché du système. Les deux ensembles de données sont, par exemple, des fichiers. 5 Selon un exemple, le langage de planification automatique comprend des fonctions de gestion de préférences. Ces fonctions de gestion de préférences prennent en compte la nature des préférences (binaires ou floues), ce que représentent la sémantique des préférences et leur agrégation. 10 Un exemple de fonction de gestion de préférence est une fonction associant à la préférence un entier de l'ensemble {0 ;1} si la préférence correspond à une satisfaction binaire ou un entier de l'intervalle [0 ;1] si la préférence correspond à une satisfaction représentable par exemple avec le formalisme de la logique floue. A titre d'illustration, le langage PPDL dans sa version 3.0 est un langage de 15 planification automatique comprenant certaines de ces fonctions de gestion de préférences. L'étape de conversion est mise en oeuvre par l'unité de traitement de données 14. A la fin de la première étape de conversion 102, des données converties sont obtenues. 20 Lors de la deuxième étape de fourniture 104, il est fourni un ensemble de préférences. Par exemple, les décideurs entrent via un clavier ou une souris des préférences. Une préférence est un souhait, que l'on peut voir comme une « pseudocontrainte » à caractère facultatif (à la différence des véritables contraintes). Ce peut être 25 un but qu'il est souhaité d'atteindre sans obligation. Le nombre de préférences est supérieur à deux, avantageusement supérieur à cinq, avantageusement supérieur à dix. Pour les besoins de l'exemple, il est supposé que les préférences sont au nombre de trois et portent sur le coût de construction, la quantité d'énergie consommée et le délai 30 d'occupation de la cale de radoub. Selon un autre exemple, un décideur fournit une pluralité de jeux distincts de préférences à l'étape de fourniture, un jeu étant un sous-ensemble de l'ensemble de préférences. Il est possible de considérer, au moins formellement, que ce cas se ramène au cas 35 illustré, à savoir une pluralité de décideurs ayant chacun des préférences pouvant éventuellement se recouper. 3051943 7 Lors de la première étape de détermination 106, il est déterminé une fonction de score de préférence par analyse de l'évolution de la satisfaction en fonction de la valeur de la préférence correspondante, et ce pour chaque préférence fournie à la deuxième étape de fourniture 104. 5 Par exemple, une satisfaction valant 0 correspond à un état d'insatisfaction totale tandis qu'une satisfaction valant 1 correspond à un état de satisfaction totale. Selon l'exemple proposé, il est déterminé pour chacune des trois préférences une fonction de score de préférence. Dans la suite, les fonctions score de préférence sont notées u,, i étant un entier 10 variant de 1 à 3. Il est ainsi déterminé une première fonction score de préférence u1 associée au coût de construction, la deuxième fonction score de préférence u2 associée à la quantité d'énergie consommée et une troisième fonction score de préférence u3 associée au délai d'occupation de la cale. 15 Chaque fonction u, est une fonction dont l'ensemble d'arrivée est un intervalle de IR. Par exemple, l'ensemble d'arrivée est l'intervalle [0, 1]. Selon l'exemple décrit, pour la détermination des différentes fonctions de score u1, l'analyse est mise en oeuvre par interaction avec au moins un décideur, à l'issue de 20 laquelle il est obtenu une fonction de score de préférence pour chaque préférence. L'interaction comprend l'obtention de réponses sur l'appréciation graduée de la satisfaction du décideur pour une pluralité finie de valeurs de la préférence. Dans l'exemple proposé, cela signifie qu'à l'issue de la première étape de détermination 106, les trois fonctions de score de préférence ul, u2 et u3 sont connues. 25 Lors de la deuxième étape de détermination 108, il est déterminé une fonction de score global à partir des fonctions de score de préférence. La fonction de score global permet d'obtenir pour un plan donné une valeur de score unique. La fonction de score global est obtenue par mise en oeuvre d'une technique 30 mathématique. Par exemple, il est utilisé un modèle d'utilité multi-attribut aussi désigné par l'acronyme MAUT (pour « Multi-attribute utility theory » en langue anglaise). Un tel modèle utilise une fonction d'agrégation. Selon un exemple, la fonction d'agrégation est une intégrale de Choquet. 35 En variante, la fonction d'agrégation est une intégrale de Choquet dont la capacité est 2-additive. 3051943 8 Selon un autre exemple, il est utilisé un modèle d'indépendance additive généralisée pour obtenir la fonction de score global. A l'issue de la deuxième étape de détermination 108, il est obtenu une fonction de score global. 5 Lors de la deuxième étape de conversion 110, la fonction de score global est convertie dans le même langage de planification automatique. A l'issue de la deuxième étape de conversion 110, il est obtenu une fonction convertie. Lors de l'étape de génération 112, il est généré une pluralité de plans à partir des 10 données converties et de la fonction convertie. Selon un exemple particulier, à l'étape de génération 112, il est généré un seul plan. L'étape de génération de plans s'appuie sur trois modules - dénommés ici lexeur, parseur et solveur - qui sont invoqués les uns à la suite des autres. 15 Le premier (le lexeur) traite les fichiers textes obtenus à l'issu des étapes de conversion (et donc exprimés selon le langage de la planification automatique PDDL) afin de les convertir en séquences d'entités lexicales. Ces éléments syntaxiques sont alors analysés par le second module (le parseur) qui leur associe une sémantique. Celle-ci est déterminée par la méthode de résolution 20 employée ; dans notre cas, il s'agit d'un graphe dont les noeuds sont caractérisés par des formules logiques. Le dernier module mis en oeuvre (le solveur) s'appuie sur les objets informatiques préalablement construits pour implémenter l'algorithme de résolution du problème. La solution retournée par l'algorithme correspond au plan obtenu à la fin de l'étape 25 de génération 112. Dans notre cas, il s'agit d'un algorithme de recherche dite « en avant » guidée par une heuristique. Les heuristiques que nous proposons s'appuient sur plusieurs estimations du potentiel d'un noeud (par rapport aux objectifs à respecter et par rapport aux préférences à optimiser) qui sont agrégées les unes aux autres à l'aide d'une intégrale de Choquet 30 (qui est aucun sans lien avec l'intégrale de Choquet utilisée pour agréger les préférences lors de l'étape de détermination 108). A l'étape d'affichage 114, il est affiché la pluralité de plans générés. Par ailleurs, il est aussi affiché des scores pour chacun des plans. Selon un exemple particulier, il est affiché la valeur de la fonction de score global 35 et la valeur de chacune des fonctions de score de préférence. 3051943 9 Selon un autre exemple particulier, dans le cas où un décideur a plusieurs jeux de préférences distincts, il est affiché la valeur de la fonction de score global ainsi que la valeur de chacune des fonctions de score de préférence pour l'ensemble des jeux de préférence considérés. 5 L'étape d'affichage 114 est mise en oeuvre pour chaque décideur qui peut ainsi participer à la prise de décision. Le procédé permet donc de déterminer des plans répondant mieux aux préférences des décideurs. Cela permet de faciliter le travail des décideurs. Notamment, le procédé permet de fournir aux décideurs toutes les informations 10 permettant de choisir avec justesse, pertinence et en connaissance de cause, la solution qui leur paraît la plus adaptée au cas d'espèce. De plus, le procédé d'aide à la détermination de plans permet la prise en compte d'une multitude de préférences, soit de manière globale (la recherche de plan prend en compte simultanément toutes les préférences), soit de manière alternative (les 15 préférences sont regroupées en différents modèles et la recherche détermine autant de plans que de modèles), notamment en présence d'au moins deux décideurs différents. La généralisation à un nombre quelconque de préférences est, en effet, immédiate, les techniques mathématiques proposées pour l'étape de deuxième détermination 108 étant aptes à fonctionner pour un grand nombre de préférences. 20 Selon une version plus élaborée, le procédé est réitéré au moins une fois, les préférences fournies et/ou la détermination des fonctions de score de préférence étant distinctes d'une itération à une autre. Selon une variante, le système 10 est un système d'aide à la détermination du plan respectant le mieux des préférences pouvant être utilisé sur plusieurs sites. 25 Par exemple, le système 10 comporte une pluralité de terminaux, chaque terminal étant accessible pour les entités. Cela permet de faciliter les échanges et d'augmenter la rapidité de détermination du meilleur plan. Selon un exemple, le procédé est mis en oeuvre successivement autant de fois 30 que désiré, et ce de manière dynamique en changeant les données d'entrée. Selon un autre exemple, le procédé est mis en oeuvre « à froid » (c'est-à-dire hors contexte dynamique - sur des cas d'étude par exemple) lors de la préparation de mission ou d'exercice, ou à fins d'entraînement pour produire des plans en conformité avec une doctrine par exemple ou en prévision de situations possiblement à venir. 35 Selon un exemple d'utilisation, le procédé est appliqué sur des données d'entrées hypothétiques, de manière à pouvoir anticiper des choix dans le cadre d'avenirs possibles 3051943 10 par exemple ou bien pour « jouer » d'autres rôles que son rôle propre (dans le cas de situations à plusieurs entités). REVENDICATIONS1.- Procédé d'aide à la détermination du plan respectant le mieux des préférences, un plan étant une suite d'actions menant un système d'un état initial à un état final recherché en respectant des contraintes prédéfinies, le procédé étant mis en oeuvre par un ordinateur et comprenant les étapes suivantes : - fourniture de données d'entrées, les données d'entrées comprenant : - l'état initial du système, - l'état final recherché du système, - l'ensemble des actions possibles, et - les contraintes, - conversion des données d'entrées en un langage de planification automatique pour obtenir des données converties, - fourniture d'un ensemble de préférences, - pour chaque préférence, détermination d'une fonction de score de préférence par analyse de l'évolution de la satisfaction en fonction de la valeur de la préférence correspondante, - détermination d'une fonction de score global à partir des fonctions de score de préférence, - conversion de la fonction de score global en le même langage de planification automatique pour obtenir une fonction convertie, et - génération d'au moins un plan à partir des données converties et de la fonction convertie. 2.- Procédé selon la revendication 1, dans lequel l'ensemble des actions possibles sont menées par plusieurs entités distinctes, l'étape de fourniture des préférences étant menée par au moins deux entités distinctes. 3.- Procédé selon la revendication 1 ou 2, dans lequel l'ensemble des actions possibles sont menées par plusieurs entités distinctes, au moins une entité fournissant une pluralité de jeux distincts de préférences à l'étape de fourniture, un jeu étant un sous-ensemble de l'ensemble de préférences. 4.- Procédé selon l'une quelconque des revendications 1 à 3, dans lequel la fonction de score global est obtenue par mise en oeuvre d'un modèle d'utilité multi-attribut 3051943 12 utilisant une fonction d'agrégation, la fonction d'agrégation étant une intégrale de Choquet ou une intégrale de Choquet dont la capacité est 2-additive. 5.- Procédé selon l'une quelconque des revendications 1 à 4, dans lequel le 5 langage de planification automatique comprend des fonctions de gestion de préférences. 6.- Procédé selon l'une quelconque des revendications 1 à 5, une pluralité de plans est générée à l'étape de génération, le procédé comprenant une étape d'affichage de la pluralité de plans et de la valeur de chaque fonction de score de préférence pour 10 chacun des plans de la pluralité de plans. 7.- Procédé selon l'une quelconque des revendications 1 à 6, le procédé étant réitéré au moins une fois, au moins l'un des éléments du groupe constitué des préférences fournies et de la détermination des fonctions de score de préférence étant 15 distincts d'une itération à une autre. 8.- Système d'aide à la détermination du plan respectant le mieux des préférences, un plan étant une suite d'actions menant un système d'un état initial à un état final recherché en respectant des contraintes prédéfinies, le système comprenant au 20 moins un ordinateur et étant propre à : - recevoir des données d'entrées, les données d'entrées comprenant : - l'état initial du système, - l'état final recherché du système, - l'ensemble des actions possibles, et 25 - les contraintes, - convertir des données d'entrées en un langage de planification automatique pour obtenir des données converties, - recevoir ensemble de préférences, - pour chaque préférence, détermination d'une fonction de score de préférence par 30 analyse de l'évolution de la satisfaction en fonction de la valeur de la préférence correspondante, - déterminer une fonction de score global à partir des fonctions de score de préférence, - convertir la fonction de score global en le même langage de planification 35 automatique pour obtenir une fonction convertie, et 3051943 13 - générer au moins un plan à partir des données converties et de la fonction convertie. 9.- Produit programme d'ordinateur comprenant des instructions logicielles qui, 5 lorsqu'elles sont exécutées par un ordinateur, mettent en oeuvre un procédé selon l'une quelconque des revendications 1 à 7. 10.- Support d'enregistrement lisible par un ordinateur sur lequel est enregistré un programme d'ordinateur pour l'exécution des étapes du procédé selon l'une quelconque 10 des revendications 1 à 7.