Planners-1-Introduction-Csharp : la planification automatique from-scratch, puis moteur SOTA

Navigation : << Setup | Twin Python unified-planning | PDDL Basics >>

Twin C# du notebook Python Planners-1-Introduction (Python + lib unified-planning). Tranche 1 = les fondations : le modèle STRIPS (Fikes & Nilsson, 1971), l’espace d’etats, et un planificateur BFS from-scratch qui resout le problème canonique de l’interrupteur. Implementation BCL .NET seule, 0 NuGet. Tranche 2 = le moteur de production : les mêmes problèmes (plus la livraison du jumeau Python) délégués au vrai Fast Downward via son API Docker, en PDDL standard.

Complementarite (#3801 Prong B)

Twin Outil Valeur
Python (unified-planning) lib up.shortcuts (modelisation + solveur 1 appel) resoudre vite des problemes PDDL reels
This — Tranche 1 (.NET from-scratch) implementation C# main : STRIPS + BFS + state-space comprendre la sémantique STRIPS et la recherche dans l’espace d’etats
This — Tranche 2 (Fast Downward) API Docker HTTP (astar(lmcut())), PDDL standard produire : moteur PDDL SOTA, plan optimal, zéro code de recherche

Pas d’equivalent NuGet maintenu et didactique a unified-planning en .NET → la Tranche 1 from-scratch porte la valeur pedagogique (on code chaque brique), la Tranche 2 porte la parité d’outil (le même moteur de production que le jumeau Python enveloppe, cf Planners-4-Fast-Downward-Csharp).

Stack technique : BCL .NET seule + HttpClient vers l’API Docker Fast Downward (Tranche 2). Kernel .net-csharp (.NET Interactive).

Cadre pédagogique et prérequis

Ce notebook ouvre la série Planners avec une approche from-scratch : le moteur de recherche (BFS) et la représentation des états (STRIPS) sont implémentés à la main en C# pur (BCL .NET seule, sans dépendance externe). L’objectif est pédagogique : comprendre comment un planificateur fonctionne avant d’utiliser des moteurs SOTA (Fast Downward, OR-Tools, LLM, cf. tranches suivantes).

Pourquoi C# / .NET Interactive ? Le choix reflète le contexte du dépôt CoursIA, qui mêle notebooks Python et C# pour montrer les deux écosystèmes en action. C# apporte un typage statique rigoureux, des HashSet<T> natifs (idéaux pour représenter un état ensembliste), et un kernel .NET Interactive stable pour Jupyter. Voir docs/reference/kernels-runtime.md pour l’installation et le déblocage du kernel.

Prérequis pour suivre ce notebook :

  1. Maîtrise de C# 9+ (types génériques, record, HashSet<T>, LINQ de base). Les spécificités BCL .NET utilisées ici sont documentées inline.
  2. Notions de recherche dans un graphe (BFS, DFS, A*). Si elles sont fraîches, la section 1 pose le cadre et la section 6 construit BFS pas à pas.

Plan du notebook : 10 sections progressives (définition STRIPS, implémentation, exemples croissant en complexité, exercices), puis la Tranche 2 qui introduit le moteur Fast Downward via API Docker en comparaison directe. Les exercices (section 10) sont à compléter pour valider la compréhension.

Note d’écosystème : la Tranche 2 s’appuie sur le moteur fast-downward.py exposé par une API Docker en localhost:8200 — c’est un prérequis explicite. La cellule Tranche 2 appelle l’API directement (HttpClient, échec rapide si le service n’est pas lancé) : pas de repli silencieux sur BFS, conformément à la règle SOTA du dépôt — pas de sortie dégradée maquillée en résultat. La Tranche 1 (BFS from-scratch, zéro dépendance) reste exécutable seule.

1. Qu’est-ce que la planification ?

La planification automatique est la branche de l’IA qui genere des sequences d’actions pour atteindre un objectif. Etant donne : - un etat initial (le monde tel qu’il est), - un ensemble d’actions (chacune decrite par ses preconditions et ses effets), - un but (un etat a atteindre),

le planificateur cherche automatiquement une suite d’actions qui mene de l’etat initial au but. La question n’est pas « que predire ? » (apprentissage) mais « que faire ? ».

Contraste : - Recherche (Search series) : on explore un graphe donne. La planification construit ce graphe (l’espace d’etats) a partir de la sémantique des actions. - CSP (Constraint series) : on satisfait des contraintes sur des variables. La planification cherche une sequence (l’ordre compte).

La planification est une technologie eprouvee : elle pilote des robots, optimise la logistique, et a dirige des engins spatiaux autonomes (Remote Agent sur Deep Space 1).

2. Le modèle STRIPS

STRIPS (STanford Research Institute Problem Solver, Fikes & Nilsson 1971) est le formalisme canonique. L’etat du monde = un ensemble de predicats (faits vrais). Une action (appelee opérateur) comporte :

  • un nom (ex: allumer(lampe)),
  • des preconditions : predicats qui doivent etre vrais pour que l’action soit applicable,
  • des effets : predicats ajoutes (deviennent vrais) et retires (deviennent faux) après l’action.

La transition : si l’etat courant contient toutes les preconditions, l’action est applicable. L’etat resultant = (etat courant − effets de retrait) ∪ effets d’ajout.

Formalisme

Soit un opérateur \(o = (pre(o), add(o), del(o))\). Pour un etat \(S\) :

  • applicable ssi \(pre(o) \subseteq S\)
  • successeur : \(S' = (S \setminus del(o)) \cup add(o)\)

Un plan = sequence d’opérateurs \(o_1, o_2, \dots, o_n\) telle que chaque \(o_i\) est applicable dans l’etat atteint après \(o_1, \dots, o_{i-1}\), et le but est atteint a la fin.

3. Setup et helpers invariant

Helper de formatage invariant (evite la collision virgule-decimale FR dans les sorties).

using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;

static string FI(double x, string fmt = "F4") => x.ToString(fmt, CultureInfo.InvariantCulture);

Console.WriteLine("Setup OK — kernel .net-csharp, BCL seule.");
Setup OK — kernel .net-csharp, BCL seule.

4. Implementation du modèle STRIPS from-scratch

On represente l’etat comme un HashSet<string> de predicats (ex: {"lampe_allumee", "lampe_fonctionne"}). Un opérateur est une classe avec preconditions, ajouts, retraits. La transition applique l’opérateur si applicable.

// Modele STRIPS from-scratch (BCL .NET seule).
// Un etat = HashSet<string> (ensemble de predicats vrais).

// Un operateur STRIPS : nom + preconditions + effets (add/del).
class Operator {
    public string Name { get; init; } = "";
    public HashSet<string> Pre { get; init; } = new();
    public HashSet<string> Add { get; init; } = new();
    public HashSet<string> Del { get; init; } = new();
}

// Une transition : applicable ssi pre <= S ; successeur = (S - del) | add.
static bool IsApplicable(Operator op, HashSet<string> s) => op.Pre.IsSubsetOf(s);

static HashSet<string> Apply(Operator op, HashSet<string> s) {
    // On ne devrait appeler Apply que si IsApplicable.
    var s2 = new HashSet<string>(s);
    foreach (var d in op.Del) s2.Remove(d);
    foreach (var a in op.Add) s2.Add(a);
    return s2;
}

// Le but est atteint ssi tous les predicats du but sont dans l'etat.
static bool GoalReached(HashSet<string> goal, HashSet<string> s) => goal.IsSubsetOf(s);

Console.WriteLine("Modele STRIPS compile : Operator + IsApplicable + Apply + GoalReached.");
Modele STRIPS compile : Operator + IsApplicable + Apply + GoalReached.

5. Exemple simple — l’interrupteur

Le problème canonique de l’interrupteur (cf twin Python) : - Etat initial : la lampe est eteinte. - Actions : allumer (pre: lampe en bon etat ; add: lampe allumee), eteindre (add: lampe eteinte, del: lampe allumee). - But : la lampe est allumee.

Ce problème trivial sert de sanity check : un planificateur BFS doit trouver le plan [allumer].

// Exemple de l'interrupteur (sanity check).

var allumer = new Operator {
    Name = "allumer",
    Pre = new HashSet<string> { "lampe_fonctionne" },
    Add = new HashSet<string> { "lampe_allumee" },
    Del = new HashSet<string> { "lampe_eteinte" }
};
var eteindre = new Operator {
    Name = "eteindre",
    Pre = new HashSet<string> { "lampe_allumee" },
    Add = new HashSet<string> { "lampe_eteinte" },
    Del = new HashSet<string> { "lampe_allumee" }
};

HashSet<string> initial = new HashSet<string> { "lampe_eteinte", "lampe_fonctionne" };
var goal = new HashSet<string> { "lampe_allumee" };

Console.WriteLine("Etat initial  : {" + string.Join(", ", initial.OrderBy(x => x)) + "}");
Console.WriteLine("But           : {" + string.Join(", ", goal) + "}");
Console.WriteLine("But atteint directement ? " + GoalReached(goal, initial));
Console.WriteLine("'allumer' applicable ? " + IsApplicable(allumer, initial));
var apres = Apply(allumer, initial);
Console.WriteLine("Apres 'allumer' : {" + string.Join(", ", apres.OrderBy(x => x)) + "}");
Console.WriteLine("But atteint apres 'allumer' ? " + GoalReached(goal, apres));
Etat initial  : {lampe_eteinte, lampe_fonctionne}
But           : {lampe_allumee}
But atteint directement ? False
'allumer' applicable ? True
Apres 'allumer' : {lampe_allumee, lampe_fonctionne}
But atteint apres 'allumer' ? True

Interpretation — l’interrupteur

L’etat initial ne contient pas le but (lampe_allumee absent). L’action allumer est applicable car sa precondition lampe_fonctionne est satisfaite. Après application, lampe_allumee est ajoutee → le but est atteint. Sanity OK : le plan [allumer] resout le problème.

C’est exactement ce que ferait unified-planning (twin Python) en un appel — mais ici on voit chaque étape (precondition, ajout, retrait).

6. Le planificateur BFS from-scratch

Un planificateur = une recherche dans l’espace d’etats. L’espace d’etats = graphe ou les noeuds sont les etats et les aretes sont les opérateurs applicables. On cherche un chemin de l’etat initial a un etat-but.

BFS (Breadth-First Search) = parcours en largeur. Garantit le plan le plus court (en nombre d’actions). Pour un petit espace d’etats, BFS suffit. Pour de grands espaces, on aurait besoin d’heuristiques (A*, relaxations — cf Planners-5).

Implementation : une file d’etats a explorer, un dictionnaire etat -> (opérateur, etat parent) pour reconstruire le plan une fois le but atteint.

#nullable enable
// Planificateur BFS from-scratch — trouve le plan le plus court.

static List<string>? PlanBFS(HashSet<string> initial, HashSet<string> goal, List<Operator> ops, int maxExpansions = 100000) {
    var queue = new Queue<HashSet<string>>();
    queue.Enqueue(initial);
    // came_from[etat] = (operateur applique, etat parent)
    var cameFrom = new Dictionary<string, (string opName, HashSet<string> parent)>(new StateComparer());
    cameFrom[StateKey(initial)] = ("__INIT__", initial);

    int expansions = 0;
    while (queue.Count > 0 && expansions < maxExpansions) {
        var current = queue.Dequeue();
        expansions++;
        if (GoalReached(goal, current)) {
            // Reconstruire le plan.
            var plan = new List<string>();
            var key = StateKey(current);
            while (cameFrom[key].opName != "__INIT__") {
                var (opName, parent) = cameFrom[key];
                plan.Add(opName);
                key = StateKey(parent);
            }
            plan.Reverse();
            return plan;
        }
        foreach (var op in ops) {
            if (IsApplicable(op, current)) {
                var next = Apply(op, current);
                var nkey = StateKey(next);
                if (!cameFrom.ContainsKey(nkey)) {
                    cameFrom[nkey] = (op.Name, current);
                    queue.Enqueue(next);
                }
            }
        }
    }
    return null;  // pas de plan trouve dans maxExpansions
}

// Cle string canonique pour un etat (predicats tries).
static string StateKey(HashSet<string> s) => string.Join("|", s.OrderBy(x => x));

// Comparateur d'etats base sur la cle string.
class StateComparer : IEqualityComparer<string> {
    public bool Equals(string? a, string? b) => a == b;
    public int GetHashCode(string s) => s?.GetHashCode() ?? 0;
}

Console.WriteLine("Planificateur BFS compile.");
Planificateur BFS compile.

Plan sur l’interrupteur

Lançons BFS sur le problème de l’interrupteur. Il doit trouver [allumer] (1 action, le plus court).

// Plan sur l'interrupteur.
var ops = new List<Operator> { allumer, eteindre };
var plan = PlanBFS(initial, goal, ops);
if (plan != null) {
    Console.WriteLine($"Plan trouve ({plan.Count} action(s)) : [{string.Join(" -> ", plan)}]");
} else {
    Console.WriteLine("Aucun plan trouve.");
}
Plan trouve (1 action(s)) : [allumer]

7. Problème plus riche — multi-interrupteurs (non-trivial)

L’interrupteur seul est trivial (1 action). Pour mettre en valeur le planificateur (cf #3801 Prong B — problème non-trivial), considerons N interrupteurs a allumer dans un ordre quelconque, mais avec une contrainte : une maitresse (master switch) doit etre allumee avant de pouvoir allumer les autres (precondition chainee). Le but = tous les interrupteurs allumes.

Ce problème a une structure (la maitresse d’abord) que BFS doit decouvrir — ce n’est pas un graphe a cout uniforme trivial.

// N interrupteurs + maitresse (probleme non-trivial).
int N = 3;
var multiOps = new List<Operator>();
// allumer_master : pre = rien ; add = master_on
multiOps.Add(new Operator {
    Name = "allumer_master",
    Pre = new HashSet<string>(),
    Add = new HashSet<string> { "master_on" },
    Del = new HashSet<string> { "master_off" }
});
// allumer_i : pre = master_on ; add = switch_i_on ; del = switch_i_off
for (int i = 1; i <= N; i++) {
    int idx = i;
    multiOps.Add(new Operator {
        Name = $"allumer_sw{idx}",
        Pre = new HashSet<string> { "master_on" },
        Add = new HashSet<string> { $"switch_{idx}_on" },
        Del = new HashSet<string> { $"switch_{idx}_off" }
    });
}

HashSet<string> multiInitial = new HashSet<string>();
multiInitial.Add("master_off");
for (int i = 1; i <= N; i++) multiInitial.Add($"switch_{i}_off");

var multiGoal = new HashSet<string> { "master_on" };
for (int i = 1; i <= N; i++) multiGoal.Add($"switch_{i}_on");

Console.WriteLine($"Probleme : {N} interrupteurs + 1 maitresse");
Console.WriteLine($"Etat initial : {multiInitial.Count} predicats (tout eteint)");
Console.WriteLine($"But : master_on + {N} switch_*_on");
Console.WriteLine();

var multiPlan = PlanBFS(multiInitial, multiGoal, multiOps);
if (multiPlan != null) {
    Console.WriteLine($"Plan trouve ({multiPlan.Count} actions) :");
    Console.WriteLine($"  [{string.Join(" -> ", multiPlan)}]");
    Console.WriteLine();
    // Verifier : master_on doit preceder tous allumer_sw*
    int masterIdx = multiPlan.IndexOf("allumer_master");
    Console.WriteLine($"'allumer_master' a la position {masterIdx + 1}/{multiPlan.Count} — doit etre PREMIERE (precondition chainee).");
    Console.WriteLine($"Structure decouverte par BFS : maitresse d'abord, puis les {N} interrupteurs (ordre arbitraire).");
} else {
    Console.WriteLine("Aucun plan trouve.");
}
Probleme : 3 interrupteurs + 1 maitresse
Etat initial : 4 predicats (tout eteint)
But : master_on + 3 switch_*_on

Plan trouve (4 actions) :
  [allumer_master -> allumer_sw1 -> allumer_sw2 -> allumer_sw3]

'allumer_master' a la position 1/4 — doit etre PREMIERE (precondition chainee).
Structure decouverte par BFS : maitresse d'abord, puis les 3 interrupteurs (ordre arbitraire).

Interpretation — multi-interrupteurs

BFS decouvre automatiquement la structure du problème : - Il faut d’abord allumer la maitresse (seule action applicable sans precondition). - Puis allumer chaque interrupteur (precondition master_on satisfaite).

Le plan a N+1 actions : allumer_master puis allumer_sw1, allumer_sw2, …, allumer_swN (l’ordre des sw* est arbitraire — BFS trouve l’un des plans optimaux). C’est exactement le genre de plan que unified-planning produirait, mais ici on voit la recherche explorer l’espace d’etats.

Pourquoi c’est non-trivial : sans precondition chainee, le problème serait degenere (toutes les actions independantes). La maitresse force un ordre partiel que le planificateur doit decouvrir — c’est ce qui met BFS en valeur (cf #3801 Prong B, problème non-degenere).

8. Explosion combinatoire de l’espace d’etats

Avec \(n\) predicats (faits booléens), il y a jusqu’a \(2^n\) etats possibles. Pour 10 predicats = 1024 etats, pour 20 = 1 million, pour 50 = \(10^{15}\)… C’est le fleau de la combinatoire qui motive les heuristiques (A*, relaxations — cf Planners-5).

// Explosion combinatoire : 2^n etats pour n predicats.
Console.WriteLine("Explosion combinatoire de l'espace d'etats (2^n) :");
Console.WriteLine();
Console.WriteLine("  n predicats | etats possibles");
Console.WriteLine("  ----------- | ---------------");
foreach (int n in new[] { 5, 10, 15, 20, 30, 50 }) {
    double states = Math.Pow(2, n);
    string repr = states < 1e6 ? FI(states, "F0") : states.ToString("E2", CultureInfo.InvariantCulture);
    Console.WriteLine($"  {n,11} | {repr,15}");
}
Console.WriteLine();
Console.WriteLine(">>> 50 predicats = ~1e15 etats : aucun planificateur aveugle (BFS) ne peut explorer.");
Console.WriteLine(">>> D'ou les HEURISTIQUES (A*, relaxations) pour guider la recherche (cf Planners-5).");
Explosion combinatoire de l'espace d'etats (2^n) :

  n predicats | etats possibles
  ----------- | ---------------
            5 |              32
           10 |            1024
           15 |           32768
           20 |       1.05E+006
           30 |       1.07E+009
           50 |       1.13E+015

>>> 50 predicats = ~1e15 etats : aucun planificateur aveugle (BFS) ne peut explorer.
>>> D'ou les HEURISTIQUES (A*, relaxations) pour guider la recherche (cf Planners-5).

9. Types de planification

La planification se declinent en plusieurs variantes (cf twin Python) :

Type Caractéristique Exemple
Classique etats discrets, actions instantanées, déterministes empiler des blocs, logistique
Temporelle actions avec durée, chevauchement ordonnancement de tâches
HTN (Hierarchical Task Network) décomposition de tâches abstraites planification militaire, cuisine
Neuro-symbolique LLM + planificateur formel agent LLM avec vérification

Ce notebook couvre les fondations classiques (STRIPS + BFS). Les notebooks suivants (PDDL, heuristiques, etc.) approfondissent.

10. Exercices

Trois exercices pour aller plus loin. Chaque stub est conforme a la règle C.1 (pas d’erreur volontaire — le notebook s’execute de bout en bout même exercices non completes).

Exercice 1 — Le monde des blocs (blocks world)

Enonce : Modelisez le monde des blocs : 3 blocs A, B, C. Etat initial : A sur la table, B sur A, C sur la table. But : C sur B sur A (pyramide). Actions : deplacer(x, y, z) (pre: x sur y, bras libre ; add: x sur z ; del: x sur y).

Étape 1 : Definissez les opérateurs (avec les predicats sur(x,y), Bras_libre, sur_table(x)). Étape 2 : Codez l’etat initial et le but. Étape 3 : Lancez PlanBFS et observez le plan.

Indice : attention aux precondition Bras_libre — un seul bloc peut etre deplace a la fois. C’est un problème classique (Sussman anomaly) plus riche que l’interrupteur.

// Exercice 1 — Monde des blocs (A sur table, B sur A, C sur table -> C sur B sur A).
// TODO etudiant : definissez les operateurs deplacer + etat initial + but, lancez PlanBFS.
Console.WriteLine("Exercice 1 a completer : monde des blocs (blocks world).");
Exercice 1 a completer : monde des blocs (blocks world).

Exercice 2 — Ajouter une heuristique (A* au lieu de BFS)

Enonce : BFS trouve le plan le plus court mais explore en aveugle. Implementez A* avec une heuristique simple : nombre de predicats du but non encore satisfaits dans l’etat courant.

Questions : (a) A* explore-t-il moins d’etats que BFS sur le multi-interrupteurs ? (b) L’heuristique est-elle admissible (ne surestime jamais le cout) ?

Indice : remplacez la Queue BFS par une PriorityQueue ordonnée par g + h (cout parcouru + heuristique). g = nombre d’actions depuis l’initial, h = predicats du but manquants.

// Exercice 2 — A* avec heuristique (predicats du but manquants).
// TODO etudiant : PriorityQueue g+h, h = |goal - S|, comparez explorations vs BFS.
Console.WriteLine("Exercice 2 a completer : A* avec heuristique de but non-satisfait.");
Exercice 2 a completer : A* avec heuristique de but non-satisfait.

Exercice 3 — Echec : problème non-realisable

Enonce : Créez un problème sans solution (ex: but = lampe allumee, mais lampe_fonctionne absent de l’etat initial et aucune action ne l’etablit). Observez le comportement de PlanBFS (retourne null après maxExpansions).

Questions : (a) Combien d’etats BFS explore-t-il avant d’abandonner ? (b) Comment detecter l’insatisfiabilite plus tot (ex: analyse des preconditions — un fait du but non atteignable par aucun effet d’ajout) ?

Indice : maxExpansions borne l’exploration. Un fait du but qui n’apparait dans aucun Add d’opérateur est mort — detection statique possible.

// Exercice 3 — Probleme non-realisable (but avec fait non-atteignable).
// TODO etudiant : etat initial sans lampe_fonctionne, but lampe_allumee, observez null.
Console.WriteLine("Exercice 3 a completer : probleme non-realisable + detection statique.");
Exercice 3 a completer : probleme non-realisable + detection statique.

Tranche 2 — Le moteur de production : Fast Downward via API Docker

La Tranche 1 a construit le planificateur (STRIPS + BFS from-scratch). Le jumeau Python, lui, invoque des moteurs de production via unified-planning (pyperplan sur l’interrupteur, plan optimal 3 actions sur le problème de livraison). Cette Tranche 2 fait de même côté .NET : on délègue au vrai Fast Downward — le moteur PDDL SOTA (Helmert 2006, lignée championne IPC) — exposé comme service Docker HTTP (conteneur coursia-fast-downward, port 8200), la même approche que Planners-4-Fast-Downward-Csharp.

Étape Tranche 1 (from-scratch) Tranche 2 (Fast Downward)
Encodage du domaine classes C# Operator à la main texte PDDL standard
Traduction + grounding rien (déjà STRIPS) faites par le moteur
Recherche BFS (aveugle) A* + heuristique lmcut (admissible)
Garantie plan le plus court plan optimal (coût minimal)

Prérequis : le service Docker doit tourner (docker start fast-downward, vérif GET http://localhost:8200/health).

// === Tranche 2 : Fast Downward via API Docker (moteur PDDL de production) ===
// Meme approche que le jumeau Python (unified-planning enveloppe les moteurs de
// production) et que Planners-4-Csharp : on poste domaine + probleme en PDDL
// standard, le moteur fait la traduction, le grounding et la recherche.
using System.Net.Http;
using System.Text;
using System.Text.Json;
using System.Text.RegularExpressions;

static readonly HttpClient FdHttp = new HttpClient { Timeout = TimeSpan.FromSeconds(30) };

// Un appel au planificateur : POST /plan {domain, problem, search} -> (rc, stdout, stderr).
static (int rc, string stdout, string stderr) RunFd(string domain, string problem, string search) {
    var payload = JsonSerializer.Serialize(new { domain, problem, search });
    var resp = FdHttp.PostAsync("http://localhost:8200/plan",
        new StringContent(payload, Encoding.UTF8, "application/json")).Result;
    var body = resp.Content.ReadAsStringAsync().Result;
    using var doc = JsonDocument.Parse(body);
    return (doc.RootElement.GetProperty("returncode").GetInt32(),
            doc.RootElement.GetProperty("stdout").GetString() ?? "",
            doc.RootElement.GetProperty("stderr").GetString() ?? "");
}

// Extraction du plan depuis le log Fast Downward.
// Ligne de plan FD : "pick rob pkg depot (1)" = action + arguments + (cout).
static List<string> FdPlanLines(string stdout) {
    var lines = new List<string>();
    foreach (var raw in stdout.Split('\n')) {
        var t = raw.Trim();
        if (Regex.IsMatch(t, @"^[a-z][a-z0-9_-]*(\s+\S+)*\s+\(\d+\)\s*$")) lines.Add(t);
    }
    return lines;
}

// Premiere metrique regex-matching du log (ex : heuristique initiale, etats expanses).
static int FdMetric(string stdout, string pattern) {
    var m = Regex.Match(stdout, pattern);
    return m.Success ? int.Parse(m.Groups[1].Value) : -1;
}

Console.WriteLine("Sante du service : " + FdHttp.GetAsync("http://localhost:8200/health")
    .Result.Content.ReadAsStringAsync().Result);
Console.WriteLine();

// --- L'interrupteur de la section 5, rejoue des deux cotes ---
// Cote Tranche 1 : BFS from-scratch sur le modele STRIPS (modeles frais, noms locaux).
var opsSw = new List<Operator> {
    new Operator { Name = "allumer", Pre = new HashSet<string> { "lampe_fonctionne" },
                   Add = new HashSet<string> { "lampe_allumee" }, Del = new HashSet<string> { "lampe_eteinte" } },
    new Operator { Name = "eteindre", Pre = new HashSet<string> { "lampe_allumee" },
                   Add = new HashSet<string> { "lampe_eteinte" }, Del = new HashSet<string> { "lampe_allumee" } }
};
var initSw = new HashSet<string> { "lampe_eteinte", "lampe_fonctionne" };
var goalSw = new HashSet<string> { "lampe_allumee" };
var planBfsSw = PlanBFS(initSw, goalSw, opsSw);

// Cote Tranche 2 : le meme domaine en PDDL (turn-on <-> allumer).
var DOMAIN_SW = @"(define (domain interrupteurs)
  (:requirements :strips)
  (:predicates (lampe-fonctionne) (lampe-allumee) (lampe-eteinte))
  (:action turn-on :parameters ()
    :precondition (lampe-fonctionne)
    :effect (and (lampe-allumee) (not (lampe-eteinte))))
  (:action turn-off :parameters ()
    :precondition (lampe-allumee)
    :effect (and (lampe-eteinte) (not (lampe-allumee))))
)";
var PROBLEM_SW = @"(define (problem interrupteur-simple)
  (:domain interrupteurs)
  (:init (lampe-fonctionne) (lampe-eteinte))
  (:goal (lampe-allumee))
)";

var (rcSw, outSw, errSw) = RunFd(DOMAIN_SW, PROBLEM_SW, "astar(lmcut())");
var fdPlanSw = FdPlanLines(outSw);
Console.WriteLine($"[FD] interrupteur : returncode = {rcSw}");
Console.WriteLine($"[FD] Plan ({fdPlanSw.Count} action(s)) : [{string.Join(" -> ", fdPlanSw)}]");
Console.WriteLine($"[FD] h(lmcut) initiale = {FdMetric(outSw, @"Initial heuristic value for lmcut:\s*(\d+)")}"
    + $" | etats expanses = {FdMetric(outSw, @"Expanded\s+(\d+)\s+state")}");
Console.WriteLine();
Console.WriteLine($"PARITE : BFS from-scratch = [{string.Join(" -> ", planBfsSw!)}] ({planBfsSw!.Count} action(s))");
Console.WriteLine(planBfsSw!.Count == fdPlanSw.Count
    ? "-> MEME LONGUEUR OPTIMALE (1 action) : turn-on <-> allumer, les deux moteurs concluent."
    : "-> DIVERGENCE de longueur ! (imprevu : BFS est optimal lui aussi)");
Sante du service : {"status": "healthy", "planner": "fast-downward", "version": "24.06.1"}

[FD] interrupteur : returncode = 0
[FD] Plan (1 action(s)) : [turn-on  (1)]
[FD] h(lmcut) initiale = 1 | etats expanses = 2

PARITE : BFS from-scratch = [allumer] (1 action(s))
-> MEME LONGUEUR OPTIMALE (1 action) : turn-on <-> allumer, les deux moteurs concluent.

Multi-interrupteurs (N=3 + maitresse) — la section 7 rejouée cote moteur

Le problème non-trivial de la Tranche 1 (maitresse + 3 interrupteurs, but conjonctif) est fourni à Fast Downward sans écrire une seule classe C# : le texte PDDL suffit. On compare plan FD et plan BFS action par action — et on lit l’heuristique initiale lmcut, qui vaut ici exactement le nombre de faits du but (4 landmarks : 1 maitresse + 3 interrupteurs).

// Multi-interrupteurs (Tranche 1 section 7) : BFS from-scratch ET Fast Downward sur le meme probleme.
const int Nfd = 3;
var opsMultiFd = new List<Operator>();
opsMultiFd.Add(new Operator { Name = "allumer_master", Pre = new HashSet<string>(),
    Add = new HashSet<string> { "master_on" }, Del = new HashSet<string> { "master_off" } });
for (int i = 1; i <= Nfd; i++) {
    int idx = i;
    opsMultiFd.Add(new Operator { Name = $"allumer_sw{idx}",
        Pre = new HashSet<string> { "master_on" },
        Add = new HashSet<string> { $"switch_{idx}_on" },
        Del = new HashSet<string> { $"switch_{idx}_off" } });
}
var initMultiFd = new HashSet<string> { "master_off" };
for (int i = 1; i <= Nfd; i++) initMultiFd.Add($"switch_{i}_off");
var goalMultiFd = new HashSet<string> { "master_on" };
for (int i = 1; i <= Nfd; i++) goalMultiFd.Add($"switch_{i}_on");
var planBfsMulti = PlanBFS(initMultiFd, goalMultiFd, opsMultiFd);

var DOMAIN_MULTI = @"(define (domain multi-interrupteurs)
  (:requirements :strips)
  (:predicates (master-on) (master-off) (sw-on ?s) (sw-off ?s))
  (:action master-on :parameters ()
    :precondition (and)
    :effect (and (master-on) (not (master-off))))
  (:action sw-on :parameters (?s)
    :precondition (master-on)
    :effect (and (sw-on ?s) (not (sw-off ?s))))
)";
var PROBLEM_MULTI = @"(define (problem multi-3)
  (:domain multi-interrupteurs)
  (:objects s1 s2 s3)
  (:init (master-off) (sw-off s1) (sw-off s2) (sw-off s3))
  (:goal (and (master-on) (sw-on s1) (sw-on s2) (sw-on s3)))
)";

var (rcM, outM, errM) = RunFd(DOMAIN_MULTI, PROBLEM_MULTI, "astar(lmcut())");
var fdPlanM = FdPlanLines(outM);
int masterPos = fdPlanM.FindIndex(a => a.StartsWith("master-on")) + 1;
Console.WriteLine($"[FD] multi-interrupteurs : returncode = {rcM}");
Console.WriteLine($"[FD] Plan ({fdPlanM.Count} actions) : [{string.Join(" -> ", fdPlanM)}]");
Console.WriteLine($"[FD] h(lmcut) initiale = {FdMetric(outM, @"Initial heuristic value for lmcut:\s*(\d+)")}"
    + $" (= 4 faits du but conjonctif) | etats expanses = {FdMetric(outM, @"Expanded\s+(\d+)\s+state")}");
Console.WriteLine();
Console.WriteLine($"PARITE : BFS = {planBfsMulti!.Count} actions ; FD = {fdPlanM.Count} actions ;"
    + $" 'master-on' en position {masterPos}/{fdPlanM.Count}");
Console.WriteLine(planBfsMulti!.Count == fdPlanM.Count && masterPos == 1
    ? "-> MEME STRUCTURE : maitresse d'abord (precondition chainee), puis les 3 interrupteurs."
    : "-> DIVERGENCE ! (imprevu)");
[FD] multi-interrupteurs : returncode = 0
[FD] Plan (4 actions) : [master-on  (1) -> sw-on s1 (1) -> sw-on s2 (1) -> sw-on s3 (1)]
[FD] h(lmcut) initiale = 4 (= 4 faits du but conjonctif) | etats expanses = 5

PARITE : BFS = 4 actions ; FD = 4 actions ; 'master-on' en position 1/4
-> MEME STRUCTURE : maitresse d'abord (precondition chainee), puis les 3 interrupteurs.

Le problème de livraison — miroir de l’Exemple guide 1 du jumeau Python

Le jumeau Python résout avec unified-planning un problème de livraison (robot rob, colis pkg, de depot vers dest) et obtient le plan optimal 3 actions pick → move → drop. Ce domaine n’existait pas dans la Tranche 1 : c’est l’apport le plus visible du moteur de production — un nouveau domaine = un simple texte PDDL, aucune classe C# à écrire.

// Livraison : nouveau domaine fourni en PDDL seul (aucune classe C# a ecrire).
var DOMAIN_LIV = @"(define (domain livraison)
  (:requirements :strips :typing)
  (:types robot package lieu)
  (:predicates
    (robot-at ?r - robot ?l - lieu) (pkg-at ?p - package ?l - lieu)
    (holding ?r - robot ?p - package) (handempty ?r - robot) (livre ?p - package))
  (:action move :parameters (?r - robot ?from ?to - lieu)
    :precondition (robot-at ?r ?from)
    :effect (and (robot-at ?r ?to) (not (robot-at ?r ?from))))
  (:action pick :parameters (?r - robot ?p - package ?l - lieu)
    :precondition (and (robot-at ?r ?l) (pkg-at ?p ?l) (handempty ?r))
    :effect (and (holding ?r ?p) (not (pkg-at ?p ?l)) (not (handempty ?r))))
  (:action drop :parameters (?r - robot ?p - package ?l - lieu)
    :precondition (and (robot-at ?r ?l) (holding ?r ?p))
    :effect (and (pkg-at ?p ?l) (not (holding ?r ?p)) (handempty ?r) (livre ?p)))
)";
var PROBLEM_LIV = @"(define (problem livraison-1)
  (:domain livraison)
  (:objects rob - robot pkg - package depot dest - lieu)
  (:init (robot-at rob depot) (pkg-at pkg depot) (handempty rob))
  (:goal (and (pkg-at pkg dest) (livre pkg)))
)";

var (rcL, outL, errL) = RunFd(DOMAIN_LIV, PROBLEM_LIV, "astar(lmcut())");
var fdPlanL = FdPlanLines(outL);
Console.WriteLine($"[FD] livraison : returncode = {rcL}");
Console.WriteLine($"[FD] Plan ({fdPlanL.Count} actions) :");
foreach (var a in fdPlanL) Console.WriteLine("    " + a);
Console.WriteLine($"[FD] h(lmcut) initiale = {FdMetric(outL, @"Initial heuristic value for lmcut:\s*(\d+)")}"
    + $" | etats expanses = {FdMetric(outL, @"Expanded\s+(\d+)\s+state")}");
Console.WriteLine();
Console.WriteLine("Miroir du jumeau Python (Exemple guide 1, unified-planning) :");
Console.WriteLine("  PY : Plan optimal trouve (3 actions) : pick(rob,pkg,depot) -> move(rob,depot,dest) -> drop(rob,pkg,dest)");
Console.WriteLine($"  C# : [{string.Join(" -> ", fdPlanL)}]");
Console.WriteLine(fdPlanL.Count == 3
    ? "-> MEME PLAN OPTIMAL 3 actions : pick, move, drop (lmcut admissible => optimalite garantie)."
    : "-> Longueur differente du jumeau Python ! (imprevu)");
[FD] livraison : returncode = 0
[FD] Plan (3 actions) :
    pick rob pkg depot (1)
    move rob depot dest (1)
    drop rob pkg dest (1)
[FD] h(lmcut) initiale = 2 | etats expanses = 4

Miroir du jumeau Python (Exemple guide 1, unified-planning) :
  PY : Plan optimal trouve (3 actions) : pick(rob,pkg,depot) -> move(rob,depot,dest) -> drop(rob,pkg,dest)
  C# : [pick rob pkg depot (1) -> move rob depot dest (1) -> drop rob pkg dest (1)]
-> MEME PLAN OPTIMAL 3 actions : pick, move, drop (lmcut admissible => optimalite garantie).

Interpretation — Tranche 2

  • Mêmes verdicts, deux moteurs : interrupteur (1 action), multi-interrupteurs (4 actions, maitresse en premier) — Fast Downward retrouve exactement les plans de notre BFS from-scratch ; sur la livraison, le même plan optimal 3 actions que le jumeau Python.
  • Ce que le moteur apporte en plus : un nouveau domaine (livraison) = un texte PDDL, zéro classe C# ; lmcut heuristique admissible → plan optimal garanti ; le log expose des métriques (heuristique initiale, états expansés) qui deviennent décisives quand l’espace d’états explose (cf section 8).
  • Ce que la Tranche 1 garde : la compréhension — on sait exactement ce que Fast Downward fait sous le capot (traduire PDDL, ground, chercher), parce qu’on l’a construit à la main.

Conclusion — Tranches 1 et 2

Ce que nous avons appris :

Concept Definition
Planification Generer une sequence d’actions pour atteindre un but
STRIPS Formalisme : etat = predicats, opérateur = pre/add/del
Transition \((S \setminus del) \cup add\) si \(pre \subseteq S\)
BFS planner Recherche en largeur dans l’espace d’etats (plan le plus court)
Explosion combinatoire \(2^n\) etats pour \(n\) predicats → motive les heuristiques
Fast Downward (Tranche 2) moteur PDDL SOTA via API Docker — PDDL standard en entrée, plan optimal A*+lmcut

Lecon cles : un planificateur = une recherche dans l’espace d’etats construit a partir de la sémantique des actions. Le twin Python unified-planning invoque un solveur ; ce twin from-scratch construit le solveur (modèle STRIPS + BFS), puis la Tranche 2 délègue au vrai moteur (Fast Downward) sur les mêmes instances — mêmes plans optimaux, et un nouveau domaine (livraison) en PDDL seul. Comprendre, puis produire.

Suite : PDDL (Planners-2 — le langage standard, ici déjà utilisé en Tranche 2), heuristiques (Planners-5 — A*, relaxations pour combattre l’explosion combinatoire).

Tranche 1 from-scratch (BCL .NET seule, 0 NuGet) + Tranche 2 Fast Downward via API Docker. Twin du notebook Python unified-planning Planners-1-Introduction. Marathon #4956, parité lib-vs-lib Epic #10382.

Retour au sommet