Partie 2 — Planification Classique

← Partie 1 — Fondations | ↑ Planification | Partie 3 — Avancée →

Cette partie est le cœur technique de la série : on y résout les problèmes modélisés en PDDL. Le cycle « décrire un problème (partie 1) → trouver un plan » se ferme ici avec un planificateur industriel, Fast Downward, et la théorie des heuristiques qui le rend efficace. On y voit qu’un plan n’est pas une prédiction mais une séquence d’actions justifiée par une structure de coût, et qu’une bonne heuristique fait la différence entre un solveur qui termine et un solveur qui explose.

Position dans la série

Étape Question
← 01-Foundation Comment modéliser un problème en PDDL ?
Partie 2 — Classique Comment résoudre ce problème de façon (sous-)optimale ?
03-Advanced → Que faire quand l’espace d’états est trop grand pour Fast Downward ?

Le fil conducteur : le notebook 3 (partie 1) a montré que la recherche aveugle explose ; cette partie introduit les deux réponses classiques — un planificateur de référence (Fast Downward) et des heuristiques admissibles (A*, LM-cut) qui guident la recherche vers le but.

Notebooks

# Notebook Durée Contenu
4 Planners-4-Fast-Downward 45 min Architecture 3 étapes (translator PDDL→SAS+, preprocessor, search) ; A*, GBFS, EHC via Docker sur Blocks World et Logistics
4 (C#) Planners-4-Fast-Downward-Csharp 45 min Jumeau C# du 4 : planificateur SAS+ from-scratch (prevail/pre/eff), A*/GBFS/EHC, hmax/hFF par RPG, domaines Ferry + Logistics — sans Docker (See #4956)
5 Planners-5-Heuristics 40 min Classification admissible/non-admissible (\(h^{add}\), \(h^{max}\), \(h^{FF}\), LM-cut) ; comparaison expérimentale du nombre de nœuds expansés
5 (C#) Planners-5-Heuristics-Csharp 40 min Jumeau C# du 5 : h-max/h-add/h-FF/landmarks from-scratch, démo de non-admissibilité de h^add (See #4956)
5b Planners-5b-Lean-Relaxation 45 min Companion natif kernel Lean 4 : preuve formelle 0-sorry de \(h^{+} \leq h^{*}\) dans le lake planning_lean
5c Planners-5c-Differentiel-Atteignabilite 45 min Différentiel d’atteignabilité (strate 7) : protocole 4 pas — inatteignabilité prouvée, contrôle d’effort, primitive nommée et payante, delta mesuré ; consomme les théorèmes du lake planning_lean ; stdlib pur, sans Docker
6 Planners-6-Domains 50 min Domaines IPC standards (Blocks World, Logistics, Gripper, Ferry, Hanoï) de complexité croissante
6 (C#) Planners-6-Domains-Csharp 45 min Jumeau C# du 6 : planificateur STRIPS from-scratch (modèle Atom/Action/State, BFS forward + anti-cycle), domaines Block World + Hanoï + Gripper (See #4956)

Prérequis

  • Partie 1 maîtrisée : modélisation PDDL, espace d’états (notebooks 1-3)
  • Docker : les notebooks 4-6 appellent le serveur HTTP Fast Downward (jsboige/coursia-fast-downward, port 8200) — les notebooks 5b et 5c n’en dépendent pas (5b : kernel Lean via WSL ; 5c : stdlib pur) ; les jumeaux C# (4-6) non plus (.NET 9 from-scratch)
  • Algorithmique : A*, recherche heuristique dans les graphes

Si Docker n’est pas disponible, les notebooks théoriques (explication de l’architecture, classification des heuristiques) restent accessibles ; seules les exécutions de planification en ligne seront sautées.

À l’issue de cette partie

Vous saurez :

  1. Configurer un planificateur optimal (Fast Downward via Docker + unified-planning)
  2. Choisir l’heuristique adéquate (LM-cut pour l’optimalité, h-FF pour la vitesse)
  3. Modéliser n’importe quel domaine IPC classique en PDDL
  4. Distinguer heuristiques admissibles (garantie d’optimalité) et non-admissibles (rapidité)
  5. Mesurer ce qu’une nouvelle primitive rend possible — différentiel d’atteignabilité vs approfondissement de recherche (notebook 5c)

Pour continuer

La limite que cette partie révèle — l’explosion combinatoire sur les grands domaines — est précisément ce que la partie 3 contourne en changeant de paradigme (contraintes, temporel, hiérarchie).

Retour au sommet