Compiling Temporal Numeric Planning into Discrete PDDL+: Extended Version

Cet article présente une compilation pratique et polynomiale qui traduit la planification temporelle avec actions duratives vers le langage PDDL+, en préservant sémantiquement la longueur des plans et en démontrant son efficacité expérimentale sur des problèmes numériques complexes.

L'essentiel

Voici une explication simple et imagée de ce papier de recherche, comme si nous en parlions autour d'un café.

Le Problème : Organiser un Chaos Temporel

Imaginez que vous êtes le chef d'orchestre d'une symphonie très complexe. Vous avez des musiciens (les actions) qui doivent jouer à des moments précis. Certains musiciens jouent une note courte (une action instantanée), tandis que d'autres doivent tenir une note longue pendant plusieurs secondes (une action qui dure, comme un accord de violon).

Le problème, c'est que dans le monde de la planification automatique (où les ordinateurs essaient de trouver la meilleure façon de faire quelque chose), il existe deux langages pour décrire cette musique :

1. PDDL 2.1 : Le langage classique pour dire "Joue cet accord pendant 5 secondes". C'est précis, mais les ordinateurs ont parfois du mal à le comprendre directement.
2. PDDL+ : Un langage plus sophistiqué, conçu pour décrire des systèmes qui évoluent en continu, comme une rivière qui coule ou une horloge qui tourne.

Jusqu'à présent, les chercheurs savaient théoriquement qu'on pouvait traduire le premier langage dans le second, mais personne n'avait trouvé la méthode pratique pour le faire sans perdre de temps ni d'informations. C'est comme savoir qu'on peut traduire du français en espagnol, mais ne pas avoir le dictionnaire.

La Solution : Le Grand Traducteur

Les auteurs de ce papier (Andrea, Enrico et Alessandro) ont créé ce "dictionnaire". Ils ont inventé une méthode pour transformer n'importe quel problème de planification temporelle (avec des actions qui durent) en un problème PDDL+ que les ordinateurs modernes peuvent résoudre très efficacement.

Voici comment leur "machine à traduire" fonctionne, avec une analogie :

1. La Boîte à Outils (Les Actions et les Processus)

Dans le langage PDDL+, on ne dit pas "Fais ça pendant 5 secondes". On dit plutôt :

• Action instantanée : "Appuie sur le bouton de départ".
• Processus : "Laisse l'eau couler tant que le robinet est ouvert".
• Événement : "Quand l'eau atteint le niveau 5, coupe le robinet".

Leur compilation transforme une action "durative" (comme "Cuisiner pendant 30 minutes") en une petite trinité :

• Un déclencheur (Action) qui dit "On commence à cuisiner".
• Un processus qui dit "Le temps passe, la température monte".
• Un arrêt (Événement ou Action) qui dit "30 minutes écoulées, on arrête".

2. Le Gardien de la Paix (Le Mécanisme de "Verrou")

C'est la partie la plus ingénieuse. Imaginez une cuisine très encombrée où plusieurs chefs travaillent. Si deux chefs essaient d'utiliser le même couteau en même temps, ou si l'un coupe un oignon pendant que l'autre essaie de le lire, le chaos s'ensuit.

Les auteurs ont inventé un système de verrous magiques (qu'ils appellent "locks") :

• Quand un chef veut utiliser un ingrédient (lire une variable), il doit prendre un verrou rouge.
• Quand il veut modifier un ingrédient (écrire une variable), il doit prendre un verrou bleu.
• Tant que le verrou est pris, personne d'autre ne peut toucher cet ingrédient.

Leur astuce géniale ? Ils utilisent une petite horloge interne (une variable numérique) qui se réinitialise à chaque instant. Cela permet de dire : "Dans cet instant précis, tout le monde a le droit de jouer, mais dès qu'on passe à l'instant suivant, les verrous se réinitialisent". Cela empêche les conflits sans ralentir la machine.

Pourquoi est-ce génial ? (Les Résultats)

Les chercheurs ont testé leur méthode sur des problèmes très difficiles, comme :

• Arrosage de plantes : Il faut ouvrir le robinet et allumer la pompe en même temps, mais avec des contraintes de temps.
• Sauvetage en bateau : Il faut arriver avant une certaine heure pour sauver des gens.

Le résultat est surprenant : en utilisant leur traduction vers le langage PDDL+, les ordinateurs ont souvent trouvé de meilleures solutions, plus vite, que les logiciels spécialisés conçus spécifiquement pour le temps. C'est un peu comme si, pour traverser une rivière, on avait essayé de construire un pont complexe (les planificateurs temporels classiques), alors que la traduction permettait d'utiliser un ferry ultra-rapide (les planificateurs PDDL+).

En Résumé

Ce papier est une victoire de l'ingéniosité. Il a pris un problème difficile (gérer le temps et les actions qui durent) et l'a transformé en un problème que les ordinateurs actuels maîtrisent déjà très bien, grâce à une traduction intelligente et à un système de "verrous" pour éviter les collisions.

C'est comme si on avait appris à un ordinateur à parler le langage des "horloges et des processus" pour mieux gérer le temps, lui permettant de résoudre des énigmes complexes que l'on croyait trop dures pour lui.

Résumé technique

Voici un résumé technique détaillé de l'article « Compiling Temporal Numeric Planning into Discrete PDDL+ » en français.

1. Problématique et Contexte

L'article aborde le problème de la planification temporelle avec actions duratives (modélisées dans le langage PDDL 2.1, niveau 3). Bien qu'il soit théoriquement connu que le langage PDDL+ (qui utilise des processus, des événements et des actions instantanées) peut exprimer des actions duratives, aucune méthode de compilation pratique et formellement rigoureuse n'avait été présentée dans la littérature jusqu'à ce travail.

Le défi principal réside dans la traduction fidèle de la sémantique de PDDL 2.1 (actions ayant une durée, conditions invariantes pendant l'exécution, effets différés) vers PDDL+, tout en garantissant :

• La correction (soundness) : tout plan généré en PDDL+ correspond à un plan valide en PDDL 2.1.
• La complétude : tout plan valide en PDDL 2.1 peut être représenté dans le modèle compilé.
• L'efficacité : la compilation doit être polynomiale et ne pas exploser la taille du problème.

2. Méthodologie et Approche de Compilation

Les auteurs proposent une compilation polynomiale qui transforme un problème de planification temporelle $\Pi$ en un problème PDDL+ $\bar{\Pi}$. L'approche repose sur l'idée qu'une action durative peut être décomposée en une séquence d'événements instantanés et de processus continus.

A. Modélisation des Actions Duratives

Chaque action durative $a$ est décomposée en :

• Actions instantanées (Snap actions) :
  • Un début ($a_{\vdash}$) : vérifie les préconditions initiales, lance un compteur de temps et un indicateur d'état.
  • Une fin ($a_{\dashv}$) : pour les actions à durée variable, vérifie que la durée est dans les bornes $[l_a, u_a]$ et termine l'action.
• Processus : Un processus continu ($\bar{p}_a$) qui s'active tant que l'action est en cours ($ra$ est vrai) et incrémente un compteur de temps $ca$ à la vitesse de 1 ($\frac{d}{dt}ca = 1$).
• Événements :
  • Pour les actions à durée fixe, un événement ($\bar{e}_{\dashv}$) déclenche automatiquement la fin lorsque le compteur atteint la durée fixe.
  • Pour les actions à durée variable, la fin est déclenchée par l'action instantanée $a_{\dashv}$.
  • Des événements de vérification ($\bar{e}_{\leftrightarrow}$) surveillent les conditions globales (invariants) de l'action. Si une condition est violée pendant l'exécution, un drapeau ok est mis à faux, rendant le plan invalide.

B. Gestion des Interférences et de la Concurrence (Mécanisme de Verrouillage)

Un point crucial de la compilation est la gestion des interférences entre actions se produisant au même instant (sémantique "non-self-overlapping" et "no-moving-target"). Les auteurs introduisent un mécanisme de verrous (locks) basé sur des prédicats booléens auxiliaires :

• Pour chaque fluide $f$, trois verrous sont définis : rlf (lecture), alf (assignation), ilf (incrément).
• Préconditions de verrouillage : Une action ne peut lire, assigner ou incrémenter un fluide que si les verrous correspondants sont à vrai.
• Effets de verrouillage : Dès qu'une action lit, assigne ou incrémente un fluide, le verrou correspondant est mis à faux.
• Réinitialisation : Un événement global $\bar{e}_E$ réinitialise tous les verrous à vrai à chaque pas de temps discret, mais seulement après que le temps ait effectivement progressé.
• Variable de temps gc : Une variable numérique gc est utilisée pour distinguer les étapes super-denses. Elle est augmentée par un processus à chaque pas de temps et réinitialisée par $\bar{e}_E$. Cela empêche deux actions interférentes de s'exécuter dans le même "instant" super-dense sans que le temps ne passe.

C. Propriétés Théoriques

• Complexité : La compilation est polynomiale par rapport à la taille du problème d'entrée.
• Longueur du plan : La longueur du plan est conservée à un facteur constant près (au maximum doublée).
• Sémantique discrète : La compilation suppose une sémantique de temps discret pour PDDL+ (avec un quantum de temps $\delta$). Cela évite les comportements de type Zeno (une infinité d'événements en temps fini) qui pourraient survenir dans une sémantique continue avec ce mécanisme de réinitialisation immédiate.

3. Résultats Expérimentaux

Les auteurs ont évalué leur compilation sur une série de domaines de planification temporelle numérique, en comparant le compilateur (utilisant le planificateur PDDL+ ENHSP) avec des planificateurs temporels natifs de l'état de l'art (ARIES, NextFLAP, TFLAP, OPTIC, TAMER, Patty).

• Domaines testés : MatchCellar, MAJSP, T-Plant-Watering, T-Sailing, et d'autres. Ces domaines mettent l'accent sur l'interaction entre variables numériques et contraintes temporelles.
• Performance :
  • ENHSP-WA (utilisant la recherche heuristique $WA^*$) a obtenu la couverture la plus élevée (nombre d'instances résolues), surpassant souvent les planificateurs natifs, en particulier sur les problèmes numériques complexes.
  • Sur les domaines purement temporels, les planificateurs natifs restent plus rapides, mais la compilation reste compétitive.
  • Sur les domaines numériques temporels (ex: MAJSP, T-Plant-Watering), la compilation PDDL+ démontre une supériorité significative, suggérant que les solveurs PDDL+ actuels sont très performants pour gérer la complexité numérique et temporelle combinée.
• Analyse : Les résultats indiquent une complémentarité : les approches natives excellent sur la pure temporalité, tandis que l'approche par compilation excelle sur la complexité numérique et les contraintes d'interférence.

4. Contributions Clés

1. Première compilation formelle complète : C'est la première fois qu'une traduction rigoureuse et complète des actions duratives PDDL 2.1 vers PDDL+ est présentée, avec des preuves de correction et de complétude.
2. Mécanisme de verrouillage innovant : Introduction d'un système de verrous (locks) et de variables de temps (gc) pour modéliser fidèlement la sémantique d'interdiction d'interférence et la règle "no-moving-target" de PDDL 2.1 dans un cadre PDDL+.
3. Validation pratique : Démonstration expérimentale que la compilation n'est pas seulement théorique mais offre des performances pratiques, souvent supérieures aux méthodes natives sur des problèmes numériques complexes.
4. Extensibilité : La méthode gère naturellement des fonctionnalités avancées comme les effets différés et les littéraux initiaux temporels, en les modélisant via des événements déclenchés.

5. Signification et Perspectives

Cet article est significatif car il comble un vide théorique et pratique entre deux langages de planification majeurs. Il démontre que PDDL+, souvent perçu comme plus complexe, peut être un langage cible puissant pour la planification temporelle, offrant une alternative viable et performante aux solveurs dédiés.

Travaux futurs envisagés :

• Étendre la compilation au niveau 4 de PDDL 2.1 pour inclure les changements continus (continuous change).
• Étudier une compilation alternative ciblant une sémantique continue pour PDDL+, bien que cela pose des défis liés aux comportements Zeno.

En résumé, ce travail fournit un pont robuste entre la planification temporelle classique et les systèmes hybrides, validant l'efficacité de l'approche par compilation pour résoudre des problèmes d'optimisation temporelle et numérique complexes.