Planners-5-Heuristiques en Planification

Navigation : Index | << Fast Downward | Domaines >>

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez :

Comprendre les proprietes des heuristiques (admissibilite, coherence)
Implementer l’heuristique additive (h^add)
Implementer l’heuristique FF (h^FF)
Comprendre les heuristiques basees sur les landmarks
Comparer les compromis qualite/vitesse des différentes heuristiques

Prerequis

Notebooks Planners-1 a 4 completes
Connaissance de la recherche A* et des graphes d’etats
unified-planning installe

Duree estimee : 40 minutes

1. Introduction aux Heuristiques

L’efficacite d’un planificateur repose sur sa capacite a guider intelligemment la recherche dans l’espace d’etats. Les heuristiques sont des fonctions qui estiment le cout pour atteindre le but depuis un etat donne.

1.1 Pourquoi les heuristiques sont essentielles

Sans heuristique, la recherche est aveugle (BFS, Dijkstra) et explore exhaustivement l’espace d’etats. Avec \(2^n\) etats possibles pour \(n\) predicats, l’explosion combinatoire rend les problemes reels intraitables.

Une heuristique \(h(s)\) transforme une recherche en largeur en une recherche guidee vers le but.

1.2 Planification optimale vs satisfiable

Objectif	Description	Algorithme typique
Optimal	Trouver le plan de cout minimal	A* + heuristique admissible
Satisfiable	Trouver un plan rapidement (qualite secondaire)	GBFS + heuristique informative

A* : \(f(n) = g(n) + h(n)\) ou \(g(n)\) est le cout accumule
GBFS (Greedy Best-First Search) : \(f(n) = h(n)\) (ignore le cout accumule)

2. Proprietes des Heuristiques

Les proprietes mathematiques d’une heuristique determinent ses garanties théoriques.

2.1 Admissibilite

Une heuristique \(h\) est admissible si elle ne surestime jamais le cout optimal :

\[h(s) \leq h^*(s) \quad \forall s\]

ou \(h^*(s)\) est le cout optimal reel de \(s\) au but.

Consequence : Avec une heuristique admissible, A* garantit de trouver le plan optimal.

2.2 Coherence (Consistence)

Une heuristique \(h\) est coherente si elle satisfait l’inegalite triangulaire :

\[h(s) \leq c(s, s') + h(s')\]

pour tout etat \(s\) et tout successeur \(s'\) avec cout de transition \(c(s, s')\).

Consequence : La coherence implique l’admissibilite. De plus, avec A*, les noeuds ne sont jamais re-ouverts (efficacite).

2.3 Tableau recapitulatif des proprietes

Propriete	Definition	Garantie
Admissible	\(h(s) \leq h^*(s)\)	Optimalite A*
Coherente	\(h(s) \leq c(s,s') + h(s')\)	Admissibilite + pas de reouverture
Sure	Fonctionne avec axiomes/effets conditionnels	Robustesse
Dominante	\(h_1(s) \geq h_2(s)\) pour tout \(s\)	Recherche plus guidee

# Imports et configuration
import numpy as np
from typing import Dict, Set, List, Tuple, Optional
from dataclasses import dataclass, field
from collections import defaultdict

# unified-planning
try:
    import unified_planning as up
    from unified_planning.shortcuts import *
    print(f"unified-planning version: {up.__version__}")
    UP_OK = True
except ImportError as e:
    print(f"ERREUR: unified-planning non installe: {e}")
    UP_OK = False

# Visualization
import matplotlib.pyplot as plt
import networkx as nx

unified-planning version: 1.3.0

Interpretation de l’environnement

Ce notebook utilise unified-planning comme interface principale et implemente les heuristiques en Python pur pour comprendre leur fonctionnement.

Bibliotheque	Usage
unified-planning	Modelisation des problemes, resolution
networkx	Visualisation des graphes de relaxation
matplotlib	Visualisation des résultats

3. Heuristiques basees sur la Relaxation

La plupart des heuristiques classiques utilisent le concept de relaxation : simplifier le problème pour obtenir une borne inferieure du cout.

3.1 La relaxation de suppression (Delete Relaxation)

L’idee centrale est d’ignorer les effets negatifs des actions : - Dans le problème relaxe, les faits ne peuvent qu’etre ajoutes, jamais supprimes - Le problème relaxe est polytime resolvable - Le cout du plan relaxe est une borne inferieure du cout reel

\[h^{relax}(s) \leq h^*(s)\]

3.2 Heuristique h^max

L’heuristique h^max considere que les sous-buts sont atteints sequentiellement :

\[h^{max}(s) = \max_{g \in G} cost(s, g)\]

ou \(cost(s, g)\) est le cout minimal pour atteindre le fait \(g\) depuis \(s\).

Proprietes : - Admissible : Ne surestime pas (considere le pire cas) - Peu informative : Ignore les interactions entre sous-buts

@dataclass
class STRIPSAction:
    """Representation simplifiee d'une action STRIPS."""
    name: str
    preconditions: Set[str]
    add_effects: Set[str]
    cost: int = 1

@dataclass 
class STRIPSProblem:
    """Probleme STRIPS simplifie."""
    initial_state: Set[str]
    goal: Set[str]
    actions: List[STRIPSAction]

def h_max(problem: STRIPSProblem, state: Set[str]) -> int:
    """
    Calcule l'heuristique h^max depuis un etat donne.
    
    Algorithme : Propagation de couts dans un graphe de relaxation.
    Pour chaque fait, on calcule le cout minimal pour l'atteindre.
    h^max = max(cout des faits du but)
    """
    # Initialisation des couts
    fact_costs: Dict[str, int] = {}
    for fact in state:
        fact_costs[fact] = 0  # Faits deja vrais
    
    # Propagation jusqu'a point fixe
    changed = True
    max_iterations = 1000  # Seurite
    iteration = 0
    
    while changed and iteration < max_iterations:
        changed = False
        iteration += 1
        
        for action in problem.actions:
            # Verifier si toutes les preconditions sont atteignables
            if all(p in fact_costs for p in action.preconditions):
                # Cout de l'action = preconditions + action
                # Garde : une action sans precondition passe all() trivialement (conjonction
                # vide) ; le max d'un ensemble vide de couts vaut 0, pas une exception.
                action_cost = max((fact_costs[p] for p in action.preconditions), default=0) + action.cost
                
                # Mettre a jour les effets
                for effect in action.add_effects:
                    if effect not in fact_costs or fact_costs[effect] > action_cost:
                        fact_costs[effect] = action_cost
                        changed = True
    
    # h^max = maximum des couts des faits du but
    if all(g in fact_costs for g in problem.goal):
        # But vide = deja satisfait : max d'un ensemble vide = 0
        return max((fact_costs[g] for g in problem.goal), default=0)
    else:
        return float('inf')  # But non atteignable
print("Classes definies : STRIPSAction, STRIPSProblem + heuristique h_max")

Classes definies : STRIPSAction, STRIPSProblem + heuristique h_max

Application de l’heuristique h^max au problème de l’interrupteur pour illustrer le calcul concret de la valeur heuristique sur un exemple minimal.

# Exemple : Probleme de l'interrupteur
switch_actions = [
    STRIPSAction("turn_on", {"off"}, {"on"}, cost=1),
    STRIPSAction("turn_off", {"on"}, {"off"}, cost=1)
]

switch_problem = STRIPSProblem(
    initial_state={"off"},
    goal={"on"},
    actions=switch_actions
)

# Calcul de h^max
h_value = h_max(switch_problem, {"off"})
print(f"h^max depuis l'etat initial : {h_value}")
print(f"Cout optimal reel : 1 (turn_on)")
print(f"Admissible ? {h_value <= 1}")

h^max depuis l'etat initial : 1
Cout optimal reel : 1 (turn_on)
Admissible ? True

Garde : `h^max` sur les ensembles vides

Une action sans precondition rend all(...) trivialement vrai (conjonction vide), et un but vide aussi — sans garde, le max() qui suit leve ValueError sur un iterateur vide. Convention retenue : le max d’un ensemble vide de couts vaut 0 (une conjonction vide ne coute rien), via max(..., default=0).

# Garde : les quatre cas limites de h_max, valeurs attendues 1 / 0 / 1 / inf
empty_precond = STRIPSProblem(
    initial_state={"s"},
    goal={"g"},
    actions=[STRIPSAction("libre", set(), {"g"}, cost=1)],
)
empty_goal = STRIPSProblem(initial_state={"s"}, goal=set(), actions=[])
unreachable = STRIPSProblem(initial_state={"s"}, goal={"g"}, actions=[])

h1 = h_max(empty_precond, {"s"})        # action sans precondition : cout 0 + 1
h2 = h_max(empty_goal, {"s"})           # but vide : deja satisfait
h3 = h_max(switch_problem, {"off"})     # controle nominal (cellule precedente)
h4 = h_max(unreachable, {"s"})          # but inatteignable

print(f"Action sans precondition : {h1} (attendu 1)")
print(f"But vide                : {h2} (attendu 0)")
print(f"Controle nominal        : {h3} (attendu 1)")
print(f"But inatteignable       : {h4} (attendu inf)")
print(f"Garde complete : {(h1, h2, h3, h4) == (1, 0, 1, float('inf'))}")

Action sans precondition : 1 (attendu 1)
But vide                : 0 (attendu 0)
Controle nominal        : 1 (attendu 1)
But inatteignable       : inf (attendu inf)
Garde complete : True

Interpretation

Le résultat h^max = 1 est admissible (h^max <= h* = 1), mais il est aussi exact dans ce cas trivial.

Pourquoi h^max = 1 : le but contient un seul fait (on), donc max(cost(on)) = 1. Avec un seul sous-but, h^max coincide avec le cout optimal.

Ce qui se passe dans le calcul : 1. Etat initial : fact_costs = {off: 0} 2. Action turn_on : preconditions {off} atteignables (cout 0), donc on atteignable au cout 0 + 1 = 1 3. h^max = max(fact_costs[on]) = 1

Dans un problème multi-sous-buts, h^max ne retient que le sous-but le plus cher, ignorant les synergies potentielles entre actions.

3.3 Heuristique h^add (Additive)

L’heuristique h^add additionne les couts des sous-buts :

\[h^{add}(s) = \sum_{g \in G} cost(s, g)\]

Proprietes : - Non admissible : Peut surestimer (ignore les synergies) - Plus informative : Meilleure guidance en pratique - Identifie les opérateurs preferes : Actions utilisees dans le plan relaxe

def h_add(problem: STRIPSProblem, state: Set[str]) -> Tuple[int, Set[str]]:
    """
    Calcule l'heuristique h^add depuis un etat donne.
    
    Retourne :
    - La valeur heuristique (somme des couts)
    - L'ensemble des actions "helpful" (operateurs preferes)
    """
    # Initialisation des couts
    fact_costs: Dict[str, int] = {}
    best_action: Dict[str, Optional[STRIPSAction]] = {}  # Action ayant atteint ce fait
    
    for fact in state:
        fact_costs[fact] = 0
        best_action[fact] = None
    
    # Propagation
    changed = True
    max_iterations = 1000
    iteration = 0
    
    while changed and iteration < max_iterations:
        changed = False
        iteration += 1
        
        for action in problem.actions:
            if all(p in fact_costs for p in action.preconditions):
                # Cout additif (somme au lieu de max)
                action_cost = sum(fact_costs[p] for p in action.preconditions) + action.cost
                
                for effect in action.add_effects:
                    if effect not in fact_costs or fact_costs[effect] > action_cost:
                        fact_costs[effect] = action_cost
                        best_action[effect] = action
                        changed = True
    
    # Identifier les helpful actions
    helpful_actions: Set[str] = set()
    for g in problem.goal:
        if g not in fact_costs:
            return float('inf'), set()  # But non atteignable
        if best_action.get(g):
            helpful_actions.add(best_action[g].name)
    
    # h^add = somme des couts des faits du but
    h_value = sum(fact_costs[g] for g in problem.goal)
    
    return h_value, helpful_actions

# Test sur le probleme de l'interrupteur
h_val, helpful = h_add(switch_problem, {"off"})
print(f"h^add depuis l'etat initial : {h_val}")
print(f"Actions helpful : {helpful}")

h^add depuis l'etat initial : 1
Actions helpful : {'turn_on'}

Interpretation

Sur le problème de l’interrupteur simple, h^add retourne 1 avec {turn_on} comme action helpful.

Ce que le résultat nous dit : - h^add = 1 : la somme des couts des sous-buts est 1 (un seul sous-but on, cout 1 via turn_on) - Actions helpful = {turn_on} : cette action est a la fois dans le plan relaxe ET applicable dans l’etat courant

Les actions helpful sont un sous-produit cle de h^add : elles guident la recherche vers les etats prometteurs. Dans Fast Downward, les “preferred operators” accelèrent la recherche greedy d’un facteur 10-100x en pratique.

3.4 Comparaison h^max vs h^add

Testons sur un problème plus complexe avec plusieurs sous-buts.

# Probleme : Allumer 3 interrupteurs
multi_switch_actions = [
    STRIPSAction("turn_on_1", {"off_1"}, {"on_1"}, cost=1),
    STRIPSAction("turn_on_2", {"off_2"}, {"on_2"}, cost=1),
    STRIPSAction("turn_on_3", {"off_3"}, {"on_3"}, cost=1),
]

multi_switch_problem = STRIPSProblem(
    initial_state={"off_1", "off_2", "off_3"},
    goal={"on_1", "on_2", "on_3"},
    actions=multi_switch_actions
)

# Comparaison
h_max_val = h_max(multi_switch_problem, {"off_1", "off_2", "off_3"})
h_add_val, helpful = h_add(multi_switch_problem, {"off_1", "off_2", "off_3"})

print("Comparaison h^max vs h^add")
print("=" * 40)
print(f"h^max  : {h_max_val}")
print(f"h^add  : {h_add_val}")
print(f"h* (optimal) : 3")
print()
print(f"h^max admissible ? {h_max_val <= 3}")
print(f"h^add admissible ? {h_add_val <= 3}")
print()
print(f"Actions helpful (h^add) : {helpful}")

Comparaison h^max vs h^add
========================================
h^max  : 1
h^add  : 3
h* (optimal) : 3

h^max admissible ? True
h^add admissible ? True

Actions helpful (h^add) : {'turn_on_2', 'turn_on_1', 'turn_on_3'}

3.5 Demonstration : h^add n’est PAS admissible en general

Les exemples précédents (3 interrupteurs independants) donnaient h^add = h* par coïncidence structurelle. Pour observer concretement la non-admissibilite de h^add, il faut un problème ou une action partagee entre plusieurs sous-buts : h^add compte son cout une fois par sous-but, mais un plan optimal ne l’execute qu’une fois. Problème a precondition partagee : une action setup produit un fait enabler p qui sert de precondition aux deux sous-buts g1 et g2. Un plan optimal execute setup une seule fois, mais h^add double-compte son cout (1 pour g1 + 1 pour g2).

# Probleme : precondition partagee entre deux sous-buts
# but = {g1, g2}, action setup produit p, deux actions distinctes utilisent p
# (Note : on utilise uniquement h^max et h^add ici ; h^FF est defini plus loin dans le notebook)
shared_actions = [
    STRIPSAction("setup",    {"s"},          {"p"},           cost=1),  # enabler partage
    STRIPSAction("make_g1",  {"p"},          {"g1"},          cost=1),  # atteint g1 via p
    STRIPSAction("make_g2",  {"p"},          {"g2"},          cost=1),  # atteint g2 via p
]

shared_problem = STRIPSProblem(
    initial_state={"s"},
    goal={"g1", "g2"},
    actions=shared_actions,
)

h_max_shared = h_max(shared_problem, shared_problem.initial_state)
h_add_shared, _ = h_add(shared_problem, shared_problem.initial_state)
h_star_shared   = 3  # plan optimal : setup, make_g1, make_g2

print("Demonstration de non-admissibilite de h^add")
print("=" * 50)
print(f"{'Heuristique':<15} {'Valeur':<10} {'Admissible':<12} {'Observation'}")
print("-" * 50)
# Admissibilite est une propriete universelle, pas per-instance
print(f"{'h^max':<15} {h_max_shared:<10} {'Oui':<12} max(cout setup+g) = 2 <= h*")
print(f"{'h^add':<15} {h_add_shared:<10} {'Non':<12} double-compte setup : 2+2 = 4 > h*")
print(f"{'h*':<15} {h_star_shared:<10} {'-':<12} cout optimal reel")
print("-" * 50)
print()
print(f"h^add = {h_add_shared} > h* = {h_star_shared} : INADMISSIBLE sur cette instance")
print("Cause : h^add compte setup (cout 1) dans le chemin de g1 ET dans celui de g2.")
print("        Cout reel de setup = 1 (execute une fois dans le plan optimal).")
print("        Cout h^add de setup = 2 (1 par sous-but qui en depend).")
print()
print("=> Conclusion : h^max reste admissible (max <= h*). h^add surestime")
print("   car la relaxation additive ne distingue pas les actions partagees.")

Demonstration de non-admissibilite de h^add
==================================================
Heuristique     Valeur     Admissible   Observation
--------------------------------------------------
h^max           2          Oui          max(cout setup+g) = 2 <= h*
h^add           4          Non          double-compte setup : 2+2 = 4 > h*
h*              3          -            cout optimal reel
--------------------------------------------------

h^add = 4 > h* = 3 : INADMISSIBLE sur cette instance
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 dans le plan optimal).
        Cout h^add de setup = 2 (1 par sous-but qui en depend).

=> Conclusion : h^max reste admissible (max <= h*). h^add surestime
   car la relaxation additive ne distingue pas les actions partagees.

Interpretation : la non-admissibilite de h^add est observee concretement

Heuristique	Valeur	Admissible (universelle)	Observation
h^max	2	Oui	Compte le sous-but le plus cher (cout 2 = setup + make)
h^add	4	Non	Double-compte `setup` : 2 (pour g1) + 2 (pour g2)
h*	3	-	Plan optimal : setup, make_g1, make_g2

Pourquoi h^add = 4 > h* = 3 :

setup (cout 1) est la precondition commune des deux sous-buts g1 et g2
Le calcul additif propage le cout de p (= 1, atteint via setup) independamment dans chaque branche du graphe de relaxation
cost(g1) = cost(p) + cout de make_g1 = 1 + 1 = 2
cost(g2) = cost(p) + cout de make_g2 = 1 + 1 = 2
h^add = cost(g1) + cost(g2) = 2 + 2 = 4
Mais un plan optimal n’execute setup qu’une fois : setup, make_g1, make_g2 = cout total 3
Donc h^add surestime de 1 (= cout de setup)

h^max reste admissible : max(2, 2) = 2 <= h* = 3. C’est la superiorite classique de h^max pour la recherche optimale : il sous-estime systematiquement, garantissant l’optimalite avec A*.

Sur h^FF : h^FF est definie et mesuree au §4 ci-dessous, ou nous la reprenons sur ce meme probleme a precondition partagee – elle y vaut 3 = h* (contrairement a h^add = 4), car le plan relaxe extrait par FF partage setup et ne la compte qu’une fois.

Implication pratique : pour la planification optimale, preferer h^max ou LM-cut (admissibles) ; pour la recherche satisfiable rapide, h^FF est souvent preferable a h^add (meilleure guidance, pas de surestimation catastrophique sur actions partagees).

Interpretation de la comparaison

Heuristique	Valeur	Admissible (sur cette instance)	Admissible (universelle)
h^max	1	Oui (1 <= 3)	Oui
h^add	3	Oui (3 <= 3)	Non
h*	3	-	-

Observations :

h^max est admissible en general : propriete universelle (max <= h* pour tout etat).
h^add coincide avec h* ici car les 3 sous-buts sont independants (pas de precondition partagee). Mais cela ne la rend pas admissible en general : sur des problemes avec actions partagees, h^add surestime. Voir la cellule 3.5 pour une demonstration concrete (h^add = 4 > h* = 3).
h^add est plus informative que h^max sur cette instance (3 vs 1) grace a la sommation, mais cette informativite a un prix : la non-admissibilite.

Note : h^add peut etre admissible dans certains cas (sous-buts independants) mais ne l’est pas en general. Le caractère admissible est une propriete universelle (h <= h* pour TOUT etat), pas une propriete per-instance.

4. Heuristique FF (Fast Forward)

L’heuristique FF (Hoffmann & Nebel, 2001) est l’une des plus influentes en planification. Elle etend h^add avec une extraction de plan relaxe.

4.1 Principe de FF

FF construit un plan relaxe (sans effets negatifs) et compte le nombre d’actions :

Construire le graphe de planification relaxe (similaire a h^add)
Extraire un plan en remontant depuis le but (extraction gloutonne)
Compter les actions uniques du plan extrait

\[h^{FF}(s) = \text{nombre d'actions dans le plan relaxe extrait}\]

4.2 Proprietes de FF

Propriete	Valeur	Explication
Admissible	Non	Peut surestimer
Rapide	Oui	Extraction gloutonne polynomiale
Opérateurs preferes	Oui	Actions du plan relaxe
Performance	Excellente	Gagnant IPC 2000

def h_ff(problem: STRIPSProblem, state: Set[str]) -> Tuple[int, Set[str]]:
    """
    Calcule l'heuristique FF.
    
    Etapes :
    1. Construire le graphe de relaxation (comme h^add)
    2. Extraire un plan glouton depuis le but
    3. Retourner le nombre d'actions + les actions helpful
    """
    # Etape 1 : Construire le graphe de relaxation
    fact_costs: Dict[str, int] = {}
    achievers: Dict[str, Optional[STRIPSAction]] = {}  # Meilleur achiever pour chaque fait
    
    for fact in state:
        fact_costs[fact] = 0
        achievers[fact] = None
    
    changed = True
    while changed:
        changed = False
        for action in problem.actions:
            if all(p in fact_costs for p in action.preconditions):
                action_cost = sum(fact_costs[p] for p in action.preconditions) + action.cost
                
                for effect in action.add_effects:
                    if effect not in fact_costs or fact_costs[effect] > action_cost:
                        fact_costs[effect] = action_cost
                        achievers[effect] = action
                        changed = True
    
    # Verifier si le but est atteignable
    if not all(g in fact_costs for g in problem.goal):
        return float('inf'), set()
    
    # Etape 2 : Extraction gloutonne du plan
    plan_actions: Set[str] = set()
    goals_to_achieve = set(problem.goal)
    processed_facts: Set[str] = set()
    
    def extract_plan(facts: Set[str], depth: int = 0) -> None:
        """Extraction recursive du plan."""
        if depth > 100:  # Limite de recursion
            return
        
        for fact in facts:
            if fact in processed_facts or fact in state:
                continue
            
            processed_facts.add(fact)
            
            if fact in achievers and achievers[fact] is not None:
                action = achievers[fact]
                plan_actions.add(action.name)
                # Recursivement traiter les preconditions
                extract_plan(action.preconditions, depth + 1)
    
    extract_plan(goals_to_achieve)
    
    # Etape 3 : h^FF = nombre d'actions dans le plan
    h_value = len(plan_actions)
    
    # Helpful actions = actions applicables dans l'etat courant
    helpful = set()
    for action in problem.actions:
        if action.preconditions.issubset(state) and action.name in plan_actions:
            helpful.add(action.name)
    
    return h_value, helpful

# Test
h_ff_val, ff_helpful = h_ff(multi_switch_problem, {"off_1", "off_2", "off_3"})
print(f"h^FF : {h_ff_val}")
print(f"Actions helpful : {ff_helpful}")

h^FF : 3
Actions helpful : {'turn_on_2', 'turn_on_1', 'turn_on_3'}

Interpretation

L’heuristique FF retourne 3 et identifie les trois actions turn_on_* comme helpful actions.

Comment FF calcule sa valeur : 1. Graphe de relaxation : comme h^add, propager les couts dans le graphe sans effets negatifs 2. Extraction gloutonne : remonter depuis les buts (on_1, on_2, on_3) vers l’etat initial via les meilleurs “achievers” 3. Comptage : chaque action unique du plan extrait contribue 1 au total

Pourquoi FF = h^add ici : sur des sous-buts independants, le plan relaxe contient exactement une action par sous-but, donc le comptage FF egal la somme h^add. FF diverge de h^add quand des actions atteignent plusieurs sous-buts simultanement (FF les compte une seule fois).

# Demonstration : FF ne double-compte pas les actions partagees (cf. section 3.5)
# Sur le probleme a precondition partagee, h^add = 4 (double-compte 'setup'),
# alors que h^FF compte le plan relaxe {setup, make_g1, make_g2} = 3 = h*.
h_ff_shared, _ = h_ff(shared_problem, shared_problem.initial_state)

print("h^add vs h^FF sur le probleme a precondition partagee (section 3.5)")
print("=" * 62)
print(f"  Action partagee 'setup' sert les deux sous-buts g1 et g2 via le fait p")
print(f"  h^add = {h_add_shared}   (compte setup deux fois : 2 + 2 = 4 > h*)")
print(f"  h^FF  = {h_ff_shared}    (plan relaxe {{setup, make_g1, make_g2}} = 3 = h*)")
print(f"  h*    = {h_star_shared}")
print()
print(f"FF = {h_ff_shared} = h* < h^add = {h_add_shared} : FF ne surestime pas ici.")

h^add vs h^FF sur le probleme a precondition partagee (section 3.5)
==============================================================
  Action partagee 'setup' sert les deux sous-buts g1 et g2 via le fait p
  h^add = 4   (compte setup deux fois : 2 + 2 = 4 > h*)
  h^FF  = 3    (plan relaxe {setup, make_g1, make_g2} = 3 = h*)
  h*    = 3

FF = 3 = h* < h^add = 4 : FF ne surestime pas ici.

Interpretation : FF vs h^add sur les actions partagees

Cette demonstration mesure concretement la divergence annoncee plus haut : sur le probleme a precondition partagee de la section 3.5, h^FF = 3 = h* alors que h^add = 4 > h*.

Pourquoi FF fait mieux ici : le plan relaxe extrait par FF est {setup, make_g1, make_g2}. L’action setup (qui produit le fait p servant de precondition aux deux sous-buts) n’apparait qu’une seule fois dans l’ensemble des actions du plan – FF compte des actions uniques, pas une somme de couts par sous-but. h^add, lui, propage le cout de p independamment dans chaque branche et le compte deux fois (2 + 2 = 4).

C’est exactement le cas que la cellule precedente decrivait (« FF diverge de h^add quand des actions atteignent plusieurs sous-buts simultanement ») : setup atteint indirectement les deux sous-buts via p, donc FF la compte une fois et h^add la compte deux fois. C’est une motivation historique de FF (Hoffmann & Nebel, 2001) : conserver la guidance de h^add sans sa surestimation catastrophique sur les actions partagees.

Source : valeurs mesurees dans la cellule de code ci-dessus (h^FF = 3, issue de h_ff(shared_problem) ; h^add = 4 et h = 3, mesurees en section 3.5).*

4.3 Intérêt des opérateurs preferes

L’heuristique FF identifie les actions helpful qui apparaissent dans le plan relaxe et sont applicables dans l’etat courant.

Utilisation : - Eager Greedy Search : Explorer en priorite les etats via les opérateurs preferes - Lazy Greedy Search : Evaluer d’abord les opérateurs preferes

Cette technique accelere considerablement la recherche en pratique.

5. Heuristiques basees sur les Landmarks

Un landmark est un fait (ou un ensemble de faits) qui doit etre vrai a un moment quelconque de tout plan solution.

5.1 Definition formelle

Un litteral \(L\) est un landmark pour le problème \(P\) si pour tout plan valide \(\pi\) pour \(P\), il existe un etat \(s\) dans la trace d’exécution de \(\pi\) tel que \(L \in s\).

Exemple : Dans le problème des blocs, pour empiler A sur B, le landmark est “A doit etre libre (clear)”.

5.2 Types de landmarks

Type	Definition	Exemple
Fait	Un predicat doit etre vrai	`holding(a)`
Disjonctif	Au moins un des faits	`on(a,b) OR on(a,c)`
Conjonctif	Tous les faits (equivalent a plusieurs landmarks)	`clear(a) AND handempty`
Ordre	\(L_1\) doit etre atteint avant \(L_2\)	`pickup(a)` avant `stack(a,b)`

def extract_simple_landmarks(problem: STRIPSProblem) -> Tuple[Set[str], List[Tuple[str, str]]]:
    """
    Extrait les landmarks simples et leur ordre.
    
    Methode simplifiee basee sur l'analyse des RCC (Relaxed Component Graph).
    Pour chaque fait du but non present dans l'etat initial, c'est un landmark.
    """
    landmarks: Set[str] = set()
    landmark_order: List[Tuple[str, str]] = []  # (L1 avant L2)
    
    # Les faits du but non dans l'initial sont des landmarks
    for g in problem.goal:
        if g not in problem.initial_state:
            landmarks.add(g)
    
    # Pour chaque landmark, les obligations sont les preconditions PARTAGEES par TOUS ses
    # achievers (intersection) : un landmark atteignable par plusieurs branches n'impose
    # que ce qui est commun a toutes les branches — l'union promouvait en obligations les
    # preconditions d'une seule branche prise pour l'autre.
    for landmark in list(landmarks):
        achiever_preconds = [
            {p for p in action.preconditions if p not in problem.initial_state}
            for action in problem.actions
            if landmark in action.add_effects
        ]
        if achiever_preconds:
            for precond in set.intersection(*achiever_preconds):
                landmarks.add(precond)
                landmark_order.append((precond, landmark))
    
    return landmarks, landmark_order

# Test sur le probleme multi-interrupteur
landmarks, order = extract_simple_landmarks(multi_switch_problem)
print("Landmarks extraits :")
for lm in landmarks:
    print(f"  - {lm}")
print(f"\nOrdre des landmarks : {order}")

Landmarks extraits :
  - on_2
  - on_3
  - on_1

Ordre des landmarks : []

Interpretation

L’extraction de landmarks identifie les faits obligatoires du problème :

on_1, on_2, on_3 sont des landmarks car ils appartiennent au but et ne sont pas dans l’etat initial
L’ordre des landmarks est vide [] car les trois actions sont independantes (pas de precondition partagee entre turn_on_1, turn_on_2, turn_on_3)

Contraste avec un problème structure : Dans Blocks World, les landmarks incluraient un ordre comme (clear_b, on_a_b) car il faut liberer B avant d’y empiler A. L’algorithme detecte ces dependances en remontant les preconditions communes des “achievers” (intersection) : une seule branche suffit a atteindre un landmark, donc seules les obligations partagees par toutes les branches sont promues landmarks.

Implementation de l’heuristique landmark-counting qui compte le nombre de landmarks non encore atteints pour estimer le cout restant jusqu’au but.

def h_landmark_count(problem: STRIPSProblem, state: Set[str]) -> int:
    """
    Heuristique landmark-counting (simplifiee).
    
    Compte le nombre de landmarks non encore atteints.
    """
    landmarks, _ = extract_simple_landmarks(problem)
    
    # Landmarks non satisfaits
    unsatisfied = landmarks - state
    
    return len(unsatisfied)

# Test
h_lm = h_landmark_count(multi_switch_problem, {"off_1", "off_2", "off_3"})
print(f"h_landmark depuis l'etat initial : {h_lm}")
print(f"Landmarks non satisfaits : {landmarks - {'off_1', 'off_2', 'off_3'}}")

h_landmark depuis l'etat initial : 3
Landmarks non satisfaits : {'on_2', 'on_3', 'on_1'}

Interpretation

L’heuristique h_landmark_count retourne 3 car aucun des trois landmarks (on_1, on_2, on_3) n’est satisfait dans l’etat initial. Chaque interrupteur eteint represente un landmark qu’il faut obligatoirement franchir.

Points cles : - L’ordre est vide ici car les trois actions turn_on_N sont independantes (aucune precondition partagee) - Dans un problème avec des dependances (ex: Blocks World), l’ordre capturerait “il faut liberer B avant de poser A sur B” - Attention : le comptage naive des landmarks n’est pas admissible en general. Une seule action peut satisfaire plusieurs landmarks simultanement, auquel cas le compte surestime le nombre d’actions necessaires. La variante admissible est LM-cut (cf section 5.3), qui utilise des cuts disjoints avec partage de cout. Sur ce problème (une action par landmark), le compte egalise h* (3 = 3), mais c’est une coincidence structurelle, pas une garantie.

Pro	Con
Simple a calculer, identifie les obligations cles	Non admissible : une action peut couvrir plusieurs landmarks
Capture les dependances via l’ordre	Compte = 1 pour chaque landmark, sans nuance

Garde : intersection vs union des preconditions des achieveurs

Un landmark atteignable par plusieurs actions n’impose pas toutes leurs preconditions : une seule branche suffit a l’atteindre. Les obligations reelles sont les preconditions communes a tous les achieveurs (intersection). Deux branches disjointes ne creent aucune obligation au-dela du but lui-meme ; deux branches partageant c font de c une vraie landmark — et h_landmark_count rend 0 sur un etat but (l’union promouvait x et y en landmarks fantomes et rendait 1).

# Controles : les obligations d'un landmark a plusieurs achievers sont les
# preconditions PARTAGEES (intersection), pas l'union.
two_branch = STRIPSProblem(
    initial_state={"s"}, goal={"g"},
    actions=[STRIPSAction("branche_x", {"x"}, {"g"}, cost=1),
             STRIPSAction("branche_y", {"y"}, {"g"}, cost=1)],
)
shared_branch = STRIPSProblem(
    initial_state={"s"}, goal={"g"},
    actions=[STRIPSAction("v1", {"c", "x"}, {"g"}, cost=1),
             STRIPSAction("v2", {"c", "y"}, {"g"}, cost=1)],
)
single_achiever = STRIPSProblem(
    initial_state={"s"}, goal={"g"},
    actions=[STRIPSAction("seul", {"c"}, {"g"}, cost=1)],
)
for pb, nom in ((two_branch, "branches disjointes (x|y)"),
                (shared_branch, "branches partageant c"),
                (single_achiever, "achiever unique")):
    lms, order = extract_simple_landmarks(pb)
    print(f"{nom:28s} -> landmarks {sorted(lms)} | ordre {sorted(order)}")

# Consequence : h_landmark_count rend 0 sur un etat but.
print(f"\nh_landmark_count(two_branch, s|x|g) = {h_landmark_count(two_branch, {'s', 'x', 'g'})} (attendu 0)")
print(f"h_landmark_count(shared, s|c|g)     = {h_landmark_count(shared_branch, {'s', 'c', 'g'})} (attendu 0)")

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)

5.3 L’heuristique LM-cut

LM-cut (Helmert & Domshlak, 2009) est une heuristique admissible basee sur les landmarks.

Principe : 1. Identifier des “cuts” (coupures) dans le graphe de relaxation 2. Chaque cut définit un landmark disjonctif (au moins une action du cut doit etre executee) 3. Sommer les couts minimaux de chaque cut

\[h^{LM-cut}(s) = \sum_{L \in \text{cuts}} \min_{a \in L} cost(a)\]

Proprietes : - Admissible : Garantit l’optimalite avec A* - Precise : Souvent superieure a h^max - Utilisee dans les planificateurs optimaux (Fast Downward)

Note : L’implementation complete de LM-cut est complexe. Fast Downward l’implemente efficacement.

6. Comparaison des Heuristiques

Comparons les différentes heuristiques sur un problème de benchmark.

6.1 Problème de benchmark : Blocks World simplifie

# Probleme Blocks World simplifie : 3 blocs
# Etat initial : (A sur table), (B sur table), (C sur table), tous clairs
# But : (A sur B), (B sur C)

blocks_actions = [
    # pick-up(x) : prendre un bloc de la table
    STRIPSAction("pick_up_a", {"clear_a", "ontable_a", "handempty"}, 
                 {"holding_a"}, cost=1),
    STRIPSAction("pick_up_b", {"clear_b", "ontable_b", "handempty"}, 
                 {"holding_b"}, cost=1),
    STRIPSAction("pick_up_c", {"clear_c", "ontable_c", "handempty"}, 
                 {"holding_c"}, cost=1),
    
    # stack(x, y) : poser un bloc sur un autre
    STRIPSAction("stack_a_b", {"holding_a", "clear_b"}, 
                 {"on_a_b", "clear_a", "handempty"}, cost=1),
    STRIPSAction("stack_b_c", {"holding_b", "clear_c"}, 
                 {"on_b_c", "clear_b", "handempty"}, cost=1),
    STRIPSAction("stack_a_c", {"holding_a", "clear_c"}, 
                 {"on_a_c", "clear_a", "handempty"}, cost=1),
]

blocks_problem = STRIPSProblem(
    initial_state={"clear_a", "clear_b", "clear_c", 
                   "ontable_a", "ontable_b", "ontable_c", "handempty"},
    goal={"on_a_b", "on_b_c"},
    actions=blocks_actions
)

print("Probleme Blocks World simplifie")
print(f"Etat initial : {blocks_problem.initial_state}")
print(f"But : {blocks_problem.goal}")
print(f"Nombre d'actions : {len(blocks_problem.actions)}")

Probleme Blocks World simplifie
Etat initial : {'clear_a', 'clear_c', 'ontable_c', 'ontable_a', 'ontable_b', 'clear_b', 'handempty'}
But : {'on_a_b', 'on_b_c'}
Nombre d'actions : 6

Calcul et comparaison des valeurs de toutes les heuristiques implementees sur l’etat initial du problème Blocks World : h^max, h^add, h^FF et h^landmark.

# Benchmark des heuristiques - propriete d'admissibilite UNIVERSELLE
# (h <= h* pour TOUT etat s), pas per-instance :
#   h^max        -> Oui    (ne surestime jamais)
#   h^add, h_FF, h_landmark -> Non  (surestiment sur problemes a actions partagees)
ADMISSIBLE_UNIVERSAL = {
    "h^max": "Oui",      # max des couts = borne inf sure
    "h^add": "Non",      # peut surestimer (cf cellule 3.5 : h^add=4 > h*=3)
    "h^FF":  "Non",      # extraction de plan relaxe, surestime generalement
    "h_landmark": "Non", # comptage naif, surestime (cf. LM-cut pour la variante admissible)
}
initial = blocks_problem.initial_state
results = {
    "h^max": h_max(blocks_problem, initial),
    "h^add": h_add(blocks_problem, initial)[0],
    "h^FF": h_ff(blocks_problem, initial)[0],
    "h_landmark": h_landmark_count(blocks_problem, initial),
}
print("Comparaison des heuristiques sur Blocks World")
print("=" * 60)
print(f"{'Heuristique':<15} {'Valeur':<10} {'Admissible (universelle)'}")
print("-" * 60)
# h* optimal = 4 actions (pick_up_b -> stack_b_c -> pick_up_a -> stack_a_b)
h_optimal = 4
for name, value in results.items():
    if value == float('inf'):
        val_str = "inf"
    else:
        val_str = str(value)
    # Admissibilite universelle (propriete theorique), pas value <= h*
    admissible = ADMISSIBLE_UNIVERSAL[name]
    print(f"{name:<15} {val_str:<10} {admissible}")
print("-" * 60)
print(f"h* (optimal)    {h_optimal}")
print()
print("Note : sur cette instance particuliere, h^add = h^FF = h_landmark = h* = 4,")
print("      mais cela ne les rend pas admissibles en general (cf cellule 3.5).")

Comparaison des heuristiques sur Blocks World
============================================================
Heuristique     Valeur     Admissible (universelle)
------------------------------------------------------------
h^max           2          Oui
h^add           4          Non
h^FF            4          Non
h_landmark      4          Non
------------------------------------------------------------
h* (optimal)    4

Note : sur cette instance particuliere, h^add = h^FF = h_landmark = h* = 4,
      mais cela ne les rend pas admissibles en general (cf cellule 3.5).

Visualisation sous forme de graphique en barres des valeurs heuristiques calculees pour chaque méthode, facilitant la comparaison visuelle de leur informativite respective.

# Visualisation des resultats
fig, ax = plt.subplots(figsize=(10, 6))

heuristic_names = list(results.keys())
values = [v if v != float('inf') else 0 for v in results.values()]
colors = ['green' if v <= h_optimal else 'red' for v in results.values()]

bars = ax.bar(heuristic_names, values, color=colors, alpha=0.7, edgecolor='black')
ax.axhline(y=h_optimal, color='blue', linestyle='--', linewidth=2, label=f'h* = {h_optimal}')

ax.set_xlabel('Heuristique', fontsize=12)
ax.set_ylabel('Valeur', fontsize=12)
ax.set_title('Comparaison des heuristiques sur Blocks World', fontsize=14)
ax.legend()

# Annoter les barres
for bar, val in zip(bars, results.values()):
    height = bar.get_height()
    ax.annotate(f'{val}',
                xy=(bar.get_x() + bar.get_width() / 2, height),
                ha='center', va='bottom', fontsize=11)

plt.tight_layout()
plt.show()

6.2 Interpretation des résultats

Heuristique	Valeur	Admissible (universelle)	Commentaire
h^max	2	Oui	Maximum des sous-buts, sous-estime systematiquement
h^add	4	Non	Somme des sous-buts, = h* ici (coincidence) mais surestime sur actions partagees (cf cellule 3.5 : h^add = 4 > h* = 3)
h^FF	4	Non	Extrait un plan relaxe, pas d’optimalite garantie en general
h_landmark	4	Non	Compte les landmarks non atteints, = h* ici, non admissible en general
h*	4	-	Cout optimal reel

Observations :

h^max est admissible (propriete universelle) mais souvent trop pessimiste : la valeur 2 sous-estime le cout optimal 4.
h^add, h^FF, h_landmark ne sont PAS admissibles en general, même s’ils coincident avec h* sur cette instance particuliere. La colonne ‘Admissible’ reflete une propriete théorique (h <= h* pour tout etat), pas une coincidence per-instance.
Demonstration concrete de non-admissibilite : voir la cellule 3.5 (problème a precondition partagee) ou h^add = 4 > h* = 3.

Compromis qualite/vitesse :

Pour optimalite : h^max, LM-cut (admissibles)
Pour vitesse : h^FF (très informative, pas d’optimalite garantie)

6.3 Les heuristiques guident-elles VRAIMENT la recherche ?

Jusqu’ici (§6.1–§6.2) nous avons calculé les valeurs des heuristiques (\(h^{max}\), \(h^{add}\), \(h^{FF}\)) et comparé leur qualité (admissibilité, informativité). 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 \(h^{max}=3\) et \(h^{add}=3\) mais qu’aucune des deux ne fait explorer moins de nœuds que la recherche aveugle, alors elles ne « valent » rien en pratique. Mesurons-le directement.

Pour cela nous avons besoin de (i) des algorithmes de recherche dans le graphe d’états — uniform-cost (aveugle, \(h \equiv 0\)), A* (\(g + h\), optimal si \(h\) admissible), et greedy best-first (\(h\) seul, non optimal mais rapide) — et (ii) d’un problème où la recherche aveugle a quelque chose à perdre : 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/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.

import heapq
import itertools

def successeurs(problem, state):
    """Etats successeurs d'un etat (semantique delete-free de STRIPSProblem :
    on accumule les add_effects des actions applicables). Renvoie (action, nouvel_etat)."""
    resultats = []
    for action in problem.actions:
        if action.preconditions.issubset(state):
            nouvel_etat = state | action.add_effects
            if nouvel_etat != state:  # ignorer les no-ops (faits deja presents)
                resultats.append((action, nouvel_etat))
    return resultats

def recherche(problem, h_fn=None, mode="ucs"):
    """Recherche dans le graphe d'etats. mode='ucs' (aveugle, h=0), 'astar' (g+h),
    'greedy' (h seul). Renvoie (cout_solution, noeuds_developpes). Un noeud est
    'developpe' quand il est sorti de la frontiere et expansé (successeurs generes)."""
    def cle(g, h):
        if mode == "ucs":    return (g,)
        if mode == "astar":  return (g + h, g)
        if mode == "greedy": return (h, g)
    compteur = itertools.count()
    depart = frozenset(problem.initial_state)
    h0 = h_fn(problem, set(depart)) if h_fn else 0
    frontiere = [(cle(0, h0), next(compteur), 0, h0, depart)]
    fermes = set()
    developpes = 0
    while frontiere:
        _, _, g, h, etat = heapq.heappop(frontiere)
        if etat in fermes:
            continue
        fermes.add(etat)
        developpes += 1
        if problem.goal.issubset(etat):
            return g, developpes
        for action, suivant in successeurs(problem, etat):
            if suivant in fermes:
                continue
            ng = g + action.cost
            nh = h_fn(problem, set(suivant)) if h_fn else 0
            heapq.heappush(frontiere, (cle(ng, nh), next(compteur), ng, nh, suivant))
    return None, developpes

def probleme_chaine_avec_distracteurs(M, D):
    """But : realiser une chaine c0 -> c1 -> ... -> cM (cout optimal M). La
    bibliotheque d'actions contient en PLUS D chaines 'leurres' d_j : c0 -> d_j ->
    dd_j qui ne contribuent PAS au but. Ces faits/actions non pertinents sont
    omnipresents dans les vrais domaines : un planificateur aveugle perd du temps a
    les explorer, une recherche guidee par heuristique les ignore."""
    actions = [STRIPSAction(f"etape_but_{j+1}", {f"c{j}"}, {f"c{j+1}"}, 1) for j in range(M)]
    for j in range(D):
        actions.append(STRIPSAction(f"leurre_{j}_1", {"c0"}, {f"d{j}"}, 1))
        actions.append(STRIPSAction(f"leurre_{j}_2", {f"d{j}"}, {f"dd{j}"}, 1))
    return STRIPSProblem({"c0"}, {f"c{M}"}, actions)

# Wrappers : h_max renvoie un int, mais h_add/h_ff renvoient (valeur, helpful_actions).
h_max_pur  = lambda p, s: h_max(p, s)
h_add_pur  = lambda p, s: h_add(p, s)[0]
h_ff_pur   = lambda p, s: h_ff(p, s)[0]

print("Benchmark : nombre de NOEUDS DEVELOPPES (deterministe, reproductible)")
print("But = chaine de longueur M  ;  D = chaines leurres (faits non pertinents)\n")
print(f"{'M':>3} {'D':>3} | {'UCS (aveugle)':>14} {'A*+h^max':>10} {'A*+h^add':>10} {'Greedy+h^FF':>12}")
print("-" * 62)
for (M, D) in [(3, 0), (3, 4), (3, 8), (3, 12), (3, 16)]:
    p = probleme_chaine_avec_distracteurs(M, D)
    _, ucs  = recherche(p, None,      "ucs")
    _, amax = recherche(p, h_max_pur, "astar")
    _, aadd = recherche(p, h_add_pur, "astar")
    _, gff  = recherche(p, h_ff_pur,  "greedy")
    print(f"{M:>3} {D:>3} | {ucs:>14} {amax:>10} {aadd:>10} {gff:>12}")

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            4

Lecture — 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.

Trois observations rendent cette mesure probante :

Elle isole le mécanisme. Les valeurs \(h^{max}\) et \(h^{add}\) (§3.4) décrivent la qualité de l’estimation ; le compte de nœuds mesure son effet sur la recherche — une grandeur différente, qui est précisément ce qui justifie l’usage pratique des heuristiques. Sur cette structure de chaîne, \(h^{max}\) et \(h^{add}\) guident identiquement (toutes deux admissibles, toutes deux identifient le chemin optimal) — leur différence (l’inadmissibilité de \(h^{add}\), §3.5) est orthogogonale au compte de nœuds ici ; ce qui compte est heuristique-guidée vs aveugle.
Elle est déterministe. Les comptes sont des entiers reproductibles à l’identique sur toute machine (même graphe d’états ⟹ mêmes développements) — là où un benchmark temporel flotterait avec la charge.
Elle est réaliste. Les vrais domaines (Logistics, Gripper, Blocks World) contiennent des dizaines à centaines de faits/actions non pertinents ; c’est exactement cette structure que les heuristiques de relaxation (\(h^{FF}\), \(h^{LM}\), LM-cut) et le filtrage des helpful actions permettent de dominer — la raison pour laquelle Fast Downward (§7) résout des problèmes où la recherche aveugle est intractable.

Lien CS : la borne théorique est que A* avec une heuristique admissible ne développe que les nœuds de \(f(n) < C^*\) (coût optimal), 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\).

Exemple guide 1 : Problème de Logistics — Comparaison complete des heuristiques

Nous definissons un problème de Logistics simplifie ou un camion doit livrer des colis dans trois villes. Ce problème est suffisamment riche pour illustrer les différences entre les heuristiques, avec des dependances entre sous-buts qui montrent pourquoi h^add peut etre non admissible.

Scénario : Un camion est en ville A. Deux colis (pkg1 en A, pkg2 en A) doivent etre livres respectivement en ville B et ville C. Le camion doit se deplacer entre les villes pour effectuer les livraisons.

# Exemple guide 1 : Probleme de Logistics simplifie avec comparaison complete
# Un camion livre 2 colis dans 3 villes (A, B, C)

# Actions STRIPS pour le probleme de logistics
logistics_actions = [
    # Deplacements du camion entre villes (cout 2 = distance)
    STRIPSAction("drive_a_b", {"truck_at_a"}, {"truck_at_b"}, cost=2),
    STRIPSAction("drive_b_a", {"truck_at_b"}, {"truck_at_a"}, cost=2),
    STRIPSAction("drive_b_c", {"truck_at_b"}, {"truck_at_c"}, cost=2),
    STRIPSAction("drive_c_b", {"truck_at_c"}, {"truck_at_b"}, cost=2),
    STRIPSAction("drive_a_c", {"truck_at_a"}, {"truck_at_c"}, cost=3),
    STRIPSAction("drive_c_a", {"truck_at_c"}, {"truck_at_a"}, cost=3),
    # Chargement de colis (cout 1)
    STRIPSAction("load_pkg1", {"truck_at_a", "pkg1_at_a"}, {"pkg1_in_truck"}, cost=1),
    STRIPSAction("load_pkg2", {"truck_at_a", "pkg2_at_a"}, {"pkg2_in_truck"}, cost=1),
    # Dechargement de colis (cout 1)
    STRIPSAction("unload_pkg1_b", {"truck_at_b", "pkg1_in_truck"}, {"pkg1_at_b"}, cost=1),
    STRIPSAction("unload_pkg2_c", {"truck_at_c", "pkg2_in_truck"}, {"pkg2_at_c"}, cost=1),
]

logistics_problem = STRIPSProblem(
    initial_state={"truck_at_a", "pkg1_at_a", "pkg2_at_a"},
    goal={"pkg1_at_b", "pkg2_at_c"},
    actions=logistics_actions
)

print("Probleme Logistics simplifie")
print(f"Etat initial : {logistics_problem.initial_state}")
print(f"But : {logistics_problem.goal}")
print(f"Nombre d'actions : {len(logistics_problem.actions)}")
print()

# Calcul de toutes les heuristiques
h_max_log = h_max(logistics_problem, logistics_problem.initial_state)
h_add_log, helpful_add = h_add(logistics_problem, logistics_problem.initial_state)
h_ff_log, helpful_ff = h_ff(logistics_problem, logistics_problem.initial_state)
h_lm_log = h_landmark_count(logistics_problem, logistics_problem.initial_state)

# Plan optimal : load_pkg1 -> drive_a_b -> unload_pkg1_b -> drive_b_a -> load_pkg2 ->
#               drive_a_c -> unload_pkg2_c = 7 actions, cout = 1+2+1+2+1+3+1 = 11
# Ou plus optimal : load_pkg1, load_pkg2, drive_a_b, unload_pkg1_b, drive_b_c, unload_pkg2_c
# Mais load a besoin de truck_at_a et pkgX_at_a simultanement
# Meilleur plan : load_pkg1(1) -> load_pkg2(1) -> drive_a_b(2) -> unload_pkg1_b(1) -> drive_b_c(2) -> unload_pkg2_c(1)
# Cout = 1+1+2+1+2+1 = 8
h_optimal_log = 8

print("Comparaison complete des heuristiques - Logistics")
print("=" * 60)
print(f"{'Heuristique':<15} {'Valeur':<10} {'Admissible':<12} {'Helpful'}")
print("-" * 60)

heuristics_log = {
    "h^max": (h_max_log, set()),
    "h^add": (h_add_log, helpful_add),
    "h^FF": (h_ff_log, helpful_ff),
    "h_landmark": (h_lm_log, set()),
}

for name, (value, helpful) in heuristics_log.items():
    admissible = "Oui" if value <= h_optimal_log else "Non"
    helpful_str = ", ".join(sorted(helpful)[:3]) if helpful else "-"
    print(f"{name:<15} {value:<10} {admissible:<12} {helpful_str}")

print("-" * 60)
print(f"h* (optimal)    {h_optimal_log}")
print()
print("Plan optimal (cout 8) :")
print("  1. load_pkg1    (1) : charger colis 1 en A")
print("  2. load_pkg2    (1) : charger colis 2 en A")
print("  3. drive_a_b    (2) : aller a B")
print("  4. unload_pkg1_b(1) : decharger colis 1 en B")
print("  5. drive_b_c    (2) : aller a C")
print("  6. unload_pkg2_c(1) : decharger colis 2 en C")

Probleme Logistics simplifie
Etat initial : {'pkg1_at_a', 'truck_at_a', 'pkg2_at_a'}
But : {'pkg2_at_c', 'pkg1_at_b'}
Nombre d'actions : 10

Comparaison complete des heuristiques - Logistics
============================================================
Heuristique     Valeur     Admissible   Helpful
------------------------------------------------------------
h^max           4          Oui          -
h^add           9          Non          unload_pkg1_b, unload_pkg2_c
h^FF            6          Oui          drive_a_b, drive_a_c, load_pkg1
h_landmark      6          Oui          -
------------------------------------------------------------
h* (optimal)    8

Plan optimal (cout 8) :
  1. load_pkg1    (1) : charger colis 1 en A
  2. load_pkg2    (1) : charger colis 2 en A
  3. drive_a_b    (2) : aller a B
  4. unload_pkg1_b(1) : decharger colis 1 en B
  5. drive_b_c    (2) : aller a C
  6. unload_pkg2_c(1) : decharger colis 2 en C

Interpretation de l’Exemple guide

Le problème de Logistics illustre comment les heuristiques se comportent sur un problème avec des dependances séquentielles : le camion doit passer par B pour aller a C, et les colis doivent etre charges avant le transport.

Points cles observes :

h^max : Ne retient que le sous-but le plus couteux. Même si deux livraisons sont necessaires, h^max ne voit que le chemin le plus long (A -> B -> C = cout 4), ignorant le cout de chargement/dechargement
h^add : Additionne les couts de chaque sous-but independamment. Cela peut surestimer car le chemin A -> B sert a la fois pour la livraison de pkg1 et comme étape vers C pour pkg2
h^FF : Extrait un plan relaxe qui peut partager les actions de deplacement, donnant une estimation plus realiste
h_landmark : Identifie les faits obligatoires (pkg1_at_b, pkg2_at_c) mais ignore les couts de deplacement entre villes

Comparaison avec le Blocks World : Contrairement au Blocks World ou les sous-buts etaient independants, le Logistics introduit une contrainte de route (B est entre A et C) qui créé des interactions entre les sous-buts. C’est dans ces situations que le choix de l’heuristique a le plus d’impact sur la qualite de la recherche.

7. Integration avec unified-planning

Voyons comment utiliser ces heuristiques avec un vrai planificateur.

if UP_OK:
    # Modele Blocks World avec unified-planning, resolu par un VRAI planificateur (pyperplan).
    # Meme probleme que le STRIPS pedagogique ci-dessus, mais avec effets de suppression
    # explicites (delete effects), indispensables a un planificateur reel.
    get_environment().credits_stream = None  # silence la banniere de credits

    problem = Problem("blocks_world")

    Block = UserType("Block")
    f_on = Fluent("on", BoolType(), x=Block, y=Block)
    f_ontable = Fluent("ontable", BoolType(), x=Block)
    f_clear = Fluent("clear", BoolType(), x=Block)
    f_holding = Fluent("holding", BoolType(), x=Block)
    f_handempty = Fluent("handempty", BoolType())
    for f in (f_on, f_ontable, f_clear, f_holding, f_handempty):
        problem.add_fluent(f, default_initial_value=False)

    blk_a = Object("a", Block); blk_b = Object("b", Block); blk_c = Object("c", Block)
    problem.add_objects([blk_a, blk_b, blk_c])

    # pick_up(x) : prendre un bloc clair pose sur la table
    pick_up = InstantaneousAction("pick_up", x=Block)
    x = pick_up.parameter("x")
    pick_up.add_precondition(f_clear(x))
    pick_up.add_precondition(f_ontable(x))
    pick_up.add_precondition(f_handempty())
    pick_up.add_effect(f_holding(x), True)
    pick_up.add_effect(f_clear(x), False)
    pick_up.add_effect(f_ontable(x), False)
    pick_up.add_effect(f_handempty(), False)
    problem.add_action(pick_up)

    # stack(x, y) : poser le bloc tenu sur un bloc clair
    stack = InstantaneousAction("stack", x=Block, y=Block)
    x = stack.parameter("x"); y = stack.parameter("y")
    stack.add_precondition(f_holding(x))
    stack.add_precondition(f_clear(y))
    stack.add_effect(f_on(x, y), True)
    stack.add_effect(f_clear(x), True)
    stack.add_effect(f_handempty(), True)
    stack.add_effect(f_holding(x), False)
    stack.add_effect(f_clear(y), False)
    problem.add_action(stack)

    # Etat initial : A, B, C sur la table, tous clairs, main vide
    for blk in (blk_a, blk_b, blk_c):
        problem.set_initial_value(f_ontable(blk), True)
        problem.set_initial_value(f_clear(blk), True)
    problem.set_initial_value(f_handempty(), True)

    # But : A sur B, B sur C
    problem.add_goal(f_on(blk_a, blk_b))
    problem.add_goal(f_on(blk_b, blk_c))

    print("Resolution avec un vrai planificateur (pyperplan)...")
    with OneshotPlanner(name="pyperplan") as planner:
        result = planner.solve(problem)

    print(f"Statut : {result.status}")
    if result.plan is not None:
        plan_actions = result.plan.actions
        print(f"Plan trouve ({len(plan_actions)} actions) :")
        for i, act in enumerate(plan_actions, 1):
            print(f"  {i}. {act}")
    else:
        plan_actions = None
        print("Aucun plan trouve.")

Resolution avec un vrai planificateur (pyperplan)...
Statut : PlanGenerationResultStatus.SOLVED_SATISFICING
Plan trouve (4 actions) :
  1. pick_up(b)
  2. stack(b, c)
  3. pick_up(a)
  4. stack(a, b)

Validons maintenant le plan trouve avec le PlanValidator de unified-planning, puis comparons son cout (nombre d’actions) avec la valeur h* estimee plus haut par nos heuristiques. Un planificateur optimal doit retourner un plan dont le cout egale exactement h*.

if UP_OK and result.plan is not None:
    # Validation du plan trouve et comparaison de son cout avec h*
    from unified_planning.engines import ValidationResultStatus

    print("Validation du plan par PlanValidator...")
    with PlanValidator(problem_kind=problem.kind, plan_kind=result.plan.kind) as validator:
        check = validator.validate(problem, result.plan)
    plan_valide = check.status == ValidationResultStatus.VALID
    print(f"Plan valide : {plan_valide}")

    cout_plan = len(result.plan.actions)
    h_star = 4  # valeur exacte calculee plus haut par nos heuristiques sur ce probleme
    print(f"Cout du plan (nombre d'actions) : {cout_plan}")
    print(f"h* estimee par nos heuristiques : {h_star}")
    coherent = (cout_plan == h_star)
    print(f"Coherence planificateur / h* : {'OK (h* = cout du plan optimal)' if coherent else 'ECART'}")
else:
    print("Pas de plan a valider (UP_OK indisponible ou aucun plan trouve).")

Validation du plan par PlanValidator...
Plan valide : True
Cout du plan (nombre d'actions) : 4
h* estimee par nos heuristiques : 4
Coherence planificateur / h* : OK (h* = cout du plan optimal)

Interpretation du plan

Le planificateur trouve un plan (optimal ou satisfiable selon l’heuristique utilisee).

Ordre	Action	Effet
1	pick_up(b)	holding(b)
2	stack(b, c)	on(b, c), handempty
3	pick_up(a)	holding(a)
4	stack(a, b)	on(a, b)

Cout optimal : 4 actions

Ce plan correspond a la valeur h* trouvee par nos heuristiques.

8. Resume et Guide de Sélection

8.1 Tableau recapitulatif des heuristiques

Heuristique	Admissible	Rapide	Opérateurs preferes	Meilleur usage
blind	Oui	Oui	Non	Reference de base
goalcount	Non	Oui	Non	Problemes simples
h^max	Oui	Oui	Non	Recherche optimale simple
h^add	Non	Oui	Oui	Guidance forte, non optimal
h^FF	Non	Oui	Oui	Recherche rapide (satisfiable)
LM-cut	Oui	Moyen	Non	Recherche optimale precise
merge-and-shrink	Oui	Lent	Non	Problemes factorises

8.2 Guide de sélection

Pour la planification optimale : - LM-cut : Meilleur compromis precision/temps - merge-and-shrink : Pour problemes avec structure exploitable - h^max : Pour une heuristique simple et rapide

Pour la planification satisfiable : - FF + GBFS : Standard industriel, très efficace - add + GBFS : Alternative proche de FF

8.3 Lien avec Fast Downward

Fast Downward implemente toutes ces heuristiques :

# Optimal
fast-downward domain.pddl problem.pddl --search "astar(lmcut())"

# Satisfiable
fast-downward domain.pddl problem.pddl --search "eager_greedy([ff()])"

8.4 Points cles a retenir

Concept	Point cle
Relaxation	Ignorer les effets negatifs simplifie le problème
Admissibilite	Garantit l’optimalite avec A*
h^max vs h^add	max = admissible, add = plus informative
FF	Extrait un plan relaxe, identifie les actions utiles
Landmarks	Faits obligatoires, base pour LM-cut
Compromis	Admissibilite vs informativite

Exercice 1

: Analyser l’admissibilitePourquoi h^add n’est pas admissible en general ? Donnez un exemple ou h^add > h.Indice :- Le problème de l’interrupteur simple et le problème a 3 interrupteurs independants ne montrent pas l’inadmissibilite (h^add = h par coincidence structurelle).- La cellule 3.5 ci-dessus demontre une instance minimale ou h^add = 4 > h* = 3 (problème a precondition partagee).- L’exemple guide 1 (Logistics) ci-dessous montre un cas plus realiste ou h^add = 9 > h* = 8 : le cout du deplacement A->B est compte pour la livraison de pkg1 ET comme étape vers C pour pkg2.- A vous : reproduire un cas minimal (2 sous-buts, 1 action partagee) ou un cas structure (>= 3 sous-buts, dependances) et commenter pourquoi h^add surestime.

# Espace pour votre reponse a l'exercice 1
# Creez un probleme ou h_add > h*

# Votre code ici...
print("Exercice a completer")

Exercice a completer

Exercice 2 : Implementer goalcount

Implementez l’heuristique goalcount qui compte simplement le nombre de faits du but non satisfaits dans l’etat courant.

def h_goalcount(problem: STRIPSProblem, state: Set[str]) -> int:
    """
    Heuristique goalcount : compte les faits du but non satisfaits.
    """
    # Votre implementation ici
    pass

# Testez sur le probleme Blocks World
# h_goal = h_goalcount(blocks_problem, blocks_problem.initial_state)
# print(f"h_goalcount : {h_goal}")
print("Exercice a completer")

Exercice a completer

Exercice 3 : Comparer avec unified-planning

Utilisez unified-planning avec Fast Downward pour comparer les temps de resolution avec différentes heuristiques.

# Espace pour votre reponse a l'exercice 3
# Comparez les temps avec lmcut, ff, add, etc.

# Votre code ici...
print("Exercice a completer")

Exercice a completer

10. Conclusion

Recapitulatif

Ce notebook a presente les heuristiques fondamentales de la planification :

Proprietes : Admissibilite, coherence, et leur impact sur l’optimalite
Relaxation : h^max et h^add basees sur la suppression des effets negatifs
FF : Heuristique très efficace avec extraction de plan relaxe
Landmarks : Faits obligatoires et heuristique LM-cut

Prochaines étapes

Dans le notebook suivant, nous explorerons les domaines classiques de planification : - Blocks World - Logistics - Gripper - Depots

Navigation : Index | << Fast Downward | Domaines >>

References

Hoffmann & Nebel (2001) : “The FF Planning System”
Helmert & Domshlak (2009) : “Landmarks, Critical Paths and Abstractions”
Bonet & Geffner (2001) : “Planning as Heuristic Search”
Fast Downward Documentation

Retour au sommet

Objectifs d’apprentissage

Prerequis

Duree estimee : 40 minutes

1. Introduction aux Heuristiques

1.1 Pourquoi les heuristiques sont essentielles

1.2 Planification optimale vs satisfiable

2. Proprietes des Heuristiques

2.1 Admissibilite

2.2 Coherence (Consistence)

2.3 Tableau recapitulatif des proprietes

Interpretation de l’environnement

3. Heuristiques basees sur la Relaxation

3.1 La relaxation de suppression (Delete Relaxation)

3.2 Heuristique h^max

Garde : h^max sur les ensembles vides

Interpretation

3.3 Heuristique h^add (Additive)

Interpretation

3.4 Comparaison h^max vs h^add

3.5 Demonstration : h^add n’est PAS admissible en general

Interpretation : la non-admissibilite de h^add est observee concretement

Interpretation de la comparaison

4. Heuristique FF (Fast Forward)

4.1 Principe de FF

4.2 Proprietes de FF

Interpretation

Interpretation : FF vs h^add sur les actions partagees

4.3 Intérêt des opérateurs preferes

5. Heuristiques basees sur les Landmarks

5.1 Definition formelle

5.2 Types de landmarks

Interpretation

Interpretation

Garde : intersection vs union des preconditions des achieveurs

5.3 L’heuristique LM-cut

6. Comparaison des Heuristiques

6.1 Problème de benchmark : Blocks World simplifie

6.2 Interpretation des résultats

6.3 Les heuristiques guident-elles VRAIMENT la recherche ?

Exemple guide 1 : Problème de Logistics — Comparaison complete des heuristiques

Interpretation de l’Exemple guide

7. Integration avec unified-planning

Interpretation du plan

8. Resume et Guide de Sélection

8.1 Tableau recapitulatif des heuristiques

8.2 Guide de sélection

8.3 Lien avec Fast Downward

8.4 Points cles a retenir

Exercice 1

Exercice 2 : Implementer goalcount

Exercice 3 : Comparer avec unified-planning

10. Conclusion

Recapitulatif

Prochaines étapes

References

Garde : `h^max` sur les ensembles vides