La présente invention se rapporte à un procédé d'aide à la décision prenant en compte une évolution incertaine et/ou dans le risque.

Pour pouvoir prendre une décision dans un contexte évolutif, tout en gérant globalement leurs ressources propres, les systèmes d'information doivent disposer d'une représentation synthétique mais précise de la réalité.

Ils ont à représenter et à raisonner sur des connaissances de plus en plus hétérogènes (propriétés géométriques, phénomènes dynamiques, gestion des ressources,...). Pour ces raisons, un problème dynamique de décision dans une situation à évolution incertaine intègre plusieurs aspects : - La description précise du contexte initial et des contraintes du problème. Ces contraintes peuvent, par exemple, tre liées à la gestion et à la disponibilité des ressources. Ces ressources peuvent tre disponibles à certaines périodes et indisponibles à d'autres.

- La description de la dynamique et de l'évolution future dans le risque ou l'incertain du contexte.

-L'objectif final de la décision, et éventuellement les différents guides de choix élaborés par des experts du métier concerné (guides également appelés « heuristiques métier ») et permettant d'orienter les décisions.

Ces problèmes de prise de décision dans un contexte évolutif sont souvent de nature hybride, c'est-à-dire qu'ils dépendent de paramètres discrets (tels que des ressources en nombre fini) et de paramètres non discrets (par exemple loi cinématique d'évolution d'un véhicule), c'est-à-dire décrits par une évolution dynamique de différents états. Il s'agit donc de problèmes dynamiques décrivant l'évolution contrôlée par un jeu de paramètres discrets ou soumise à des contraintes discrètes. On peut citer ici en exemple la planification d'un système d'armes, pour lequel la fonction d'assignation des pistes et des missiles dépend fortement de l'évolution de l'encombrement et de la qualité des pistes, des modèles de leurres (aspect non discret), mais aussi du stock de munitions disponibles (aspect discret).

Cet exemple est non seulement un problème combinatoire (de type allocation de ressources), mais est régi par un système dynamique défini soit

par des équations différentielles, soit par des inclusions différentielles (prise en compte d'un degré d'incertitude) suivant le degré de précision du modèle dont on dispose.

La résolution des systèmes hybrides ne se cantonne pas à des problèmes bien définis, mais doit intégrer la combinaison de plusieurs sous- problèmes mlant la complexité liée à la nature combinatoire des contraintes à celle de la nature dynamique du système.

Pour résoudre la partie combinatoire et discrète de ces problèmes hybrides, on connaît la Programmation Par Contraintes (PPC) qui a été utilisée avec succès dans des domaines tels que les problèmes combinatoires, l'ordonnancement, la planification,... Ce procédé peut tre avantageusement mis en oeuvre dans des systèmes d'aide à la décision, en particulier pour l'optimisation de ressources. La PPC est fondée sur un langage de description de modèles relationnels. La relation, qui est l'élément de base de ce procédé, permet la spécification de modèles qui se combinent ensuite lors de la résolution d'un but. C'est donc une bonne alternative à la résolution de problèmes que posent les systèmes combinatoires et qui peuvent tre exprimés à l'aide de contraintes linéaires, symboliques ou boléennes.

Un programme de PPC est alors vu comme un ensemble de modèles, un pour chaque constituant, qu'il soit fonctionnel ou physique. Du point de vue sémantique, un modèle est l'ensemble des spécifications du comportement du composant ou de la fonction qu'il modélise. Les spécifications étant exprimées à partir de relations, un modèle est donc identifié à l'ensemble des relations définies sur ses variables. Ces contraintes sont soit des briques de base du langage (dites « primitives »), c'est-à-dire des contraintes génériques du solveur, soit définies par l'utilisateur. II existe des solutions logicielles permettant la mise en oeuvre de ce procédé, comme par exemple « Chip » de la Société Cosytec, « ILOG Solver » de la Société ILOG, ou « Eclair » de la Société THALES. Toutes ces solutions ne se servent que de variables et de contraintes dans des domaines finis, c'est-à-dire dans un espace discret, et ne permettent donc pas de prendre en compte des systèmes dynamiques hybrides.

La présente invention a pour objet un procédé permettant d'apporter une aide à la décision lorsque se posent des problèmes hybrides,

c'est-à-dire des problèmes faisant intervenir des variables continues et des variables discrètes, et en particulier dans lesquels l'évolution de la situation est de nature incertaine et/ou peut se produire dans le risque.

Le procédé d'aide à la décision conforme à l'invention, du type prenant en compte une évolution incertaine et/ou dans le risque de la situation est caractérisé par le fait qu'il consiste, dans un système, à : - modéliser mathématiquement les contraintes et les relations entre ces contraintes ; - modéliser tout ce qui est dynamique ; - à modéliser le risque ; - à transformer le problème hybride en un problème de recherche de noyau de viabilité ; - à transformer le noyau de viabilité en une contrainte - à résoudre le problème par la PPC.

Par définition, la recherche du noyau de viabilité inclut la recherche des conditions initiales de la dynamique décrites par les équations différentielles du système.

Selon un autre aspect du procédé de l'invention, la résolution prend en compte l'incertain en utilisant les inclusions différentielles.

La présente invention sera mieux comprise à la lecture de la description détaillée d'un mode de mise en oeuvre.

Le procédé de l'invention combine la PPC avec la théorie de la viabilité. Cette théorie a jusqu'à présent été mise en oeuvre pour résoudre des problèmes dans le domaine de l'économie et de la finance, pour prendre en compte l'incertain. Cette théorie a été exposée par exemple dans les documents suivants : [1] AUBIN J. P. (1991) Viability theory, Birkhauser [2] AUBIN J. P. (1997) Dynamique Economic Theory : a viability approach, Springer-Verlag.

[3] SAINT PIERRE P. (1994) Approximation of the viability kemel, Applied Mathematics & Optimisation, 29,187-209.

Cette mise en oeuvre connue n'a jamais abordé la résolution de problèmes de décision sous contraintes discrètes du fait mme qu'elle ne pouvait pas les résoudre.

La théorie de la viabilité a été élaborée au début des années 80 pour étudier les évolutions des systèmes complexes en avenir incertain, soumis à des contraintes de viabilité, d'où le nom de cette théorie. Elle s'avère un outil mathématique efficace pour adapter la programmation dynamique non seulement à des problèmes de contrôle optimal en horizon fini ou infini, mais aussi à des problèmes de temps d'arrt, de temps de crise, de finances,... Elle offre un cadre mathématique bien adapté à l'étude des problèmes de contrôle dynamique. L'invention prévoit de combiner ce cadre mathématique avec la PPC pour résoudre le problème de l'évolution des systèmes hybrides, c'est-à-dire en particulier, des systèmes présentant une alternance d'évolutions en temps continu et de remises à niveau en temps discret. De tels systèmes commencent à tre étudiés tant en économie qu'en automatique. A cet effet, l'invention adapte toute la théorie de la viabilité développée dans le cadre des inclusions différentielles au cas des systèmes dynamiques discrets sous contraintes.

Cette adaptation de la théorie de la viabilité consiste en un enrichissement de la PPC qui, seule, ne peut résoudre des problèmes évolutifs. L'invention tire parti de caractéristiques intéressantes de la PPC.

Parmi ces caractéristiques, l'invention retient le fait que lors du développement d'une application, il n'y a pas lieu de se soucier de l'ordre dans lequel les contraintes sont introduites dans le système à résoudre. La conséquence principale est que la PPC rend possible une programmation incrémentale. Cela signifie que si l'on désire modifier la modélisation ou lui ajouter un nouveau modèle, on peut le faire sans avoir à se soucier des interactions avec les modèles déjà existants. Cependant, la conception d'un système dynamique d'aide à la décision, c'est-à-dire dans lequel on peut remettre en cause certaines hypothèses, par une seule de ses composantes (discrète ou continue), n'est pas possible si l'on veut que cette aide soit la plus proche possible de la réalité.

De façon générale, un tel système d'aide à la décision peut comporter des définitions de variables réelles ou discrètes sur lesquelles reposent les contraintes du système (ressources, limites d'utilisation,...), mais ce système doit aussi présenter un aspect dynamique caractérisant l'évolution de ses états.

De façon détaillée, le procédé de l'invention comprend les étapes suivantes : 1. Modélisation des contraintes du problème. La première partie de cette étape utilise la formalisation mathématique du problème pour en déduire, de façon classique, une modélisation mathématique des contraintes et des relations entre ces contraintes. La modélisation du problème est faite de la mme façon que pour la programmation par contraintes dans les domaines finis, l'arithmétique linéaire entière et le calcul propositionnel. Pour mener à bien cette étape, il faut modéliser le problème soit par le biais de conditions équivalentes soit par le biais de « dégradation » des relations du problème. Ces relations sont soit des conditions suffisantes, ce qui permet de garantir formellement que toute solution trouvée est valide (mais il se peut que l'on perde alors des solutions), soit elles sont trouvées par des approximations qui rendent moins fine la modélisation.

La seconde partie de cette première étape traduit la formalisation en modèles de type « contraintes ». En effet, les problèmes combinatoires traités par la PPC, qu'il s'agisse de problèmes de « satisfiabilité » (consistant à trouver une solution) ou de problèmes d'optimisation (consistant à trouver la meilleure solution) sont définis par un ensemble de variables et de leurs domaines de valeurs potentielles et un ensemble de relations caractérisant les propriétés de la solution, à savoir les contraintes. Formellement, à tout problème P on fait correspondre un triplet : ( (v1..., vn) ; (dom (vu.., dom (vn)) ; ((P1 (Pn)) où les vi sont les variables à exemplifier par une valeur du domaine dom (v*) de telle sorte que les formules algébriques yi (les contraintes) soient satisfaites.

2. Modélisation de la loi d'évolution du système. Une fois déterminées, les contraintes définissent le sous-ensemble potentiel des valeurs des variables qui les satisfait à chaque instant de l'évolution du système. Cette deuxième étape consiste à discrétiser en fonction du temps les dynamiques d'évolution si elles sont définies de manière continue.

Plusieurs types d'évolutions peuvent tre pris en compte : - une évolution déterministe, modélisée par une équation différentielle discrète ; - une évolution dans le risque : l'équation dépend d'un ou de plusieurs paramètres qualifiant la « probabilité » ou la « possibilité » de réalisation d'un événement ; - une évolution dans l'incertain : l'équation différentielle régissant l'évolution de la situation dépend d'un ou de plusieurs paramètres de perturbations inconnus. On se trouve alors dans le contexte des « jeux dynamiques contre toute la nature » dans lesquels le premier joueur est le décideur et le second joueur est la nature. La théorie des jeux dynamiques est alors appliquée pour modéliser la loi d'évolution.

Ces lois d'évolution discrète sont ensuite transformées en contraintes. Ceci revient à transformer le problème initial en un problème dynamique de recherche de « noyau de viabilité » d'un ensemble K, noté Viab (K), qui est défini comme le plus grand sous-ensemble inclus dans K, avec des conditions initiales telles qu'il existe au moins une trajectoire associée à cette nouvelle dynamique qui ne sorte pas de K.

Ceci revient à dire que l'ensemble des valeurs initiales de K à partir desquelles est définie cette trajectoire permet de trouver une solution qui ne sorte jamais de K. On peut montrer (voir les deux livres de J. P. AUBIN cités ci-dessus) que les problèmes de calcul des points d'équilibre d'un système dynamique, de temps minimal d'atteinte d'une cible,

... peuvent se modéliser à l'aide du « noyau de viabilité ».

Grâce à l'utilisation de ce « noyau de viabilité », permettant de réduire l'espace de recherche, l'ensemble de la modélisation du problème, incluant les contraintes et les lois d'évolution du contexte, est alors possible en PPC.

3. Conception d'un algorithme de recherche ou d'optimisation utilisant les « heuristiques métier » (guides de base des différentes applications) identifiées en vue de trouver soit simplement une solution satisfaisante, soit une bonne solution, soit une solution optimisée. Cette partie d'étape peut tre omise dans un premier temps, car elle peut masquer une possible analyse du comportement de chacune des contraintes du problème. On utilise alors l'algorithme générique du solveur PPC. Ce n'est que dans un deuxième temps qu'une étude fine des différentes heuristiques permet de concevoir un algorithme de recherche efficace.

L'algorithme de viabilité (voir le livre de J. P. AUBIN de 1991 et l'article de P. SAINT PIERRE cités ci-dessus) permet de trouver le noyau de viabilité sans calculer aucune trajectoire.

Cet algorithme peut tre transposé dans un solveur PPC, en utilisant les mécanismes d'arc cohérence et leur incrémentalité. Les mécanismes de propagation faisant partie du solveur permettent alors de considérer les contraintes de dynamique au mme titre que les autres contraintes du système étudié (par exemple les contraintes liées à la disponibilité des ressources ou les contraintes de durée maximale d'une opération à ne pas dépasser).

En conclusion, le procédé de l'invention permet, dans une approche classique de résolution d'un problème combinatoire à l'aide de la PPC, de dissocier la modélisation du problème (qui est ici une modélisation en contraintes) de sa résolution (algorithme de recherche d'une solution optimisée ou non). Cependant, grâce à la mise en oeuvre de la notion de

« noyau de viabilité », ce procédé permet aussi de dissocier dans la modélisation les contraintes limitant les décisions de la dynamique du contexte ou de la situation. Ceci permet donc, en particulier, de pouvoir tenir compte de changements de nature des évolutions de la situation (entre déterministe, risque et incertain), indépendamment de la nature mme du problème de décision à résoudre, et on modélise la loi d'évolution en fonction de ces changements.