💻 computer science

Learning Lifted Action Models from Traces with Minimal Information About Actions and States

Cet article présente des algorithmes et des résultats de complétude pour l'apprentissage de domaines d'actions STRIPS+ à partir de traces comportant des informations partielles sur les actions et les états, en palliant les limitations antérieures en considérant des scénarios allant de l'absence d'observabilité des états à une observabilité totale ou locale de prédicats d'état spécifiques.

Auteurs originaux : Jonas Gösgens, Niklas Jansen, Hector Geffner

Publié 2026-05-19

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jonas Gösgens, Niklas Jansen, Hector Geffner

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de comprendre les règles d'un jeu de société complexe, comme les Échecs ou un puzzle à glisser, mais que vous avez un problème très étrange : vous ne pouvez pas voir le plateau.

Vous ne pouvez voir que les coups que les joueurs effectuent. Vous voyez une pièce passer de « A » à « B », ou un joueur saisir un jeton. Mais vous ne savez pas quelle pièce a bougé, où elle a commencé, ni à quoi ressemblait le plateau avant ou après le coup. Vous tentez de reconstituer le manuel de règles du jeu en observant simplement une série d'actions.

C'est le défi central abordé dans l'article « Learning Lifted Action Models from Traces with Minimal Information ».

Voici une décomposition de ce que les auteurs ont fait, en utilisant des analogies simples.

Le Problème : Le Piège de « Trop d'Informations »

Dans le passé, les informaticiens ont tenté d'enseigner à l'IA d'apprendre ces règles. Ils avaient deux approches principales, mais toutes deux présentaient des défauts :

L'Approche « Plateau Complet » : L'IA recevait l'état complet du plateau (la position de chaque pièce) et le coup joué.
- Le Défaut : Dans le monde réel, nous voyons rarement le plateau entier. De plus, les règles demandent souvent trop de détails. Par exemple, pour déplacer une tuile dans un puzzle, les anciennes règles exigeaient que vous spécifiiez l'emplacement actuel de la tuile, son nouvel emplacement et l'emplacement vide. Mais pour décider de bouger, vous n'avez réellement besoin de savoir que « Bouger à Gauche ». Les détails supplémentaires ne sont que du bruit pour le décideur.
L'Approche « Action Uniquement » : L'IA recevait uniquement la liste des coups (par exemple, « Bouger à Gauche », « Saisir »).
- Le Défaut : Sans voir le plateau, l'IA ne pouvait pas déterminer ce qu'elle déplaçait. Elle ne savait pas si « Bouger à Gauche » signifiait déplacer un robot, une voiture ou une boîte.

La Solution : Un Nouveau Langage (STRIPS+)

Les auteurs ont introduit un juste milieu appelé STRIPS+. Considérez cela comme une manière plus intelligente d'écrire les règles.

Dans l'ancienne méthode (STRIPS), une règle pouvait ressembler à un formulaire strict :

Move(Robot, CurrentCell, NextCell)

Dans la nouvelle méthode (STRIPS+), la règle ressemble davantage à une énigme :

Move()

La règle dit : « S'il y a un robot dans une case, et qu'il y a une case à droite, vous pouvez bouger. » L'ordinateur doit déterminer quel robot et quelles cases correspondent à cette description. C'est comme un détective résolvant un crime où le suspect est décrit uniquement comme « la personne portant un chapeau rouge », plutôt que d'être nommé « John Smith ».

Les Nouveaux Algorithmes : SIFT+ et SYNTH+

L'article présente deux nouveaux « détectives » (algorithmes) pour résoudre ce mystère lorsque l'information manque.

1. SIFT+ (Le Détective « Action Uniquement »)

Ce qu'il fait : Il apprend les règles en observant uniquement une liste de coups, avec zéro vue du plateau.
Comment il fonctionne : Il utilise une astuce appelée « Mutex Features » (Fonctions d'exclusion mutuelle).
- L'Analogie : Imaginez que vous voyez un joueur saisir une tasse. Vous ne voyez pas la tasse, mais vous savez qu'un joueur ne peut tenir qu'une tasse à la fois. Si le joueur saisit une tasse, il a dû déposer celle qu'il tenait.
- SIFT+ recherche ces modèles « mutuellement exclusifs ». Il réalise : « Ah, chaque fois que cette action se produit, quelque chose doit être vrai concernant l'objet tenu. » Il invente de nouveaux « prédicats » (concepts comme is_holding / est_en_train_de_tenir) pour combler les lacunes manquantes.
Le Résultat : Il peut apprendre le manuel de règles complet même si les noms des actions sont dépouillés de presque tous leurs détails.

2. SYNTH+ (Le Détective « Vue Partielle »)

Ce qu'il fait : Il apprend lorsqu'il peut voir certaines parties du plateau, mais pas toutes.
Comment il fonctionne : Il combine la « résolution d'énigmes » du nouveau langage STRIPS+ avec les compétences d'« invention » de SIFT+.
- L'Analogie : Imaginez que vous observez un livreur. Vous pouvez voir l'emplacement du livreur (la partie « entièrement observable »), mais vous ne pouvez pas voir les colis à l'intérieur du camion. Cependant, vous savez que le livreur ne peut transporter qu'un seul colis à la fois.
- SYNTH+ utilise l'emplacement visible pour déduire le colis invisible. Il se demande : « Si le livreur est à la porte et qu'il vient de "déposer" quelque chose, qu'est-ce qui devait être dans sa main ? »
La Touche : L'article introduit la « Observabilité Locale ». Cela signifie que vous n'avez pas besoin de voir le plateau entier. Vous avez seulement besoin de voir les parties pertinentes pour l'action en cours.
- Exemple : Si un robot se déplace « à Gauche », vous n'avez besoin de voir que la case à sa gauche. Vous n'avez pas besoin de voir la case de l'autre côté de la carte. Cela rend l'apprentissage beaucoup plus réaliste.

Le « Graphique de Dépendance » (La Carte Routière)

Pour s'assurer que ces détectives ne restent pas bloqués dans une boucle, les auteurs ont créé une carte appelée Graphique de Dépendance.

Considérez cela comme un organigramme. Pour apprendre la « Règle A », vous pourriez avoir besoin de connaître le « Fait B ». Pour apprendre le « Fait B », vous pourriez avoir besoin de la « Règle C ».
L'article prouve que tant que cet organigramme ne contient pas de boucle circulaire (où A a besoin de B, B a besoin de C, et C a besoin de A), l'algorithme peut apprendre les règles étape par étape, en partant des éléments visibles pour remonter vers ceux qui ne le sont pas.

Les Résultats : Est-ce que ça a marché ?

Les auteurs ont testé ces détectives sur des puzzles classiques comme Blocksworld (empiler des blocs), Delivery (déplacer des colis) et Sokoban (pousser des boîtes).

Le Test : Ils ont soumis aux algorithmes des traces où 50 % à 90 % des informations étaient cachées.
Le Résultat :
- SIFT+ a appris avec succès les règles à partir de listes d'actions seules, récupérant les détails manquants (comme « quel bloc est au sommet ») simplement en remarquant des modèles.
- SYNTH+ a appris les règles même lorsque le « plateau » était majoritairement caché, tant que les pièces critiques (comme l'emplacement de l'agent) étaient visibles.
- Dans presque tous les tests, les algorithmes ont atteint une précision de 100 %, reconstruisant correctement les manuels de règles cachés.

Résumé

Cet article traite de l'enseignement aux ordinateurs d'apprendre les « règles du jeu » lorsqu'ils disposent de très peu d'informations.

Ancienne méthode : « Voici le plateau, voici le coup. Apprenez les règles. » (Trop d'informations nécessaires).
Nouvelle méthode : « Voici une liste de coups. Vous pouvez voir l'emplacement du joueur, mais pas les objets. Déduisez les règles. »
La Percée : En utilisant un langage plus intelligent (STRIPS+) et une méthode astucieuse consistant à « inventer » des faits manquants basés sur ce qui doit être vrai (Mutex Features), l'IA peut combler les lacunes et apprendre la logique complète d'un domaine sans avoir besoin d'une vue complète du monde.

L'article affirme qu'il s'agit d'une étape majeure vers la création d'une IA capable d'apprendre à partir d'observations naturelles et imparfaites, similaire à la façon dont les humains apprennent en observant les autres, plutôt que de nécessiter un manuel parfait et riche en données.

Résumé technique : Apprentissage de modèles d'actions relevés à partir de traces avec un minimum d'informations

Énoncé du problème

Des travaux récents ont démontré que des modèles STRIPS relevés peuvent être appris efficacement à partir de traces d'actions seules (algorithme SIFT), et que des modèles STRIPS+ (qui autorisent des arguments d'action implicites) peuvent être appris à partir de traces état-action entièrement observables (algorithme SYNTH). Cependant, ces approches rencontrent des limitations pratiques :

SIFT nécessite des traces d'actions STRIPS complètes où les arguments sont explicites, ce qui inclut souvent des paramètres inutiles non requis pour la sélection d'actions (par exemple, dans les puzzles à tuiles coulissantes, la position actuelle d'une tuile doit être transmise explicitement même si l'action est « déplacer vers la gauche »).
SYNTH suppose l'observabilité complète de tous les prédicats d'état, ce qui est irréaliste pour des agents opérant dans des environnements partiellement observables.

Cet article aborde le problème de l'apprentissage de domaines d'actions STRIPS+ à partir de traces où les arguments d'action et les informations d'état sont partiellement observables. Plus précisément, les auteurs examinent les conditions dans lesquelles un domaine équivalent peut être appris lorsque les traces comportent un minimum d'informations : certains arguments d'action sont omis, et les prédicats d'état sont soit totalement inobservables, soit totalement observables, soit seulement localement observables (observables uniquement pour les objets pertinents pour l'état actuel).

Méthodologie

La solution proposée, SYNTH+, est un algorithme unifié qui étend et combine les capacités de SIFT et de SYNTH. Il opère sur des traces étendues (séquences d'actions et d'observations partielles d'état) et repose sur deux mécanismes fondamentaux :

1. Caractéristiques Mutex (Extension de SIFT)

Pour gérer les arguments d'action manquants sans observabilité d'état, les auteurs introduisent des caractéristiques mutex.

Concept : Une caractéristique mutex $f = \langle k, A, D \rangle$ représente un prédicat d'arité $k$ où le $k$ -ième argument est implicitement déterminé par les $k-1$ premiers arguments.
Mécanisme : Contrairement aux caractéristiques standards où les motifs d'ajout et de suppression ont la même arité, les caractéristiques mutex permettent aux motifs de suppression d'avoir une arité de $k-1$ . Cela capture la contrainte qu'une action (par exemple, drop()) supprime un prédicat (par exemple, holding(o)) en fonction de l'objet actuellement tenu, sans nommer explicitement cet objet dans la trace d'action.
Cohérence : Une caractéristique mutex est cohérente si, à travers le graphe de traces, chaque atome ground $f(o)$ reçoit une seule valeur de vérité, et pour deux atomes vrais $f(o)$ et $f(o')$ dans le même état, si les derniers arguments diffèrent ( $o_k \neq o'_k$ ), alors au moins un argument précédent doit également différer ( $o_i \neq o'_i$ pour un certain $i < k$ ).

2. Synthèse de requêtes et intégration (Extension de SYNTH)

SYNTH+ intègre l'« invention » de prédicats (via SIFT) avec l'inférence d'arguments implicites (via SYNTH) dans une boucle itérative :

Entrée : Un graphe étiqueté de traces étendues et un ensemble de prédicats entièrement observables $P_\omega$ .
Itération :
- Étape SIFT+ : Utilise des motifs d'actions sur les arguments explicites et les arguments implicites actuellement connus pour inventer de nouvelles caractéristiques mutex et caractéristiques simples. Ces caractéristiques représentent de nouveaux prédicats et leurs effets.
- Étape SYNTH : Utilise les prédicats nouvellement inventés (et tout prédicat observable) pour définir des requêtes (sous-requêtes $Q_i$ ) qui lient les variables implicites ( $z_i$ ) à des objets uniques dans l'état.
- Mise à jour : Le graphe est mis à jour avec les nouveaux arguments implicites et leurs requêtes définissantes.
Terminaison : Le processus se poursuit jusqu'à l'atteinte d'un point fixe ou au dépassement d'une borne de profondeur maximale ( $d_{max}$ ).

3. Observabilité locale

Le cadre est étendu à LOCAL SYNTH+, qui gère l'observabilité locale. Dans ce contexte, un prédicat est observable uniquement pour les objets « locaux » (ceux apparaissant comme arguments dans l'action actuelle). L'algorithme modifie le procédure de test de cohérence (TEST*) pour supposer que les atomes non locaux sont faux lors du test des préconditions, garantissant ainsi que les parties non observées de l'état n'invalident pas l'apprentissage des arguments implicites.

Contributions clés

Algorithme SYNTH+ : Un algorithme général pour l'apprentissage de domaines STRIPS+ à partir de traces avec une observabilité partielle des actions et des états. Il unifie l'invention de prédicats de SIFT avec la résolution d'arguments implicites de SYNTH.
Caractéristiques Mutex : Un formalisme novateur permettant l'apprentissage de prédicats où le dernier argument dépend fonctionnellement des autres, permettant la récupération d'arguments d'action omis sans observation complète de l'état.
Résultats de complétude : Des conditions théoriques sont établies pour déterminer quand les algorithmes sont complets :
- SIFT+ (Sans observabilité d'état) : Nécessite que le domaine STRIPS+ caché soit bien formé, fortement connexe et acyclique dans son graphe de dépendance (où les nœuds sont des prédicats et des variables implicites).
- SYNTH+ (Observabilité partielle de l'état) : Nécessite que le graphe de dépendance restreint aux prédicats non observables soit acyclique.
- LOCAL SYNTH+ : Prouvé complet sous observabilité locale pour les prédicats clés (prédicats dans les préconditions n'impliquant que des arguments implicites) s'ils sont entièrement observables, et si les autres prédicats sont localement observables.
Généralisation : Le travail démontre que SIFT et SYNTH sont des cas particuliers de SYNTH+ (où $P_\omega = \emptyset$ et $P_\omega = P$ , respectivement).

Résultats expérimentaux

Les auteurs ont évalué SIFT+ et SYNTH+ sur une suite de domaines de planification standards (par exemple, Blocks, Delivery, Grid, Sokoban, Logistics) en utilisant des traces étendues générées à partir de modèles STRIPS+ cachés.

Performance de SIFT+ : A appris avec succès des domaines corrects (taux de vérification de 100 %) à partir de traces d'actions seules sur tous les domaines testés, récupérant en moyenne 55 % des arguments d'action qui avaient été omis des traces.
Performance de SYNTH+ : A appris des domaines corrects en utilisant significativement moins de prédicats observables que SYNTH.
- Dans Delivery, SYNTH+ a appris le domaine en observant uniquement la position de l'agent (at(x)) et l'adjacence statique, alors que SYNTH nécessitait tous les prédicats fluents.
- Dans Sokoban et Logistics*, SYNTH+ a appris des domaines avec uniquement des prédicats statiques observés, un scénario où ni SYNTH ni SIFT+ ne pouvaient réussir.
Efficacité : Les algorithmes ont fonctionné efficacement (de quelques secondes à quelques minutes) sur du matériel standard, s'adaptant à des domaines comportant des milliers d'étapes de traces.

Importance et affirmations

L'article affirme que SYNTH+ fournit une alternative pratique et relevée à l'apprentissage par renforcement basé sur des modèles en permettant l'apprentissage de modèles dynamiques à partir de traces « naturelles ». Ces traces nécessitent un minimum d'informations :

Elles n'ont pas besoin de lister chaque argument requis par un codage STRIPS formel (par exemple, la position actuelle d'un bloc étant déposé).
Elles ne nécessitent pas une observabilité complète de l'état ; une observabilité partielle ou locale de prédicats spécifiques est suffisante.

Les auteurs soulignent que leur approche comble le fossé entre l'apprentissage théorique de modèles (qui suppose souvent une observabilité complète) et l'application pratique (où les agents ont une perception limitée). En caractérisant les conditions exactes (acyclicité des graphes de dépendance) dans lesquelles l'apprentissage est possible, le travail établit un cadre rigoureux pour l'apprentissage de modèles d'actions relevés dans des contextes partiellement observables. Les résultats suggèrent que des domaines complexes peuvent être reconstruits à partir de traces qui ne transmettent que les informations nécessaires pour sélectionner des actions, plutôt que la description complète de l'état.