Planification classique, sous incertitude, temporelle, épistémique

La synthèse de plans d’actions pour traiter des domaines du monde réel est un problème difficile à cause de sa complexité et de l’incomplétude, l’inexactitude et de l’incertitude des informations. L’obtention d’algorithmes efficaces nécessite un cadre très restrictif dans lequel on considère des actions atomiques, instantanées, déterministes, sans ressources… et un monde fini, statique…  Après avoir travaillé dans ce cadre restrictif, nous cherchons maintenant à l’élargir pour traiter des problèmes dans le monde réel et nous avons développé des méthodes de calcul de plans optimaux qui intégrent :

  • des actions valuées (on optimise alors le coût) [1,2] ;
  • des actions avec durée qui peuvent nécessiter un prétraitement pour la gestion des cycles temporels [3] et qui nous ont permis de définir une  nouvelle classe traitable [4]) ;
  • des actions non déterministes, quantifiées de manière qualitative [10,11,12,], et possiblement les fonctions d’utilité de plusieurs agents [13].
Actuellement et dans le cadre d’un travail conjoint avec l’équipe LILaC, nous travaillons plus particulièrement sur la planification épistémique dans laquelle les actions changent non seulement le monde, mais également les connaissances des agents, y compris les connaissances d’ordre supérieur (c’est-à-dire celles qui portent sur les connaissances des autres agents). Ce travail se situe dans le cadre du problème plus général du raisonnement sur les états mentaux des agents. Nous étudions en particulier le problème du bavardage (Gossip Problem) comme une tâche de planification dans laquelle les agents doivent partager des secrets [5,6]. Nous avons caractérisé une version du “Gossip Problem” comportant des connaissances d’ordre supérieur et nous avons proposé et étudié la complexité d’une version temporellement étendue [7].

Nous avons aussi développé un traducteur automatique, TouIST qui nous permet de coder des problèmes en formules logiques pour les résoudre ensuite à l’aide d’un solveur SAT, QBF ou SMT. Notre module TouISTPlan permet de résoudre automatiquement des problèmes de planification en utilisant différents types de codages. Dans le cadre de la planification classique, nous avons proposé deux nouveaux codages QBF compacts qui sont plus efficaces que les codages existants pour résoudre les benchmarks des compétitions internationales de planification IPC [8]. Dans le cadre de la planification temporelle nous avons également proposé un nouveau codage SMT.

Nous étudions également la manière de coder des problèmes de planification de manière compacte dans des logiques non classiques. Nous avons notamment développé une logique dynamique qui permet de traiter des tâches de planification parallèles sans augmenter la complexité [9].

La simulation du processus de planification est également nécessaire pour la gestion de la chaîne logistique, où des décisions doivent être prises en termes de production, de distribution et d’approvisionnement dans un environnement complexe. L’équipe travaille, avec d’autres laboratoires de la région, sur des approches de type simulation pour l’aide à la décision dans lesquelles le décideur évalue différents processus de planification de la chaîne logistique notamment en terme de risque [14,15,16].

Références

  • [1] Martin Cooper, Marie de Roquemaurel, Pierre Régnier. Transformation of optimal planning problems. Dans / In : Journal of Experimental & Theoretical Artificial Intelligence, Taylor & Francis Group, Vol. 23 N. 2, p. 181-199, juin / june 2011. (pdf)
  • [2]Martin Cooper, Marie de Roquemaurel, Pierre Régnier. A weighted CSP approach to cost-optimal planning. Dans / In : AI Communications, IOS Press, Vol. 24 N. 1, p. 1-29, 2011. (pdf)
  • [3] Martin Cooper, Frédéric Maris, Pierre Régnier. Managing temporal cycles in planning problems requiring concurrency. Dans / In : Computational Intelligence, Wiley-Blackwell, USA, Vol. 29 N. 1, p. 111-128, 2013. (pdf)
  • [4] Martin Cooper, Frédéric Maris, Pierre Régnier. Monotone Temporal Planning: Tractability, Extensions and Applications. Dans / In : Journal of Artificial Intelligence Research (JAIR), AAAI Press, Vol. 50, p. 447-485, 2014. (pdf)
  • [5] Martin Cooper, Andreas Herzig, Faustine Maffre, Frédéric Maris, Pierre Régnier. A simple account of multi-agent epistemic planning. Dans / In : European Conference on Artificial Intelligence (ECAI 2016), IOS Press, p. 193-201, août / august 2016. (pdf)
  • [6] Martin Cooper, Andreas Herzig, Faustine Maffre, Frédéric Maris, Pierre Régnier. The epistemic gossip problem. Dans / In : Discrete Mathematics, Elsevier, Vol. 342 N. 3, p. 654-663, 2019. (pdf)
  • [7] Martin Cooper, Andreas Herzig, Frédéric Maris, Julien Vianey. Temporal Epistemic Gossip Problems. Dans : European Conference on Multi-Agent Systems (EUMAS 2018), Springer, LNCS 11450, p. 1-14, 2019.
  • [8] Olivier Gasquet, Dominique Longin, Frédéric Maris, Pierre Régnier, Maël Valais. Compact Tree Encodings for Planning as QBF. Dans / In : Inteligencia Artificial (Ibero-American Journal of Artificial Intelligence), Asociación Española de Inteligencia Artificial (AEPIA), Spain, Vol. 21 N. 62, p. 103-113, 2018. (pdf)
  • [9] Andreas Herzig, Frédéric Maris, Julien Vianey. Dynamic logic of parallel propositional assignments and its applications to planning . Dans / In : International Joint Conference on Artificial Intelligence (IJCAI 2019), Kraus (Eds.), p. 5576-5582, août 2019. (pdf)
  • [10] Nahla Ben Amor, Zeineb El Khalfi, Helene Fargier, Regis Sabbadin. Lexicographic refinements in possibilistic decision trees and finite-horizon Markov decision processes. Dans / In : Fuzzy Sets and Systems. Elsevier, Vol. 366: p. 85-109 (2019).
  • [11] Nahla Ben Amor, Zeineb El Khalfi, Helene Fargier, Regis Sabbadin. Lexicographic refinements in stationary possibilistic Markov Decision Processes. Dans / In : International Journal of Approximate Reasoning Vol. 103: p. 343-363 (2018).(pdf)
  • [12] Nahla Ben Amor, Zeineb El Khalfi, Helene Fargier, Regis Sabbadin. Efficient Policies for Stationary Possibilistic Markov Decision Processes. Dans / In : European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2017). Springer, p. 306-317. (pdf)
  • [13] Nahla Ben Amor, Fatma Essghaier, Hélène Fargier. Egalitarian collective decision making under qualitative possibilistic uncertainty : Principles and characterization. . Dans / In : AAAI Conference on Artificial Intelligence, AAAI Press, p. 3482-3488, janvier / january 2015. (pdf)
  • [14] Romain Guillaume, Caroline Thierry, Bernard Grabot. Integration of the Supplier Capacity for Choosing the Less Risky Schedule within an Uncertain Environment . Dans / In : IFIP Working Conference on Virtual Enterprises (PRO-VE 2010), Springer, (electronic medium), 2010.
  • [15] François Galasso, Caroline Thierry. Design of cooperative processes in a customer-supplier relationship: An approach based on simulation and decision theory. Dans / In : Engineering Applications of Artificial Intelligence, Elsevier, Vol. 22 N. 6, p. 865-881, septembre / september 2009.(pdf)
  • [16]Caroline Thierry, Jacques Lamothe, Jaouher Mahmoudi. A simulation model for customer-supplier cooperation in the telecom supply chain. Dans / In : International Journal of Business Performance Management, National Academy of Sciences, Vol. 9 N. 2, p. 188-205, février / february 2007.