Planners-2-PDDL-Basics-Csharp

Navigation : Index | << Introduction C# | State Space C# >> |

Objectifs d’apprentissage

À la fin de ce notebook, vous saurez :

1. Modéliser un domaine de planification en C# selon le paradigme STRIPS (types, prédicats, actions avec préconditions et effets add/delete).
2. Représenter un problème (objets typés, état initial, but) et l’encoder comme un ensemble d’atomes groundés.
3. Implémenter le grounding — instancier les schémas d’action avec toutes les affectations d’objets compatibles avec les types.
4. Résoudre un problème PDDL par recherche BFS forward dans l’espace d’états, et retourner un plan.
5. Comprendre la mécanique interne qu’une bibliothèque comme unified-planning (côté Python) cache derrière un appel solve().

Parité .NET (#4956). Ce notebook est le jumeau C# de Planners-2-PDDL-Basics.ipynb. Le notebook Python définit les domaines PDDL en texte puis invoque la bibliothèque unified-planning qui grounde et solve. Ici, tout est déroulé à la main (.NET 9, 0 NuGet) : on construit le modèle STRIPS, on grounde les actions et on code la recherche. C’est la complémentarité axe-2 SOTA (#3801) : la lib utilitaire d’un côté, la compréhension des internes de l’autre.

---

1. Introduction : PDDL et le modèle STRIPS

PDDL (Planning Domain Definition Language) est le langage standard pour décrire des problèmes de planification automatique. Développé en 1998 pour la première compétition internationale de planification (IPC), il repose sur le modèle STRIPS (Stanford Research Institute Problem Solver, 1971) — la formalisation la plus simple et la plus répandue d’un problème de planification.

1.1 Le triptyque État–Action–But

Un problème de planification se décompose en trois éléments :

Élément	Question	Implémentation C#
État	Quels faits sont vrais maintenant ?	Un HashSet<string> d’atomes groundés (le monde fermé : ce qui n’est pas dans l’ensemble est faux)
Action	Comment passe-t-on d’un état à un autre ?	Un schéma avec précondition (atomes requis) et effets add/delete
But	Quel état veut-on atteindre ?	Une conjonction d’atomes ; un état but satisfait le but si tous les atomes du but y sont présents

Un plan est une séquence d’actions qui, exécutée depuis l’état initial, aboutit à un état qui satisfait le but.

1.2 STRIPS : la base de PDDL

Dans STRIPS, une action est définie par cinq composantes :

Composante	Description
Nom	Identifiant de l’action (ex. load, drive)
Paramètres	Liste de variables typées (ex. ?p - package ?v - vehicle ?l - location)
Précondition	Conjonction d’atomes qui doivent être vrais dans l’état courant
Effets add	Atomes qui deviennent vrais après l’action
Effets delete	Atomes qui deviennent faux après l’action

Hypothèse du monde fermé. L’état est un ensemble fini de faits vrais ; tout fait absent est considéré faux. Les effets delete retirent de l’ensemble, les effets add y ajoutent.

---

2. Modèle de domaine en C

Plutôt qu’écrire du PDDL textuel puis le faire parser, nous construisons le modèle directement en C#. C’est l’approche « API » — équivalente à unified-planning.shortcuts côté Python, sauf que toutes les classes sont les nôtres.

Nous définissons quatre classes :

• TypeDef — un type avec son parent (hiérarchie de types, ex. truck - vehicle - object).
• Domain — l’ensemble des types, prédicats et schémas d’action ; porte la fonction IsSubtype pour la compatibilité de typage.
• ActionSchema — nom, paramètres typés, et trois listes d’atomes (précondition, add, delete) où les arguments sont des noms de paramètres (variables).
• Problem — objets typés, état initial (HashSet<string>), but (liste d’atomes).

// Modèle de domaine STRIPS from-scratch (0 NuGet, BCL .NET 9)
using System;
using System.Collections.Generic;
using System.Linq;

// Type avec parent (hiérarchie : truck -> vehicle -> object)
public class TypeDef { public string Name; public string Parent; }

// Action : 5 composantes STRIPS. Les atomes référencent des noms de parametres (?p, ?v...).
public class ActionSchema {
    public string Name;
    public List<(string Name, string Type)> Params = new();
    public List<(string Pred, string[] Vars)> Pre = new();   // precondition (conjonction)
    public List<(string Pred, string[] Vars)> Add = new();   // effets add
    public List<(string Pred, string[] Vars)> Del = new();   // effets delete
}

// Domaine : types + actions. Porte la résolution de sous-typage.
public class Domain {
    public string Name;
    public Dictionary<string, TypeDef> Types = new();
    public List<ActionSchema> Actions = new();

    // a est-il un sous-type de b ? (truck <= vehicle <= object)
    public bool IsSubtype(string a, string b) {
        if (a == b) return true;
        string cur = a;
        while (Types.TryGetValue(cur, out var td)) {
            if (td.Name == b) return true;
            if (td.Parent == null) return false;
            cur = td.Parent;
        }
        return false;
    }
}

// Probleme : objets typés, etat initial, but
public class Problem {
    public string Name;
    public Domain Dom;
    public List<(string Name, string Type)> Objects = new();
    public HashSet<string> Init = new();
    public List<(string Pred, string[] Vars)> Goal = new();
}

// Atome canonique : "pred(arg1,arg2)" -> clé string pour HashSet
public static string Atom(string pred, params string[] args) =>
    pred + "(" + string.Join(",", args) + ")";

display("Modèle STRIPS défini : TypeDef, ActionSchema, Domain (avec IsSubtype), Problem, Atom.");
display("Domaine = types + actions ; Problème = objets + état initial (HashSet<string>) + but.");

The below script needs to be able to find the current output cell; this is an easy method to get it.

Modèle STRIPS défini : TypeDef, ActionSchema, Domain (avec IsSubtype), Problem, Atom.

Domaine = types + actions ; Problème = objets + état initial (HashSet<string>) + but.

---

3. Exemple complet : le domaine Logistics

Le domaine Logistics est un classique : un camion doit déplacer des colis entre des lieux. Trois actions suffisent : load (charger), unload (décharger), drive (déplacer le véhicule).

Types et hiérarchie

Le domaine introduit une hiérarchie de types : truck est un sous-type de vehicle. Quand une action attend un paramètre de type vehicle, un objet de type truck est acceptable — c’est ce que capture Domain.IsSubtype.

// Construction du domaine Logistics en C# (equivalent du fichier PDDL)
var logistics = new Domain { Name = "logistics-simple" };

// Types avec hiérarchie
logistics.Types["object"]  = new TypeDef { Name = "object",  Parent = null };
logistics.Types["location"]= new TypeDef { Name = "location", Parent = "object" };
logistics.Types["package"] = new TypeDef { Name = "package", Parent = "object" };
logistics.Types["vehicle"] = new TypeDef { Name = "vehicle", Parent = "object" };
logistics.Types["truck"]   = new TypeDef { Name = "truck",   Parent = "vehicle" };

// Action load(?p - package, ?v - vehicle, ?l - location)
logistics.Actions.Add(new ActionSchema {
    Name = "load",
    Params = { ("p","package"), ("v","vehicle"), ("l","location") },
    Pre  = { ("at-loc", new[]{"p","l"}), ("at-veh", new[]{"v","l"}), ("empty", new[]{"v"}) },
    Add  = { ("in", new[]{"p","v"}) },
    Del  = { ("at-loc", new[]{"p","l"}), ("empty", new[]{"v"}) }
});

// Action unload(?p - package, ?v - vehicle, ?l - location)
logistics.Actions.Add(new ActionSchema {
    Name = "unload",
    Params = { ("p","package"), ("v","vehicle"), ("l","location") },
    Pre  = { ("in", new[]{"p","v"}), ("at-veh", new[]{"v","l"}) },
    Add  = { ("at-loc", new[]{"p","l"}), ("empty", new[]{"v"}) },
    Del  = { ("in", new[]{"p","v"}) }
});

// Action drive(?v - vehicle, ?from - location, ?to - location)
logistics.Actions.Add(new ActionSchema {
    Name = "drive",
    Params = { ("v","vehicle"), ("from","location"), ("to","location") },
    Pre  = { ("at-veh", new[]{"v","from"}) },
    Add  = { ("at-veh", new[]{"v","to"}) },
    Del  = { ("at-veh", new[]{"v","from"}) }
});

var sb = new System.Text.StringBuilder();
sb.AppendLine($"Domaine défini : {logistics.Name}");
sb.AppendLine($"Types ({logistics.Types.Count}) : " +
              string.Join(", ", logistics.Types.Values.Select(t =>
                  t.Parent == null ? t.Name : $"{t.Name} - {t.Parent}")));
sb.AppendLine($"Actions ({logistics.Actions.Count}) :");
foreach (var a in logistics.Actions) {
    var parms = string.Join(", ", a.Params.Select(pr => $"?{pr.Name} - {pr.Type}"));
    sb.AppendLine($"  - {a.Name}({parms})");
    sb.AppendLine($"      pre : {string.Join(", ", a.Pre.Select(p => Atom(p.Pred, p.Vars)))}");
    sb.AppendLine($"      add : {string.Join(", ", a.Add.Select(p => Atom(p.Pred, p.Vars)))}");
    sb.AppendLine($"      del : {string.Join(", ", a.Del.Select(p => Atom(p.Pred, p.Vars)))}");
}
// Vérification du sous-typage
sb.AppendLine();
sb.AppendLine($"IsSubtype(truck, vehicle)   = {logistics.IsSubtype("truck","vehicle")}  (attendu : True)");
sb.AppendLine($"IsSubtype(truck, object)    = {logistics.IsSubtype("truck","object")}   (attendu : True)");
sb.AppendLine($"IsSubtype(package, vehicle) = {logistics.IsSubtype("package","vehicle")} (attendu : False)");
display(sb.ToString());

Domaine défini : logistics-simple
Types (5) : object, location - object, package - object, vehicle - object, truck - vehicle
Actions (3) :
  - load(?p - package, ?v - vehicle, ?l - location)
      pre : at-loc(p,l), at-veh(v,l), empty(v)
      add : in(p,v)
      del : at-loc(p,l), empty(v)
  - unload(?p - package, ?v - vehicle, ?l - location)
      pre : in(p,v), at-veh(v,l)
      add : at-loc(p,l), empty(v)
      del : in(p,v)
  - drive(?v - vehicle, ?from - location, ?to - location)
      pre : at-veh(v,from)
      add : at-veh(v,to)
      del : at-veh(v,from)

IsSubtype(truck, vehicle)   = True  (attendu : True)
IsSubtype(truck, object)    = True   (attendu : True)
IsSubtype(package, vehicle) = False (attendu : False)

Interprétation : domaine Logistics

Le domaine est défini avec 3 actions et 5 types (dont la hiérarchie truck - vehicle - object).

Action	Précondition	Effets add	Effets delete
load(p,v,l)	at-loc(p,l), at-veh(v,l), empty(v)	in(p,v)	at-loc(p,l), empty(v)
unload(p,v,l)	in(p,v), at-veh(v,l)	at-loc(p,l), empty(v)	in(p,v)
drive(v,from,to)	at-veh(v,from)	at-veh(v,to)	at-veh(v,from)

La contrainte empty(v) dans la précondition de load impose qu’un véhicule ne peut transporter qu’un seul colis à la fois — il faudra donc déposer box1 avant de charger box2. Cette contrainte structure le plan que BFS trouvera plus bas.

---

4. Le problème : objets, état initial, but

Un problème instancie le domaine avec des objets concrets. Il fixe :

• les objets avec leur type (ex. truck1 - truck) ;
• l’état initial — les atomes vrais au départ (hypothèse du monde fermé) ;
• le but — une conjonction d’atomes à atteindre.

4.1 Problème Logistics

Deux colis (box1, box2) sont au depot avec un camion truck1 vide. Le but : livrer box1 au store et box2 au warehouse.

// Construction du problème Logistics
var pLog = new Problem { Name = "logistics-simple-1", Dom = logistics };

// Objets typés
pLog.Objects.AddRange(new[] {
    ("depot","location"), ("warehouse","location"), ("store","location"),
    ("box1","package"), ("box2","package"),
    ("truck1","truck")
});

// État initial (hypothese du monde fermé : seuls ces faits sont vrais)
pLog.Init.UnionWith(new[] {
    Atom("at-loc","box1","depot"),
    Atom("at-loc","box2","depot"),
    Atom("at-veh","truck1","depot"),
    Atom("empty","truck1")
});

// But : conjonction d'atomes
pLog.Goal.AddRange(new[] {
    ("at-loc", new[]{"box1","store"}),
    ("at-loc", new[]{"box2","warehouse"})
});

var sb = new System.Text.StringBuilder();
sb.AppendLine($"Problème défini : {pLog.Name}");
sb.AppendLine($"Objets ({pLog.Objects.Count}) :");
foreach (var (n,t) in pLog.Objects)
    sb.AppendLine($"  - {n} : {t}");
sb.AppendLine();
sb.AppendLine("État initial :");
foreach (var f in pLog.Init) sb.AppendLine($"  {f}");
sb.AppendLine();
sb.AppendLine("But :");
foreach (var g in pLog.Goal) sb.AppendLine($"  {Atom(g.Pred, g.Vars)}");
display(sb.ToString());

Problème défini : logistics-simple-1
Objets (6) :
  - depot : location
  - warehouse : location
  - store : location
  - box1 : package
  - box2 : package
  - truck1 : truck

État initial :
  at-loc(box1,depot)
  at-loc(box2,depot)
  at-veh(truck1,depot)
  empty(truck1)

But :
  at-loc(box1,store)
  at-loc(box2,warehouse)

Visualisation du problème

Objet	Type	État initial	But
box1	package	depot	store
box2	package	depot	warehouse
truck1	truck	depot (vide)	—

Une solution possible : charger box1, rouler vers store, déposer, revenir au depot, charger box2, rouler vers warehouse, déposer. Soit 7 actions. La question est : est-ce le plan le plus court ? C’est exactement ce qu’une recherche BFS (en largeur) dans l’espace d’états garantit de trouver.

Pour cela, il faut d’abord grounder les actions (les instancier sur tous les objets valides), puis explorer.

---

5. Le cœur du planificateur : grounding + recherche BFS

C’est ici que réside tout l’intérêt du jumeau C# : la bibliothèque unified-planning (côté Python) fait ces deux étapes automatiquement quand on appelle solve(). Nous allons les dérouler à la main.

5.1 Grounding

Un schéma d’action (ex. load(?p,?v,?l)) est abstrait : ses paramètres sont des variables. Le grounding consiste à générer toutes les instances concètes en remplaçant les variables par des objets compatibles avec le type. Pour load(?p - package, ?v - vehicle, ?l - location) avec 2 colis, 1 camion (truck1 est un vehicle par hiérarchie) et 3 lieux : \(2 \times 1 \times 3 = 6\) actions groundées.

Chaque action groundée a alors une précondition concrète (atomes instanciés) et des effets add/delete concrets — on peut tester en un IsSubsetOf si elle est applicable.

5.2 Recherche BFS forward

Une fois les actions groundées, on explore l’espace d’états en largeur depuis l’état initial :

1. File de priorité FIFO initialisée avec l’état initial.
2. Pour chaque état extrait : pour chaque action groundée applicable (précondition ⊆ état), calculer l’état successeur (appliquer add/delete).
3. Si le successeur satisfait le but → reconstruire le plan et le retourner.
4. Sinon, l’ajouter à la file (s’il n’a pas déjà été visité).

BFS garantit de trouver un plan de longueur minimale (en nombre d’actions).

// === Grounding + BFS forward search : les deux briques que unified-planning cache ===
using System.Collections.Generic;
using System.Linq;

// Action groundée (concrète) : précondition + add/delete sont des atomes instanciés
public class GroundedAction {
    public string Name;
    public string[] Args;
    public HashSet<string> Pre;
    public List<string> Add;
    public List<string> Del;
    public string Label => $"{Name}({string.Join(",", Args)})";
}

public static class Planner {
    // Grounding : instancier chaque schéma sur tous les objets type-compatibles
    public static List<GroundedAction> Ground(Domain d, Problem p) {
        // Index des objets par type (un objet apparaît sous son type ET tous ses supertypes)
        var byType = new Dictionary<string, List<string>>();
        foreach (var (oName, oType) in p.Objects) {
            string cur = oType;
            while (cur != null) {
                if (!byType.ContainsKey(cur)) byType[cur] = new List<string>();
                byType[cur].Add(oName);
                cur = d.Types.TryGetValue(cur, out var td) ? td.Parent : null;
            }
        }
        var result = new List<GroundedAction>();
        foreach (var a in d.Actions) {
            // Domaines de chaque paramètre = objets type-compatibles
            var domains = a.Params.Select(pr =>
                byType.TryGetValue(pr.Type, out var lst) ? lst : new List<string>()).ToList();
            // Énumération du produit cartésien (récursif)
            var combos = new List<List<string>>();
            void Rec(int i, List<string> cur) {
                if (i == domains.Count) { combos.Add(cur.ToList()); return; }
                foreach (var v in domains[i]) { cur.Add(v); Rec(i + 1, cur); cur.RemoveAt(cur.Count - 1); }
            }
            Rec(0, new List<string>());
            foreach (var combo in combos) {
                var sub = new Dictionary<string, string>();
                for (int k = 0; k < a.Params.Count; k++) sub[a.Params[k].Name] = combo[k];
                string Inst((string Pred, string[] Vars) at) =>
                    Atom(at.Pred, at.Vars.Select(v => sub[v]).ToArray());
                result.Add(new GroundedAction {
                    Name = a.Name,
                    Args = combo.ToArray(),
                    Pre = new HashSet<string>(a.Pre.Select(Inst)),
                    Add = a.Add.Select(Inst).ToList(),
                    Del = a.Del.Select(Inst).ToList()
                });
            }
        }
        return result;
    }

    // BFS forward : retourne un plan de longueur minimale, ou null si introuvable
    public static List<string> Solve(Problem p, List<GroundedAction> grounded, int maxExpand = 200000) {
        var goalAtoms = new HashSet<string>(p.Goal.Select(g => Atom(g.Pred, g.Vars)));
        string Key(HashSet<string> s) => string.Join(";", s.OrderBy(x => x));
        var start = new HashSet<string>(p.Init);
        if (goalAtoms.IsSubsetOf(start)) return new List<string>();
        var visited = new HashSet<string> { Key(start) };
        var queue = new Queue<(HashSet<string> state, List<string> plan)>();
        queue.Enqueue((start, new List<string>()));
        int expanded = 0;
        while (queue.Count > 0) {
            var (state, plan) = queue.Dequeue();
            if (++expanded > maxExpand) break;
            foreach (var ga in grounded) {
                if (!ga.Pre.IsSubsetOf(state)) continue;
                var next = new HashSet<string>(state);
                foreach (var del in ga.Del) next.Remove(del);
                foreach (var add in ga.Add) next.Add(add);
                var np = new List<string>(plan) { ga.Label };
                if (goalAtoms.IsSubsetOf(next)) return np;
                var key = Key(next);
                if (visited.Add(key)) queue.Enqueue((next, np));
            }
        }
        return null;
    }
}

var grounded = Planner.Ground(logistics, pLog);
var sb = new System.Text.StringBuilder();
sb.AppendLine($"Grounding Logistics : {grounded.Count} actions groundées au total");
var byName = grounded.GroupBy(g => g.Name);
foreach (var g in byName)
    sb.AppendLine($"  - {g.Key} : {g.Count()} instances");
sb.AppendLine();
sb.AppendLine($"Exemples d'actions groundées applicables depuis l'état initial :");
foreach (var ga in grounded.Where(g => g.Pre.IsSubsetOf(pLog.Init)).Take(8))
    sb.AppendLine($"  {ga.Label}  pre=[{string.Join(", ", ga.Pre)}]");
display(sb.ToString());

Grounding Logistics : 21 actions groundées au total
  - load : 6 instances
  - unload : 6 instances
  - drive : 9 instances

Exemples d'actions groundées applicables depuis l'état initial :
  load(box1,truck1,depot)  pre=[at-loc(box1,depot), at-veh(truck1,depot), empty(truck1)]
  load(box2,truck1,depot)  pre=[at-loc(box2,depot), at-veh(truck1,depot), empty(truck1)]
  drive(truck1,depot,depot)  pre=[at-veh(truck1,depot)]
  drive(truck1,depot,warehouse)  pre=[at-veh(truck1,depot)]
  drive(truck1,depot,store)  pre=[at-veh(truck1,depot)]

// Résolution : BFS trouve le plan le plus court
var watch = System.Diagnostics.Stopwatch.StartNew();
var plan = Planner.Solve(pLog, grounded);
watch.Stop();

var sb = new System.Text.StringBuilder();
if (plan == null) {
    sb.AppendLine("Aucun plan trouvé (le but n'est pas atteignable).");
} else {
    sb.AppendLine($"Plan trouvé : {plan.Count} actions (BFS = longueur minimale)");
    sb.AppendLine($"Temps : {watch.Elapsed.TotalMilliseconds:F2} ms");
    sb.AppendLine();
    // Simuler l'execution pour montrer l'état après chaque pas
    var st = new HashSet<string>(pLog.Init);
    for (int i = 0; i < plan.Count; i++) {
        var ga = grounded.First(g => g.Label == plan[i]);
        foreach (var del in ga.Del) st.Remove(del);
        foreach (var add in ga.Add) st.Add(add);
        sb.AppendLine($"  {i+1}. {plan[i]}");
    }
    sb.AppendLine();
    var goalAtoms = new HashSet<string>(pLog.Goal.Select(g => Atom(g.Pred, g.Vars)));
    sb.AppendLine($"État final satisfait le but : {goalAtoms.IsSubsetOf(st)}");
    sb.AppendLine("  atome du but présent dans l'état final :");
    foreach (var ga in goalAtoms) sb.AppendLine($"    {ga} : {st.Contains(ga)}");
}
display(sb.ToString());

Plan trouvé : 7 actions (BFS = longueur minimale)
Temps : 1,73 ms

  1. load(box1,truck1,depot)
  2. drive(truck1,depot,store)
  3. unload(box1,truck1,store)
  4. drive(truck1,store,depot)
  5. load(box2,truck1,depot)
  6. drive(truck1,depot,warehouse)
  7. unload(box2,truck1,warehouse)

État final satisfait le but : True
  atome du but présent dans l'état final :
    at-loc(box1,store) : True
    at-loc(box2,warehouse) : True

Interprétation : le plan à 7 actions

BFS trouve le plan le plus court (en nombre d’actions) :

Étape	Action	Effet
1	load(box1,truck1,depot)	box1 dans le camion
2	drive(truck1,depot,store)	camion au store
3	unload(box1,truck1,store)	box1 livré au store ✓
4	drive(truck1,store,depot)	retour au depot
5	load(box2,truck1,depot)	box2 dans le camion (libéré en étape 3)
6	drive(truck1,depot,warehouse)	camion au warehouse
7	unload(box2,truck1,warehouse)	box2 livré au warehouse ✓

La contrainte empty(truck1) force à déposer box1 (étape 3) avant de charger box2 (étape 5) — d’où l’aller-retour au depot. C’est exactement le genre de raisonnement qu’un planificateur fait automatiquement, et que la recherche BFS rend visible.

Pourquoi BFS est optimal ici. BFS explore tous les états à distance n avant ceux à distance n+1. Le premier plan trouvé est donc de longueur minimale. La contrepartie : l’espace d’états explose exponentiellement (c’est le sujet du notebook Planners-3-State-Space).

---

6. Deuxième exemple : le domaine Gripper

Le Gripper est un autre classique : un robot à deux pinces doit déplacer des balles entre deux pièces. Trois actions : move (déplacer le robot), pick (saisir une balle avec une pince libre), drop (poser une balle).

Contrairement à Logistics où le camion n’avait qu’un « slot » (empty), le robot gripper a deux pinces indépendantes (free(left), free(right)) — il peut donc porter deux balles à la fois.

// Domaine + problème Gripper, résolus avec le MÊME planificateur (0 changement)
var gripper = new Domain { Name = "gripper-strips" };
gripper.Types["room"]    = new TypeDef { Name = "room",    Parent = null };
gripper.Types["ball"]    = new TypeDef { Name = "ball",    Parent = null };
gripper.Types["gripper"] = new TypeDef { Name = "gripper", Parent = null };

// move(?from,?to - room)
gripper.Actions.Add(new ActionSchema {
    Name = "move", Params = { ("from","room"), ("to","room") },
    Pre  = { ("room", new[]{"from"}), ("room", new[]{"to"}), ("at-robby", new[]{"from"}) },
    Add  = { ("at-robby", new[]{"to"}) },
    Del  = { ("at-robby", new[]{"from"}) }
});
// pick(?obj - ball, ?room - room, ?gripper - gripper)
gripper.Actions.Add(new ActionSchema {
    Name = "pick", Params = { ("obj","ball"), ("room","room"), ("gripper","gripper") },
    Pre  = { ("ball", new[]{"obj"}), ("room", new[]{"room"}), ("gripper", new[]{"gripper"}),
            ("at", new[]{"obj","room"}), ("at-robby", new[]{"room"}), ("free", new[]{"gripper"}) },
    Add  = { ("carry", new[]{"obj","gripper"}) },
    Del  = { ("at", new[]{"obj","room"}), ("free", new[]{"gripper"}) }
});
// drop(?obj - ball, ?room - room, ?gripper - gripper)
gripper.Actions.Add(new ActionSchema {
    Name = "drop", Params = { ("obj","ball"), ("room","room"), ("gripper","gripper") },
    Pre  = { ("ball", new[]{"obj"}), ("room", new[]{"room"}), ("gripper", new[]{"gripper"}),
            ("at-robby", new[]{"room"}), ("carry", new[]{"obj","gripper"}) },
    Add  = { ("at", new[]{"obj","room"}), ("free", new[]{"gripper"}) },
    Del  = { ("carry", new[]{"obj","gripper"}) }
});

var pGrip = new Problem { Name = "gripper-2balls", Dom = gripper };
pGrip.Objects.AddRange(new[] {
    ("rooma","room"), ("roomb","room"),
    ("ball1","ball"), ("ball2","ball"),
    ("left","gripper"), ("right","gripper")
});
pGrip.Init.UnionWith(new[] {
    Atom("room","rooma"), Atom("room","roomb"),
    Atom("ball","ball1"), Atom("ball","ball2"),
    Atom("gripper","left"), Atom("gripper","right"),
    Atom("at-robby","rooma"),
    Atom("free","left"), Atom("free","right"),
    Atom("at","ball1","rooma"), Atom("at","ball2","rooma")
});
pGrip.Goal.AddRange(new[] {
    ("at", new[]{"ball1","roomb"}),
    ("at", new[]{"ball2","roomb"})
});

var gGrip = Planner.Ground(gripper, pGrip);
var planG = Planner.Solve(pGrip, gGrip);

var sb = new System.Text.StringBuilder();
sb.AppendLine($"Gripper grounding : {gGrip.Count} actions groundées");
sb.AppendLine($"Plan trouvé : {planG?.Count ?? 0} actions");
sb.AppendLine();
if (planG != null) foreach (var step in planG)
    sb.AppendLine($"  - {step}");
sb.AppendLine();
sb.AppendLine("Lecture : le robot saisit les 2 balles (1 par pince), ");
sb.AppendLine("déplace, puis pose les 2 — exploite les 2 pinces en parallèle.");
display(sb.ToString());

Gripper grounding : 20 actions groundées
Plan trouvé : 5 actions

  - pick(ball1,rooma,left)
  - pick(ball2,rooma,right)
  - move(rooma,roomb)
  - drop(ball1,roomb,left)
  - drop(ball2,roomb,right)

Lecture : le robot saisit les 2 balles (1 par pince), 
déplace, puis pose les 2 — exploite les 2 pinces en parallèle.

Interprétation : Gripper à 5 actions

Étape	Action
1	pick(ball1,rooma,left)
2	pick(ball2,rooma,right)
3	move(rooma,roomb)
4	drop(ball1,roomb,left)
5	drop(ball2,roomb,right)

BFS profite des deux pinces : on saisit les deux balles avant de se déplacer, plutôt que de faire deux aller-retours. Le plan fait 5 actions au lieu de 7 — l’optimal en largeur.

Le même code Ground + Solve résout Logistics et Gripper. C’est la force d’un planificateur générique : le moteur (grounding + recherche) est indépendant du domaine — seul le modèle change.

Tranche 2 (#10382) : le vrai planificateur Fast Downward

La §1–8 ci-dessus réimplémente un planificateur STRIPS from-scratch (grounding + BFS forward, 0 NuGet) — la brique pédagogique qui rend visible ce que unified-planning (côté Python) cache. La Tranche 2 branche le même moteur production que le jumeau Python — Fast Downward 24.06.1 (Helmert ; A* + heuristique landmark-cut lmcut) — via l’API HTTP du conteneur Docker coursia-fast-downward (port 8200). Mêmes domaines PDDL (Logistics + Gripper), mêmes instances → on confronte le BFS pédagogique au solveur SOTA.

// === Tranche 2 (#10382) : Fast Downward 24.06.1 via API Docker (vrai planificateur SOTA) ===
using System.Net.Http;
using System.Text.RegularExpressions;

var httpFD = new HttpClient { Timeout = TimeSpan.FromSeconds(60) };

// Domaine PDDL Logistics (prédicats identiques au from-scratch : at-loc/at-veh/empty/in)
string DOMAIN_LOG = @"(define (domain logistics-simple)
  (:requirements :strips :typing)
  (:types location package vehicle - object
          truck - vehicle)
  (:predicates (at-loc ?p - package ?l - location)
               (at-veh ?v - vehicle ?l - location)
               (empty ?v - vehicle)
               (in ?p - package ?v - vehicle))
  (:action load :parameters (?p - package ?v - vehicle ?l - location)
           :precondition (and (at-loc ?p ?l) (at-veh ?v ?l) (empty ?v))
           :effect (and (in ?p ?v) (not (at-loc ?p ?l)) (not (empty ?v))))
  (:action unload :parameters (?p - package ?v - vehicle ?l - location)
           :precondition (and (in ?p ?v) (at-veh ?v ?l))
           :effect (and (at-loc ?p ?l) (empty ?v) (not (in ?p ?v))))
  (:action drive :parameters (?v - vehicle ?from - location ?to - location)
           :precondition (at-veh ?v ?from)
           :effect (and (at-veh ?v ?to) (not (at-veh ?v ?from)))))";

string PROB_LOG = @"(define (problem logistics-simple-1)
  (:domain logistics-simple)
  (:objects depot warehouse store - location
            box1 box2 - package
            truck1 - truck)
  (:init (at-loc box1 depot) (at-loc box2 depot)
         (at-veh truck1 depot) (empty truck1))
  (:goal (and (at-loc box1 store) (at-loc box2 warehouse))))";

// Domaine PDDL Gripper (prédicats identiques au from-scratch : at-robby/free/at/carry)
string DOMAIN_GRIP = @"(define (domain gripper-strips)
  (:requirements :strips :typing)
  (:types room ball gripper)
  (:predicates (at-robby ?r - room)
               (free ?g - gripper)
               (at ?b - ball ?r - room)
               (carry ?b - ball ?g - gripper))
  (:action move :parameters (?from - room ?to - room)
           :precondition (at-robby ?from)
           :effect (and (at-robby ?to) (not (at-robby ?from))))
  (:action pick :parameters (?obj - ball ?room - room ?gripper - gripper)
           :precondition (and (at ?obj ?room) (at-robby ?room) (free ?gripper))
           :effect (and (carry ?obj ?gripper) (not (at ?obj ?room)) (not (free ?gripper))))
  (:action drop :parameters (?obj - ball ?room - room ?gripper - gripper)
           :precondition (and (at-robby ?room) (carry ?obj ?gripper))
           :effect (and (at ?obj ?room) (free ?gripper) (not (carry ?obj ?gripper)))))";

string PROB_GRIP = @"(define (problem gripper-2balls)
  (:domain gripper-strips)
  (:objects rooma roomb - room
            ball1 ball2 - ball
            left right - gripper)
  (:init (at-robby rooma) (free left) (free right)
         (at ball1 rooma) (at ball2 rooma))
  (:goal (and (at ball1 roomb) (at ball2 roomb))))";

// Appel au conteneur Docker Fast Downward
string SolveFD(string domain, string problem, string search) {
    var payloadObj = new { domain, problem, search };
    var payloadJson = System.Text.Json.JsonSerializer.Serialize(payloadObj);
    var resp = httpFD.PostAsync("http://localhost:8200/plan",
        new StringContent(payloadJson, System.Text.Encoding.UTF8, "application/json")).Result;
    return resp.Content.ReadAsStringAsync().Result;
}

string ReportFD(string label, string body, int expectedActions) {
    var doc = System.Text.Json.JsonDocument.Parse(body);
    int returncode = doc.RootElement.GetProperty("returncode").GetInt32();
    string stdout = doc.RootElement.GetProperty("stdout").GetString();
    var sb = new System.Text.StringBuilder();
    sb.AppendLine($"--- {label} (Fast Downward 24.06.1, astar(lmcut())) ---");
    var mCost = Regex.Match(stdout, @"Plan cost: (\d+)");
    var mExp = Regex.Match(stdout, @"Expanded (\d+) state");
    var planLines = Regex.Matches(stdout, @"^([a-z][\w-]*(?:\s+[\w?-]+)*)\s+\(\d+\)\s*$", RegexOptions.Multiline);
    int cost = mCost.Success ? int.Parse(mCost.Groups[1].Value) : -1;
    int expanded = mExp.Success ? int.Parse(mExp.Groups[1].Value) : -1;
    sb.AppendLine($"returncode={returncode} | Coût du plan : {cost} | États expansés : {expanded}");
    foreach (Match m in planLines)
        sb.AppendLine($"  {m.Groups[1].Value.Trim()}");
    sb.AppendLine($"Parité from-scratch : BFS trouvait {expectedActions} actions → FD coût {cost} = {(cost == expectedActions ? "PARITÉ CONFIRMÉE" : "diffère")}");
    return sb.ToString();
}

Console.WriteLine(ReportFD("Logistics", SolveFD(DOMAIN_LOG, PROB_LOG, "astar(lmcut())"), 7));
Console.WriteLine(ReportFD("Gripper", SolveFD(DOMAIN_GRIP, PROB_GRIP, "astar(lmcut())"), 5));

--- Logistics (Fast Downward 24.06.1, astar(lmcut())) ---
returncode=0 | Coût du plan : 7 | États expansés : 9
  load box1 truck1 depot
  drive truck1 depot store
  unload box1 truck1 store
  drive truck1 store depot
  load box2 truck1 depot
  drive truck1 depot warehouse
  unload box2 truck1 warehouse
Parité from-scratch : BFS trouvait 7 actions → FD coût 7 = PARITÉ CONFIRMÉE

--- Gripper (Fast Downward 24.06.1, astar(lmcut())) ---
returncode=0 | Coût du plan : 5 | États expansés : 8
  pick ball1 rooma left
  pick ball2 rooma right
  move rooma roomb
  drop ball1 roomb left
  drop ball2 roomb right
Parité from-scratch : BFS trouvait 5 actions → FD coût 5 = PARITÉ CONFIRMÉE

Interprétation : parité lib-vs-lib, scalabilité du SOTA

Domaine	BFS from-scratch (§4)	Fast Downward lmcut	États expansés (FD)
Logistics (1 camion, 2 colis, contrainte empty)	7 actions	coût 7	9
Gripper (2 pinces, 2 balles)	5 actions	coût 5	8

Parité exacte. Le moteur réel Fast Downward retrouve les mêmes plans optimaux que le BFS from-scratch. C’est la preuve que la sémantique STRIPS réimplémentée §1–8 est correcte — un planificateur “jouet” cassé divergerait.

La nuance n’est pas le résultat, c’est le coût de recherche. Sur ces instances minuscules, BFS (forward, en aveugle) et A+lmcut trouvent l’optimum ; mais le BFS explore aveuglément (coût uniforme, aucune heuristic), tandis que lmcut (heuristique landmark-cut de Helmert & Domshlak 2009) focalise la recherche vers le but. Sur une instance plus grande (Logistics à 10 colis), le BFS exploserait exponentiellement quand FD reste polynomial-grâce-à-l’heuristique. Le from-scratch rend visible ce que fait un planificateur* (grounding + search) ; le moteur SOTA montre pourquoi l’heuristique compte.

Verdict SOTA-OK (#3801). Le moteur réel Fast Downward est invoqué (API Docker, returncode=0), produit les vrais plans optimaux. Tranche 1 from-scratch préservée intacte. Niveau de parité native-both : le jumeau Python invoque unified-planning (qui wrap Fast Downward), le jumeau C# invoque le même engine 24.06.1 via HttpClient.

---

7. Extensions PDDL au-delà de STRIPS

Le cœur STRIPS que nous avons implémenté couvre les requirements :strips et :typing. PDDL définit de nombreuses extensions pour exprimer des problèmes plus riches :

Requirement	Apport	Exemple
:negative-preconditions	Préconditions avec (not ...)	(not (locked ?room))
:conditional-effects	Effets qui dépendent d’une condition	« si la balle est rouge, alors … »
:universal-preconditions	Quantificateur forall	« tous les colis doivent être livrés »
:numeric-fluents	Variables numériques et arithmétique	carburant, temps, coût

Limite de ce jumeau. Notre planificateur from-scratch gère les préconditions positives (conjonction d’atomes) — c’est le cas de la grande majorité des domaines IPC. Les préconditions négatives s’ajoutent en vérifiant !state.Contains(atomNég) ; les effets conditionnels demandent une structure d’effet plus riche. Ces extensions sont l’amorce d’un travail plus avancé, hors scope de cette introduction.

La bibliothèque unified-planning (côté Python) gère ces extensions via des traductions vers les solveurs industriels (Fast Downward, ENHSP) — d’où l’intérêt pédagogique d’avoir les deux jumeaux.

---

8. Exercices

Trois exercices pour ancrer la modélisation STRIPS. Les cellules sont des stubs (// TODO étudiant) : à vous de compléter en vous inspirant des domaines Logistics et Gripper ci-dessus. Le planificateur Planner.Ground + Planner.Solve est déjà défini — réutilisez-le.

Exercice 8.1 — Gripper à 3 balles (instancier un nouveau problème)

Le domaine gripper défini plus haut reste inchangé. Écrivez un nouveau problème avec 3 balles (ball1, ball2, ball3) initialement dans rooma à amener toutes dans roomb. Combien d’actions fait le plan optimal ? (Le robot n’a que 2 pinces.)

// Exercice 8.1 : Gripper à 3 balles
// TODO étudiant : construire pGrip3 (Problem) sur le domaine `gripper` existant,
// avec 3 balles dans rooma à amener dans roomb. Puis résoudre avec Planner.Solve.
//
// Indice :
//   1. Définir les objets : rooma, roomb (room) ; ball1, ball2, ball3 (ball) ; left, right (gripper)
//   2. Init : (room rooma)(room roomb)(ball ball1..3)(gripper left/right)(at-robby rooma)
//             (free left)(free right)(at ball1 rooma)(at ball2 rooma)(at ball3 rooma)
//   3. Goal : (at ball1 roomb)(at ball2 roomb)(at ball3 roomb)
//
// Étape 1 : déclarer pGrip3 = new Problem { Name = "gripper-3balls", Dom = gripper };
// Étape 2 : ajouter objets + init + goal
// Étape 3 : var plan3 = Planner.Solve(pGrip3, Planner.Ground(gripper, pGrip3));

var pGrip3 = (Problem)null;  // TODO étudiant : remplacer par la construction du problème
display("Exercice 8.1 à compléter : Gripper à 3 balles. " +
        "Construisez pGrip3 puis appelez Planner.Solve. " +
        "Question : avec 2 pinces et 3 balles, le plan optimal fait combien d'actions ?");

Exercice 8.1 à compléter : Gripper à 3 balles. Construisez pGrip3 puis appelez Planner.Solve. Question : avec 2 pinces et 3 balles, le plan optimal fait combien d'actions ?

Exemple guidé : domaine Robot-Entrepôt

Avant l’exercice 8.2, un exemple de définition de domaine. Un robot d’entrepôt peut saisir un objet (sur une étagère) et deposer un objet (sur une étagère). Le schéma est proche de Gripper.

; Domaine robot-entrepot
; types : objet, etagere
; predicats : (sur ?o - objet ?e - etagere)  (tenu ?o - objet)
; action saisir(?o,?e) : pre (sur ?o ?e) ; add (tenu ?o) ; del (sur ?o ?e)
; action deposer(?o,?e) : pre (tenu ?o) ; add (sur ?o ?e) ; del (tenu ?o)

Exercice 8.2 — Domaine Robot-Cuisine

Définissez un domaine robot-cuisine : un robot peut prendre un ingrédient et le poser dans un plat. Types : ingredient, location, plat. Prédicats : (at ?i - ingredient ?l - location), (dans ?i - ingredient ?p - plat), (robot-libre). Construisez ensuite un petit problème et résolvez-le.

// Exercice 8.2 : Domaine Robot-Cuisine
// TODO étudiant : définir le domaine `cuisine` (types + 2 actions prendre/poser)
// puis un problème, puis résoudre avec Planner.Solve.
//
// Indice :
//   - action prendre(?i - ingredient, ?l - location)
//       pre : (at ?i ?l) (robot-libre)
//       add : (tenu ?i)
//       del : (at ?i ?l) (robot-libre)
//   - action poser(?i - ingredient, ?p - plat)
//       pre : (tenu ?i)
//       add : (dans ?i ?p) (robot-libre)
//       del : (tenu ?i)

var cuisine = (Domain)null;  // TODO étudiant : new Domain { Name = "robot-cuisine", ... }
display("Exercice 8.2 à compléter : construisez le domaine robot-cuisine " +
        "(types ingredient/location/plat, actions prendre/poser) puis un problème, " +
        "et résolvez-le avec Planner.Ground + Planner.Solve.");

Exercice 8.2 à compléter : construisez le domaine robot-cuisine (types ingredient/location/plat, actions prendre/poser) puis un problème, et résolvez-le avec Planner.Ground + Planner.Solve.

Exercice 8.3 — Étendre le domaine Logistics d’une action fly

Le domaine Logistics ne couvre que les camions. Ajoutez une action fly(?a - airplane, ?from - location, ?to - location) pour un avion (nouveau sous-type airplane - vehicle), reconstruisez un problème avec un avion plane1 et un colis à livrer loin, et résolvez. Observez comment BFS choisit entre drive et fly.

Cet exercice vous fait manipuler la hiérarchie de types (ajouter airplane - vehicle) et vérifier que le grounding génère bien les actions fly pour les objets de type airplane.

// Exercice 8.3 : étendre Logistics avec un avion
// TODO étudiant :
//   1. Ajouter le type 'airplane' (parent 'vehicle') au domaine `logistics`
//   2. Ajouter l'action fly(?a - airplane, ?from - location, ?to - location)
//        pre : (at-veh ?a ?from)
//        add : (at-veh ?a ?to)
//        del : (at-veh ?a ?from)
//   3. Construire un problème avec plane1 (airplane) + colis, puis résoudre.
//
// Indice : logistics.Types["airplane"] = new TypeDef { Name = "airplane", Parent = "vehicle" };
//          (le grounding fera que fly n'accepte QUE les airplane, pas les truck)

var logisticsAvecAvion = (Domain)null;  // TODO étudiant : cloner + étendre logistics
display("Exercice 8.3 à compléter : ajoutez le type airplane + l'action fly au domaine " +
        "logistics, construisez un problème avec plane1, et résolvez. " +
        "Question : fly accepte-t-il truck1 comme 1er argument ? (Pourquoi non ?)");

Exercice 8.3 à compléter : ajoutez le type airplane + l'action fly au domaine logistics, construisez un problème avec plane1, et résolvez. Question : fly accepte-t-il truck1 comme 1er argument ? (Pourquoi non ?)

---

9. Résumé

Points clés

Concept	Implémentation C#
PDDL	Langage standard de planification, basé sur STRIPS
Domaine	Domain : types (hiérarchie), schémas d’action (pre/add/del)
Problème	Problem : objets typés, état initial (HashSet<string>), but
Atome groundé	Chaîne canonique "pred(a,b)" — clé d’un HashSet
Grounding	Planner.Ground : produit cartésien type-compatible des paramètres
Recherche	Planner.Solve : BFS forward, plan de longueur minimale

Ce que vous avez construit

Un planificateur STRIPS complet from-scratch — le même moteur résout Logistics (7 actions) et Gripper (5 actions). Vous avez déroulé à la main ce que unified-planning.solve() fait en un appel côté Python : la modélisation typée, le grounding et la recherche dans l’espace d’états.

---

Conclusion

Ce notebook a couvert les fondamentaux de PDDL en s’appuyant sur un modèle STRIPS implémenté en C#. Vous avez vu comment un problème de planification se décompose en domaine (types, prédicats, actions) et problème (objets, état initial, but), et comment un planificateur générique (grounding + BFS) résout n’importe quelle instance.

La limite de STRIPS + BFS

La recherche BFS trouve le plan optimal en nombre d’actions, mais l’espace d’états explose exponentiellement avec le nombre d’objets. Pour les problèmes réalistes (des dizaines d’objets), il faut :

• des heuristiques admissibles pour guider la recherche (A*, h-max, h-FF) — c’est l’objet de Planners-5-Heuristics-Csharp ;
• ou des solveurs industriels qui compilent le problème vers SAT/CP — c’est ce que font Fast Downward et unified-planning.

Prochaines étapes

• Planners-3-State-Space-Csharp : la structure des espaces d’états et pourquoi BFS explose.
• Planners-5-Heuristics-Csharp : les heuristiques qui rendent la recherche tractable.

---

Ressources

• PDDL Reference — Documentation complète du langage.
• unified-planning — Bibliothèque Python (jumeau Python de ce notebook).
• IPC Benchmarks — Domaines de test des International Planning Competitions.
• Fast Downward — Le solveur planification de référence (utilisé via unified-planning côté Python).
• Russell, S., & Norvig, P. — Artificial Intelligence: A Modern Approach (4e éd.), ch. « Planning and Acting in the Real World ».