Navigation : Index | << Fast Downward C# | Domaines C# >>
Twin C# de Planners-5-Heuristics (Python + unified-planning). Complementarite (#3801 Prong B) : le twin Python appelle la lib
unified-planning(pas d’equivalent NuGet maintenu) ; ce twin C# implemente from-scratch la propagation de couts et l’extraction de plan relaxe – la valeur pedagogique est de comprendre la mecanique des heuristiques de relaxation (Bonet & Geffner 2001, Hoffmann & Nebel 2001).
#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 seule, 0 NuGet)".Display();Imports OK : System.Linq, Globalization, DotNet.Interactive (BCL seule, 0 NuGet)Une heuristique \(h(s)\) estime le cout du chemin d’un etat \(s\) jusqu’au but. Sans heuristique, A* se reduit a Dijkstra (exploration uniforme) ; une bonne heuristique ordinaire le guide vers le but et reduit drastiquement le nombre de nœuds explores (cf Planners-3).
\(h\) est admissible si \(h(s) \le h^*(s)\) pour tout etat \(s\) (\(h^*\) = cout optimal reel). Admissible + consistant => A* trouve la solution optimale.
\(h\) est consistant si \(h(s) \le c(s, s') + h(s')\) pour tout arc \(s \to s'\). La consistance implique l’admissibilite (et evite de re-ouvrir des nœuds en A*).
| Heuristique | Admissible | Consistante | Commentaire |
|---|---|---|---|
| h^max | Oui | Oui | max des couts de faits du but |
| h^add | Non | Non | somme -> double-compte les enablers partages |
| h^FF | Non (mais proche) | Non | cardinalite d’un plan relaxe glouton |
| h_landmark | Non | Non | compte de landmarks non atteints |
On ignore les effets de suppression d’une action (on ne garde que les add_effects). Dans le monde relaxe, le nombre de faits vrais ne fait que croitre : un plan relaxe existe ssi le but est atteignable. Le cout d’un fait dans ce monde relaxe se calcule par propagation jusqu’a point fixe.
Pour chaque fait \(f\), \(cost(f)\) = cout cumule minimal pour le rendre vrai dans le monde relaxe :
avec \(cost(a)\) = cout de l’action. Alors \(h^{max}(s) = \max_{g \in G} cost(g)\).
// Structures STRIPS + heuristique h^max
public record STRIPSAction(string Name, HashSet<string> Preconditions,
HashSet<string> AddEffects, int Cost = 1);
public record STRIPSProblem(HashSet<string> InitialState,
HashSet<string> Goal,
List<STRIPSAction> Actions);
public static int HMax(STRIPSProblem problem, HashSet<string> state)
{
var factCosts = new Dictionary<string, int>();
foreach (var f in state) factCosts[f] = 0;
bool changed = true;
int iter = 0;
while (changed && iter < 1000)
{
changed = false; iter++;
foreach (var a in problem.Actions)
{
if (a.Preconditions.All(p => factCosts.ContainsKey(p)))
{
// Garde : Preconditions vide -> All() trivialement vrai et Max() leverait ;
// le max d'un ensemble vide de couts vaut 0 (conjonction vide).
int actionCost = a.Preconditions.Select(p => factCosts[p]).DefaultIfEmpty(0).Max() + a.Cost;
foreach (var eff in a.AddEffects)
if (!factCosts.ContainsKey(eff) || factCosts[eff] > actionCost)
{
factCosts[eff] = actionCost;
changed = true;
}
}
}
}
if (problem.Goal.All(g => factCosts.ContainsKey(g)))
// But vide (deja satisfait) : max d'un ensemble vide = 0
return problem.Goal.Select(g => factCosts[g]).DefaultIfEmpty(0).Max();
return int.MaxValue; // but non atteignable
}
"Structures STRIPS + heuristique h^max definies".Display();Structures STRIPS + heuristique h^max definiesEtat initial {off}, but {on}. Action turn_on : {off} -> {on} (cout 1). \(h^{max}\) = 1 = cout optimal reel => admissible.
// Probleme de l'interrupteur
var switchActions = new List<STRIPSAction>{
new("turn_on", new(){"off"}, new(){"on"}, 1),
new("turn_off", new(){"on"}, new(){"off"}, 1),
};
var switchProblem = new STRIPSProblem(
InitialState: new(){"off"},
Goal: new(){"on"},
Actions: switchActions);
int hVal = HMax(switchProblem, new(){"off"});
var sb = new System.Text.StringBuilder();
sb.AppendLine("h^max depuis l'etat initial : " + hVal);
sb.AppendLine("Cout optimal reel : 1 (turn_on)");
sb.AppendLine("Admissible ? " + (hVal <= 1));
sb.ToString().Display();h^max depuis l'etat initial : 1
Cout optimal reel : 1 (turn_on)
Admissible ? TrueHMax sur les ensembles videsAll() est trivialement vrai sur un ensemble vide (action sans precondition, but vide) et Max() y leve InvalidOperationException. Convention retenue : le max d’un ensemble vide de couts vaut 0 (conjonction vide), via DefaultIfEmpty(0).
// Garde : les quatre cas limites de HMax, valeurs attendues 1 / 0 / 1 / inf
var emptyPrecondPB = new STRIPSProblem(
new HashSet<string>{"s"}, new HashSet<string>{"g"},
new List<STRIPSAction>{ new("libre", new HashSet<string>(), new HashSet<string>{"g"}, 1) });
var emptyGoalPB = new STRIPSProblem(
new HashSet<string>{"s"}, new HashSet<string>(), new List<STRIPSAction>());
var unreachablePB = new STRIPSProblem(
new HashSet<string>{"s"}, new HashSet<string>{"g"}, new List<STRIPSAction>());
int c1 = HMax(emptyPrecondPB, new HashSet<string>{"s"}); // action sans precondition
int c2 = HMax(emptyGoalPB, new HashSet<string>{"s"}); // but vide : deja satisfait
int c3 = HMax(switchProblem, new HashSet<string>{"off"}); // controle nominal
int c4 = HMax(unreachablePB, new HashSet<string>{"s"}); // but inatteignable
var sbG = new System.Text.StringBuilder();
sbG.AppendLine("Garde HMax (ensembles vides) :");
sbG.AppendLine(" Action sans precondition : " + c1 + " (attendu 1)");
sbG.AppendLine(" But vide : " + c2 + " (attendu 0)");
sbG.AppendLine(" Controle nominal : " + c3 + " (attendu 1)");
sbG.AppendLine(" But inatteignable : " + (c4 == int.MaxValue ? "inf" : c4.ToString()) + " (attendu inf)");
sbG.ToString().Display();Garde HMax (ensembles vides) :
Action sans precondition : 1 (attendu 1)
But vide : 0 (attendu 0)
Controle nominal : 1 (attendu 1)
But inatteignable : inf (attendu inf)Comme h^max, mais \(cost(f) = \min_a [\, cost(a) + \mathbf{sum}_{p \in pre(a)} cost(p)\,]\) et \(h^{add}(s) = \mathbf{sum}_{g \in G} cost(g)\). La somme (au lieu du max) surestime car elle compte plusieurs fois un même enabler partage entre sous-buts.
// Heuristique h^add (somme additive) + actions helpful
public static (int hValue, HashSet<string> helpful) HAdd(STRIPSProblem problem, HashSet<string> state)
{
var factCosts = new Dictionary<string, int>();
var bestAction = new Dictionary<string, STRIPSAction>(); // meilleur achiever par fait
foreach (var f in state) factCosts[f] = 0; // faits initiaux : cout 0, pas d'achiever
bool changed = true;
int iter = 0;
while (changed && iter < 1000)
{
changed = false; iter++;
foreach (var a in problem.Actions)
{
if (a.Preconditions.All(p => factCosts.ContainsKey(p)))
{
int actionCost = a.Preconditions.Sum(p => factCosts[p]) + a.Cost;
foreach (var eff in a.AddEffects)
if (!factCosts.ContainsKey(eff) || factCosts[eff] > actionCost)
{
factCosts[eff] = actionCost;
bestAction[eff] = a;
changed = true;
}
}
}
}
var helpful = new HashSet<string>();
foreach (var g in problem.Goal)
{
if (!factCosts.ContainsKey(g)) return (int.MaxValue, new HashSet<string>());
if (bestAction.TryGetValue(g, out var ba)) helpful.Add(ba.Name);
}
int h = problem.Goal.Sum(g => factCosts[g]);
return (h, helpful);
}
var (hAddSwitch, helpSwitch) = HAdd(switchProblem, new(){"off"});
var sb = new System.Text.StringBuilder();
sb.AppendLine("h^add depuis l'etat initial : " + hAddSwitch);
sb.AppendLine("Actions helpful : [" + string.Join(", ", helpSwitch) + "]");
sb.ToString().Display();h^add depuis l'etat initial : 1
Actions helpful : [turn_on]But {on_1, on_2, on_3}, trois actions independantes turn_on_i : {off_i} -> {on_i} (cout 1 chacune). Cout optimal reel \(h^* = 3\). Sur cette instance les deux heuristiques sont admissibles (3 interrupteurs independants -> pas d’enabler partage) : \(h^{max} = 1\) (max des trois couts unitaires), \(h^{add} = 3\).
// Trois interrupteurs independants
var multiSwitch = new List<STRIPSAction>{
new("turn_on_1", new(){"off_1"}, new(){"on_1"}, 1),
new("turn_on_2", new(){"off_2"}, new(){"on_2"}, 1),
new("turn_on_3", new(){"off_3"}, new(){"on_3"}, 1),
};
var multiProblem = new STRIPSProblem(
InitialState: new(){"off_1", "off_2", "off_3"},
Goal: new(){"on_1", "on_2", "on_3"},
Actions: multiSwitch);
var init3 = new HashSet<string>{"off_1", "off_2", "off_3"};
int hMaxMulti = HMax(multiProblem, init3);
var (hAddMulti, helpMulti) = HAdd(multiProblem, init3);
var sb = new System.Text.StringBuilder();
sb.AppendLine("Comparaison h^max vs h^add (3 interrupteurs independants)");
sb.AppendLine(new string('=', 48));
sb.AppendLine("h^max : " + hMaxMulti);
sb.AppendLine("h^add : " + hAddMulti);
sb.AppendLine("h* (optimal): 3");
sb.AppendLine();
sb.AppendLine("h^max admissible ? " + (hMaxMulti <= 3));
sb.AppendLine("h^add admissible ? " + (hAddMulti <= 3));
sb.AppendLine();
sb.AppendLine("Actions helpful (h^add) : [" + string.Join(", ", helpMulti) + "]");
sb.ToString().Display();Comparaison h^max vs h^add (3 interrupteurs independants)
================================================
h^max : 1
h^add : 3
h* (optimal): 3
h^max admissible ? True
h^add admissible ? True
Actions helpful (h^add) : [turn_on_1, turn_on_2, turn_on_3]On construit une instance ou un enabler est partage entre deux sous-buts : setup : {s} -> {p} produit p, puis make_g1 : {p} -> {g1} et make_g2 : {p} -> {g2} l’utilisent tous deux. But {g1, g2}.
Cout optimal reel \(h^* = 3\) (setup, make_g1, make_g2). Mais h^add double-compte setup : \(cost(p)=1\), \(cost(g_1)=2\), \(cost(g_2)=2\), \(h^{add} = 2+2 = 4 > h^* = 3\). La relaxation additive ne voit pas que setup s’execute une seule fois. C’est l’observation concrete de la non-admissibilite.
// Enabler partage entre deux sous-buts -> h^add double-compte
var sharedActions = new List<STRIPSAction>{
new("setup", new(){"s"}, new(){"p"}, 1), // enabler partage
new("make_g1", new(){"p"}, new(){"g1"}, 1),
new("make_g2", new(){"p"}, new(){"g2"}, 1),
};
var sharedProblem = new STRIPSProblem(
InitialState: new(){"s"},
Goal: new(){"g1", "g2"},
Actions: sharedActions);
int hMaxShared = HMax(sharedProblem, new(){"s"});
var (hAddShared, _) = HAdd(sharedProblem, new(){"s"});
int hStarShared = 3; // setup, make_g1, make_g2
var sb = new System.Text.StringBuilder();
sb.AppendLine("Demonstration de non-admissibilite de h^add");
sb.AppendLine(new string('=', 52));
sb.AppendLine("h^max : " + hMaxShared + " (<= h*=3, admissible)");
sb.AppendLine("h^add : " + hAddShared + " (> h*=3, INADMISSIBLE)");
sb.AppendLine("h* : " + hStarShared);
sb.AppendLine();
sb.AppendLine("Cause : h^add compte setup (cout 1) dans le chemin de g1 ET dans celui de g2.");
sb.AppendLine(" Cout reel de setup = 1 (execute une fois). Cout h^add de setup = 2.");
sb.AppendLine();
sb.AppendLine("=> h^max reste admissible (max <= h*). h^add surestime la relaxation additive.");
sb.ToString().Display();Demonstration de non-admissibilite de h^add
====================================================
h^max : 2 (<= h*=3, admissible)
h^add : 4 (> h*=3, INADMISSIBLE)
h* : 3
Cause : h^add compte setup (cout 1) dans le chemin de g1 ET dans celui de g2.
Cout reel de setup = 1 (execute une fois). Cout h^add de setup = 2.
=> h^max reste admissible (max <= h*). h^add surestime la relaxation additive.h^FF (Hoffmann & Nebel 2001) evite le double-compte de h^add en extrayant un plan relaxe :
h^FF n’est pas admissible en théorie, mais très proche de h* en pratique (elle ignore les deletes mais ne double-compte pas les enablers partages). C’est l’heuristique de reference pour la planification satisfiable.
// Heuristique h^FF : extraction gloutonne d'un plan relaxe
public static (int hValue, HashSet<string> helpful) HFF(STRIPSProblem problem, HashSet<string> state)
{
var factCosts = new Dictionary<string, int>();
var achiever = new Dictionary<string, STRIPSAction>();
foreach (var f in state) factCosts[f] = 0; // faits initiaux : pas d'achiever
bool changed = true;
while (changed)
{
changed = false;
foreach (var a in problem.Actions)
if (a.Preconditions.All(p => factCosts.ContainsKey(p)))
{
int actionCost = a.Preconditions.Sum(p => factCosts[p]) + a.Cost;
foreach (var eff in a.AddEffects)
if (!factCosts.ContainsKey(eff) || factCosts[eff] > actionCost)
{
factCosts[eff] = actionCost;
achiever[eff] = a;
changed = true;
}
}
}
if (!problem.Goal.All(g => factCosts.ContainsKey(g)))
return (int.MaxValue, new HashSet<string>());
// Extraction gloutonne du plan relaxe depuis le but
var planActions = new HashSet<string>();
var processed = new HashSet<string>();
var stack = new Stack<string>(problem.Goal);
int guard = 0;
while (stack.Count > 0 && guard < 10000)
{
guard++;
var fact = stack.Pop();
if (processed.Contains(fact) || state.Contains(fact)) continue;
processed.Add(fact);
if (achiever.TryGetValue(fact, out var a))
{
planActions.Add(a.Name);
foreach (var p in a.Preconditions) stack.Push(p);
}
}
// Actions helpful = actions du plan relaxe applicables dans l'etat courant
var helpful = new HashSet<string>();
foreach (var a in problem.Actions)
if (a.Preconditions.IsSubsetOf(state) && planActions.Contains(a.Name))
helpful.Add(a.Name);
return (planActions.Count, helpful);
}
var (hFFMulti, ffHelp) = HFF(multiProblem, new HashSet<string>{"off_1","off_2","off_3"});
var sb = new System.Text.StringBuilder();
sb.AppendLine("h^FF (3 interrupteurs) : " + hFFMulti);
sb.AppendLine("Actions helpful : [" + string.Join(", ", ffHelp) + "]");
sb.ToString().Display();h^FF (3 interrupteurs) : 3
Actions helpful : [turn_on_1, turn_on_2, turn_on_3]Un landmark est un fait (ou ensemble d’actions) qui doit etre vrai (ou executé) dans tout plan valide. La presence de landmarks impose un ordre partiel : si toute action qui atteint \(L_2\) a pour Precondition \(L_1\), alors \(L_1\) doit preceder \(L_2\).
Une approximation : tout fait du but absent de l’etat initial est un landmark ; pour chaque landmark, les Preconditions communes a tous ses achievers sont des landmarks potentiels (et doivent le preceder) — l’intersection, pas l’union : une seule branche suffit a atteindre le landmark.
// Extraction de landmarks simples (backchaining depuis le but)
public static (HashSet<string> landmarks, List<(string before, string after)> order)
ExtractLandmarks(STRIPSProblem problem)
{
var landmarks = new HashSet<string>();
var order = new List<(string, string)>();
foreach (var g in problem.Goal)
if (!problem.InitialState.Contains(g)) landmarks.Add(g);
// Obligations = preconditions PARTAGEES par TOUS les achieveurs du landmark
// (intersection) : un landmark atteignable par plusieurs branches n'impose que
// ce qui est commun a toutes — l'union promouvait en obligations les
// preconditions d'une seule branche prise pour l'autre.
foreach (var lm in landmarks.ToList()) // snapshot
{
var achieverPreconds = problem.Actions
.Where(a => a.AddEffects.Contains(lm))
.Select(a => a.Preconditions.Where(p => !problem.InitialState.Contains(p)).ToHashSet())
.ToList();
if (achieverPreconds.Count == 0) continue;
var common = achieverPreconds.Aggregate(
(HashSet<string> acc, HashSet<string> next) => { acc.IntersectWith(next); return acc; });
foreach (var pre in common)
{
landmarks.Add(pre);
order.Add((pre, lm));
}
}
return (landmarks, order);
}
public static int HLandmarkCount(STRIPSProblem problem, HashSet<string> state)
{
var (lms, _) = ExtractLandmarks(problem);
int unsat = lms.Count(lm => !state.Contains(lm));
return unsat;
}
var (lms, lorder) = ExtractLandmarks(multiProblem);
var sb = new System.Text.StringBuilder();
sb.AppendLine("Landmarks extraits (3 interrupteurs) :");
foreach (var lm in lms) sb.AppendLine(" - " + lm);
sb.AppendLine();
sb.AppendLine("Ordre des landmarks (avant -> apres) :");
foreach (var (before, after) in lorder) sb.AppendLine(" " + before + " -> " + after);
sb.AppendLine();
sb.AppendLine("h_landmark_count depuis l'etat initial : " + HLandmarkCount(multiProblem, new HashSet<string>{"off_1","off_2","off_3"}));
sb.ToString().Display();Landmarks extraits (3 interrupteurs) :
- on_1
- on_2
- on_3
Ordre des landmarks (avant -> apres) :
h_landmark_count depuis l'etat initial : 3Un landmark atteignable par plusieurs actions n’impose pas toutes leurs preconditions : une seule branche suffit. Les obligations reelles sont les preconditions communes a tous les achieveurs (intersection). Deux branches disjointes ne creent aucune obligation au-dela du but ; deux branches partageant c font de c une vraie landmark — et HLandmarkCount rend 0 sur un etat but (l’union rendait 1).
// Controles : les obligations d'un landmark a plusieurs achieveurs sont les
// preconditions PARTAGEES (intersection), pas l'union.
var twoBranchPB = new STRIPSProblem(new HashSet<string>{"s"}, new HashSet<string>{"g"},
new List<STRIPSAction>{
new("branche_x", new HashSet<string>{"x"}, new HashSet<string>{"g"}, 1),
new("branche_y", new HashSet<string>{"y"}, new HashSet<string>{"g"}, 1) });
var sharedBranchPB = new STRIPSProblem(new HashSet<string>{"s"}, new HashSet<string>{"g"},
new List<STRIPSAction>{
new("v1", new HashSet<string>{"c","x"}, new HashSet<string>{"g"}, 1),
new("v2", new HashSet<string>{"c","y"}, new HashSet<string>{"g"}, 1) });
var singleAchieverPB = new STRIPSProblem(new HashSet<string>{"s"}, new HashSet<string>{"g"},
new List<STRIPSAction>{ new("seul", new HashSet<string>{"c"}, new HashSet<string>{"g"}, 1) });
var sbL = new System.Text.StringBuilder();
sbL.AppendLine("Garde landmarks (intersection des achieveurs) :");
foreach (var (pb, nom) in new[]{
(twoBranchPB, "branches disjointes (x|y)"),
(sharedBranchPB, "branches partageant c"),
(singleAchieverPB,"achiever unique") })
{
var (lms2, ord2) = ExtractLandmarks(pb);
var lmsStr = string.Join(",", lms2.OrderBy(l => l));
var ordStr = string.Join(" ", ord2.Select(o => "(" + o.before + "->" + o.after + ")"));
sbL.AppendLine(" " + nom.PadRight(26) + " -> landmarks [" + lmsStr + "] | ordre " + ordStr);
}
sbL.AppendLine(" h_landmark_count(two_branch, s|x|g) = " + HLandmarkCount(twoBranchPB, new HashSet<string>{"s","x","g"}) + " (attendu 0)");
sbL.AppendLine(" h_landmark_count(shared, s|c|g) = " + HLandmarkCount(sharedBranchPB, new HashSet<string>{"s","c","g"}) + " (attendu 0)");
sbL.ToString().Display();Garde landmarks (intersection des achieveurs) :
branches disjointes (x|y) -> landmarks [g] | ordre
branches partageant c -> landmarks [c,g] | ordre (c->g)
achiever unique -> landmarks [c,g] | ordre (c->g)
h_landmark_count(two_branch, s|x|g) = 0 (attendu 0)
h_landmark_count(shared, s|c|g) = 0 (attendu 0)Trois blocs A, B, C sur table, tous clairs, main vide. But : on_a_b (A sur B) ET on_b_c (B sur C). Cout optimal \(h^* = 4\) : pick_up_b, stack_b_c, pick_up_a, stack_a_b. On compare les quatre heuristiques sur l’etat initial.
// Blocks World simplifie : A,B,C sur table -> (A sur B) et (B sur C)
var blocksActions = new List<STRIPSAction>{
new("pick_up_a", new(){"clear_a","ontable_a","handempty"}, new(){"holding_a"}, 1),
new("pick_up_b", new(){"clear_b","ontable_b","handempty"}, new(){"holding_b"}, 1),
new("pick_up_c", new(){"clear_c","ontable_c","handempty"}, new(){"holding_c"}, 1),
new("stack_a_b", new(){"holding_a","clear_b"}, new(){"on_a_b","clear_a","handempty"}, 1),
new("stack_b_c", new(){"holding_b","clear_c"}, new(){"on_b_c","clear_b","handempty"}, 1),
new("stack_a_c", new(){"holding_a","clear_c"}, new(){"on_a_c","clear_a","handempty"}, 1),
};
var blocksProblem = new STRIPSProblem(
InitialState: new(){"clear_a","clear_b","clear_c","ontable_a","ontable_b","ontable_c","handempty"},
Goal: new(){"on_a_b","on_b_c"},
Actions: blocksActions);
var initB = new HashSet<string>{"clear_a","clear_b","clear_c","ontable_a","ontable_b","ontable_c","handempty"};
int hMaxB = HMax(blocksProblem, initB);
var (hAddB, _) = HAdd(blocksProblem, initB);
var (hFFB, _) = HFF(blocksProblem, initB);
int hLmB = HLandmarkCount(blocksProblem, initB);
int hStarB = 4;
var sb = new System.Text.StringBuilder();
sb.AppendLine("Benchmark Blocks World (but : on_a_b, on_b_c)");
sb.AppendLine(new string('=', 56));
sb.AppendLine(" Heuristique Valeur <= h*=4 ? (admissible)");
sb.AppendLine(" " + new string('-', 48));
sb.AppendLine(" h^max " + hMaxB.ToString().PadLeft(5) + " " + (hMaxB <= hStarB));
sb.AppendLine(" h^add " + hAddB.ToString().PadLeft(5) + " " + (hAddB <= hStarB));
sb.AppendLine(" h^FF " + hFFB.ToString().PadLeft(5) + " " + (hFFB <= hStarB));
sb.AppendLine(" h_landmark_count " + hLmB.ToString().PadLeft(5) + " " + (hLmB <= hStarB));
sb.AppendLine(" h* " + hStarB.ToString().PadLeft(5));
sb.AppendLine();
sb.AppendLine("Observation : h^max seule garantit admissible. Les autres peuvent");
sb.AppendLine("surestimer mais restent informatives pour une recherche satisfiable.");
sb.ToString().Display();Benchmark Blocks World (but : on_a_b, on_b_c)
========================================================
Heuristique Valeur <= h*=4 ? (admissible)
------------------------------------------------
h^max 2 True
h^add 4 True
h^FF 4 True
h_landmark_count 4 True
h* 4
Observation : h^max seule garantit admissible. Les autres peuvent
surestimer mais restent informatives pour une recherche satisfiable.Le benchmark Blocks World ci-dessus (§6) compare les valeurs des heuristiques (\(h^{max}\), \(h^{add}\), \(h^{FF}\)) sur un problème donné. Mais toute la valeur d’une heuristique réside dans une chose : guider la recherche, c’est-à-dire réduire le nombre de nœuds développés par rapport à une recherche aveugle (uniform-cost, qui n’utilise aucune heuristique). Si deux heuristiques donnent la même valeur mais qu’aucune ne fait explorer moins de nœuds que la recherche aveugle, alors elles ne « valent » rien en pratique. Mesurons-le directement.
Nous ajoutons au problème de la chaîne \(c_0 \to c_1 \to \dots \to c_M\) un ensemble de \(D\) chaînes leurres (faits et actions non pertinents pour le but). Ces leurres représentent les éléments non pertinents omniprésents dans les vrais domaines de planification : un planificateur aveugle perd son temps à les explorer, une recherche guidée par heuristique les ignore.
#nullable enable
// === Port du §6.3 : les heuristiques guident-elles VRAIMENT la recherche ? ===
static List<(STRIPSAction action, HashSet<string> state)> Successeurs(STRIPSProblem problem, HashSet<string> state)
{
var res = new List<(STRIPSAction, HashSet<string>)>();
foreach (var a in problem.Actions)
if (a.Preconditions.All(p => state.Contains(p)))
{
var ns = new HashSet<string>(state);
ns.UnionWith(a.AddEffects);
if (!ns.SetEquals(state)) res.Add((a, ns));
}
return res;
}
static string CleEtat(HashSet<string> s) => string.Join(",", s.OrderBy(x => x));
static (int cost, int expansions) Recherche(STRIPSProblem problem, Func<STRIPSProblem, HashSet<string>, int>? hFn, string mode)
{
var frontier = new PriorityQueue<(HashSet<string> state, int g), (int p1, int p2, int ord)>();
int counter = 0;
var depart = new HashSet<string>(problem.InitialState);
int h0 = hFn != null ? hFn(problem, depart) : 0;
(int, int) pk(int g, int h) => mode switch { "ucs" => (g, 0), "astar" => (g + h, g), "greedy" => (h, g), _ => (g, 0) };
var k0 = pk(0, h0);
frontier.Enqueue((depart, 0), (k0.Item1, k0.Item2, counter++));
var fermes = new HashSet<string>();
int expansions = 0;
while (frontier.Count > 0)
{
var (etat, g) = frontier.Dequeue();
var cle = CleEtat(etat);
if (fermes.Contains(cle)) continue;
fermes.Add(cle); expansions++;
if (problem.Goal.All(gl => etat.Contains(gl))) return (g, expansions);
foreach (var (action, suivant) in Successeurs(problem, etat))
{
if (fermes.Contains(CleEtat(suivant))) continue;
int ng = g + action.Cost;
int nh = hFn != null ? hFn(problem, suivant) : 0;
var nk = pk(ng, nh);
frontier.Enqueue((suivant, ng), (nk.Item1, nk.Item2, counter++));
}
}
return (-1, expansions);
}
static int HMaxPur(STRIPSProblem p, HashSet<string> s) => HMax(p, s);
static int HAddPur(STRIPSProblem p, HashSet<string> s) => HAdd(p, s).hValue;
static int HFFPur(STRIPSProblem p, HashSet<string> s) => HFF(p, s).hValue;
static STRIPSProblem ProblemeChaineAvecDistracteurs(int M, int D)
{
var actions = new List<STRIPSAction>();
for (int j = 0; j < M; j++)
actions.Add(new STRIPSAction($"etape_but_{j+1}", new(){$"c{j}"}, new(){$"c{j+1}"}, 1));
for (int j = 0; j < D; j++)
{
actions.Add(new STRIPSAction($"leurre_{j}_1", new(){"c0"}, new(){$"d{j}"}, 1));
actions.Add(new STRIPSAction($"leurre_{j}_2", new(){$"d{j}"}, new(){$"dd{j}"}, 1));
}
return new STRIPSProblem(new(){"c0"}, new(){$"c{M}"}, actions);
}
var sb = new System.Text.StringBuilder();
sb.AppendLine("Benchmark : nombre de NOEUDS DEVELOPPES (deterministe, reproductible)");
sb.AppendLine("But = chaine de longueur M ; D = chaines leurres (faits non pertinents)");
sb.AppendLine();
sb.AppendLine(string.Format("{0,3} {1,3} | {2,14} {3,10} {4,10} {5,12}", "M", "D", "UCS (aveugle)", "A*+h^max", "A*+h^add", "Greedy+h^FF"));
sb.AppendLine(new string('-', 62));
foreach (var (M, D) in new[] {(3,0),(3,4),(3,8),(3,12),(3,16)})
{
var p = ProblemeChaineAvecDistracteurs(M, D);
int ucs = Recherche(p, null, "ucs").expansions;
int amax = Recherche(p, HMaxPur, "astar").expansions;
int aadd = Recherche(p, HAddPur, "astar").expansions;
int gff = Recherche(p, HFFPur, "greedy").expansions;
sb.AppendLine(string.Format("{0,3} {1,3} | {2,14} {3,10} {4,10} {5,12}", M, D, ucs, amax, aadd, gff));
}
sb.ToString().Display();Benchmark : nombre de NOEUDS DEVELOPPES (deterministe, reproductible)
But = chaine de longueur M ; D = chaines leurres (faits non pertinents)
M D | UCS (aveugle) A*+h^max A*+h^add Greedy+h^FF
--------------------------------------------------------------
3 0 | 4 4 4 4
3 4 | 22 4 4 4
3 8 | 56 4 4 4
3 12 | 106 4 4 4
3 16 | 172 4 4 4Lecture — la différence se mesure en nœuds, pas en valeurs. Le contraste est tranché : la recherche aveugle (UCS) explose quand on ajoute des faits non pertinents (4 → 22 → 56 → 106 → 172 nœuds développés quand \(D\) passe de 0 à 16), alors que toute recherche guidée par heuristique reste plate à 4 nœuds, indépendamment de \(D\). À \(D = 16\), c’est ~43× moins de nœuds — et l’écart ne fait que croître avec le nombre de faits leurres.
Ce résultat est strictement identique à celui du jumeau Python (Planners-5-Heuristics.ipynb §6.3) : les deux implémentations (C# et Python) des heuristiques de relaxation produisent les mêmes comptes de nœuds, ce qui confirme que la propriété démontrée est algorithmique (indépendante du langage).
Sur cette structure de chaîne, \(h^{max}\), \(h^{add}\) et \(h^{FF}\) guident identiquement (toutes admissibles ici, toutes identifient le chemin optimal en ignorant les leurres) ; leur différence de valeur (l’inadmissibilité de \(h^{add}\) en général) est orthogonale au compte de nœuds sur ce problème. Ce qui compte ici est le contraste heuristique-guidée vs aveugle.
Lien CS : A* avec une heuristique admissible ne développe que les nœuds de \(f(n) < C^*\), contre tous les nœuds de \(g(n) < C^*\) pour uniform-cost. Plus le domaine contient de faits/états non pertinents à \(f\) élevé, plus le ratio de nœuds épargnés grandit — exactement ce que la table ci-dessus montre croître avec \(D\). C’est la raison pour laquelle Fast Downward résout des problèmes où la recherche aveugle est intractable.
Le §6.1 a mesuré notre implémentation from-scratch : A* avec \(h^{max}\), \(h^{add}\), \(h^{FF}\) reste à 4 nœuds quand l’aveugle (UCS) explose (172 nœuds à \(D=16\)). Le §7 l’anticipait : « Fast Downward combine ces idées… LM-cut ». Mesurons-le pour de vrai.
Fast Downward (Helmert 2006, vainqueur répété de l’IPC) est l’engine de référence en planification classique. On l’invoque ici via son API Docker (coursia-fast-downward, port 8200) — le même type d’engine que charge le jumeau Python via pyperplan/unified-planning. C’est la vraie parité lib-vs-lib : les deux côtés appellent un engine de production externe, pas une réimplémentation jouet.
FD offre des heuristiques de pointe que notre from-scratch n’implémente pas, notamment \(h^{lmcut}\) (Landmark-Cut, Helmert & Domshlak 2009) — admissible et bien plus informative que \(h^{max}\). On lance A* avec quatre heuristiques FD sur le même Blocks World \(h^* = 4\) et on compte les nœuds expansés.
// === §6.2 Tranche 2 : Fast Downward (engine de référence) sur Blocks World h*=4 ===
// Le from-scratch §6.1 prouve le principe (l'heuristique guide vs l'aveugle). On invoque ici
// le VRAI engine de compétition (Fast Downward, Helmert 2006) via son API Docker, pour :
// (1) valider le coût optimal h*=4 par un engine indépendant ;
// (2) comparer les heuristiques SOTA dont LM-cut (absente du from-scratch) en nœuds expansés.
// Même démarche que le jumeau Python (pyperplan/unified-planning) : vraie parité lib-vs-lib.
using System.Net.Http;
using System.Text.RegularExpressions;
var DOMAIN_BLOCKS = @"(define (domain blocks)
(:requirements :strips :typing)
(:types block)
(:predicates (holding ?x) (on ?x ?y) (ontable ?x) (clear ?x) (handempty))
(:action pick-up :parameters (?x - block)
:precondition (and (clear ?x) (ontable ?x) (handempty))
:effect (and (holding ?x) (not (clear ?x)) (not (ontable ?x)) (not (handempty))))
(:action put-down :parameters (?x - block)
:precondition (holding ?x)
:effect (and (ontable ?x) (clear ?x) (handempty) (not (holding ?x))))
(:action stack :parameters (?x - block ?y - block)
:precondition (and (holding ?x) (clear ?y))
:effect (and (on ?x ?y) (clear ?x) (handempty) (not (holding ?x)) (not (clear ?y))))
(:action unstack :parameters (?x - block ?y - block)
:precondition (and (on ?x ?y) (clear ?x) (handempty))
:effect (and (holding ?x) (clear ?y) (not (on ?x ?y)) (not (clear ?x)) (not (handempty)))))";
var PROBLEM_BLOCK3 = @"(define (problem blocks3)
(:domain blocks)
(:objects a b c - block)
(:init (ontable a) (ontable b) (ontable c) (clear a) (clear b) (clear c) (handempty))
(:goal (and (on a b) (on b c))))";
// FD tourne dans le conteneur Docker coursia-fast-downward (port 8200). On poste le PDDL +
// la config de recherche ; FD renvoie le plan et les logs (états évalués/expansés/générés).
var httpFD = new HttpClient { Timeout = TimeSpan.FromSeconds(30) };
(string plan, int cost, int evalN, int expN, int genN, int rc) SolveFD(string search)
{
var payload = System.Text.Json.JsonSerializer.Serialize(new {
domain = DOMAIN_BLOCKS, problem = PROBLEM_BLOCK3, search = search });
var resp = httpFD.PostAsync("http://localhost:8200/plan",
new StringContent(payload, System.Text.Encoding.UTF8, "application/json")).Result;
var body = resp.Content.ReadAsStringAsync().Result;
using var doc = System.Text.Json.JsonDocument.Parse(body);
var root = doc.RootElement;
int rc = root.GetProperty("returncode").GetInt32();
var stdout = root.GetProperty("stdout").GetString() ?? "";
int Grab(string pat) { var m = Regex.Match(stdout, pat); return m.Success ? int.Parse(m.Groups[1].Value) : -1; }
var planLines = Regex.Matches(stdout, @"(?m)^[a-z][a-z0-9_-]*(?:[ \t]+[^()\r\n]+)*[ \t]*\(\d+\)[ \t]*$")
.Select(m => m.Value.Trim()).ToList();
return (string.Join(" ; ", planLines),
Grab(@"Plan cost: (\d+)"), Grab(@"Evaluated (\d+) state"),
Grab(@"Expanded (\d+) state"), Grab(@"Generated (\d+) state"), rc);
}
var sbFD = new System.Text.StringBuilder();
sbFD.AppendLine("§6.2 Fast Downward (engine SOTA) sur Blocks World h*=4 (but : on a b, on b c)");
sbFD.AppendLine(new string('=', 80));
sbFD.AppendLine(string.Format("{0,-26} {1,5} {2,5} {3,10} {4,10} {5,10}",
"Heuristique FD", "cout", "plan", "evaluees", "expanses", "generees"));
sbFD.AppendLine(new string('-', 80));
foreach (var (label, search) in new[] {
("lmcut (Landmark-Cut)", "astar(lmcut())"),
("h^max (relaxation max)", "astar(hmax())"),
("h^FF (Fast-Forward)", "astar(ff())"),
("h^add (additive)", "astar(add())"),
})
{
var r = SolveFD(search);
int nPlan = r.plan.Length == 0 ? 0 : r.plan.Split(" ; ").Length;
sbFD.AppendLine(string.Format("{0,-26} {1,5} {2,5} {3,10} {4,10} {5,10}",
label, r.cost, nPlan, r.evalN, r.expN, r.genN));
}
sbFD.AppendLine();
var rLmcut = SolveFD("astar(lmcut())");
sbFD.AppendLine("Plan optimal (lmcut) : " + rLmcut.plan);
sbFD.ToString().Display();§6.2 Fast Downward (engine SOTA) sur Blocks World h*=4 (but : on a b, on b c)
================================================================================
Heuristique FD cout plan evaluees expanses generees
--------------------------------------------------------------------------------
lmcut (Landmark-Cut) 4 4 10 6 13
h^max (relaxation max) 4 4 13 8 18
h^FF (Fast-Forward) 4 4 11 7 15
h^add (additive) 4 4 11 7 15
Plan optimal (lmcut) : pick-up b (1) ; stack b c (1) ; pick-up a (1) ; stack a b (1)Lecture — LM-cut est l’heuristique admissible de choix. Les quatre heuristiques FD trouvent le même plan optimal de coût 4 (pick-up b → stack b c → pick-up a → stack a b), validant \(h^* = 4\) par un engine indépendant. Mais le nombre de nœuds expansés diffère : LM-cut en développe le moins, \(h^{max}\) le plus — exactement la signature attendue.
LM-cut domine \(h^{max}\) (toutes deux admissibles, mais LM-cut exploite la structure de landmarks que \(h^{max}\) ignore) ; \(h^{FF}\) et \(h^{add}\) sont informatives mais inadmissibles. Le §6.1 mesurait ce contraste sur une chaîne avec notre A* maison ; ici l’engine de compétition le confirme sur Blocks World — et c’est précisément pour cette économie de nœuds que Fast Downward résout des problèmes où la recherche aveugle est intractable (cf §6.1, \(D = 16\) : 172 nœuds pour UCS vs 4 pour une recherche guidée).
Parité lib-vs-lib. Le jumeau Python appelle
pyperplan(engine unified-planning) sur ce même domaine ; cette Tranche 2 C# appelle Fast Downward. Les deux invoquent un engine de production externe — d’où le passage du registre de paritésemanticànative-both. La Tranche 1 from-scratch (§1-6.1) est préservée intégralement : elle enseigne la mécanique des heuristiques de relaxation, cette Tranche 2 branche le vrai moteur dont le §7 disait qu’il « combine ces idées ».
Conformement a la règle C.1, les stubs ci-dessous s’executent sans erreur (rendent une valeur par defaut ou affichent un message) et ne bloquent pas le notebook.
Implementer l’heuristique goalcount : nombre de faits du but non encore satisfaits dans l’etat. C’est l’heuristique la plus simple (et la moins informative) : elle ignore les Preconditions et les couts.
Indice : problem.Goal.Count(g => !state.Contains(g)).
// Exercice 1 : h^goalcount (a completer)
// TODO etudiant : compter les faits du but non satisfaits dans l'etat.
// Resultat attendu sur blocksProblem/initB : 2 (on_a_b et on_b_c absents).
int? hGoalCount = null; // TODO etudiant : affecter la valeur
"Exercice 1 (goalcount) a completer.".Display();Exercice 1 (goalcount) a completer.Verifier empiriquement la consistance de h^max sur le Blocks World : pour chaque successeur \(s'\) d’un etat \(s\) (via une action applicable), on doit avoir \(h^{max}(s) \le cost(a) + h^{max}(s')\).
Indice : enumerer les actions applicables, calculer l’etat successeur (state \ del) ∪ add, appliquer HMax au successeur et comparer.
// Exercice 2 : coherence de h^max (a completer)
// TODO etudiant : pour chaque action applicable dans initB, calculer le successeur
// et verifier h^max(initB) <= cost(a) + h^max(successeur).
bool? hMaxConsistent = null; // TODO etudiant : true si la coherence tient partout
"Exercice 2 (coherence h^max) a completer.".Display();Exercice 2 (coherence h^max) a completer.Sur une instance que vous concevez (ex. 4 blocs a empiler), calculer h^FF et le comparer au cout optimal reel \(h^*\) (trouve par BFS sur l’espace d’etats, cf Planners-3). h^FF est-elle admissible sur votre instance ?
Indice : reutiliser HFF et un BFS sur les etats (HashSet
// Exercice 3 : h^FF vs plan optimal (a completer)
// TODO etudiant : definir un probleme a 4 blocs, calculer h^FF et h* (BFS), comparer.
int? hFFcmp = null; // TODO etudiant : valeur h^FF
int? hStarCmp = null; // TODO etudiant : cout optimal BFS
"Exercice 3 (h^FF vs optimal) a completer.".Display();Exercice 3 (h^FF vs optimal) a completer.Fast Downward (Helmert 2006) combine ces idees : traduction en FDR, pattern databases, et surtout LM-cut (une heuristique admissible basee sur les landmarks, au cout h^max). Ce twin C# couvre les fondations algorithmiques ; le notebook Python branche le vrai moteur via unified-planning.
Twin C# dans le cadre du marathon de parite .NET/Python (#4956), suite Planners-1 (#5528) -> Planners-3 (#5534) -> Planners-5.