Navigation : << Planners-3 State-Space (C#) | Index | Planners-5 Heuristics (C#) >>
Twin C# (.NET Interactive) de Planners-4-Fast-Downward.ipynb — marathon #4956 (parite .NET <-> Python).
Fast Downward (Helmert 2006, gagnant a plusieurs reprises de l’IPC) est le planificateur de reference de la planification classique. Son architecture se decompose en trois étapes : un translator (PDDL -> SAS+), un preprocessor C++ et un moteur de recherche C++. Ce twin C# rend visibles les internes que le binaire Fast Downward cache : la representation SAS+ (variables multi-valuees), les opérateurs a prevail/precondition/effect, le graphe de plan relaxation (RPG) pour l’heuristique h^FF, et les trois stratégies de recherche A*, Greedy Best-First et Enforced Hill Climbing.
A la fin de ce notebook, vous saurez :
Verdict SOTA (#3801 Prong A). Ce twin C# est un planificateur SAS+ pedagogique from-scratch (SOTA-OK pour le concept du moteur). Le notebook Python Planners-4-Fast-Downward invoque le vrai Fast Downward (IPC winner, Helmert 2006) via Docker +
unified-planning= RECOVERABLE-MACHINE (le solveur reel n’est pas lie a .NET pedagogique). Le twin from-scratch rend visibles les internes (representation SAS+, opérateurs prevail/pre/eff, RPG, EHC) que Fast Downward cache dans son binaire C++ — compagnon pedagogique intentionnel, même pattern que le twin App-19 WFC C#. Implementation en BCL .NET 9 pure, 0 NuGet.
Le translator de Fast Downward convertit un problème PDDL (predicats booléens) en une representation SAS+ (Simplified Action Structures) ou l’etat est un vecteur de variables multi-valuees. C’est le changement de representation fondateur du planificateur.
| PDDL (STRIPS) | SAS+ |
|---|---|
Predicats booléens (on a b) |
Variables multi-valuees on_a = b |
| Etat = ensemble de faits vrais | Etat = Dictionary<var, val> |
| Action = (precond, add, del) | Opérateur = (prevail, pre, eff) |
| Actions parametrees non instantiees | Opérateurs déjà instanties (groundes) |
| Doublons d’encodage | Variables irrelevantes eliminees |
Trois avantages concrets de SAS+ :
ferry_pos{L,R} remplace deux predicats booléens mutuellement exclusifs (ferry_at_L, ferry_at_R). L’etat est un vecteur court, pas un gros ensemble.PDDL (domain + problem)
|
[TRANSLATOR] Python : parse PDDL, construit la tâche SAS+ (variables, domaines, opérateurs)
|
[PREPROCESSOR] C++ : simplifie, elimine variables invariantes, construit le successor generator
|
[SEARCH] C++ : A* / GBFS / EHC avec heuristique (h^max, LM-cut, h^FF, ...)
|
Plan (sequence d'actions)Ce twin C# implemente les trois couches conceptuelles (representation SAS+, heuristique RPG, recherche) en code pedagogique lisible — Fast Downward les optimise en C++ industriel.
#r "Microsoft.DotNet.Interactive"
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using Microsoft.DotNet.Interactive;
static string FI(double x, string fmt = "F4") => x.ToString(fmt, CultureInfo.InvariantCulture);
"Imports OK : System.Linq, Globalization, DotNet.Interactive (BCL .NET 9, 0 NuGet)".Display();Imports OK : System.Linq, Globalization, DotNet.Interactive (BCL .NET 9, 0 NuGet)Un etat SAS+ est un dictionnaire Dictionary<string,int> : chaque variable a une valeur entiere codant son domaine (par ex. ferry_pos = 0 pour left). Un opérateur SAS+ se decompose en trois parties, distinguees par leur rôle causal :
var = val sur des variables que l’opérateur ne modifie pas (elles doivent tenir au moment de l’application et restent invariantes).var -> nouvelle valeur appliquees a l’etat.Separer prevail et pre reflte le fait qu’une variable non modifiée n’a pas besoin d’etre lue-then-written : elle est juste un contexte. C’est une optimisation centrale de SAS+.
// SAS+ : etat = variables multi-valuees. Un operateur a Prevail / Precondition / Effect.
public record SasOperator(
string Name,
Dictionary<string, int> Prevail,
Dictionary<string, int> Precondition,
Dictionary<string, int> Effect,
int Cost = 1);
// Cle canonique d'un etat (pour hash / closed set) : "car1=0;car2=0;car3=0;empty=1;ferry_pos=0".
public static string StateKey(Dictionary<string, int> s) =>
string.Join(";", s.OrderBy(kv => kv.Key).Select(kv => $"{kv.Key}={kv.Value}"));
public static Dictionary<string, int> CloneState(Dictionary<string, int> s) => new(s);
// Un operateur est applicable ssi toutes ses conditions (prevail + pre) tiennent dans l'etat.
public static bool Applicable(Dictionary<string, int> s, SasOperator op)
{
foreach (var (v, val) in op.Prevail)
if (!s.TryGetValue(v, out var sv) || sv != val) return false;
foreach (var (v, val) in op.Precondition)
if (!s.TryGetValue(v, out var sv) || sv != val) return false;
return true;
}
// Appliquer : on n'ecrit que les variables de Effect (prevail reste invariant par construction).
public static Dictionary<string, int> ApplyOp(Dictionary<string, int> s, SasOperator op)
{
var s2 = CloneState(s);
foreach (var (v, val) in op.Effect) s2[v] = val;
return s2;
}
// Le but est atteint si toutes les paires var=val requises sont presentes dans l'etat.
public static bool SatisfiesGoal(Dictionary<string, int> s, Dictionary<string, int> goal) =>
goal.All(kv => s.TryGetValue(kv.Key, out var sv) && sv == kv.Value);
"Structures SAS+ definies : record SasOperator(Prevail/Precondition/Effect), ApplyOp, Applicable, StateKey, SatisfiesGoal.".Display();Structures SAS+ definies : record SasOperator(Prevail/Precondition/Effect), ApplyOp, Applicable, StateKey, SatisfiesGoal.Le translator Fast Downward parse un domaine PDDL et produit un encodage SAS+ equivalent. L’algorithme complet (Helmert 2009) est sophistique : decoupage en invariants mutuels (deux faits jamais vrais simultanement deviennent les valeurs d’une même variable), grounding des opérateurs, detection des variables derivables. Nous n’implementons pas ce pipeline ici — nous hardcodons le résultat de la traduction sur un petit domaine pour illustrer la correspondance.
(:action board :parameters (?c - car ?l - location)
:precondition (and (car-at ?c ?l) (ferry-at ?l) (empty-ferry))
:effect (and (not (car-at ?c ?l)) (car-on-ferry ?c) (not (empty-ferry))))
(:action sail :parameters (?from ?to - location)
:precondition (ferry-at ?from)
:effect (and (not (ferry-at ?from)) (ferry-at ?to)))
(:action debark :parameters (?c - car ?l - location)
:precondition (and (car-on-ferry ?c) (ferry-at ?l))
:effect (and (not (car-on-ferry ?c)) (car-at ?c ?l) (empty-ferry)))Le translator detecte les invariants : car-at_X_left et car-at_X_right et car-on-ferry_X sont mutuellement exclusifs -> une seule variable car_X a 3 valeurs {left, right, on_ferry}. De même ferry-at_left / ferry-at_right -> variable ferry_pos a 2 valeurs, et empty-ferry/not-empty -> variable empty a 2 valeurs.
| Opérateur PDDL | Opérateur SAS+ (prevail / pre / eff) |
|---|---|
board(car1, left) |
prevail {ferry_pos=left, empty=YES} pre {car1=left} eff {car1=on_ferry, empty=NO} |
sail(left, right) |
prevail {} pre {ferry_pos=left} eff {ferry_pos=right} |
debark(car1, right) |
prevail {ferry_pos=right} pre {car1=on_ferry} eff {car1=right, empty=YES} |
L’encodage SAS+ est plus compact (5 variables vs ~10 predicats) et les opérateurs sont déjà instanties (groundes), pret pour la recherche.
// Domaine FERRY encode directement en SAS+ (3 voitures, 2 rives, capacite ferry = 1).
// Valeurs encodees en int. ferry_pos{0=left,1=right}, empty{0=NO,1=YES}, car_i{0=left,1=right,2=CARRIED}.
const int LEFT = 0, RIGHT = 1;
const int EM_NO = 0, EM_YES = 1;
const int CARRIED = 2;
List<SasOperator> FerryOps()
{
var ops = new List<SasOperator>();
string[] cars = { "car1", "car2", "car3" };
string Tag(int side) => side == LEFT ? "L" : "R";
foreach (var car in cars)
{
// board(car, side) : prevail ferry_pos=side, empty=YES ; pre car=side ; eff car=CARRIED, empty=NO.
foreach (var side in new[] { LEFT, RIGHT })
ops.Add(new SasOperator(
$"board({car},{Tag(side)})",
Prevail: new() { ["ferry_pos"] = side, ["empty"] = EM_YES },
Precondition: new() { [car] = side },
Effect: new() { [car] = CARRIED, ["empty"] = EM_NO }));
// debark(car, side) : prevail ferry_pos=side ; pre car=CARRIED ; eff car=side, empty=YES.
foreach (var side in new[] { LEFT, RIGHT })
ops.Add(new SasOperator(
$"debark({car},{Tag(side)})",
Prevail: new() { ["ferry_pos"] = side },
Precondition: new() { [car] = CARRIED },
Effect: new() { [car] = side, ["empty"] = EM_YES }));
}
ops.Add(new SasOperator("sail(L,R)", new(), new() { ["ferry_pos"] = LEFT }, new() { ["ferry_pos"] = RIGHT }));
ops.Add(new SasOperator("sail(R,L)", new(), new() { ["ferry_pos"] = RIGHT }, new() { ["ferry_pos"] = LEFT }));
return ops;
}
var ferryInit = new Dictionary<string, int>
{
["ferry_pos"] = LEFT, ["empty"] = EM_YES,
["car1"] = LEFT, ["car2"] = LEFT, ["car3"] = LEFT,
};
var ferryGoal = new Dictionary<string, int>
{
["car1"] = RIGHT, ["car2"] = RIGHT, ["car3"] = RIGHT,
};
var ferryOps = FerryOps();
var sb = new System.Text.StringBuilder();
sb.AppendLine($"Domaine FERRY (SAS+) : {ferryOps.Count} operateurs, 5 variables multi-valuees.");
sb.AppendLine("Variables : ferry_pos{L,R}, empty{NO,YES}, car1/car2/car3{L,R,CARRIED}");
sb.AppendLine($"Espace d'etats = 2 x 2 x 3 x 3 x 3 = {2 * 2 * 3 * 3 * 3} etats.");
sb.AppendLine($"Etat initial : {StateKey(ferryInit)}");
sb.AppendLine($"But : {StateKey(ferryGoal)}");
sb.AppendLine();
sb.AppendLine("Echantillon d'operateurs SAS+ (prevail / pre / eff) :");
foreach (var op in ferryOps.Where(o => o.Name.StartsWith("board(car1") || o.Name.StartsWith("sail")).Take(3))
{
string Fmt(Dictionary<string, int> d) => string.Join(",", d.OrderBy(kv => kv.Key).Select(kv => $"{kv.Key}={kv.Value}"));
sb.AppendLine($" {op.Name,-16} prevail={{{Fmt(op.Prevail)}}} pre={{{Fmt(op.Precondition)}}} eff={{{Fmt(op.Effect)}}}");
}
sb.ToString().Display();Domaine FERRY (SAS+) : 14 operateurs, 5 variables multi-valuees.
Variables : ferry_pos{L,R}, empty{NO,YES}, car1/car2/car3{L,R,CARRIED}
Espace d'etats = 2 x 2 x 3 x 3 x 3 = 108 etats.
Etat initial : car1=0;car2=0;car3=0;empty=1;ferry_pos=0
But : car1=1;car2=1;car3=1
Echantillon d'operateurs SAS+ (prevail / pre / eff) :
board(car1,L) prevail={empty=1,ferry_pos=0} pre={car1=0} eff={car1=2,empty=0}
board(car1,R) prevail={empty=1,ferry_pos=1} pre={car1=1} eff={car1=2,empty=0}
sail(L,R) prevail={} pre={ferry_pos=0} eff={ferry_pos=1}Observations :
| Aspect | Valeur | Signification |
|---|---|---|
| Variables | 5 ( ferry_pos, empty, car1, car2, car3 ) | vecteur compact vs ~10 predicats PDDL |
| Opérateurs | 14 (6 board + 6 debark + 2 sail) | déjà groundes, instanties par (car, side) |
| Espace d’etats | 108 | 2 x 2 x 3 x 3 x 3 — petit, soluble exactement |
| Prevail distinct de pre | board a prevail ferry_pos, empty (non modifiés) + pre car1 (modifie) |
reflete la structure causale |
Plan optimal théorique : pour n voitures, capacite 1, ferry du cote de depart, le plan compte 3n + (n-1) = 4n - 1 actions (n cycles board-sail-debark + n-1 sail-retour, sauf après la dernière). Pour n=3 -> 11 actions. C’est ce qu’A* doit retrouver.
Les trois recherches ci-dessous ont besoin d’une heuristique h(s) estimant le cout restant. On construit le graphe de plan relaxation (RPG) : on ignore les effets de suppression (delete-relaxation), et on propage les faits couche par couche. Dans le monde relaxe, le nombre de faits vrais ne fait que croitre — le problème devient polynomial.
Projection SAS+ -> atomes : la relaxation est plus simple a raisonner sur des propositions booleennes independantes. On projette chaque paire (var=val) en un atome string "var=val". L’opérateur SAS+ devient un opérateur STRIPS relaxe (pre-atomes, add-atomes). C’est la reduction standard (Bonet & Geffner 2001) ; elle est admissible pour h^max car la relaxation est un sur-ensemble de l’atteignabilite reelle.
cost(fact) = min_a [ cost(a) + max_{p in pre(a)} cost(p) ], puis h^max = max_{g in goal} cost(g). Minore le cout optimal -> A* avec h^max est optimal.h^FF = nombre d'actions du plan relaxe. C’est l’heuristique de reference pour la planification satisficing (Hoffmann & Nebel 2001).Le detail des propagations (point fixe, double-compte de h^add vs max) est dans Planners-5-Heuristics-Csharp ; ici on reutilise la même mecanique, adaptee a la projection d’atomes SAS+.
// Heuristiques par relaxation de suppression sur SAS+ (projection en atomes).
// Chaque paire (var=val) devient un atome string "var=val". L'operateur relaxe = (pre-atomes, add-atomes).
public static HashSet<string> StateAtoms(Dictionary<string, int> s) =>
s.Select(kv => $"{kv.Key}={kv.Value}").ToHashSet();
public static (HashSet<string> pre, HashSet<string> add) RelaxedOp(SasOperator op)
{
var pre = new HashSet<string>();
foreach (var (v, val) in op.Prevail) pre.Add($"{v}={val}");
foreach (var (v, val) in op.Precondition) pre.Add($"{v}={val}");
var add = new HashSet<string>();
foreach (var (v, val) in op.Effect) add.Add($"{v}={val}");
return (pre, add);
}
// h^max : propagation point-fixe, h = max des couts des atomes du but. ADMISSIBLE -> A* optimal.
public static int HMaxSas(List<SasOperator> ops, Dictionary<string, int> goal, Dictionary<string, int> state)
{
var relaxed = ops.Select(RelaxedOp).ToList();
var goalAtoms = goal.Select(kv => $"{kv.Key}={kv.Value}").ToHashSet();
var cost = new Dictionary<string, int>();
foreach (var a in StateAtoms(state)) cost[a] = 0;
bool changed = true; int iter = 0;
while (changed && iter++ < 1000)
{
changed = false;
foreach (var (pre, add) in relaxed)
if (pre.All(p => cost.ContainsKey(p)))
{
int c = (pre.Count == 0 ? 0 : pre.Max(p => cost[p])) + 1;
foreach (var a in add)
if (!cost.ContainsKey(a) || cost[a] > c) { cost[a] = c; changed = true; }
}
}
if (goalAtoms.All(g => cost.ContainsKey(g))) return goalAtoms.Max(g => cost[g]);
return int.MaxValue;
}
// h^FF : graphe de relaxation + extraction gloutonne d'un plan relaxe depuis le but. Non admissible.
public static int HFFSas(List<SasOperator> ops, Dictionary<string, int> goal, Dictionary<string, int> state)
{
var relaxed = ops.Select(RelaxedOp).ToList();
var goalAtoms = goal.Select(kv => $"{kv.Key}={kv.Value}").ToHashSet();
var initState = StateAtoms(state);
var cost = new Dictionary<string, int>();
var achiever = new Dictionary<string, (HashSet<string> pre, HashSet<string> add)>();
foreach (var a in initState) cost[a] = 0;
bool changed = true;
while (changed)
{
changed = false;
foreach (var ro in relaxed)
if (ro.pre.All(p => cost.ContainsKey(p)))
{
int c = (ro.pre.Count == 0 ? 0 : ro.pre.Sum(p => cost[p])) + 1;
foreach (var a in ro.add)
if (!cost.ContainsKey(a) || cost[a] > c) { cost[a] = c; achiever[a] = ro; changed = true; }
}
}
if (!goalAtoms.All(g => cost.ContainsKey(g))) return int.MaxValue;
// Extraction gloutonne : on remonte les achievers depuis le but.
var plan = new HashSet<(HashSet<string>, HashSet<string>)>();
var done = new HashSet<string>();
var stack = new Stack<string>(goalAtoms);
int guard = 0;
while (stack.Count > 0 && guard++ < 10000)
{
var f = stack.Pop();
if (done.Contains(f) || initState.Contains(f)) continue;
done.Add(f);
if (achiever.TryGetValue(f, out var ro))
{
plan.Add(ro);
foreach (var p in ro.pre) stack.Push(p);
}
}
return plan.Count;
}
var sb = new System.Text.StringBuilder();
sb.AppendLine($"h^max(Ferry init) = {HMaxSas(ferryOps, ferryGoal, ferryInit)} (admissible : minore h*)");
sb.AppendLine($"h^FF (Ferry init) = {HFFSas(ferryOps, ferryGoal, ferryInit)} (informatif : guide GBFS/EHC)");
sb.AppendLine();
sb.AppendLine("Lecture : h^max est faible (les 3 voitures partagent le ferry dans la relaxation) ;");
sb.AppendLine("h^FF compte un plan relaxe de 7 actions (board x3 + sail + debark x3, les 2 sail-retour economises).");
sb.ToString().Display();h^max(Ferry init) = 2 (admissible : minore h*)
h^FF (Ferry init) = 7 (informatif : guide GBFS/EHC)
Lecture : h^max est faible (les 3 voitures partagent le ferry dans la relaxation) ;
h^FF compte un plan relaxe de 7 actions (board x3 + sail + debark x3, les 2 sail-retour economises).A* ordonne la frontiere par f(n) = g(n) + h(n) ou g est le cout accumule depuis l’initial et h l’estimation restante. Avec une heuristique admissible (ici h^max), A* est garanti de retourner le plan de cout optimal. On l’implemente avec la PriorityQueue .NET 9 ; les etats sont identifies par leur cle canonique (StateKey).
// A* sur SAS+ : f = g + h. Optimal si h admissible (on branche h^max dessus).
public static (List<string> plan, int cost, int nodesExpanded) AStarSas(
Dictionary<string, int> init, Dictionary<string, int> goal, List<SasOperator> ops,
Func<Dictionary<string, int>, int> h)
{
var frontier = new PriorityQueue<string, int>();
string iKey = StateKey(init);
frontier.Enqueue(iKey, h(init));
var gScore = new Dictionary<string, int> { [iKey] = 0 };
var stateOf = new Dictionary<string, Dictionary<string, int>> { [iKey] = init };
var cameFrom = new Dictionary<string, (string parent, string op)>();
var closed = new HashSet<string>();
int nodes = 0;
while (frontier.Count > 0)
{
frontier.TryDequeue(out var curKey, out _);
if (closed.Contains(curKey)) continue;
closed.Add(curKey);
var cur = stateOf[curKey];
nodes++;
if (SatisfiesGoal(cur, goal))
{
var plan = new List<string>();
var k = curKey;
while (cameFrom.ContainsKey(k)) { plan.Add(cameFrom[k].op); k = cameFrom[k].parent; }
plan.Reverse();
return (plan, gScore[curKey], nodes);
}
foreach (var op in ops.Where(o => Applicable(cur, o)))
{
var next = ApplyOp(cur, op);
string nKey = StateKey(next);
if (closed.Contains(nKey)) continue;
int tentative = gScore[curKey] + op.Cost;
if (tentative < gScore.GetValueOrDefault(nKey, int.MaxValue))
{
gScore[nKey] = tentative;
stateOf[nKey] = next;
cameFrom[nKey] = (curKey, op.Name);
frontier.Enqueue(nKey, tentative + h(next)); // f = g + h
}
}
}
return (new(), -1, nodes);
}
var (planA, costA, nodesA) = AStarSas(ferryInit, ferryGoal, ferryOps, s => HMaxSas(ferryOps, ferryGoal, s));
var sb = new System.Text.StringBuilder();
sb.AppendLine($"A* (h^max) sur Ferry : cout={costA}, noeuds expanses={nodesA}, longueur plan={planA.Count}");
sb.AppendLine($"Plan optimal : [{string.Join(", ", planA)}]");
sb.ToString().Display();A* (h^max) sur Ferry : cout=11, noeuds expanses=37, longueur plan=11
Plan optimal : [board(car1,L), sail(L,R), debark(car1,R), sail(R,L), board(car3,L), sail(L,R), debark(car3,R), sail(R,L), board(car2,L), sail(L,R), debark(car2,R)]GBFS ordonne la frontiere par h(n) uniquement (le cout g accumule est ignore). Cela pousse la recherche droit vers le but estime — beaucoup plus rapide en pratique, mais sans garantie d’optimalite. On la branche sur h^FF, l’heuristique la plus informative pour la planification satisficing.
// Greedy Best-First Search : priorite = h uniquement. Rapide, NON optimal.
public static (List<string> plan, int cost, int nodesExpanded) GBFSSas(
Dictionary<string, int> init, Dictionary<string, int> goal, List<SasOperator> ops,
Func<Dictionary<string, int>, int> h)
{
var frontier = new PriorityQueue<string, int>();
string iKey = StateKey(init);
frontier.Enqueue(iKey, h(init));
var gScore = new Dictionary<string, int> { [iKey] = 0 };
var stateOf = new Dictionary<string, Dictionary<string, int>> { [iKey] = init };
var cameFrom = new Dictionary<string, (string parent, string op)>();
var closed = new HashSet<string>();
int nodes = 0;
while (frontier.Count > 0)
{
frontier.TryDequeue(out var curKey, out _);
if (closed.Contains(curKey)) continue;
closed.Add(curKey);
var cur = stateOf[curKey];
nodes++;
if (SatisfiesGoal(cur, goal))
{
var plan = new List<string>();
var k = curKey;
while (cameFrom.ContainsKey(k)) { plan.Add(cameFrom[k].op); k = cameFrom[k].parent; }
plan.Reverse();
return (plan, gScore[curKey], nodes);
}
foreach (var op in ops.Where(o => Applicable(cur, o)))
{
var next = ApplyOp(cur, op);
string nKey = StateKey(next);
if (closed.Contains(nKey)) continue;
int tentative = gScore[curKey] + op.Cost;
if (tentative < gScore.GetValueOrDefault(nKey, int.MaxValue))
{
gScore[nKey] = tentative;
stateOf[nKey] = next;
cameFrom[nKey] = (curKey, op.Name);
frontier.Enqueue(nKey, h(next)); // f = h seul (greedy)
}
}
}
return (new(), -1, nodes);
}
var (planG, costG, nodesG) = GBFSSas(ferryInit, ferryGoal, ferryOps, s => HFFSas(ferryOps, ferryGoal, s));
var sb = new System.Text.StringBuilder();
sb.AppendLine($"GBFS (h^FF) sur Ferry : cout={costG}, noeuds expanses={nodesG}, longueur plan={planG.Count}");
sb.AppendLine($"Plan : [{string.Join(", ", planG)}]");
sb.ToString().Display();GBFS (h^FF) sur Ferry : cout=11, noeuds expanses=12, longueur plan=11
Plan : [board(car1,L), sail(L,R), debark(car1,R), sail(R,L), board(car2,L), sail(L,R), debark(car2,R), sail(R,L), board(car3,L), sail(L,R), debark(car3,R)]EHC (Hoffmann & Nebel 2001) est l’algorithme distinctif de ce notebook : il n’apparait ni dans Planners-3 (state-space generique) ni dans Planners-5 (heuristiques pures). C’est le coeur du planificateur FF.
Principe : EHC ne maintient pas de frontiere globale. A chaque étape, depuis l’etat courant, il fait une BFS a la recherche d’un etat de heuristique strictement inferieure. Des qu’il en trouve un, il commit tout le chemin (toutes les actions intermediaires) vers cet etat ameliorant, puis recommence depuis la. Si la BFS epuise tout l’espace reachable sans trouver d’ameliorant, EHC echoue (ou, dans le FF complet, bascule sur GBFS en fallback).
current = initial ; plan = []
tant que h(current) > 0 :
(trouve, chemin, noeuds) = BFS-pour-un-etat-strictement-mieux-que-h(current)
si non trouve : retourner ECHEC
appliquer chemin a current ; plan += chemin
retourner planL’idee : h^FF est souvent parfaitement informative sur les problemes faciles — la BFS trouve un ameliorant a faible profondeur, et EHC descend en escalier vers le but en très peu de noeuds expanses. Sur les problemes ou h^FF a des plateaux ou des minima locaux, EHC peut en revanche echouer la ou A* (avec replan complet) reussit.
// Enforced Hill Climbing : a chaque pas, BFS depuis current vers un etat strictement meilleur ;
// on commit le chemin et on recommence. Si aucun ameliorant accessible : ECHEC.
public static (List<string> plan, int cost, int nodesExpanded, bool success) EHCSas(
Dictionary<string, int> init, Dictionary<string, int> goal, List<SasOperator> ops,
Func<Dictionary<string, int>, int> h)
{
var plan = new List<string>();
int nodes = 0;
var current = CloneState(init);
int hCur = h(current);
int guard = 0;
while (hCur > 0 && hCur < int.MaxValue && guard++ < 100000)
{
var (found, path, bfsNodes) = BfsImprove(current, hCur, ops, h);
nodes += bfsNodes;
if (!found) return (plan, -1, nodes, false); // bloque : aucun ameliorant accessible
foreach (var opName in path)
{
var op = ops.First(o => o.Name == opName);
current = ApplyOp(current, op);
plan.Add(opName);
}
hCur = h(current);
}
bool ok = hCur == 0 && SatisfiesGoal(current, goal);
return (plan, ok ? plan.Count : -1, nodes, ok);
}
// BFS cherchant un etat de heuristique strictement inferieure a hTarget (depuis start).
static (bool found, List<string> path, int nodes) BfsImprove(
Dictionary<string, int> start, int hTarget, List<SasOperator> ops, Func<Dictionary<string, int>, int> h)
{
string sKey = StateKey(start);
var q = new Queue<string>(); q.Enqueue(sKey);
var stateOf = new Dictionary<string, Dictionary<string, int>> { [sKey] = start };
var cameFrom = new Dictionary<string, (string parent, string op)>();
var seen = new HashSet<string> { sKey };
int nodes = 0;
while (q.Count > 0)
{
var ck = q.Dequeue();
var cur = stateOf[ck];
nodes++;
foreach (var op in ops.Where(o => Applicable(cur, o)))
{
var next = ApplyOp(cur, op);
var nk = StateKey(next);
if (seen.Contains(nk)) continue;
seen.Add(nk); stateOf[nk] = next; cameFrom[nk] = (ck, op.Name);
if (h(next) < hTarget)
{
var path = new List<string>();
var k = nk;
while (cameFrom.ContainsKey(k)) { path.Add(cameFrom[k].op); k = cameFrom[k].parent; }
path.Reverse();
return (true, path, nodes);
}
q.Enqueue(nk);
}
}
return (false, new List<string>(), nodes);
}
var (planE, costE, nodesE, okE) = EHCSas(ferryInit, ferryGoal, ferryOps, s => HFFSas(ferryOps, ferryGoal, s));
var sb = new System.Text.StringBuilder();
sb.AppendLine($"EHC (h^FF) sur Ferry : succes={okE}, cout={costE}, noeuds expanses={nodesE}, longueur plan={planE.Count}");
if (okE) sb.AppendLine($"Plan : [{string.Join(", ", planE)}]");
else sb.AppendLine("(EHC bloque : aucun etat ameliorant accessible — EHC tombe dans un plateau/minimum local de h^FF.)");
sb.ToString().Display();EHC (h^FF) sur Ferry : succes=True, cout=11, noeuds expanses=15, longueur plan=11
Plan : [board(car1,L), sail(L,R), debark(car1,R), sail(R,L), board(car2,L), sail(L,R), debark(car2,R), sail(R,L), board(car3,L), sail(L,R), debark(car3,R)]L’EHC ci-dessus explore tout le sous-espace reachable a chaque phase (BFS illimitee). Sur de gros domaines, cela coute cher. Implementez une variante bornee : la BFS s’arrete a une profondeur maxDepth donnee ; si aucun ameliorant trouve dans cette profondeur, on retourne ECHEC (ou on bascule en BFS complete).
Indices : ajoutez un paramètre maxDepth a BfsImprove ; suivez la profondeur dans la queue (file de tuples (stateKey, depth)) ; ne detronque pas la condition d’amelioration h(next) < hTarget.
// Exercice 1 : EHC avec BFS de profondeur bornee.
// TODO etudiant : implementer EHCDepthBounded en limitant la profondeur d'exploration de chaque phase.
// Indice : modifier BfsImprove pour suivre (key, depth) et stopper l'enqueue au-dela de maxDepth.
// Etape 1 : ajouter maxDepth a la signature.
// Etape 2 : propager la profondeur dans la queue.
// Etape 3 : si aucune amelioration trouvee dans la profondeur -> retourner (false).
public static (List<string> plan, int cost, int nodesExpanded, bool success) EHCDepthBounded(
Dictionary<string, int> init, Dictionary<string, int> goal, List<SasOperator> ops,
Func<Dictionary<string, int>, int> h, int maxDepth)
{
return (new List<string>(), -1, 0, false); // TODO etudiant
}
"Exercice 1 (EHC borne en profondeur) a completer.".Display();Exercice 1 (EHC borne en profondeur) a completer.On execute les trois recherches sur le même problème Ferry et on compare : cout du plan, optimalite (par rapport au cout trouve par A* + h^max admissible), nombre de noeuds expanses. C’est le punchline pedagogique — trois stratégies très différentes pour le même planificateur sous-jacent.
// Comparaison sur le meme probleme Ferry. A* (h^max) = reference optimale.
string gOpt = costG == costA ? "OUI" : "NON";
string eCost = costE > 0 ? costE.ToString() : "ECHEC";
string eOpt = !okE ? "ECHEC" : (costE == costA ? "OUI" : "NON");
int eLen = costE > 0 ? planE.Count : 0;
var sb = new System.Text.StringBuilder();
sb.AppendLine("=== Comparaison A* (h^max) / GBFS (h^FF) / EHC (h^FF) sur Ferry (3 voitures) ===");
sb.AppendLine($"{"Algo",-6} {"Heur.",-7} {"Cout",-6} {"Optimal",-9} {"Noeuds",-8} {"Plan(len)"}");
sb.AppendLine(new string('-', 50));
sb.AppendLine($"{"A*",-6} {"h^max",-7} {costA,-6} {"OUI",-9} {nodesA,-8} {planA.Count}");
sb.AppendLine($"{"GBFS",-6} {"h^FF",-7} {costG,-6} {gOpt,-9} {nodesG,-8} {planG.Count}");
sb.AppendLine($"{"EHC",-6} {"h^FF",-7} {eCost,-6} {eOpt,-9} {nodesE,-8} {eLen}");
sb.AppendLine();
sb.AppendLine($"h* (cout optimal, garanti par A* + h^max admissible) = {costA}.");
sb.AppendLine($"Plan optimal theorique pour 3 voitures : 4*3 - 1 = 11 actions (cf §3).");
sb.ToString().Display();=== Comparaison A* (h^max) / GBFS (h^FF) / EHC (h^FF) sur Ferry (3 voitures) ===
Algo Heur. Cout Optimal Noeuds Plan(len)
--------------------------------------------------
A* h^max 11 OUI 37 11
GBFS h^FF 11 OUI 12 11
EHC h^FF 11 OUI 15 11
h* (cout optimal, garanti par A* + h^max admissible) = 11.
Plan optimal theorique pour 3 voitures : 4*3 - 1 = 11 actions (cf §3).Résultats observes (exécution reelle ci-dessus) :
| Algorithme | Heuristique | Cout | Optimal | Noeuds expanses |
|---|---|---|---|---|
| A* (h^max) | h^max (admissible) | 11 | OUI (garanti) | 37 |
| GBFS (h^FF) | h^FF | 11 | OUI (sur cette instance) | 12 |
| EHC (h^FF) | h^FF | 11 | OUI (sur cette instance) | 15 |
Lecture : sur le Ferry, h^FF est suffisamment informative pour que GBFS et EHC trouvent aussi le plan optimal (11 actions), tout en expansant environ 3 fois moins de noeuds qu’A*. A* paie le cout de l’optimalite garantie : il prouve qu’aucun plan plus court n’existe en rouvrant davantage d’etats (37).
Auto-correction G.1. Une première version de cette interpretation affirmait que EHC expansait le moins de noeuds des trois. L’exécution reelle infirme : sur cette instance, c’est GBFS (12 noeuds) qui en expansse le moins, devant EHC (15). La predominance “EHC = le plus rapide” est une tendance générale (EHC ne maintient pas de closed set global entre phases), pas une garantie sur chaque instance. Verifie contre l’output, corrige.
Generalisation : la différence d’optimalite s’observe sur des domaines ou h^FF presente des plateaux (Logistics a plus de colis, Satellite). Sur les petits domaines ou h^FF est quasi parfait, les trois stratégies convergent vers l’optimal — cf §9 Logistics.
Le domaine Gripper (IPC canonique) : un robot a deux pinces (left, right) et doit deplacer des balles entre deux pieces. Chaque pince tient au plus une balle. Encodez ce domaine en SAS+ et resolvez-le avec A*.
Indices / suggestions de variables : robot{roomA, roomB}, gripperL{free, ball1, ball2}, gripperR{free, ball1, ball2}, ball_i{roomA, roomB}. Opérateurs : pick(ball, room, gripper), drop(ball, room, gripper), move(A,B), move(B,A). Inspirez-vous de FerryOps() pour la structure prevail/pre/eff.
// Exercice 2 : encoder GRIPPER en SAS+ (2 pinces, N balles, 2 pieces).
// TODO etudiant : implementer GripperOps() + un probleme (balles en A, but en B), puis resoudre par A*.
// Indice : une pince est une variable multi-valuee {free, ball1, ball2, ...}.
// Etape 1 : definir les operateurs pick/drop/move avec prevail/pre/eff.
// Etape 2 : construire l'etat initial (robot en A, pinces libres, balles en A) et le but (balles en B).
// Etape 3 : appeler AStarSas(...) et verifier le plan.
public static List<SasOperator> GripperOps()
{
return new List<SasOperator>(); // TODO etudiant
}
"Exercice 2 (Gripper en SAS+) a completer.".Display();Exercice 2 (Gripper en SAS+) a completer.Pour illustrer le translator sur un second domaine, encodons Logistics : 1 camion transporte 2 colis entre 2 lieux (A, B). Le camion a capacite illimitee (modèle simplifie — ajouter une capacite est un exercice classique). Le translator PDDL -> SAS+ donnerait :
| Variable SAS+ | Domaine | Sens |
|---|---|---|
truck |
{A, B} | position du camion |
pkg1 |
{A, B, in_truck} | ou est le colis 1 |
pkg2 |
{A, B, in_truck} | ou est le colis 2 |
Espace d’etats = 2 x 3 x 3 = 18 etats. Problème : camion, pkg1, pkg2 tous en A ; but : pkg1 et pkg2 en B. Plan optimal attendu : load(pkg1,A), load(pkg2,A), drive(A,B), unload(pkg1,B), unload(pkg2,B) = 5 actions.
// Domaine LOGISTICS en SAS+ : 1 camion (capacite illimitee), 2 colis, 2 lieux (A,B).
// Variables : truck{A,B}, pkg1{A,B,in_truck}, pkg2{A,B,in_truck}.
const int LOC_A = 0, LOC_B = 1, IN_TRUCK = 2;
List<SasOperator> LogisticsOps()
{
var ops = new List<SasOperator>();
ops.Add(new SasOperator("drive(A,B)", new(), new() { ["truck"] = LOC_A }, new() { ["truck"] = LOC_B }));
ops.Add(new SasOperator("drive(B,A)", new(), new() { ["truck"] = LOC_B }, new() { ["truck"] = LOC_A }));
foreach (var pkg in new[] { "pkg1", "pkg2" })
foreach (var loc in new[] { LOC_A, LOC_B })
{
string tag = loc == LOC_A ? "A" : "B";
// load(pkg, loc) : prevail truck=loc ; pre pkg=loc ; eff pkg=in_truck.
ops.Add(new SasOperator($"load({pkg},{tag})",
Prevail: new() { ["truck"] = loc }, Precondition: new() { [pkg] = loc },
Effect: new() { [pkg] = IN_TRUCK }));
// unload(pkg, loc) : prevail truck=loc ; pre pkg=in_truck ; eff pkg=loc.
ops.Add(new SasOperator($"unload({pkg},{tag})",
Prevail: new() { ["truck"] = loc }, Precondition: new() { [pkg] = IN_TRUCK },
Effect: new() { [pkg] = loc }));
}
return ops;
}
var logInit = new Dictionary<string, int> { ["truck"] = LOC_A, ["pkg1"] = LOC_A, ["pkg2"] = LOC_A };
var logGoal = new Dictionary<string, int> { ["pkg1"] = LOC_B, ["pkg2"] = LOC_B };
var logOps = LogisticsOps();
var (planLA, costLA, nodesLA) = AStarSas(logInit, logGoal, logOps, s => HMaxSas(logOps, logGoal, s));
var (planLE, costLE, nodesLE, okLE) = EHCSas(logInit, logGoal, logOps, s => HFFSas(logOps, logGoal, s));
var (planLG, costLG, nodesLG) = GBFSSas(logInit, logGoal, logOps, s => HFFSas(logOps, logGoal, s));
var sb = new System.Text.StringBuilder();
sb.AppendLine($"Logistics (SAS+) : 3 variables, {logOps.Count} operateurs, espace = 2 x 3 x 3 = {2 * 3 * 3} etats.");
sb.AppendLine($"Probleme : truck + pkg1 + pkg2 en A ; but pkg1 et pkg2 en B.");
sb.AppendLine();
sb.AppendLine($"A* (h^max) : cout={costLA}, noeuds={nodesLA}");
sb.AppendLine($" plan : [{string.Join(", ", planLA)}]");
sb.AppendLine($"GBFS(h^FF) : cout={costLG}, noeuds={nodesLG}, longueur={planLG.Count}");
sb.AppendLine($"EHC (h^FF) : succes={okLE}, cout={costLE}, noeuds={nodesLE}");
sb.AppendLine();
sb.AppendLine($"Cout optimal attendu = 5 : load(pkg1,A), load(pkg2,A), drive(A,B), unload(pkg1,B), unload(pkg2,B).");
sb.ToString().Display();Logistics (SAS+) : 3 variables, 10 operateurs, espace = 2 x 3 x 3 = 18 etats.
Probleme : truck + pkg1 + pkg2 en A ; but pkg1 et pkg2 en B.
A* (h^max) : cout=5, noeuds=10
plan : [load(pkg1,A), load(pkg2,A), drive(A,B), unload(pkg2,B), unload(pkg1,B)]
GBFS(h^FF) : cout=5, noeuds=6, longueur=5
EHC (h^FF) : succes=True, cout=5, noeuds=5
Cout optimal attendu = 5 : load(pkg1,A), load(pkg2,A), drive(A,B), unload(pkg1,B), unload(pkg2,B).Sur ce petit domaine, A*, GBFS et EHC convergent vers le même plan optimal de 5 actions : la structure est tellement simple que les trois stratégies convergent. On notera toutefois que sur cette instance precise, h^FF est exactement egal a h* (le plan relaxe coincide avec le plan reel : pas d’interaction cachee) — EHC descend donc en escalier direct, une action par phase (5 phases, 5 noeuds expanses).
Ce que le translator apporte ici : en passant des predicats PDDL (at pkg1 A) / (at pkg1 B) / (in pkg1 truck) a une seule variable pkg1{A, B, in_truck}, l’encodage elimine les etats impossibles (pkg1 ne peut pas etre simultanement en A et dans le camion) et compactifie la representation.
Comparez les deux heuristiques comme fonction de guidage pour A* sur le domaine Ferry. A* + h^max est optimal (h^max admissible) mais h^max est faible ; A* + h^FF n’est pas garanti optimal (h^FF non admissible) mais explore généralement beaucoup moins de noeuds. Quantifiez le trade-off.
Indices : appelez AStarSas(ferryInit, ferryGoal, ferryOps, s => HFFSas(...)) et comparez nodesA (h^max) au nombre de noeuds avec h^FF. Comparez aussi les couts — A* + h^FF peut retourner un plan non optimal (cout potentiellement superieur a costA).
// Exercice 3 : comparer h^max vs h^FF comme guidage de A* sur Ferry.
// TODO etudiant : executer AStarSas avec h = HFFSas (non admissible), noter le nombre de noeuds et le cout,
// et comparer a A* + h^max (cout optimal).
// Indice : A* + h^FF n'est PAS garanti optimal mais explore generalement moins de noeuds.
// Etape 1 : var (planAFF, costAFF, nodesAFF) = AStarSas(..., s => HFFSas(...));
// Etape 2 : comparer nodesAFF vs nodesA, et costAFF vs costA.
public static (int nodesHMax, int nodesHFF, int costHMax, int costHFF) CompareAStarHeuristics()
{
return (0, 0, 0, 0); // TODO etudiant
}
"Exercice 3 (h^max vs h^FF en A*) a completer.".Display();Exercice 3 (h^max vs h^FF en A*) a completer.La Tranche 1 (cells 4-24) implemente l’integralite de la chaine de planification classique from-scratch en C# : representation SAS+, heuristiques \(h^{max}\) / \(h^{FF}\) par relaxation de planning graph, et trois strategies de recherche (A* optimal, GBFS satisficing, EHC). C’est volontairement pedagogique — on voit chaque rouage. Mais en production, on delegue cette chaine a un moteur SOTA : Fast Downward (Helmert 2006), le planner qui domine les IPC (International Planning Competition) depuis 2008.
L’asymetrie engine que cette Tranche 2 resout : le jumeau Python (cellule 18) delegue deja a Fast Downward via une API Docker HTTP ; le C# n’invoquait aucun moteur de production. On comble l’ecart via System.Net.Http.HttpClient — le C# atteint le MEME moteur (parite lib-vs-lib), sans installation de binaire natif (le conteneur Docker coursia-fast-downward expose l’API sur le port 8200, reusable par les deux langages).
Pourquoi PDDL ici alors que la Tranche 1 utilise SAS+ ? C’est precisement le point : SAS+ est la representation interne de Fast Downward, et la Tranche 1 fait a la main la translation domaine \(\to\) SAS+ (cellule 6 pour Ferry, cellule 24 pour Logistics). Fast Downward automatise cette translation : on lui fournit le domaine en PDDL standard (STRIPS), et il fait lui-meme (i) la translation PDDL \(\to\) SAS+, (ii) le grounding, (iii) la recherche avec une heuristic admissible (\(lmcut\) = landmark-cut) qui garantit un plan optimal.
Test falsifiable : le C# invoque-t-il bien le moteur de production, et obtient-il un plan correct (cout minimal) sur une instance PDDL canonique (Blocks World, “empiler A sur B”) ?
// === Tranche 2 : Fast Downward via API Docker (moteur PDDL de production, .NET natif) ===
// La Tranche 1 (cells 4-24) encode le domaine directement en SAS+ et implemente A*/GBFS/EHC
// from-scratch. Ici on delegue au VRAI Fast Downward -- le moteur PDDL SOTA -- expose via une
// API Docker HTTP (conteneur coursia-fast-downward, port 8200), la MEME approche que le jumeau
// Python (cellule 18). Le domaine est fourni en PDDL standard (STRIPS) : FD fait lui-meme la
// translation PDDL -> SAS+ (l'etape que la Tranche 1 fait a la main).
using System;
using System.Collections.Generic;
using System.Net.Http;
using System.Text;
using System.Text.Json;
using System.Text.RegularExpressions;
// Domaine Blocks World en PDDL (STRIPS) -- 4 actions : pick-up, put-down, stack, unstack
var DOMAIN_BLOCKS_FD = @"(define (domain blocks)
(:requirements :strips :typing)
(:types block)
(:predicates
(on ?x - block ?y - block) (ontable ?x - block) (clear ?x - block)
(handempty) (holding ?x - block))
(:action pick-up :parameters (?x - block)
:precondition (and (clear ?x) (ontable ?x) (handempty))
:effect (and (not (ontable ?x)) (not (clear ?x)) (not (handempty)) (holding ?x)))
(:action put-down :parameters (?x - block)
:precondition (holding ?x)
:effect (and (not (holding ?x)) (clear ?x) (handempty) (ontable ?x)))
(:action stack :parameters (?x - block ?y - block)
:precondition (and (holding ?x) (clear ?y))
:effect (and (not (holding ?x)) (not (clear ?y)) (clear ?x) (handempty) (on ?x ?y)))
(:action unstack :parameters (?x - block ?y - block)
:precondition (and (on ?x ?y) (clear ?x) (handempty))
:effect (and (not (on ?x ?y)) (not (clear ?x)) (not (handempty)) (holding ?x) (clear ?y)))
)";
// Probleme : empiler A sur B. Init : A, B sur la table, bras vide. Goal : on a b.
var PROBLEM_BLOCKS_FD = @"(define (problem blocks-simple)
(:domain blocks)
(:objects a b - block)
(:init (ontable a) (ontable b) (clear a) (clear b) (handempty))
(:goal (on a b))
)";
Console.WriteLine("Tranche 2 : Fast Downward via API Docker (moteur PDDL de production)");
Console.WriteLine("Domaine PDDL : blocks (STRIPS, 4 actions). Probleme : empiler A sur B.");
Console.WriteLine("Recherche : A* + heuristic admissible lmcut (landmark-cut) -> plan OPTIMAL.");
Console.WriteLine();
var payload = JsonSerializer.Serialize(new {
domain = DOMAIN_BLOCKS_FD, problem = PROBLEM_BLOCKS_FD, search = "astar(lmcut())" });
Console.WriteLine("[FD] POST http://localhost:8200/plan (" + payload.Length + " octets)");
var http = new HttpClient { Timeout = TimeSpan.FromSeconds(30) };
var resp = http.PostAsync("http://localhost:8200/plan",
new StringContent(payload, Encoding.UTF8, "application/json")).Result;
var body = resp.Content.ReadAsStringAsync().Result;
Console.WriteLine("[FD] HTTP " + (int)resp.StatusCode + " " + resp.StatusCode);
int rc;
string stdout, stderr;
using (var doc = JsonDocument.Parse(body))
{
rc = doc.RootElement.GetProperty("returncode").GetInt32();
stdout = doc.RootElement.GetProperty("stdout").GetString() ?? "";
stderr = doc.RootElement.GetProperty("stderr").GetString() ?? "";
}
if (rc == 0)
{
Console.WriteLine("[FD] returncode = " + rc + " -> SOLUTION TROUVEE.");
var planLines = new List<string>();
int planCost = -1, planLen = -1, nExpanded = -1;
foreach (var raw in stdout.Split('\n'))
{
var t = raw.Trim();
// FD plan lines : "pick-up a (1)" (action args (cost))
if (Regex.IsMatch(t, @"^[a-z][a-z0-9_-]*(\s+\S+)*\s+\(\d+\)\s*$")) planLines.Add(t);
var m = Regex.Match(t, @"Plan cost:\s*(\d+)"); if (m.Success) planCost = int.Parse(m.Groups[1].Value);
m = Regex.Match(t, @"Plan length:\s*(\d+)"); if (m.Success) planLen = int.Parse(m.Groups[1].Value);
m = Regex.Match(t, @"Expanded\s+(\d+)\s+state"); if (m.Success) nExpanded = int.Parse(m.Groups[1].Value);
}
Console.WriteLine("[FD] Plan length = " + planLen + " step(s) | cout optimal = " + planCost + " | etats expanses = " + nExpanded);
Console.WriteLine("[FD] Plan (" + planLines.Count + " actions) :");
foreach (var a in planLines) Console.WriteLine(" " + a);
}
else
{
Console.WriteLine("[FD] returncode = " + rc + " -> ECHEC. stderr :");
foreach (var l in stderr.Split('\n', StringSplitOptions.RemoveEmptyEntries))
Console.WriteLine(" " + l);
}
Console.WriteLine();
Console.WriteLine("Apport du moteur de production :");
Console.WriteLine("- La Tranche 1 (from-scratch) resout le Ferry encode A LA MAIN en SAS+ : 1 domaine,");
Console.WriteLine(" re-encode necessaire pour chaque nouveau domaine (cf. cellule 24 Logistics).");
Console.WriteLine("- Fast Downward resout n'importe quel domaine PDDL standard : on fournit le texte");
Console.WriteLine(" PDDL, FD fait la translation PDDL -> SAS+ + le grounding + la recherche A*+lmcut.");
Console.WriteLine("- lmcut (landmark-cut) est une heuristic admissible -> A* trouve un plan OPTIMAL");
Console.WriteLine(" (cout = 2 ici = nombre d'actions), comme l'A* from-scratch h^max sur le Ferry.");Tranche 2 : Fast Downward via API Docker (moteur PDDL de production)
Domaine PDDL : blocks (STRIPS, 4 actions). Probleme : empiler A sur B.
Recherche : A* + heuristic admissible lmcut (landmark-cut) -> plan OPTIMAL.
[FD] POST http://localhost:8200/plan (1175 octets)
[FD] HTTP 200 OK
[FD] returncode = 0 -> SOLUTION TROUVEE.
[FD] Plan length = 2 step(s) | cout optimal = 2 | etats expanses = 3
[FD] Plan (2 actions) :
pick-up a (1)
stack a b (1)
Apport du moteur de production :
- La Tranche 1 (from-scratch) resout le Ferry encode A LA MAIN en SAS+ : 1 domaine,
re-encode necessaire pour chaque nouveau domaine (cf. cellule 24 Logistics).
- Fast Downward resout n'importe quel domaine PDDL standard : on fournit le texte
PDDL, FD fait la translation PDDL -> SAS+ + le grounding + la recherche A*+lmcut.
- lmcut (landmark-cut) est une heuristic admissible -> A* trouve un plan OPTIMAL
(cout = 2 ici = nombre d'actions), comme l'A* from-scratch h^max sur le Ferry.Dictionary<string,int>), plus compact que STRIPS. Un opérateur se decompose en prevail (conditions sur variables invariantes), precondition (valeurs from des variables modifiees), effect (affectations).| Concept de ce twin | Equivalent Fast Downward (C++) |
|---|---|
SasOperator(Prevail/Pre/Eff) |
fichier output.sas du translator |
HMaxSas / HFFSas |
heuristiques hmax() / ff() du moteur |
AStarSas |
astar(...) |
GBFSSas |
eager_greedy(...) / lazy_greedy(...) |
EHCSas |
ehc(...) |
Le notebook Python Planners-4-Fast-Downward appelle le vrai Fast Downward via Docker + unified-planning (RECOVERABLE-MACHINE) : il montre les performances et la sortie brute du solveur industriel. Ce twin C# montre comment ca marche a l’interieur : les structures, les boucles, les compromis. Les deux sont complementaires.
Marathon #4956 (parite .NET <-> Python). Twin C# du notebook Python Planners-4-Fast-Downward.ipynb. Regitre SOTA : EPIC #3801.