Planification : STRIPS, monde des blocs, heuristiques par relaxation et planification dans les agents IA

Le langage STRIPS et PDDL, la planification en avant et en arrière, les heuristiques hmax et hadd, l’anomalie de Sussman, la planification hiérarchique et la replanification — du robot Shakey aux agents IA qui écrivent leur propre liste de tâches.

14 minutes Matěj Žalmánek 2026-10-15

Série Bases de l’IA Partie 25 sur 52

1. Carte de l’intelligence artificielle : qu’est-ce qui est quoi et comment tout s’emboîte
2. Brève histoire de l’intelligence artificielle : de Turing aux modèles de langage
3. Données, modèle, entraînement, inférence : les notions de base sur un seul exemple
4. Lire la notation mathématique : symboles, indices, sommes et quantificateurs
5. Ensembles et relations : les briques dont sont faites les définitions en IA
6. Fonctions et applications : pourquoi tout modèle d’IA est une fonction
7. Logique et démonstrations : les règles selon lesquelles on raisonne en IA
8. Graphes et arbres : la structure sur laquelle reposent la recherche et les réseaux de neurones
9. Algèbre linéaire pour l’apprentissage automatique : vecteurs, matrices et pourquoi l’IA multiplie surtout
10. Dérivées, gradient et règle de dérivation en chaîne : comment un modèle sait dans quelle direction apprendre
11. Descente de gradient : comment un modèle apprend
12. Qu’est-ce que la probabilité : du lancer de dé aux axiomes de Kolmogorov
13. Probabilité conditionnelle et théorème de Bayes : comment réviser une estimation quand on apprend du nouveau
14. Variable aléatoire et fonction de répartition : une seule fonction qui dit tout de la loi
15. Fonction de densité et fonction de masse : pourquoi une variable continue a une probabilité nulle en chaque point
16. Espérance, variance et covariance : où se situe une loi, quelle est sa largeur et ce qui varie avec quoi
17. Panorama des lois de probabilité : Bernoulli, binomiale, Poisson, uniforme, normale et exponentielle
18. Loi des grands nombres et théorème central limite : pourquoi les moyennes sont si prévisibles
19. Statistique et estimation de paramètres : maximum de vraisemblance, MAP et intervalles de confiance
20. Théorie de l’information : entropie, entropie croisée et divergence KL — d’où viennent les fonctions de perte
21. Recherche dans l’espace d’états : BFS, DFS, UCS et A* en animations
22. Jeux et adversaires : minimax, élagage alpha-bêta et Monte Carlo tree search
23. Satisfaction de contraintes : backtracking, propagation de contraintes et AC-3 sur un sudoku et une carte des régions tchèques
24. Logique et systèmes à base de connaissances : chaînage avant et arrière, résolution et systèmes experts
25. Planification : STRIPS, monde des blocs, heuristiques par relaxation et planification dans les agents IA
26. Recherche locale et recuit simulé : un voyageur de commerce à travers les chefs-lieux de région tchèques
27. Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée
28. Stratégies d’évolution et programmation génétique : de la règle du cinquième à la loi de Kepler
29. Optimisation par colonies de fourmis : comment une piste de phéromone trouve un chemin court
30. Optimisation par essaim de particules : inertie, expérience propre et expérience de l’essaim
31. Neuroévolution : faire évoluer les poids et la forme des réseaux de neurones, et l’algorithme NEAT
32. Ensembles flous et fonctions d’appartenance : comment écrire « un peu chaud »
33. Logique floue et probabilité : pourquoi « un peu chaud » ne veut pas dire « probablement chaud »
34. Logique floue : t-normes, implications et règles SI–ALORS
35. Commande floue : Mamdani et Sugeno, du ventilateur au pendule inversé sur un chariot
36. Clustering flou : l’algorithme fuzzy c-means et les points entre les clusters
37. Systèmes neuro-flous (ANFIS) : des règles floues qui apprennent à partir des données
38. Chaînes de Markov : matrice de transition, distribution stationnaire et PageRank
39. Modèles de Markov cachés : l’algorithme de Viterbi et le casino malhonnête
40. Réseaux bayésiens : pourquoi l’herbe est mouillée et ce que cela implique pour l’arroseur
41. Le filtre de Kalman : comment estimer, à partir de mesures imprécises, où se trouve une voiture et à quelle vitesse elle roule
42. Types d’apprentissage automatique : supervisé, non supervisé, semi-supervisé et plus
43. Prompts, contexte et RAG : comment donner au modèle les bonnes informations
44. Autoencodeurs variationnels (VAE) : de nouvelles images à partir d’un espace latent continu
45. Réseaux antagonistes génératifs (GAN) : le faussaire contre le détective
46. Modèles de diffusion : comment une image naît du bruit pur
47. Processus de décision markoviens : états, actions, récompenses et équations de Bellman
48. Q-learning et DQN : apprendre la valeur des actions, du tableau au réseau de neurones
49. Policy gradient et PPO : apprendre directement la politique
50. Comment fonctionne un agent IA : un modèle de langage en boucle avec des outils
51. Programmer avec des agents IA : consigne, tests et vérification
52. Évaluation et sécurité des systèmes d’IA : comment mesurer et comment surveiller

Programme complet de la série 52 sur 83 sujets publiés

À la fin des années soixante, le robot Shakey du Stanford Research Institute circulait dans quelques pièces, poussait des caisses et éteignait la lumière. C’était le premier robot à raisonner sur ses propres actes : il recevait un but (« amène la caisse dans la pièce voisine ») et trouvait lui-même quelles actions y mènent, et dans quel ordre. Le langage dans lequel il le faisait s’appelle STRIPS — et on retrouve aujourd’hui ses idées dans la logistique, dans les jeux vidéo et dans la boucle de l’agent IA qui écrit du code pour vous.

Cette partie fait suite à Recherche dans l’espace d’états et à Logique et systèmes à base de connaissances.

1. La planification : une recherche qui voit à l’intérieur

Planifier, c’est chercher une suite d’actions qui mène au but — exactement comme dans la partie sur la recherche. La différence tient à la manière dont le problème est écrit. Dans le labyrinthe, l’état était une boîte noire et l’algorithme en savait seulement où menaient les actions. Le planificateur voit à l’intérieur : l’état est une liste de faits sur le monde, et l’action dit de quels faits elle a besoin et lesquels elle change. Grâce à cela, le planificateur sait déduire lui-même une estimation de la distance au but — vous n’avez aucune heuristique à écrire à la main.

2. Le langage STRIPS

Définition — problème de planification STRIPS

On se donne un ensemble fini d’atomes F (des propositions sur le monde). Un état est un sous-ensemble s ⊆ F — les atomes qui y sont vrais ; ce qui n’est pas dans s est faux.

Une action a est un triplet (pre(a), add(a), del(a)) de sous-ensembles de F : les préconditions, les atomes ajoutés et les atomes supprimés. L’action est applicable dans s si pre(a) ⊆ s, et l’état résultant est

T(s, a) = (s ∖ del(a)) ∪ add(a)

T(s, a)

l’état après l’exécution de l’action — la fonction de transition que, dans la partie sur la recherche, fournissait le programmeur ; ici, le planificateur la déduit lui-même de la description de l’action

s

l’état de départ : tout ce que l’action ne mentionne pas passe tel quel dans le nouvel état (l’hypothèse de STRIPS qui règle le problème du cadre — inutile d’énumérer ce qui ne change pas)

del(a)

les atomes que l’action rend faux ; ils sont retirés par la différence ensembliste ∖

add(a)

les atomes que l’action établit ; ils sont ajoutés par l’union seulement après la suppression, si bien qu’un atome présent dans les deux listes est vrai au bout du compte

Un problème est un quadruplet (F, A, s₀, G), où G ⊆ F est le but. Un plan est une suite d’actions a₁, …, a_k dont chacune est applicable dans l’état obtenu après les précédentes, et telle que dans le dernier état s_k on a G ⊆ s_k.

Exemple — une action pas à pas

Le bloc C est posé sur A, B est à côté. L’action sur la table(C, A) a pre = {sur(C, A), libre(C)}, add = {table(C), libre(A)}, del = {sur(C, A)} (la description complète des actions se trouve dans la section suivante).

s = {sur(C, A), table(A), table(B), libre(B), libre(C)}

pre ⊆ s ?   sur(C, A) ∈ s, libre(C) ∈ s → l’action est applicable

s ∖ del = {table(A), table(B), libre(B), libre(C)}

(s ∖ del) ∪ add = {table(A), table(B), table(C), libre(A), libre(B), libre(C)} — les trois blocs sont sur la table

STRIPS est né en 1971 (Fikes et Nilsson) précisément pour Shakey. Son successeur actuel est le langage PDDL, dans lequel on formule depuis 1998 les problèmes des compétitions internationales de planificateurs. Une action s’y écrit comme un schéma avec des variables :

(:action sur-table
  :parameters (?a ?b)
  :precondition (and (sur ?a ?b) (libre ?a))
  :effect (and (table ?a) (libre ?b) (not (sur ?a ?b))))

3. Le monde des blocs

Le problème d’essai classique de la planification : des blocs sont posés sur une table, certains les uns sur les autres. En une action, vous prenez un bloc sur lequel rien n’est posé et vous le posez sur la table ou sur un autre bloc libre. Il y a trois sortes d’atomes : sur(A, B) — A est posé sur B, table(A) et libre(A).

Les actions du monde des blocs

• sur la table(A, B) : pre = {sur(A, B), libre(A)}, add = {table(A), libre(B)}, del = {sur(A, B)}
• depuis la table(A, C) : pre = {table(A), libre(A), libre(C)}, add = {sur(A, C)}, del = {table(A), libre(C)}
• déplacer(A, B, C) : pre = {sur(A, B), libre(A), libre(C)}, add = {sur(A, C), libre(B)}, del = {sur(A, B), libre(C)}

Le planificateur commence par instancier le schéma à variables : il remplace les variables par toutes les combinaisons de blocs. Pour n blocs, il y a n(n − 1) actions « sur la table », autant de « depuis la table » et n(n − 1)(n − 2) déplacements, soit au total n²(n − 1). Pour trois blocs, cela fait 9 · 2 = 18 actions, pour six 36 · 5 = 180. Mais dans chaque état, seules quelques-unes sont applicables — les blocs sur lesquels rien n’est posé sont peu nombreux.

Ce monde a l’air d’un jouet, mais il grandit vite. Trois blocs peuvent être disposés de 13 façons, quatre de 73, cinq de 501 et six déjà de 4 051. D’où viennent ces nombres :

nombre d’états = ∑_k=1ⁿ n! · C(n − 1, k − 1) / k!

n!

on aligne tous les blocs en une seule rangée — chaque ordre est un candidat ; on en obtient les tours en la découpant

C(n − 1, k − 1)

on découpe la rangée en k tours non vides : on choisit k − 1 des n − 1 intervalles entre les blocs. L’ordre à l’intérieur d’une tour compte (A sur B n’est pas B sur A), c’est pourquoi on découpe un ordre et non un ensemble

k!

l’ordre des tours sur la table ne compte pas — deux tours côte à côte forment le même état, dans quelque ordre qu’on les énumère. Chaque état a donc été compté k! fois

Le planificateur les a comptés autrement — il a parcouru tous les états accessibles — et il a obtenu la même chose. Essayons deux problèmes. Dans le plus grand, deux tours A–B–C et D–E–F (notées de bas en haut) sont posées sur la table, et le but est une tour unique F–E–D–C–B–A :

4. Planification en avant

Définition — planification en avant (progression)

Une recherche dans l’espace d’états à partir de l’état s₀ : les successeurs de l’état s sont les états T(s, a) pour toutes les actions a applicables dans s. Test de but : G ⊆ s.

from collections import deque

def proved(stav, akce):
    return (stav - akce.odeber) | akce.pridej

def planuj(start, cil, akce):
    okraj, rodic = deque([start]), {start: None}
    while okraj:
        stav = okraj.popleft()
        if cil <= stav:                      # tous les atomes du but sont vrais
            return plan_z(rodic, stav)
        for a in akce:
            if a.predpoklady <= stav:
                dalsi = proved(stav, a)
                if dalsi not in rodic:
                    rodic[dalsi] = (stav, a)
                    okraj.append(dalsi)

Sur le problème de la tour, le parcours en largeur trouve le plan le plus court, de 6 actions, mais il développe pour cela 2 132 états — plus de la moitié des 4 051. C’est qu’il ne sait rien de la direction dans laquelle se trouve le but.

5. Heuristiques par relaxation

Dans la partie sur la recherche, nous avons inventé nous-mêmes l’heuristique pour le labyrinthe. Le planificateur sait la calculer à partir de la description des actions — en simplifiant le problème, en le résolvant et en prenant le coût de la solution simplifiée comme estimation.

Définition — relaxation sans suppressions

Le problème relâché s’obtient en posant del(a) = ∅ pour toutes les actions. Un atome qui est devenu vrai le reste alors pour toujours.

On estime récursivement le coût d’un atome p depuis l’état s dans le problème relâché : c(p) = 0 pour p ∈ s, sinon c(p) = le minimum, sur les actions a telles que p ∈ add(a), de la valeur 1 + c(pre(a)), où le coût d’un ensemble d’atomes est

• pour h_max, le maximum des coûts de ses atomes — l’heuristique est admissible,
• pour h_add, la somme des coûts de ses atomes — un guide plus précis, mais qui peut surestimer.

L’heuristique de l’état s est le coût de l’ensemble but G.

c(p) = min_{a : p ∈ add(a)} [ 1 + c(pre(a)) ]

c(p)

l’estimation du nombre d’actions nécessaires pour que l’atome p devienne vrai (0 pour les atomes déjà vrais)

min sur les actions avec p ∈ add(a)

plusieurs actions peuvent établir l’atome ; on choisit la moins chère, puisque le planificateur choisit lui-même son chemin

1

le coût de l’action elle-même, celle qui finit par ajouter p

c(pre(a))

le coût pour que l’action soit seulement applicable — satisfaire toutes ses préconditions. C’est ici que h_max et h_add diffèrent : le maximum suppose que les préconditions sont satisfaites « en même temps » et que leurs préparations se recouvrent, la somme que chacune demande un travail séparé

def ceny(stav, akce, agreguj):             # agreguj = max (hmax) ou sum (hadd)
    c = {p: 0 for p in stav}
    zmena = True
    while zmena:                             # répéter tant qu’un coût s’améliore
        zmena = False
        for a in akce:
            if all(p in c for p in a.predpoklady):
                nova = 1 + agreguj(c[p] for p in a.predpoklady)
                for p in a.pridej:           # a.odeber est ignoré — relaxation
                    if nova < c.get(p, float("inf")):
                        c[p], zmena = nova, True
    return c

def h(stav, cil, akce, agreguj):
    c = ceny(stav, akce, agreguj)
    return agreguj(c[g] for g in cil)        # but inaccessible : h = ∞

Exemple — h_max et h_add pour l’anomalie de Sussman

Départ : C est posé sur A, B est à côté ; but G = {sur(A, B), sur(B, C)} (nous analysons ce problème plus bas). Les coûts des atomes couche par couche :

coût 0 (vrais) : table(A), table(B), sur(C, A), libre(B), libre(C)

coût 1 : sur la table(C, A) → table(C), libre(A) ;   depuis la table(B, C) → sur(B, C) ;   déplacer(C, A, B) → sur(C, B)

coût 2 : depuis la table(A, B) requiert table(A), libre(A), libre(B), de coûts 0, 1, 0

   h_max : 1 + max(0, 1, 0) = 2,   h_add : 1 + (0 + 1 + 0) = 2 → sur(A, B) a le coût 2

h_max(s₀) = max(2, 1) = 2,   h_add(s₀) = 2 + 1 = 3,   réellement nécessaire : h* = 3

h_max sous-estime, car elle ne compte que le but le plus cher : sur(A, B) coûte deux actions, mais sur(B, C) en demande encore une troisième, propre à lui, et le maximum l’avale. La somme la compte et tombe ici juste. Sur le problème de la tour, l’effet est plus marqué : depuis le départ, h* = 6, h_max = 3, le nombre de buts non satisfaits vaut 5 et h_add = 15 — la somme compte la préparation commune (dégager les blocs) à nouveau pour chaque but et surestime le coût réel de deux fois et demie.

Théorème — h_max et le nombre de buts non satisfaits sont admissibles

L’admissibilité vue dans la partie sur la recherche : h(s) ≤ h*(s), où h*(s) est la longueur du plus court plan depuis s.

h_max. Prenons un plus court plan a₁, …, a_k du problème réel. C’est aussi un plan pour le problème relâché (sans suppressions, au moins les mêmes atomes sont vrais à chaque étape, donc les préconditions restent satisfaites). Par récurrence sur i : tout atome vrai après i actions a c_max ≤ i — soit il était déjà vrai avant, soit il a été ajouté par l’action a_i, dont les préconditions étaient vraies après i − 1 actions et ont donc un coût ≤ i − 1, de sorte que 1 + max ≤ i. Tous les atomes du but sont vrais après k actions, donc h_max(s) = max_{g ∈ G} c(g) ≤ k = h*(s).

Nombre de buts non satisfaits. Les buts du monde des blocs sont des atomes sur(·, ·), et chaque action ajoute au plus un tel atome. Pour satisfaire m buts manquants, il faut donc au moins m actions.

Pour h_add, la preuve échoue à la dernière étape : la somme des coûts peut dépasser k, car les mêmes actions du plan sont comptées pour plusieurs buts.

Trois heuristiques sur le problème de la tour, toutes avec l’algorithme A* :

L’heuristique admissible h_max trouve l’optimum et économise plus de 90 % du travail. Le nombre de buts non satisfaits est lui aussi admissible dans notre monde (chaque action ne pose qu’un seul bloc et satisfait donc au plus un but), et ici il fonctionne encore mieux. h_add développe le moins d’états, mais le paie : le plan a une étape de plus que nécessaire. Aucune heuristique ne gagne à tous les coups — et les vrais planificateurs comme FF ou Fast Downward disposent de tout un arsenal d’heuristiques qu’ils combinent.

Le fonctionnement d’A* avec h_max se voit le mieux sur un petit problème — l’anomalie de Sussman, que nous analysons deux sections plus loin. Chaque ligne est un état développé (tours de bas en haut) ; A* prend toujours l’état de plus petit f = g + h, où g est le nombre d’actions depuis le départ, et en cas d’égalité celui qui a été découvert en premier :

Le parcours en largeur développe sur ce même problème les 13 états, A* avec h_max seulement 5. À la troisième étape, il fait fausse route — il pose C sur B — parce que cet état a f = 3, tout comme le bon chemin, et a été découvert plus tôt. Dès l’étape suivante, il se rattrape. Le premier état but développé a le plus court plan — A* le garantit lorsque l’heuristique est admissible (et h_max est même cohérente, si bien qu’il n’a pas à revenir aux états fermés).

6. Planification en arrière

Définition — planification en arrière (régression)

Elle cherche à partir du but : l’état de la recherche est un ensemble d’atomes g qui doivent encore être vrais (au départ, g = G). Une action a est pertinente pour g si add(a) ∩ g ≠ ∅ et del(a) ∩ g = ∅. La régression du but par a est

g′ = (g ∖ add(a)) ∪ pre(a)

g′

ce qui doit être vrai avant l’action a pour que g soit vrai après elle — un nouveau sous-but, antérieur

g

le sous-but actuel ; les atomes que l’action ne mentionne pas doivent être vrais dès avant, car l’action ne les établit pas elle-même (et grâce à la condition de pertinence, elle ne les détruit pas non plus)

add(a)

on les retire, car ces atomes, l’action les établit elle-même — ils n’ont pas besoin d’être vrais avant

pre(a)

on les ajoute, car sans ses préconditions l’action ne peut pas être exécutée — elles deviennent de nouveaux sous-buts

La recherche s’arrête lorsque g′ ⊆ s₀ ; le plan est formé des actions trouvées, dans l’ordre inverse.

Exemple — régression du but de l’anomalie de Sussman

But g = {sur(A, B), sur(B, C)}, départ s₀ = {sur(C, A), table(A), table(B), libre(B), libre(C)}. On prend les actions en partant de la dernière :

depuis la table(A, B) : add = {sur(A, B)} touche g, del = {table(A), libre(B)} non → pertinente

   g′ = {sur(B, C)} ∪ {table(A), libre(A), libre(B)}

depuis la table(B, C) : add = {sur(B, C)}, del = {table(B), libre(C)} → pertinente

   g″ = {table(A), libre(A), libre(B)} ∪ {table(B), libre(B), libre(C)} = {table(A), table(B), libre(A), libre(B), libre(C)}

sur la table(C, A) : add = {table(C), libre(A)}, del = {sur(C, A)} → pertinente

   g‴ = {table(A), table(B), libre(B), libre(C)} ∪ {sur(C, A), libre(C)} = {sur(C, A), table(A), table(B), libre(B), libre(C)} ⊆ s₀ ✓

Le plan, lu à rebours : sur la table(C, A), depuis la table(B, C), depuis la table(A, B). Mais si nous avions essayé depuis la table(B, C) comme dernière action, nous aurions obtenu le sous-but {sur(A, B), table(B), libre(B), libre(C)} — A est posé sur B et B est en même temps libre. Un tel état n’existe pas, mais la régression ne s’en aperçoit pas d’elle-même ; les planificateurs en arrière ont donc besoin de règles supplémentaires qui détectent les combinaisons impossibles.

7. L’anomalie de Sussman

L’idée la plus simple pour planifier : découper le but en parties et les atteindre l’une après l’autre. Cela marche souvent — et échoue dès trois blocs. Le problème porte le nom de Gerald Sussman, qui l’a analysé dans les années soixante-dix : C est posé sur A, B est à côté, et le but est A sur B et en même temps B sur C.

Le plus court plan pour « A sur B » descend C et pose A sur B. Seulement, B se retrouve alors sous A, et mettre B sur C oblige à redescendre A. À la fin, seul le second but est atteint, et cela a coûté 4 étapes. L’ordre inverse se termine de la même façon : nous posons B sur C, mais nous enterrons ainsi A sous C et B — et le dégager détruit à nouveau le premier but. Les buts s’annulent mutuellement, quel que soit celui par lequel vous commencez.

La solution exige d’entrelacer les étapes des deux buts : d’abord dégager A (une étape pour le premier but), puis B sur C (le second but), et seulement ensuite A sur B (le premier but). Un planificateur qui cherche dans l’espace des états complets le trouve lui-même — il a parcouru ici les 13 états du monde à trois blocs. Un planificateur qui assemble des plans partiels doit savoir les démêler et les recombiner. C’est le sujet de toute la famille de la « planification dans l’espace des plans ».

8. Planification hiérarchique

Définition — HTN

Dans un réseau hiérarchique de tâches (HTN), il existe, outre les actions primitives, des tâches composées. Chaque tâche composée a une ou plusieurs méthodes — des suites de sous-tâches en lesquelles elle peut être décomposée. La planification part d’une seule tâche de plus haut niveau et la décompose jusqu’à ce qu’il ne reste que des actions primitives.

def rozloz(ukoly, stav):                   # ukoly : liste des tâches restantes
    if not ukoly:
        return []                            # tout est décomposé
    u, zbytek = ukoly[0], ukoly[1:]
    if u.primitivni:                         # action STRIPS ordinaire
        if not u.predpoklady <= stav:
            return None
        plan = rozloz(zbytek, proved(stav, u))
        return None if plan is None else [u] + plan
    for metoda in u.metody:                  # essayer les recettes une par une
        if metoda.podminka <= stav:
            plan = rozloz(metoda.podukoly + zbytek, stav)
            if plan is not None:
                return plan
    return None                              # aucune méthode n’a marché — retour arrière

On cherche ici dans l’espace des décompositions, et non des états : on ne se ramifie que selon la méthode choisie pour une tâche composée. Les tâches sont décomposées dans l’ordre où elles seront exécutées, si bien que le planificateur connaît toujours l’état courant — c’est ainsi que procède par exemple le planificateur SHOP2.

La planification hiérarchique s’emploie là où les experts ont des procédures éprouvées : dans la logistique, dans le pilotage de la production et beaucoup dans les jeux vidéo. Le jeu d’action F.E.A.R. (2005) s’est rendu célèbre par ses soldats qui planifiaient leur tactique en cours de partie dans un langage de type STRIPS — et les planificateurs de nombreux autres jeux partent de la même idée.

9. Planifier dans un monde incertain

STRIPS suppose que le monde est exactement tel que nous le croyons et que les actions se déroulent exactement comme décrit. Mais un vrai robot laisse tomber le bloc et un vrai serveur ne répond pas. Les réponses les plus courantes à cela sont au nombre de trois :

• Surveillance et replanification. Après chaque action, vérifier si le monde ressemble à ce que le plan attendait. Sinon, replanifier à partir de ce qui est. Simple et étonnamment efficace (la boucle est ci-dessous).
• Les plans conditionnels comportent des branchements : « si la porte s’ouvre, continue, sinon prends la seconde entrée ».
• Planification probabiliste. Quand une action a plusieurs résultats possibles avec des probabilités données, on ne cherche pas une suite d’actions, mais une stratégie pour chaque situation — les processus de décision markoviens ont leur propre partie dans le programme.

def proved_s_dohledem(cil, akce, svet):
    plan = planuj(svet.pozoruj(), cil, akce)
    while plan:
        a = plan.pop(0)
        cekany = proved(svet.pozoruj(), a)   # ce qui devrait être vrai selon le modèle
        svet.udelej(a)
        skutecny = svet.pozoruj()
        if cil <= skutecny:
            return True
        if skutecny != cekany:               # le monde s’est comporté autrement
            plan = planuj(skutecny, cil, akce)   # replanifier à partir de ce qui est
    return cil <= svet.pozoruj()

Il suffit d’ailleurs de surveiller ce dont dépend le reste du plan : si un atome qui n’est la précondition d’aucune action suivante ni une partie du but change, le plan reste valable. Cette économie a déjà été introduite par le système PLANEX, qui exécutait les plans de Shakey (Fikes, Hart et Nilsson, 1972).

10. La planification dans les agents IA

Un agent à base de modèle de langage qui corrige un bogue dans du code planifie, lui aussi : il décompose la tâche en une liste d’étapes, regarde le résultat après chaque étape (les tests passent-ils ? le fichier existe-t-il ?) et ajuste le plan en conséquence. C’est de la surveillance et de la replanification, sauf que les actions sont des commandes dans le terminal et que les préconditions et les effets ne sont écrits formellement nulle part — le modèle les devine à partir du texte.

C’est justement là le point faible. Les recherches sur des problèmes du monde des blocs (par exemple le jeu de tests PlanBench) ont montré que les modèles de langage se trompent souvent en planification classique, en particulier quand on renomme les blocs avec des mots dénués de sens, de sorte que le modèle ne peut pas puiser dans des exemples appris. Les modèles plus récents, qui raisonnent plus longuement, s’en sortent bien mieux, mais n’offrent aucune garantie d’exactitude. Ce qui fait ses preuves, c’est donc la division du travail : le modèle traduit le problème en PDDL ou propose un plan, et un planificateur classique ou un validateur le vérifie — chacun fait ce qu’il sait faire.

11. Résumé

• Planifier, c’est chercher une suite d’actions menant au but ; STRIPS décrit l’état comme un ensemble d’atomes et l’action par ses préconditions et ses atomes ajoutés et supprimés.
• La planification en avant est une recherche dans les états ; la planification en arrière fait régresser le but par des actions pertinentes.
• Le planificateur calcule lui-même son heuristique à partir du problème relâché sans suppressions : h_max est admissible, h_add plus rapide, mais elle peut mener à un plan plus long.
• L’anomalie de Sussman montre qu’on ne peut pas toujours atteindre les sous-buts l’un après l’autre — il faut entrelacer les étapes.
• La planification hiérarchique décompose les tâches selon des méthodes éprouvées ; dans un monde incertain, on surveille le plan et on replanifie — c’est exactement ce que font les agents IA d’aujourd’hui.

Envie d’essayer par vous-même ? Demandez à un agent IA d’écrire le monde des blocs en PDDL et de lancer dessus le planificateur libre Fast Downward — puis voyez combien de blocs le modèle parvient à gérer seul, sans lui.

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.