Planification avec préférences

De la problématique de la planification 

La planification automatisée est un domaine de l’Intelligence Artificielle qui consiste à choisir et séquencer un ensemble d’actions par anticipation de leurs résultats afin d’atteindre des objectifs fixés [66]. Si cette tâche est souvent triviale pour un certain nombre de problèmes du quotidien, elle demeure néanmoins complexe lorsque les problèmes considérés sont fortement combinatoires. Cette section introduit le modèle conceptuel de la planification (cf. section 1.1.1) ainsi que le problème dit de planification classique (cf. section 1.1.2). De plus, le langage formel utilisé pour spécifier et résoudre les problèmes de planification est également présenté (cf. section 1.1.3). 

Modèle conceptuel de la planification

 La planification a pour objectif de faire évoluer un système Σ dans un état initial connu vers un état final satisfaisant un ensemble d’objectifs fixés. Dans son acception la plus générique, l’activité de la planification englobe à la fois l’élaboration du plan d’action considéré ainsi que l’exécution de ce dernier. Le modèle conceptuel de la planification formalise l’activité de la planification et a été proposé dans l’ouvrage de référence Automated Planning : Theory and Practice [66]. Il repose sur les interactions de trois composants : un planificateur, un contrôleur et un système Σ (cf. figure 1.1a). 1. Le planificateur construit le plan d’action en se basant sur la description du système Σ, de son état initial et des objectifs à atteindre. 2. Le contrôleur exécute le plan qui lui est transmis produisant ainsi des actions sur le système. Il s’appuie sur les informations (éventuellement incomplètes) qu’il possède sur l’état actuel du système. 3. Le système Σ évolue en réponse aux actions qui sont exécutées par le contrôleur ou aux événements extérieurs qui surviennent. Le contrôleur est généralement supposé assez robuste pour gérer les différences qui peuvent exister entre le monde réel et son modèle Σ. Si cette hypothèse n’est pas acceptable, le contrôleur peut retourner un statut d’exécution au planificateur permettant à ce dernier de produire un nouveau plan lorsque la situation observée 28 Chapitre 1 – Planification avec préférences et la situation attendue divergent. Le terme de planification dynamique est alors employé puisque la création du plan et son exécution deviennent intimement liées (cf. boucle de rétroaction sur la figure 1.1b).

Définition 1.1 – Système à événements discrets [40] Un système à événements discrets est un quadruplet Σ = (S, A, E, γ) avec : • S un ensemble fini ou récursivement énumérable d’états ; • A un ensemble fini ou récursivement énumérable d’actions ; • E un ensemble fini ou récursivement énumérable d’événements ; • γ : S × A × E → P(S) une fonction de transition d’états. Modéliser Σ comme un système à événements discrets revient à caractériser ce dernier par l’état s ∈ S dans lequel il se trouve. Une évolution du système Σ correspond donc à un changement d’état s → s 0 . Dans le modèle conceptuel de la planification, la transition d’un état s vers un état s 0 est représentée par l’application d’un couple action/événement (a, e) dans l’état s. L’action neutre α et l’événement neutre  sont introduits afin de décrire des transitions provoquées uniquement par des actions ou des événements. Dans de tels cas, les notations γ(s, a) et γ(s, e) sont utilisées en lieu et place de γ(s, a, ) et γ(s, α, e). Il convient de remarquer que bien que les actions et les événements contribuent tous deux à l’évolution du système, leur sémantique diffère. Les actions sont contrôlées par les personnes en charge de l’exécution du plan alors que les événements sont des transitions qui échappent à leur contrôle. Ces derniers peuvent être causés par la dynamique interne du système ou encore par l’évolution de l’environnement du système. La fonction γ précise l’ensemble des états s 0 vers lesquels le système Σ est susceptible d’évoluer à partir de l’état s en réponse à une action a, un événement e ou un couple action/événement (a, e). Ainsi, la taille de l’ensemble retourné par γ(s, a) notée |γ(s, a)| fournit plusieurs informations quant à l’exécution de a dans s. Si |γ(s, a)| > 0, l’action a est dite applicable dans s puisque le système Σ peut évoluer vers au moins un état s 0 lors de l’exécution de a dans s. De plus, si |γ(s, a)| ≤ 1 alors l’application de a dans s est dite déterministe. En effet, si l’action a est exécutable et qu’elle est exécutée dans s, Σ ne peut alors évoluer que vers un unique état s 0 . Le modèle conceptuel de la planification [66] propose également huit hypothèses pour caractériser les différentes classes de problèmes de planification. Hypothèse H1 (Σ fini). L’ensemble S des états de Σ est fini. Hypothèse H2 (Σ complètement observable). L’état du système Σ est entièrement observable. Par conséquent, les observations du système sur lesquelles s’appuie le contrôleur sont toutes parfaites. Hypothèse H3 (Σ déterministe). Le système Σ est déterministe si pour tout état s, pour toute action a et pour tout événement e, |γ(s, a, e)| ≤ 1. Ainsi, en réponse à un couple action/événement (a, e) applicable dans s, le système Σ ne peut évoluer que vers un unique état s 0 . Hypothèse H4 (Σ statique). L’ensemble E des événements de Σ est vide. Hypothèse H5 (Plans séquentiels). Un problème de planification admet des plans solutions représentés par une séquence d’actions finie ordonnée linéairement, il n’y a donc aucune parallélisme dans les plans solutions. 

Problème de la planification classique 

Le terme planification classique fait référence à la classe des problèmes obtenue lorsque les huit hypothèses du modèle conceptuel de la planification sont considérées simultanément. L’étude de ce problème est fondamentale puisque la majorité des problèmes de planification sont définis par extension de ce dernier à l’image de la problématique de la planification avec préférences. Problème de la planification classique [66] Étant donné un système à événements discrets Σ = (S, A, γ), un problème de planification classique est défini par le triplet P C = (Σ, s0, SG) où s0 est un état initial et SG ⊂ S est l’ensemble des états qui vérifient les objectifs G. Une solution de P C est une séquence d’actions ha1, · · · , ani qui correspond à une séquence d’états hs0, · · · , sni telle que : s1 = γ(s0, a1), · · · , sn = γ(sn−1, an) et sn ∈ SG. Exemple illustratif Pour illustrer la problématique de la planification classique, une version simplifiée du problème Rovers [42] est utilisée. Dans ce problème, des robots réalisent une exploration planétaire. Ils doivent prendre des photographies et récolter des échantillons de sols ou de roches de plusieurs lieux différents. La récolte des échantillons de sols et de roches est modélisée par deux actions distinctes dans ce problème pour préciser que les robots utilisent des outils différents dans les deux cas. L’exemple considéré ici s’intéresse au cas d’un unique robot N1 qui évolue à travers six lieux Li différents. L’ensemble { robot, planète } constitue le système Σ et évolue en fonction des actions A du robot : déplacement d’un lieu à un autre, prise de photographies et récolte d’échantillons. Tous les lieux ne sont pas accessibles les uns des autres en raison de la présence d’obstacles infranchissables par le robot. En outre, pour pouvoir prendre la photographie d’un lieu L1, le robot doit soit se situer dans L1 soit dans un lieu L2 à partir duquel L1 est visible. Dans l’état initial s0 (représenté sur la figure 1.2), le robot est en L5, des échantillons de sols sont présents dans tous les lieux mais seuls les lieux L2, L3 et L6 possèdent des échantillons de roches. Enfin, les objectifs G sont notés [S4], [R3] et [P1] et désignent respectivement l’acquisition d’un échantillon de sol de L4, l’acquisition d’un échantillon de roche de L3 et la prise d’une photographie de L1. Cet exemple sera enrichi (utilisation de plusieurs robots…) tout au long de ce chapitre pour présenter les mécanismes de la planification ainsi que pour illustrer le problème de la planification avec préférences (cf. sections 1.2.2, 1.1.3 et 1.2.3).

Langage formel pour la planification

Afin de standardiser la représentation des problèmes de planification, le langage pddl (Planning Domain Definition Language) a été proposé en 1998 par la communauté de la planification [107]. Le pddl est couramment utilisé et a connu quatre évolutions majeures depuis sa création [49, 61, 64, 91]. Cette section a pour but de présenter en détails les mécanismes de la planification. A cette fin, la syntaxe du pddl et la sémantique qui y est associée sont introduits. Les éléments de 33 Chapitre 1 – Planification avec préférences sémantique présentés traitent de la planification classique et de l’exploitation de variables numériques. En outre, ils sont illustrés à l’aide de l’exemple introduit dans la section 1.1.2. Syntaxe pour la planification Le pddl a été élaboré en s’inspirant de plusieurs travaux antérieurs dont notamment les langages strips [99] et adl [114], le formalisme ucpop [11] ainsi que le situation calculus [106, 120]. Par ailleurs, le pddl présente de nombreuses similarités avec la logique du premier ordre. Les notions de prédicats, d’arité, de formules, d’atomes, de littéraux et de formules closes qui sont utilisées dans la suite de cette section sont définies dans l’annexe A qui présente la syntaxe de la logique du premier ordre. L’ensemble des états caractérisant un problème de planification ne peut généralement pas être énuméré explicitement au vu de sa grande taille. Pour contourner ce problème et représenter de façon compacte les problèmes de planification, les états sont donc caractérisés à l’aide de formules de la logique du premier ordre dont les variables peuvent éventuellement être typées. Ainsi, pour formaliser un problème de planification en pddl, les principaux éléments à renseigner sont des prédicats et des objets, des actions, une situation initiale et des objectifs et contraintes. La notation bnf [4] est utilisée pour décrire avec précision et sans ambigüité la syntaxe du pddl [63, 91]. Quelques extraits du langage pddl sont exposés ci-dessous. Des exemples complets sont disponibles dans l’annexe B.