When both Grounding and not Grounding are Bad -- A Partially Grounded Encoding of Planning into SAT (Extended Version)

Each language version is independently generated for its own context, not a direct translation.

🚀 Le Dilemme du Planificateur : Trop gros ou trop lent ?

Imaginez que vous êtes un chef d'orchestre (un planificateur d'IA) chargé d'organiser une symphonie complexe. Votre but est de trouver la séquence parfaite de notes (actions) pour transformer un chaos initial en une mélodie magnifique (l'objectif).

Le problème, c'est que votre partition est écrite dans un langage très abstrait et général (le "lifted"). Par exemple, au lieu d'écrire "Le violoniste Jean joue la note Do", on écrit "Tout violoniste peut jouer n'importe quelle note". C'est élégant et compact, mais l'ordinateur ne peut pas jouer de musique avec des concepts abstraits ; il a besoin de noms précis.

Traditionnellement, les ordinateurs font deux choses :

Tout détailler (Grounding) : Ils écrivent une partition pour chaque violoniste, chaque note, chaque instrument. C'est précis, mais si vous avez 1000 violonistes, la partition devient un livre de 10 000 pages. L'ordinateur s'étouffe (explosion combinatoire).
Tout garder abstrait (Lifting) : Ils essaient de jouer avec les concepts. C'est rapide au début, mais pour vérifier si la musique est juste, ils doivent faire des liens complexes entre chaque note potentielle et chaque musicien potentiel. Plus la symphonie est longue, plus ces liens deviennent un enchevêtrement impossible à démêler (croissance quadratique).

💡 La Solution : L'Approche "Hybride"

Les auteurs de ce papier (João Filipe et Gregor Behnke) proposent une troisième voie, un juste milieu intelligent.

Imaginez que vous organisez un grand banquet avec 1000 invités.

L'approche classique (Tout détailler) : Vous imprimez une carte de place pour chaque combinaison possible de chaise et d'invité. C'est énorme.
L'approche abstraite (Tout garder flou) : Vous dites "Assieds-toi quelque part", mais vous devez vérifier à chaque seconde si cette personne ne gêne pas les autres, ce qui prend un temps fou.
L'approche de ce papier (Partiellement ancré) : Vous gardez les actions floues ("Le serveur apporte un plat"), mais vous gérez les places assises de manière intelligente.

Ils utilisent une astuce appelée Groupes de Mutex Levés (PLMG).

Analogie : Imaginez que vous savez qu'un invité ne peut jamais être assis à deux tables en même temps. Au lieu de vérifier chaque chaise individuellement, vous créez un "groupe de chaises" pour cet invité. Vous dites simplement : "L'invité est soit à la table A, soit à la table B, soit nulle part".
Cela permet de garder la description de l'état (qui est où) beaucoup plus petite, sans avoir à lister chaque possibilité individuelle.

⚡ Le Résultat : Une Croissance Linéaire vs Quadratique

C'est ici que la magie opère.

L'ancienne méthode (LiSAT) : Si vous voulez planifier une action de plus, le travail de l'ordinateur augmente de façon explosive (comme le carré d'un nombre : 2, 4, 9, 16...). C'est comme si chaque nouvelle note ajoutée à la symphonie obligeait à réécrire toute la partition précédente.
La nouvelle méthode : Le travail augmente de façon proportionnelle (linéaire : 1, 2, 3, 4...). Ajouter une note ne demande que d'ajouter une petite ligne à la fin.

En résumé :

Actions : On les garde "floues" (lifted) pour ne pas les multiplier inutilement.
État (le monde) : On le "détaille" partiellement en utilisant des groupes logiques (les mutex) pour éviter de lister chaque fait individuellement.
Encodage binaire : Pour les très grands nombres d'objets, ils utilisent une sorte de code binaire (comme des interrupteurs ON/OFF) au lieu de lister chaque objet un par un, ce qui économise énormément d'espace.

🏆 Les Résultats : Qui gagne ?

Les auteurs ont testé leur méthode sur des problèmes difficiles (comme la logistique, les robots, les labyrinthes).

Sur les plans courts et optimaux : Leur méthode bat souvent l'état de l'art (LiSAT), surtout dans les domaines où il y a beaucoup d'objets et où les anciennes méthodes s'effondrent sous le poids des détails.
Sur les plans longs : Grâce à leur croissance linéaire, ils ne s'essoufflent pas. Là où les autres méthodes deviennent trop lentes, la leur reste efficace.

🎯 Conclusion Simple

Ce papier nous dit qu'on n'a pas besoin de choisir entre "tout détailler" (trop lourd) et "tout garder abstrait" (trop complexe à vérifier). En utilisant une représentation hybride intelligente (garder les actions floues mais structurer l'état avec des groupes logiques), on peut résoudre des problèmes de planification beaucoup plus grands et plus longs que jamais auparavant.

C'est comme passer d'une carte routière dessinée à la main pour chaque kilomètre, à un GPS qui utilise des zones géographiques intelligentes pour vous guider rapidement, même sur un trajet de 10 000 km.

Each language version is independently generated for its own context, not a direct translation.

1. Problématique

Le domaine de la planification automatique classique repose souvent sur des représentations « levées » (lifted), c'est-à-dire utilisant un langage de premier ordre sans fonctions, ce qui offre une grande compacité et généralité. Cependant, la plupart des planificateurs traditionnels « groundent » (instancient) entièrement ces représentations pour simplifier le raisonnement, ce qui entraîne une explosion exponentielle de la taille du problème lorsque le nombre d'objets est élevé.

Les approches récentes tentent d'éviter ce problème en opérant directement au niveau levé (lifted). L'approche de l'état de l'art pour la planification optimale en longueur est LiSAT (Höller et Behnke, 2022), qui encode le problème en Satisfiabilité Booléenne (SAT) sans jamais ground les faits. Bien que LiSAT évite l'explosion de l'état, son encodage souffre d'une croissance quadratique de la taille de la formule par rapport à la longueur du plan ( $\ell$ ). Cela est dû à la nécessité d'encoder des liens de causalité explicites entre chaque précondition et ses réalisateurs potentiels à chaque étape temporelle antérieure, rendant l'approche peu scalable pour les plans longs.

Le défi consiste donc à trouver un compromis entre le grounding complet (trop volumineux) et le lifting complet (trop complexe en termes de liens de causalité pour les plans longs).

2. Méthodologie

Les auteurs proposent une approche intermédiaire : un encodage partiellement ground. L'idée centrale est de garder les actions entièrement levées (comme dans LiSAT) tout en groundant partiellement la description de l'état (les prédicats).

Concepts Clés

Arguments Unifiés (Unified Arguments) : Comme LiSAT, l'approche utilise une méthode de splitting des arguments où les variables d'arguments sont partagées selon leur type plutôt que leur position, réduisant la variabilité.
Groupes de Mutex Levés (LMG) et Partiellement Levés (PLMG) : Les auteurs exploitent la structure inhérente du problème via des groupes de mutex (ensembles de faits où au plus un peut être vrai). Ils utilisent des PLMG, qui sont des mutex définis par des variables, permettant de représenter un grand nombre de faits groundés de manière compacte sans les énumérer tous.

Les Trois Encodages Proposés

Les auteurs introduisent trois variantes d'encodage SAT :

Fully Grounded (Grounding Complet) : Une approche de base qui ground tous les prédicats. Elle sert de référence mais n'est pas compétitive face aux méthodes avancées.
Partially Grounded (One-Hot) : Utilise des PLMG pour représenter les états. Pour chaque groupe PLMG, au lieu de créer une variable par fait ground, on utilise des variables de comptage (counted variables) pour indiquer quel objet est actif. Cela utilise un codage « one-hot » (une variable par objet possible).
Partially Grounded (Binary) : Une optimisation de la précédente. Au lieu d'un codage one-hot, les objets sont encodés en binaire ( $\lceil \log_2 |O| \rceil$ variables). Cela réduit considérablement le nombre de variables nécessaires pour les grands ensembles d'objets.

Structure de l'Encodage

Contrairement à LiSAT qui ne suit pas l'état explicitement, ces encodages suivent l'évolution de l'état à travers le temps ( $t \to t+1$ ).

Croissance Linéaire : En encodant l'état explicitement via des axiomes de cadre (frame axioms) et des variables de cause, la taille de la formule $\Phi_\ell$ croît linéairement avec la longueur du plan $\ell$ , éliminant le problème quadratique de LiSAT.
Élagage des Prédicats (Predicate Pruning) : Une optimisation majeure consiste à supprimer les prédicats qui n'apparaissent ni dans les préconditions des actions, ni dans l'objectif (sauf si le fait est un fait d'objectif). Cela réduit drastiquement le nombre de faits à encoder.

3. Contributions Clés

Nouvelle Classe d'Encodage SAT : Introduction d'encodages qui maintiennent les actions levées tout en groundant partiellement les états via des PLMG.
Complexité Linéaire : Preuve théorique et empirique que la taille de la formule scalaire linéairement avec la longueur du plan, contrairement à la croissance quadratique de LiSAT.
Optimisation par Codage Binaire : Proposition d'un codage binaire pour les variables d'état dans les PLMG, réduisant la densité d'information et le nombre de variables pour les domaines à nombreux objets.
Élagage Intelligent : Intégration d'une méthode d'élagage des prédicats (Predicate Pruning) adaptée au contexte levé, éliminant les faits inutiles sans perdre d'information critique.

4. Résultats Expérimentaux

Les expériences ont été menées sur un ensemble de benchmarks standard pour la planification levée (domaines comme Blocks, Logistics, Rovers, Visitall, etc.) en mode optimal en longueur et satisfaisant.

Performance en Planification Optimale :
- Les encodages proposés (notamment Binary avec Predicate Pruning) surpassent LiSAT sur 5 domaines sur 9.
- Ils obtiennent un score global supérieur à LiSAT.
- Dans des domaines difficiles à ground (comme Logistics, Pipesworld, Rover), l'amélioration est significative (≥ 20 % d'instances résolues en plus).
- LiSAT reste compétitif sur quelques domaines (GED, OS, Labyrinth), mais la différence est minime (< 5 %).
- Les méthodes basées sur la recherche (Powerlifted, CPDDL) sont nettement moins performantes que les méthodes SAT dans ce contexte optimal.
Performance en Planification Satisfaisante :
- Bien que légèrement inférieurs aux meilleurs planificateurs basés sur la recherche (comme Fast Downward ou Powerlifted) en termes de couverture globale, les encodeurs SAT (y compris LiSAT et la nouvelle méthode) résolvent des instances que les planificateurs de recherche ne peuvent pas traiter, notamment dans les domaines Blocks, Childsnack et Visitall.
- Cela suggère une complémentarité des approches.
Analyse de la Taille des Formules :
- Les graphiques montrent clairement la croissance linéaire du nombre de variables et de clauses pour les encodages proposés, contre une croissance quadratique pour LiSAT.
- Bien que les encodages proposés génèrent parfois plus de clauses que LiSAT pour de très courtes longueurs de plan (due à la complexité de l'encodage des PLMG), ils deviennent nettement plus efficaces dès que la longueur du plan augmente.

5. Signification et Conclusion

Cet article démontre qu'il est possible de combiner les avantages du grounding (gestion explicite de l'état) et du lifting (compacité des actions) pour surmonter les limitations des approches purement levées ou purement groundées.

Impact Théorique : La résolution du problème de la croissance quadratique dans les encodeurs SAT levés ouvre la voie à la résolution de problèmes nécessitant des plans beaucoup plus longs, jusqu'alors inaccessibles.
Impact Pratique : Les encodeurs proposés offrent des capacités complémentaires aux planificateurs basés sur la recherche. Ils sont particulièrement efficaces dans les domaines où la structure du problème (mutex) peut être exploitée pour compresser l'état.
Perspectives Futures : Les auteurs suggèrent d'étendre ces encodages pour supporter le parallélisme d'actions, les préconditions négatives et les effets conditionnels, ce qui pourrait élargir encore leur applicabilité.

En résumé, cette recherche établit un nouvel état de l'art pour la planification optimale en longueur basée sur SAT, en prouvant qu'une approche « partiellement ground » est supérieure aux approches entièrement levées pour les plans longs.