Planning (classical, temporal, epistemic) and under uncertainty

The synthesis of action plans to address real-world areas is a difficult problem because of its complexity and the incompleteness, inaccuracy and uncertainty of information. Obtaining effective algorithms requires a very restrictive framework in which we consider atomic, instantaneous, deterministic, resourceless actions… and a finite, static world… After working within this restrictive framework, we now seek to extend it to address problems in the real world and we have developed methods for calculating optimal plans that integrate:

  • of the actions valued (the cost is then optimized)[1,2] ;
  • actions with duration that may require pre-processing for time cycle management[3] and that have allowed us to define a new treatable class[4]) ;
  • non-deterministic actions, quantified qualitatively[10,11,12,12], and possibly the utility functions of several agents[13].
Currently and as part of a joint work with the LILaC team, we are working more particularly on epistemic planning in which actions change not only the world, but also the knowledge of agents, including higher order knowledge (i.e. those that relate to the knowledge of other agents). This work is part of the more general problem of reasoning on the mental states of agents. In particular, we study the problem of chatting (Gossip Problem) as a planning task in which agents must share secrets[5,6]. We characterized a version of the “Gossip Problem” with higher order knowledge and proposed and studied the complexity of a time-extended version[7].

We have also developed an automatic translator, TouIST which allows us to code problems into logical formulas and then solve them using a SAT, QBF or SMT solver. Our TouISTPlan module allows you to automatically solve planning problems using different types of coding. As part of traditional planning, we have proposed two new compact QBF codings that are more effective than existing ones in solving benchmarks for international IPC planning competitions[8]. As part of the time planning we have also proposed a new SMT coding.

We also study how to code planning problems in a compact way in unconventional logics. In particular, we have developed a dynamic logic that allows us to handle parallel planning tasks without increasing complexity[9].

Simulation of the planning process is also necessary for supply chain management, where decisions must be made in terms of production, distribution and supply in a complex environment. The team is working with other laboratories in the region on simulation-type approaches to decision support in which the decision-maker evaluates different supply chain planning processes, particularly in terms of risk[14,15,16].

References

  • [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.