Search-03f · Réparer localement sous garantie : la recherche incrémentale LPA*

Ce carnet approfondit Search-03 (recherche informée et A*) : A* calcule un plan optimal une fois pour toutes — mais le monde, lui, bouge. Une route se bloque, une cellule se révèle infranchissable, et le plan optimal d’hier traverse un mur. La question de ce carnet est celle de l’opération 6 de la table des opérations (EPIC #12204) :

Réparer localement sous garantie — réparer un plan après un changement local, en ne recalculant que ce que le changement a invalidé, tout en transportant la garantie (ici : l’optimalité) du calcul initial.

C’est la même opération que le safe subgame solving attesté côté GameTheory par le binôme GT-13b/13c : réparer la stratégie dans le sous-jeu affecté, la garantie globale reste tenue. Ce carnet en est la seconde attestation, sur un autre substrat : la recherche de chemin incrémentale.

Les trois personnages :

Stratégie	Ce qu’elle fait	Garantie
A* from scratch	oublie tout, recalcule tout	optimale, mais payée 273 expansions
Repair naïf	suit le plan initial, contourne l’obstacle, rejoint le plan	aucune — c’est le contre-témoin
LPA* (Koenig & Likhachev, 2002)	réutilise les estimations \(g\) encore valides, ne répare que les incohérences	optimale, transportée — payée 12 expansions

Ce que le carnet atteste, en une phrase : la garantie d’optimalité n’est pas une propriété du calcul complet, mais de la propagation des incohérences — couper la propagation produit un plan invalide ou un coût faux ; la réparer entièrement rend l’optimalité au prix uniquement de ce qui a changé.

Navigation : << Search-03e — optimalité de A* | Index | retour au parent Search-03 (A*) ↑

# Le monde : grille 24x16, 4-connexe, couts unitaires. Un couloir muré force le passage.
import heapq
import itertools

INF = float("inf")


class Grid:
    def __init__(self, w, h, walls):
        self.w, self.h = w, h
        self.walls = set(walls)

    def in_bounds(self, s):
        x, y = s
        return 0 <= x < self.w and 0 <= y < self.h

    def passable(self, s):
        return s not in self.walls

    def neighbors(self, s):
        x, y = s
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            n = (x + dx, y + dy)
            if self.in_bounds(n) and self.passable(n):
                yield n

    def cost(self, s, t):
        return 1 if t in set(self.neighbors(s)) else INF


def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def astar(grid, start, goal, expansions=None):
    # A* from scratch : tas + heuristique Manhattan. expansions[0] compte les noeuds depiles.
    if expansions is None:
        expansions = [0]
    g = {start: 0}
    came = {}
    tie = itertools.count()
    pq = [(manhattan(start, goal), next(tie), start)]
    while pq:
        _, _, cur = heapq.heappop(pq)
        if cur == goal:
            path = [cur]
            while cur in came:
                cur = came[cur]
                path.append(cur)
            return g[goal], path[::-1]
        expansions[0] += 1
        for n in grid.neighbors(cur):
            ng = g[cur] + 1
            if ng < g.get(n, INF):
                g[n] = ng
                came[n] = cur
                heapq.heappush(pq, (ng + manhattan(n, goal), next(tie), n))
    return INF, []


W, H = 24, 16
BASE_WALLS = {(x, 7) for x in range(3, 19)} | {(10, 3), (11, 4), (12, 5), (6, 12), (7, 12), (8, 12)}
START, GOAL = (1, 1), (22, 14)

g_init = Grid(W, H, BASE_WALLS)
exp_init = [0]
c_init, plan_init = astar(g_init, START, GOAL, exp_init)
print(f"Plan initial : cout {c_init}, {len(plan_init)} cellules, {exp_init[0]} expansions A*")
print(f"Un chemin monotone existe (cout = distance Manhattan {manhattan(START, GOAL)}) : "
      f"{'oui' if c_init == manhattan(START, GOAL) else 'non'}")

Plan initial : cout 34, 35 cellules, 285 expansions A*
Un chemin monotone existe (cout = distance Manhattan 34) : oui

Lecture du résultat

Le plan initial est monotone : son coût (34) égale exactement la distance Manhattan — le mur du couloir ne force aucun détour, il y a un passage aligné. Le compteur d’expansions (le nombre de nœuds dépilés par A*) va devenir notre monnaie : c’est lui qui mesure ce qu’un calcul a dû apprendre.

# Le monde change : une cellule du plan optimal se bloque (nouvel obstacle).
blocked = plan_init[10]  # sur le plan optimal, assez tot pour forcer un vrai contournement
assert blocked not in BASE_WALLS and blocked != START and blocked != GOAL

g_apres = Grid(W, H, BASE_WALLS | {blocked})
exp_scratch = [0]
c_scratch, plan_scratch = astar(g_apres, START, GOAL, exp_scratch)
print(f"Cellule bloquee : {blocked} (etait sur le plan optimal)")
print(f"A* from scratch : cout {c_scratch}, {exp_scratch[0]} expansions")

Cellule bloquee : (11, 1) (etait sur le plan optimal)
A* from scratch : cout 34, 273 expansions

Lecture du résultat

Le nouveau plan optimal coûte toujours 34 — la grille offrait un second chemin monotone. Mais pour le découvrir, A* a tout réappris : 273 expansions, comme si aucun calcul n’avait jamais eu lieu. C’est le coût de l’amnésie : le changement a invalidé une cellule, et la refacturation porte sur toute la grille.

# Contre-temoin : le repair nave (suivre le plan, contourner, rejoindre).
def naive_repair(grid, plan, blocked_cell):
    # suit le plan jusqu'a la cellule bloquee, contourne par le plus court chemin LOCAL
    # vers le premier waypoint du plan situe au-dela de l'obstacle, puis rejoint le plan tel quel.
    # retourne (cout total, plan, expansions du detour local).
    i = plan.index(blocked_cell)
    before, after = plan[:i], plan[i:]
    for j in range(1, len(after)):
        if grid.passable(after[j]):
            rejoin, rejoin_idx = after[j], j
            break
    else:
        return None, None, 0
    exp_detour = [0]
    detour_cost, detour = astar(grid, before[-1], rejoin, exp_detour)
    if detour_cost == INF:
        return None, None, exp_detour[0]
    total = (len(before) - 1) + detour_cost + (len(after) - 1 - rejoin_idx)
    return total, before[:-1] + detour + after[rejoin_idx + 1:], exp_detour[0]


c_naif, plan_naif, exp_naif = naive_repair(g_apres, plan_init, blocked)
print(f"Repair nave : cout {c_naif} (detour local : {exp_naif} expansions)  |  optimal reel : {c_scratch}")
print(f"Dette du repair nave : +{c_naif - c_scratch} (chemin valide, optimalite perdue)")
print(f"Le plan naive rejoint le plan initial et le suit tel quel apres le detour : "
      f"rien ne l'incite a reviser une decision devenue sous-optimale")

Repair nave : cout 36 (detour local : 8 expansions)  |  optimal reel : 34
Dette du repair nave : +2 (chemin valide, optimalite perdue)
Le plan naive rejoint le plan initial et le suit tel quel apres le detour : rien ne l'incite a reviser une decision devenue sous-optimale

Lecture du résultat

Le repair naïf produit un chemin valide — on arrive bien au but — mais sans garantie : +2 de dette par rapport à l’optimum. C’est le témoin exigé par l’opération 6 : la déviation est mesurable quand la loi est violée. La loi dit « conditions de bord préservant la garantie » ; le naïf n’a pas de conditions de bord du tout : il répare le point de friction et déclare le reste du plan intouchable, alors que l’apparition de l’obstacle a pu déplacer l’optimum ailleurs.

LPA* : garder la mémoire, réparer l’incohérence

LPA* (Lifelong Planning A*, Koenig & Likhachev 2002) reprend exactement les quantités d’A* et en ajoute une :

• \(g(s)\) : le coût actuel du meilleur chemin trouvé vers \(s\) — l’estimation héritée du calcul précédent ;
• \(rhs(s)\) (« right-hand side ») : ce que ce coût devrait être, recalculé localement : \(rhs(s) = \min_{s' \to s}\big(g(s') + c(s', s)\big)\), et \(rhs(start) = 0\) ;
• un sommet est localement consistant si \(g(s) = rhs(s)\). L’incohérence \(g \neq rhs\) signifie : ce que je crois et ce que je devrais croire diffèrent — pile là où le changement a touché.

La repair tourne autour d’une file de priorité U d’incohérences, triée par la clé \(k(s) = \big(\min(g, rhs) + h(s),\ \min(g, rhs)\big)\). Dépiler une incohérence \(g > rhs\) relève \(g\) (on a trouvé mieux) ; \(g < rhs\) abaisse \(g\) à l’infini (ce qu’on croyait n’existe plus) et replace les voisins dans la file. L’algorithme s’arrête dès que la clé minimale dépasse celle du but et que le but est consistant : tout ce qui n’a pas été touché n’a jamais été re-dépilé. La garantie d’optimalité d’A* est transportée au repair ; seule la propagation paie.

# Implementation LPA* : g, rhs, file d'incoherences U, cles k = (k1, k2).
class LPAStar:
    def __init__(self, grid, start, goal):
        self.grid, self.start, self.goal = grid, start, goal
        self.g, self.rhs = {}, {}
        self.U = {}
        self.expansions = 0
        self.rhs[start] = 0
        self._insert(start, self._calc_key(start))

    def _calc_key(self, s):
        m = min(self.g.get(s, INF), self.rhs.get(s, INF))
        return (m + manhattan(s, self.goal), m)

    def _insert(self, s, k):
        self.U[s] = k

    def _top(self):
        # sommet d'incoherence de plus petite cle (k1, k2) lexicographique
        return min(self.U.items(), key=lambda kv: kv[1]) if self.U else (None, (INF, INF))

    def _update_vertex(self, u):
        # rapproche rhs(u) de la realite locale, puis (re)insere u dans U s'il reste incoherent
        if u != self.start:
            self.rhs[u] = min(
                (self.g.get(s, INF) + self.grid.cost(s, u) for s in self.grid.neighbors(u)),
                default=INF,
            )
        if u in self.U:
            del self.U[u]
        if self.g.get(u, INF) != self.rhs.get(u, INF):
            self._insert(u, self._calc_key(u))

    def compute_shortest_path(self):
        while True:
            s_top, k_top = self._top()
            g_goal, rhs_goal = self.g.get(self.goal, INF), self.rhs.get(self.goal, INF)
            if not (k_top < self._calc_key(self.goal) or g_goal != rhs_goal):
                break
            self.expansions += 1
            del self.U[s_top]
            if self.g.get(s_top, INF) > self.rhs.get(s_top, INF):
                self.g[s_top] = self.rhs[s_top]          # raise : on a trouve mieux
                for s in self.grid.neighbors(s_top):
                    self._update_vertex(s)
            else:
                self.g[s_top] = INF                       # lower : ce qu'on croyait n'existe plus
                for s in list(self.grid.neighbors(s_top)) + [s_top]:
                    self._update_vertex(s)
        return self.g.get(self.goal, INF)

    def change_walls(self, added=(), removed=()):
        # applique le changement puis declare incoherents les sommets dont le voisinage a bouge
        for c in added:
            self.grid.walls.add(c)
        for c in removed:
            self.grid.walls.discard(c)
        for c in set(added) | set(removed):
            for s in self.grid.neighbors(c):
                self._update_vertex(s)
            self._update_vertex(c)

    def path(self):
        if self.g.get(self.goal, INF) == INF:
            return []
        path = [self.goal]
        cur = self.goal
        while cur != self.start:
            cur = min(self.grid.neighbors(cur),
                      key=lambda s: self.g.get(s, INF) + self.grid.cost(s, cur))
            path.append(cur)
        return path[::-1]


# sanite : premier calcul complet, doit reproduire A* exactement.
# le plan optimal n'est PAS unique (plusieurs chemins de meme cout) : on compare
# le cout et la longueur, jamais l'identite des cellules.
lp_check = LPAStar(Grid(W, H, BASE_WALLS), START, GOAL)
assert lp_check.compute_shortest_path() == c_init, "premier passage LPA* = A*"
assert len(lp_check.path()) == len(plan_init), "meme longueur de plan optimal"
print(f"Sanite : premier passage LPA* = A* (cout {c_init}, meme longueur de plan, "
      f"{lp_check.expansions} expansions)")

Sanite : premier passage LPA* = A* (cout 34, meme longueur de plan, 286 expansions)

Lecture du résultat

Le premier passage de LPA* est volontairement équivalent à A* (même coût, même plan) : c’est le contrôle de cohérence — le repair ne peut pas mieux faire qu’un calcul complet quand il part de zéro. Toute la valeur de LPA* est dans les passages suivants.

# Le repair : le MEME changement de monde, traite par LPA* sans rien oublier.
lp = LPAStar(Grid(W, H, BASE_WALLS), START, GOAL)
lp.compute_shortest_path()
e_avant = lp.expansions

lp.change_walls(added={blocked})              # declaration de l'incoherence, pas de re-calcul
c_lpa = lp.compute_shortest_path()            # propagation minimale
e_repair = lp.expansions - e_avant

print(f"LPA* repair : cout {c_lpa} ({'=' + str(c_scratch) + ' = optimal' if c_lpa == c_scratch else 'ECART'})")
print(f"Expansions du repair : {e_repair}  |  A* from scratch : {exp_scratch[0]}")
print(f"Reutilisation : le repair coute {exp_scratch[0] / e_repair:.0f}x moins cher que tout reapprendre")

LPA* repair : cout 34 (=34 = optimal)
Expansions du repair : 12  |  A* from scratch : 273
Reutilisation : le repair coute 23x moins cher que tout reapprendre

Lecture du résultat

Les deux faces de l’opération 6, mesurées :

• la garantie est transportée : coût LPA* = coût A* from scratch, à l’égalité près — le repair ne dégrade jamais l’optimalité ;
• la réparation est locale : 12 expansions contre 273, un rapport de 23×. Tout ce que le changement n’a pas invalidé — la majorité de la grille — n’a jamais été re-dépilé.

Le repair n’est pas « un A* bon marché » : c’est un autre contrat. A* répond à « quel est le plan optimal dans ce monde ? » ; LPA* répond à « mon plan reste-t-il optimal, et si non, qu’est-ce que le changement a détruit ? ».

La garantie, écrite noir sur blanc

Pourquoi l’optimalité survit-elle au repair ? Parce que la sortie de compute_shortest_path n’est pas « un chemin », c’est un état cohérent : à l’arrêt, \(g(goal) = rhs(goal)\) et la clé minimale de U dépasse celle du but — ce qui signifie (théorème 3 de l’article) que \(g\) coïncide avec les coûts de plus court chemin partout où cela importe pour extraire le plan. Les sommets non touchés n’ont pas changé de \(g\) parce que rien ne pouvait les changer ; les sommets touchés ont été propagés jusqu’à cohérence. Il n’existe pas d’état intermédiaire « à peu près cohérent » qui s’arrête tôt : la clause d’arrêt est la condition de bord de la loi.

La correspondance terme à terme avec le safe subgame solving (GT-13b/13c) :

Safe subgame solving (jeux)	LPA* (chemins)
réparer la stratégie dans le sous-jeu atteint	réparer \(g\) le long des incohérences
la garantie de non-exploitabilité reste tenue hors du sous-jeu	l’optimalité reste tenue hors de la zone touchée
contre-témoin : raffinement naïf → exploitabilité mesurable	contre-témoin : repair naïf → dette +2 mesurée
imbricable : les repairs s’enchaînent	imbricable : chaque changement repart de l’état cohérent précédent

C’est la seconde attestation indépendante de l’opération 6 : deux substrats (stratégies de jeu, chemins), deux moteurs, même patron — réparer localement, garantir globalement.

# Imbricabilite : une SEQUENCE de 8 changements (murs ajoutes puis retires), seed fixe.
import random

random.seed(7)
g_seq = Grid(W, H, BASE_WALLS)
lp_seq = LPAStar(g_seq, START, GOAL)
lp_seq.compute_shortest_path()

concordances, exp_lpa_total, exp_scratch_total = 0, 0, 0
for t in range(8):
    free = [c for c in ((x, y) for x in range(W) for y in range(H))
            if g_seq.passable(c) and c not in (START, GOAL) and c not in BASE_WALLS]
    added, removed = [], []
    if t % 3 == 2 and (g_seq.walls - BASE_WALLS):
        removed = [random.choice(sorted(g_seq.walls - BASE_WALLS))]   # un mur part
    else:
        cands = [c for c in free if c not in lp_seq.path()]           # ne bloque pas le plan courant
        added = [random.choice(cands)] if cands else []
    lp_seq.change_walls(added=added, removed=removed)
    e0 = lp_seq.expansions
    c_l = lp_seq.compute_shortest_path()
    e_repair_seq = lp_seq.expansions - e0
    exp_lpa_total += e_repair_seq
    e_ref = [0]
    c_ref, _ = astar(Grid(W, H, set(g_seq.walls)), START, GOAL, e_ref)
    exp_scratch_total += e_ref[0]
    ok = (c_l == c_ref)
    concordances += ok
    print(f"t={t} murs {'+' + str(added) if added else '-' + str(removed)} : "
          f"LPA* {c_l} vs scratch {c_ref} {'OK' if ok else 'MISMATCH'} "
          f"(repair {e_repair_seq} expansions)")

print(f"\nConcordances : {concordances}/8 | expansions cumulees : LPA* {exp_lpa_total} vs scratch {exp_scratch_total}")

t=0 murs +[(12, 13)] : LPA* 34 vs scratch 34 OK (repair 1 expansions)
t=1 murs +[(6, 2)] : LPA* 34 vs scratch 34 OK (repair 1 expansions)
t=2 murs -[(12, 13)] : LPA* 34 vs scratch 34 OK (repair 1 expansions)
t=3 murs +[(2, 6)] : LPA* 34 vs scratch 34 OK (repair 1 expansions)
t=4 murs +[(3, 5)] : LPA* 34 vs scratch 34 OK (repair 2 expansions)
t=5 murs -[(6, 2)] : LPA* 34 vs scratch 34 OK (repair 1 expansions)
t=6 murs +[(4, 3)] : LPA* 34 vs scratch 34 OK (repair 1 expansions)
t=7 murs +[(14, 10)] : LPA* 34 vs scratch 34 OK (repair 1 expansions)

Concordances : 8/8 | expansions cumulees : LPA* 9 vs scratch 2258

Lecture du résultat

Huit changements, huit concordances exactes avec la référence recalculée de zéro — l’optimalité est transportée à chaque étape, et chaque repair repart de l’état cohérent précédent (imbricabilité). Le budget cumulé de LPA* reste une fraction de celui de la référence : c’est le sens de lifelong dans le nom — sur la durée de vie d’un problème qui change, l’amortissement du calcul initial se cumule.

# Recapitulatif des trois strategies sur le changement unique.
rows = [
    ("A* from scratch", c_scratch, "optimale", exp_scratch[0]),
    ("Repair nave", c_naif, f"aucune (dette +{c_naif - c_scratch})", exp_naif),
    ("LPA* repair", c_lpa, "optimale (transportee)", e_repair),
]
print(f"{'Strategie':<18} {'Cout':>5}  {'Garantie':<26} {'Expansions':>10}")
for nom, cout, gar, exp in rows:
    print(f"{nom:<18} {cout:>5}  {gar:<26} {exp:>10}")
print()
print("Le repair nave paie peu (detour local) mais ne garantit rien ;")
print("LPA* garantit l'optimalite au prix exactement de ce que le changement a invalide.")

Strategie           Cout  Garantie                   Expansions
A* from scratch       34  optimale                          273
Repair nave           36  aucune (dette +2)                   8
LPA* repair           34  optimale (transportee)             12

Le repair nave paie peu (detour local) mais ne garantit rien ;
LPA* garantit l'optimalite au prix exactement de ce que le changement a invalide.

Lecture du résultat, et la dette restante

Le tableau est le résumé de la loi : aucune stratégie n’a les trois colonnes à la fois gratuites. Le naïf économise le calcul et perd la garantie ; le scratch a la garantie et paie tout ; LPA* a la garantie et ne paie que le delta. La dette reste ouverte sur deux points, à traiter ailleurs :

• LPA* suppose le monde connu : quand l’obstacle n’est observé qu’à proximité, il faut D* Lite (LPA* + déplacement de l’agent, but et départ échangés) — piste naturelle pour un approfondissement ultérieur ;
• les coûts unitaires cachent le cas pondéré (terrain à \(c(s, s')\) variable) — le mécanisme de rhs le supporte tel quel, mais les témoins seraient à re-mesurer.

# Test negatif de l'op 6 : couper la propagation = croire une valeur fausse.
# Monde a goulet : mur vertical x=12, ouverture unique en (12, 8), bords haut/bas ouverts.
W2, H2 = 24, 16
PONT = (12, 8)
mur_goulet = {(12, y) for y in range(1, H2 - 1)} - {PONT}

g_pont = Grid(W2, H2, mur_goulet)
c_avant, plan_pont = astar(g_pont, START, GOAL)
assert PONT in set(plan_pont), "le plan initial passe bien par le pont"
print(f"Goulet : plan initial cout {c_avant}, unique passage en {PONT}")

# (a) AUCUNE propagation : on meure le pont, l'etat interne ne bouge pas
lp_croire = LPAStar(Grid(W2, H2, mur_goulet), START, GOAL)
lp_croire.compute_shortest_path()
lp_croire.grid.walls.add(PONT)                        # le monde change, l'etat interne non
c_cru = lp_croire.g[GOAL]
print(f"(a) sans propagation : g(goal) affirme toujours {c_cru}")

# (b) reference honnete : A* from scratch apres blocage du pont
exp_goulet = [0]
c_vrai, _ = astar(Grid(W2, H2, mur_goulet | {PONT}), START, GOAL, exp_goulet)
print(f"(b) optimum reel apres blocage : {c_vrai} ({exp_goulet[0]} expansions scratch)")

# (c) propagation COMPLETE par LPA* : la meme instance, traitee honnetement
lp_vrai = LPAStar(Grid(W2, H2, mur_goulet), START, GOAL)
lp_vrai.compute_shortest_path()
e_avant_g = lp_vrai.expansions
lp_vrai.change_walls(added={PONT})
c_lpa_g = lp_vrai.compute_shortest_path()
e_repair_g = lp_vrai.expansions - e_avant_g
print(f"(c) LPA* repair : {c_lpa_g} en {e_repair_g} expansions "
      f"(vs {exp_goulet[0]} au scratch -- un changement structurel n'economise presque rien)")
print(f"Ecart de croyance : {c_cru} affirme vs {c_vrai} reel -> la garantie n'etait pas "
      f"deposee dans le calcul initial, elle est retablie par la propagation")

Goulet : plan initial cout 34, unique passage en (12, 8)
(a) sans propagation : g(goal) affirme toujours 34
(b) optimum reel apres blocage : 36 (276 expansions scratch)
(c) LPA* repair : 36 en 269 expansions (vs 276 au scratch -- un changement structurel n'economise presque rien)
Ecart de croyance : 34 affirme vs 36 reel -> la garantie n'etait pas deposee dans le calcul initial, elle est retablie par la propagation

Lecture du résultat

Deux enseignements, le second n’étant pas le plus confortable :

• La croyance fausse est mesurée : sans propagation, \(g(goal)\) affirme 34 alors que l’optimum réel est 36. Un état interne non propagé n’est pas « un peu optimiste » : il ment. On n’en extrait même pas de plan — un état incohérent n’a pas de chemin bien défini. La garantie d’optimalité n’est donc pas une propriété que le premier calcul aurait « déposée » quelque part : elle est ré-établie à chaque changement par la propagation des incohérences — les conditions de bord (jusqu’où propager) ne sont pas un détail d’implémentation, elles SONT la garantie.
• La localité paie quand le changement est local : ici le repair LPA* coûte presque autant que le scratch (269 contre 276), car bloquer l’unique passage invalide tout ce qui est au-delà du pont. LPA* ne dégénère jamais en pire que scratch, mais son avantage (23× sur le changement local du début) disparaît quand le changement est structurel. C’est la dette honnête de l’opération : la garantie est transportée, l’économie ne l’est que si le monde change localement.

Recoller : compatibilité puis composition

C’est l’opération 5 de la table des opérations (EPIC #12204) : « Recoller — compatibilité puis composition ». Cette section en apporte une seconde attestation, sur un substrat indépendant de la première (de Finetti dans decision_theory_lean, Lean-formel : un Dutch book exploite des prix incohérents). Ici le substrat est le recollement de solutions locales de recherche — le geste de tout pathfinding hiérarchique (HPA*, Botea, Müller & Schaeffer 2004) : des zones calculent des tables locales, des tables d’intégration les recollent.

C’est le prolongement direct de la section précédente, par l’autre bout : LPA* répare un plan quand le monde change ; cette section recelle des tables locales en un objet global. Les deux posent la même question — qu’est-ce qu’un calcul local garantit au niveau global ?

Critère de la Tombée 3 (ledger) : le témoin exigé est exploitable, pas le résidu — « si nous prétendons détecter un défaut de recollement, pouvons-nous produire un cycle concret qui exploite ce défaut ? » Cette section produit ce cycle : une marche de méidentification exécutée pas à pas sur la grille, qui traverse son but puis le dépasse en croyant arriver. La dette d’ICT-15d est respectée : aucun mot de cadre abstrait n’est invoqué avant que les transports soient possédés — ici ce sont des permutations explicites, composées et mesurées.

Posture : pas d’auto-promotion. La décision de promotion de l’op 5 vers la table appartient à la relecture de l’EPIC (même posture que la section 12 de Search-03b pour l’op 3 et que GT-19 pour l’op 2).

La loi et le décor

La loi de l’opération : une famille de correspondances locales se recolle en un objet global cohérent si et seulement si (i) chaque chevauchement porte une correspondance compatible (ici : une bijection complète des états partagés) et (ii) la composition autour de chaque chevauchement triple est l’identité. La condition (i) est celle que tout intégrateur écrit ; la condition (ii) est celle que personne n’écrit — c’est précisément là que le défaut vit.

Le décor, réaliste : une carte est couverte par trois fenêtres rectangulaires chevauchantes (les clusters d’un planificateur hiérarchique). Chaque fenêtre résout indépendamment son sous-problème (BFS) et numérote ses états de bord (les portails) dans son ordre de découverte — trois intégrateurs, trois conventions. Entre chaque paire de fenêtres, une table d’intégration écrite à la main associe les numérotations locales. Le contrat vérifié à l’intégration est le contrat faible : chaque table est une bijection, la couverture est complète.

# Carte, fenetres (zones), murs et portails
ROWS, COLS = 9, 11
WALLS = {(1, 2), (2, 5), (3, 5), (6, 4)}

ZONES = {  # rectangle (r0, c0)-(r1, c1) inclus
    "A": ((0, 0), (4, 6)),
    "B": ((0, 4), (4, 10)),
    "C": ((3, 1), (8, 7)),
}
REFS = {"A": (0, 0), "B": (0, 10), "C": (8, 1)}  # reference locale de chaque fenetre

# Portails : etats de bord partages par les TROIS fenetres (le triple chevauchement)
PORTALS = [(3, 4), (3, 6), (4, 4), (4, 6)]

def inside(z, r, c):
    (r0, c0), (r1, c1) = ZONES[z]
    return r0 <= r <= r1 and c0 <= c <= c1

def zone_set(r, c):
    return "".join(z for z in "ABC" if inside(z, r, c))

zone_cells = {
    z: {(r, c) for r in range(ROWS) for c in range(COLS)
        if inside(z, r, c) and (r, c) not in WALLS}
    for z in ZONES
}

# Rendu : chaque position affiche la liste des fenetres qui la couvrent
print("Couverture (mur = #) :")
for r in range(ROWS):
    row = []
    for c in range(COLS):
        if (r, c) in WALLS:
            row.append("  # ")
        else:
            row.append(f"{zone_set(r, c): >3} ")
    print("".join(row))

print()
print("Portails du triple chevauchement :")
for p in PORTALS:
    print(f"  {p} -> couvert par {zone_set(*p)}")
assert all(zone_set(*p) == "ABC" for p in PORTALS)

# Le triple chevauchement complet, pour voir ou vit la composition
triple = [(r, c) for r in range(ROWS) for c in range(COLS) if zone_set(r, c) == "ABC"]
print("Triple chevauchement (A et B et C) :", sorted(triple))

Couverture (mur = #) :
  A   A   A   A  AB  AB  AB   B   B   B   B 
  A   A   #   A  AB  AB  AB   B   B   B   B 
  A   A   A   A  AB   #  AB   B   B   B   B 
  A  AC  AC  AC ABC   # ABC  BC   B   B   B 
  A  AC  AC  AC ABC ABC ABC  BC   B   B   B 
      C   C   C   C   C   C   C             
      C   C   C   #   C   C   C             
      C   C   C   C   C   C   C             
      C   C   C   C   C   C   C             

Portails du triple chevauchement :
  (3, 4) -> couvert par ABC
  (3, 6) -> couvert par ABC
  (4, 4) -> couvert par ABC
  (4, 6) -> couvert par ABC
Triple chevauchement (A et B et C) : [(3, 4), (3, 5), (3, 6), (4, 4), (4, 5), (4, 6)]

Lecture du décor

Les trois fenêtres se chevauchent par paires (bandes AB, AC, BC) et leur intersection commune forme le bloc ABC — c’est le triple chevauchement, le seul endroit où une correspondance peut être confrontée à elle-même en boucle. Les quatre portails vivent tous dans ce bloc : chaque paire de fenêtres les voit, aucun intégrateur ne les voit de la même façon.

# Sous-problemes locaux : BFS par fenetre depuis sa reference, numerotation par decouverte
from collections import deque

def bfs(cells, src):
    dist = {src: 0}
    parent = {src: None}
    q = deque([src])
    while q:
        r, c = q.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            n = (r + dr, c + dc)
            if n in cells and n not in dist:
                dist[n] = dist[(r, c)] + 1
                parent[n] = (r, c)
                q.append(n)
    return dist, parent

numbering = {}      # fenetre -> {portail: indice local}
by_num = {}         # fenetre -> [portails par indice local]
dists = {}          # fenetre -> {portail: {portail: distance locale}}
parents = {}
for z in "ABC":
    d, par = bfs(zone_cells[z], REFS[z])
    parents[z] = par
    assert all(p in d for p in PORTALS), f"portail non atteignable dans la fenetre {z}"
    order = sorted(PORTALS, key=lambda p: d[p])          # ordre de decouverte BFS
    numbering[z] = {p: i for i, p in enumerate(order)}
    by_num[z] = order
    table = {}
    for p in PORTALS:
        dp, _ = bfs(zone_cells[z], p)
        table[p] = {q: dp[q] for q in PORTALS}
    dists[z] = table
    print(f"Fenetre {z} (reference {REFS[z]}) numerotation par decouverte :")
    for i, p in enumerate(order):
        print(f"   {z}#{i} = {p}")

# Les trois conventions sont deux a deux distinctes : personne n'a coordonne
assert numbering["A"] != numbering["B"]
assert numbering["B"] != numbering["C"]
assert numbering["A"] != numbering["C"]
print("Numerotations deux a deux distinctes : assert OK")

# Epingle : les ordres de decouverte attendus (garde la construction verifiable)
assert by_num["A"] == [(3, 4), (4, 4), (3, 6), (4, 6)]
assert by_num["B"] == [(3, 6), (4, 6), (3, 4), (4, 4)]
assert by_num["C"] == [(4, 4), (3, 4), (4, 6), (3, 6)]
print("Ordres de decouverte epingles : assert OK")

print()
print("Table locale de la fenetre A (distances entre portails via l'interieur de A) :")
for p in PORTALS:
    print("  ", p, {q: dists["A"][p][q] for q in PORTALS})

Fenetre A (reference (0, 0)) numerotation par decouverte :
   A#0 = (3, 4)
   A#1 = (4, 4)
   A#2 = (3, 6)
   A#3 = (4, 6)
Fenetre B (reference (0, 10)) numerotation par decouverte :
   B#0 = (3, 6)
   B#1 = (4, 6)
   B#2 = (3, 4)
   B#3 = (4, 4)
Fenetre C (reference (8, 1)) numerotation par decouverte :
   C#0 = (4, 4)
   C#1 = (3, 4)
   C#2 = (4, 6)
   C#3 = (3, 6)
Numerotations deux a deux distinctes : assert OK
Ordres de decouverte epingles : assert OK

Table locale de la fenetre A (distances entre portails via l'interieur de A) :
   (3, 4) {(3, 4): 0, (3, 6): 4, (4, 4): 1, (4, 6): 3}
   (3, 6) {(3, 4): 4, (3, 6): 0, (4, 4): 3, (4, 6): 1}
   (4, 4) {(3, 4): 1, (3, 6): 3, (4, 4): 0, (4, 6): 2}
   (4, 6) {(3, 4): 3, (3, 6): 1, (4, 4): 2, (4, 6): 0}

Lecture des sous-problèmes

Chaque fenêtre a produit un objet local complet : une numérotation des portails (ordre de découverte depuis sa référence — coin haut-gauche pour A, coin haut-droit pour B, coin bas-gauche pour C) et une table de distances locales. Les trois numérotations diffèrent deux à deux : c’est le vécu de trois intégrations indépendantes, et la raison d’être des tables de correspondance.

# Tables d'integration ecrites par paire (format reel : paires d'indices locaux)
# La table A->B porte l'erreur d'integration : les deux sorties (3,4) et (3,6)
# y sont CROISEES -- deux lignes voisines de la table, permutees a la main.
pi_AB_idx = {0: 0, 1: 3, 2: 2, 3: 1}   # A#i <-> B#j  (croisee sur la paire 0/2)
pi_BC_idx = {0: 3, 1: 2, 2: 1, 3: 0}   # correcte
pi_CA_idx = {0: 1, 1: 0, 2: 3, 3: 2}   # correcte

def show_binding(name, z1, z2, binding):
    print(f"Table {name} ({z1} -> {z2}) :")
    for i, j in sorted(binding.items()):
        print(f"   {z1}#{i} {by_num[z1][i]}  <->  {z2}#{j} {by_num[z2][j]}")

show_binding("pi_AB", "A", "B", pi_AB_idx)
show_binding("pi_BC", "B", "C", pi_BC_idx)
show_binding("pi_CA", "C", "A", pi_CA_idx)

# --- Le contrat faible, celui que l'integration verifie reellement ---
def check_pairwise(name, binding):
    cible = sorted(binding.values())
    assert cible == list(range(4)), f"{name} n'est pas une bijection"
    assert len(binding) == 4, f"{name} ne couvre pas tout le chevauchement"
    print(f"{name} : bijection OK, couverture complete OK")

for name, b in (("pi_AB", pi_AB_idx), ("pi_BC", pi_BC_idx), ("pi_CA", pi_CA_idx)):
    check_pairwise(name, b)
print()
print("Compatibilite sur les chevauchements : VERIFIEE par le contrat faible (asserts OK)")

Table pi_AB (A -> B) :
   A#0 (3, 4)  <->  B#0 (3, 6)
   A#1 (4, 4)  <->  B#3 (4, 4)
   A#2 (3, 6)  <->  B#2 (3, 4)
   A#3 (4, 6)  <->  B#1 (4, 6)
Table pi_BC (B -> C) :
   B#0 (3, 6)  <->  C#3 (3, 6)
   B#1 (4, 6)  <->  C#2 (4, 6)
   B#2 (3, 4)  <->  C#1 (3, 4)
   B#3 (4, 4)  <->  C#0 (4, 4)
Table pi_CA (C -> A) :
   C#0 (4, 4)  <->  A#1 (4, 4)
   C#1 (3, 4)  <->  A#0 (3, 4)
   C#2 (4, 6)  <->  A#3 (4, 6)
   C#3 (3, 6)  <->  A#2 (3, 6)
pi_AB : bijection OK, couverture complete OK
pi_BC : bijection OK, couverture complete OK
pi_CA : bijection OK, couverture complete OK

Compatibilite sur les chevauchements : VERIFIEE par le contrat faible (asserts OK)

Pourquoi la compatibilité par paires ne suffit pas

Le contrat faible ne consulte aucune donnée croisée : il vérifie que chaque table, prise seule, associe chaque état partagé de gauche à exactement un état partagé de droite. La table pi_AB croisée satisfait ce contrat parfaitement — une permutation en est une. Aucune vérification par paire ne compose les tables entre elles ; la contrainte qui tue n’est visible que lorsqu’on compose autour du triple.

# Composition sur le triple : sigma = pi_AB o pi_BC o pi_CA (cellule -> cellule)
def convert(p, z_from, binding, z_to):
    i = numbering[z_from][p]
    return by_num[z_to][binding[i]]

sigma = {}
for p in PORTALS:
    p_b = convert(p, "A", pi_AB_idx, "B")   # A -> B
    p_c = convert(p_b, "B", pi_BC_idx, "C") # B -> C
    p_a = convert(p_c, "C", pi_CA_idx, "A") # C -> A (retour dans la numerotation A)
    sigma[p] = p_a

moved = [p for p in PORTALS if sigma[p] != p]
fixes = [p for p in PORTALS if sigma[p] == p]
print("sigma (aller-retour A -> B -> C -> A) :")
for p in PORTALS:
    tag = "FIXE" if sigma[p] == p else "DEPLACE"
    print(f"   {p} -> {sigma[p]}   [{tag}]")
print(f"Points fixes : {fixes}")
print(f"Points deplaces : {moved}")

def cycle_notation(s):
    seen, cycles = set(), []
    for p in sorted(s):
        if p in seen:
            continue
        cyc, cur = [], p
        while cur not in seen:
            seen.add(cur); cyc.append(cur); cur = s[cur]
        if len(cyc) > 1:
            cycles.append("(" + " ".join(map(str, cyc)) + ")")
    return " ".join(cycles) if cycles else "identite"

print("Notation cyclique de sigma :", cycle_notation(sigma))
assert moved, "sigma devrait deplacer au moins un portail"
assert sigma[(3, 4)] == (3, 6) and sigma[(3, 6)] == (3, 4)
print("Composition sur le triple : VIOLATION mesuree (sigma != identite)")

sigma (aller-retour A -> B -> C -> A) :
   (3, 4) -> (3, 6)   [DEPLACE]
   (3, 6) -> (3, 4)   [DEPLACE]
   (4, 4) -> (4, 4)   [FIXE]
   (4, 6) -> (4, 6)   [FIXE]
Points fixes : [(4, 4), (4, 6)]
Points deplaces : [(3, 4), (3, 6)]
Notation cyclique de sigma : ((3, 4) (3, 6))
Composition sur le triple : VIOLATION mesuree (sigma != identite)

La loi violée

En composant les trois tables autour du triple chevauchement, un portail revient sur la position d’un autre : (3,4) et (3,6) sont échangés par l’aller-retour. Chaque table prise seule était irréprochable au contrat faible ; le produit, lui, n’est pas l’identité — la loi de l’opération 5 exige l’identité. La question de la Tombée 3 devient concrète : ce défaut est-il exploitable ?

# Non-recollabilite : AUCUNE numerotation globale n'est coherente avec les trois tables
# (enumeration exhaustive de toutes les etiquetages injectifs des portails)
from itertools import permutations

def count_global_numberings(b_ab, b_bc, b_ca):
    ok_count = 0
    for perm in permutations(range(4)):
        lab = {p: perm[i] for i, p in enumerate(PORTALS)}
        ok = True
        for z1, z2, b in (("A", "B", b_ab), ("B", "C", b_bc), ("C", "A", b_ca)):
            for i, j in b.items():
                if lab[by_num[z1][i]] != lab[by_num[z2][j]]:
                    ok = False
        if ok:
            ok_count += 1
    return ok_count

n_ok = count_global_numberings(pi_AB_idx, pi_BC_idx, pi_CA_idx)
total = sum(1 for _ in permutations(range(4)))
print(f"Numerotations globales coherentes : {n_ok} / {total} etiquetages injectifs testes")
assert n_ok == 0
print("Argument en une ligne : toute etiquette coherente devrait satisfaire")
print("lab[(3,4)] = lab[sigma[(3,4)]] = lab[(3,6)] -- deux portails distincts, meme etiquette :")
print("l'injectivite est violee. Le recollement n'existe pas.")

Numerotations globales coherentes : 0 / 24 etiquetages injectifs testes
Argument en une ligne : toute etiquette coherente devrait satisfaire
lab[(3,4)] = lab[sigma[(3,4)]] = lab[(3,6)] -- deux portails distincts, meme etiquette :
l'injectivite est violee. Le recollement n'existe pas.

# Consequence mesuree : la table recollee repond DEUX valeurs a la meme requete physique
requete = ((3, 4), (4, 4))   # deux portails voisins (une ligne l'un sous l'autre)
reponse_directe = dists["A"][requete[0]][requete[1]]
# En passant par l'aller-retour tordu A -> B -> C -> A, la colle reidentifie le depart :
depart_reidentifie = sigma[requete[0]]
reponse_via_colle = dists["A"][depart_reidentifie][requete[1]]
print(f"Requete physique : distance {requete[0]} -> {requete[1]}")
print(f"  reponse directe (table A)                    : {reponse_directe}")
print(f"  reponse apres reidentification par la colle  : {reponse_via_colle}")
print(f"     (la colle croit que le depart est {depart_reidentifie})")
assert reponse_directe != reponse_via_colle
print("Deux reponses pour une requete : l'objet recolle n'est pas une fonction.")

Requete physique : distance (3, 4) -> (4, 4)
  reponse directe (table A)                    : 1
  reponse apres reidentification par la colle  : 3
     (la colle croit que le depart est (3, 6))
Deux reponses pour une requete : l'objet recolle n'est pas une fonction.

Lecture

La même paire physique de portails reçoit deux distances selon le chemin de consultation. Un objet recollé qui répond deux valeurs n’est pas une table dégradée : il n’existe pas. Toute couche au-dessus (un planificateur, un estimateur) consomme donc un objet incohérent — et le dommage devient observable par un adversaire.

# LE TEMOIN EXPLOITABLE (Loi I) : la marche de meidentification, executee pas a pas
# Situation : un agent est physiquement en (3,4) et demande a la colle un plan vers (4,4).
# La colle consulte son identification : depart (3,4) -> (apres aller-retour tordu) (3,6).
# Elle planifie donc dans la fenetre A depuis (3,6) et retourne les mouvements RELATIFS.
start_vrai = (3, 4)
but = (4, 4)
depart_cru = sigma[start_vrai]           # ce que la colle croit etre le point de depart

def path_from(src, goal, z):
    _, par = bfs(zone_cells[z], src)
    chemin = [goal]
    while chemin[-1] != src:
        chemin.append(par[chemin[-1]])
    chemin.reverse()
    return chemin

chemin_cru = path_from(depart_cru, but, "A")    # plan calcule depuis la position crue
moves = [(chemin_cru[i + 1][0] - chemin_cru[i][0], chemin_cru[i + 1][1] - chemin_cru[i][1])
         for i in range(len(chemin_cru) - 1)]
print(f"Position reelle de l'agent      : {start_vrai}")
print(f"Ce que la colle croit           : {depart_cru} (reidentification tordue)")
print(f"Plan retourne (depuis la croyance) : {chemin_cru}  ({len(moves)} mouvements)")

# L'agent execute les mouvements RELATIFS depuis sa position REELLE
pos = start_vrai
trace = [pos]
for dr, dc in moves:
    pos = (pos[0] + dr, pos[1] + dc)
    trace.append(pos)
print("Execution pas a pas depuis la position reelle :")
for i, t in enumerate(trace):
    print(f"   pas {i} : {t}")
print(f"Arrivee revendiquee : {but} (apres {len(moves)} pas)")
print(f"Position reelle finale : {pos}")

# Verites de terrain (BFS sur la carte entiere)
map_cells = {(r, c) for r in range(ROWS) for c in range(COLS) if (r, c) not in WALLS}
d_full, _ = bfs(map_cells, start_vrai)
optimum = d_full[but]
print(f"Optimum reel {start_vrai} -> {but} : {optimum} pas (le but etait le voisin direct)")
print(f"Cout du defaut : arrivee au mauvais endroit ({pos} != {but}), {len(moves)} pas payes")
print(f"contre {optimum} optimal -- et le but a ete TRAVERSE au pas 1 puis quitte.")

assert pos != but, "l'exploit doit mener au mauvais endroit"
assert len(moves) == 3 and optimum == 1
assert trace[1] == but, "le but est traverse au premier pas puis abandonne"
print("Cycle concret exploitant le defaut de recollement : EXECUTE et mesure.")

Position reelle de l'agent      : (3, 4)
Ce que la colle croit           : (3, 6) (reidentification tordue)
Plan retourne (depuis la croyance) : [(3, 6), (4, 6), (4, 5), (4, 4)]  (3 mouvements)
Execution pas a pas depuis la position reelle :
   pas 0 : (3, 4)
   pas 1 : (4, 4)
   pas 2 : (4, 3)
   pas 3 : (4, 2)
Arrivee revendiquee : (4, 4) (apres 3 pas)
Position reelle finale : (4, 2)
Optimum reel (3, 4) -> (4, 4) : 1 pas (le but etait le voisin direct)
Cout du defaut : arrivee au mauvais endroit ((4, 2) != (4, 4)), 3 pas payes
contre 1 optimal -- et le but a ete TRAVERSE au pas 1 puis quitte.
Cycle concret exploitant le defaut de recollement : EXECUTE et mesure.

Lecture — le témoin exigé par la Tombée 3

Voilà le cycle concret qui exploite le défaut : l’agent traverse son but au premier pas, continue deux pas de plus, et revendique une arrivée à côté. Aucun « résidu », aucune grandeur abstraite : des positions, des pas, un mauvais endroit. C’est la forme pathfinding du Dutch book de de Finetti — la première attestation de l’opération, sur un autre substrat : un objet local plausible, une incohérence invisible par paires, un cycle qui la monnaie. un adversaire qui connaît la table croisée peut router l’agent n’importe où dans le rayon de confusion.

# Reparation : decroiser la table pi_AB, puis tout re-teser
pi_AB_corrige = {0: 2, 1: 3, 2: 0, 3: 1}   # identification cellule a cellule, correcte
show_binding("pi_AB (corrigee)", "A", "B", pi_AB_corrige)
check_pairwise("pi_AB corrigee", pi_AB_corrige)

# sigma recompose
sigma2 = {}
for p in PORTALS:
    p_b = convert(p, "A", pi_AB_corrige, "B")
    p_c = convert(p_b, "B", pi_BC_idx, "C")
    sigma2[p] = convert(p_c, "C", pi_CA_idx, "A")
assert all(sigma2[p] == p for p in PORTALS)
print("sigma recompose : identite sur tous les portails -- assert OK")

# Le recollement EXISTE desormais : une numerotation globale coherente est exhibee
n_ok2 = count_global_numberings(pi_AB_corrige, pi_BC_idx, pi_CA_idx)
print(f"Numerotations globales coherentes apres reparation : {n_ok2} / 24")
assert n_ok2 == 24   # toute numerotation de depart est coherente : les tables ne contraignent plus

# La table recollee devient univaluee : toute chaine de consultation donne la meme reponse
from itertools import combinations
paires_testees = 0
for p, q in combinations(PORTALS, 2):
    direct = dists["A"][p][q]
    via_ab = dists["B"][convert(p, "A", pi_AB_corrige, "B")][convert(q, "A", pi_AB_corrige, "B")]
    via_ac = dists["C"][convert(convert(p, "A", pi_AB_corrige, "B"), "B", pi_BC_idx, "C")][
                 convert(convert(q, "A", pi_AB_corrige, "B"), "B", pi_BC_idx, "C")]
    assert direct == via_ab == via_ac, f"reponses divergentes pour {p} -> {q}"
    paires_testees += 1
print(f"Univalence : les trois chaines de consultation accordent leurs reponses sur les {paires_testees} paires -- assert OK")

# Exactitude de la table recollee face a la verite de terrain
print(f"{'paire':<22} {'colle (min des fenetres)':>24} {'carte entiere':>14}")
for p, q in combinations(PORTALS, 2):
    glued = min(dists[z][p][q] for z in "ABC")
    d_map = bfs(map_cells, p)[0][q]
    print(f"{str((p, q)):<22} {glued:>24} {d_map:>14}")
    assert glued >= d_map   # une fenetre ne cree jamais de raccourci impossible
print("La table recollee majore l'optimum global, avec egalite quand une fenetre porte l'optimum : assert OK")

Table pi_AB (corrigee) (A -> B) :
   A#0 (3, 4)  <->  B#2 (3, 4)
   A#1 (4, 4)  <->  B#3 (4, 4)
   A#2 (3, 6)  <->  B#0 (3, 6)
   A#3 (4, 6)  <->  B#1 (4, 6)
pi_AB corrigee : bijection OK, couverture complete OK
sigma recompose : identite sur tous les portails -- assert OK
Numerotations globales coherentes apres reparation : 24 / 24
Univalence : les trois chaines de consultation accordent leurs reponses sur les 6 paires -- assert OK
paire                  colle (min des fenetres)  carte entiere
((3, 4), (3, 6))                              4              4
((3, 4), (4, 4))                              1              1
((3, 4), (4, 6))                              3              3
((3, 6), (4, 4))                              3              3
((3, 6), (4, 6))                              1              1
((4, 4), (4, 6))                              2              2
La table recollee majore l'optimum global, avec egalite quand une fenetre porte l'optimum : assert OK

Récapitulatif des témoins mesurés

#	Ce qui est mesuré	Valeur
Compatibilité par paires	les trois tables passent le contrat faible (bijection, couverture)	✓ (asserts)
Composition sur le triple	σ = π_AB ∘ π_BC ∘ π_CA	((3,4) (3,6)) ≠ identité
Non-recollabilité	numérotations globales cohérentes (énumération exhaustive)	0 / 24
Colle multivaluée	même requête physique, deux réponses	1 contre 3
Témoin exploitable (Loi I)	marche exécutée depuis (3,4) vers (4,4)	traverse le but au pas un, finit en (4,2) après trois pas, optimum 1
Réparation	π_AB décroisée → σ = identité, numérotation globale exhibée, univalence des réponses	✓ (asserts)

Exercices (C.1 — à compléter)

Les exercices 1 à 3 portent sur LPA* (sections précédentes) ; les exercices 4 à 6 portent sur la section « recoller ».

Les six exercices reprennent l’instance du carnet (BASE_WALLS, START, GOAL, blocked). Chaque stub s’exécute sans erreur une fois complété ; les attendus ont été mesurés avec le code ci-dessus.

Les exercices 4 à 6 suivent la convention du dépôt : stubs sans erreur volontaire, la section s’exécute de bout en bout même non complétée.

# Exercice 1 : reimplanter le coeur du repair -- _update_vertex.
# La classe LPAStarEtu est une copie ou _update_vertex est vide. Completez-la pour que
# le repair retrouve l'optimalite : rhs(u) = min sur les voisins entrants de g(s') + c(s', u),
# puis (re)insertion dans U uniquement si u reste incoherent.
class LPAStarEtu(LPAStar):
    def _update_vertex(self, u):
        pass  # TODO etudiant : recalculer rhs(u) puis maintenir la file U
        return None


lp_etu = LPAStarEtu(Grid(W, H, BASE_WALLS), START, GOAL)
lp_etu.compute_shortest_path()
lp_etu.change_walls(added={blocked})
c_etu = lp_etu.compute_shortest_path()
print(f"Exercice 1 a completer : repair via _update_vertex etudiant")
print(f"Attendu : cout {c_scratch} (optimal), repair 12 expansions ; obtenu : {c_etu}")

Exercice 1 a completer : repair via _update_vertex etudiant
Attendu : cout 34 (optimal), repair 12 expansions ; obtenu : inf

# Exercice 2 : faire croitre la dette du repair nave -- position du blocage.
# Bloquez la cellule plan_init[k] pour k dans {5, 10, 15, 20} et mesurez la dette
# (cout naif - optimal scratch) a chaque fois : ou l'obstacle fait-il le plus mal ?
dettes = {}
for k in (5, 10, 15, 20):
    pass  # TODO etudiant : bloquer plan_init[k], calculer naif et optimal, stocker la dette
print("Exercice 2 a completer : dette du repair nave selon la position du blocage")
print(f"Attendu : une dette non nulle sur au moins une position (mesure : "
      f"k=10 donne +{c_naif - c_scratch}) ; obtenu : {dettes}")

Exercice 2 a completer : dette du repair nave selon la position du blocage
Attendu : une dette non nulle sur au moins une position (mesure : k=10 donne +2) ; obtenu : {}

# Exercice 3 : la clause d'arret. Combien d'expansions le test k_top >= key(goal)
# evite-t-il ? Executez la propagation SANS la clause (propagez TOUTES les incoherences
# restantes de U) puis comparez le nombre d'expansions a celui du repair standard.
exp_avec_arret = None   # TODO etudiant : e_repair du carnet (ou re-mesurez-le)
exp_sans_arret = None   # TODO etudiant : compter les expansions en vidant U entierement
print("Exercice 3 a completer : expansions evitees par la clause d'arret")
print(f"Attendu : arret des le but coherent (12 expansions) vs vidage complet plus couteux")

Exercice 3 a completer : expansions evitees par la clause d'arret
Attendu : arret des le but coherent (12 expansions) vs vidage complet plus couteux

Exercice 4 — généraliser la preuve de non-recollabilité

La fonction count_global_numberings énumère les étiquetages injectifs pour trois fenêtres. Généralisez-la à k fenêtres et m portails (indice : seul le graphe des contraintes change, pas l’énumération).

# Exercice 4 -- a completer
def count_global_numberings_k(portals, tables):
    """tables : liste de (z_from, z_to, binding) pour k fenetres.
    Retourne le nombre d'etiquetages injectifs coherents avec toutes les tables."""
    print("Exercice a completer")
    # TODO etudiant : enumerer les etiquetages injectifs et compter les coherents
    pass

count_global_numberings_k(PORTALS, [("A", "B", pi_AB_idx), ("B", "C", pi_BC_idx), ("C", "A", pi_CA_idx)])

Exercice a completer

Exercice 5 — un second jeu de portails

Ajoutez le portail (4,5) (le centre du bloc ABC) et recomposez σ avec la table croisée d’origine : que devient la notation cyclique ? (indice : le nouveau portail est un point fixe de π_AB si la table l’associe à lui-même.)

# Exercice 5 -- a completer
def sigma_avec_portail_central():
    """Recompose sigma apres ajout du portail (4,5), tables d'origine (croisee incluse).
    Retourne la notation cyclique, ou None si non implemente."""
    # TODO etudiant : reconstruire numbering/by_num avec le portail supplementaire,
    # etendre les tables d'integration (le portail central s'associe a lui-meme), recomposer
    return None  # TODO etudiant

print("Exercice a completer :", sigma_avec_portail_central())

Exercice a completer : None

Exercice 6 — que fallait-il vérifier par paires ?

# Exercice 6 -- a completer
# Quel test par paires aurait detecte le croisement ICI, et pourquoi il ne suffit pas en general ?
# Reponse attendue (ecrite en commentaire) puis, si vous voulez le mesurer :
# comparerez les profils dists["A"][p][*] et dists["B"][pi_AB_idx(...)][*].
profils_coherents = None  # TODO etudiant : True/False apres mesure des profils A vs B
print("Exercice a completer")

Exercice a completer

Conclusion

Ce carnet a attesté la seconde occurrence de l’opération 6 — « réparer localement sous garantie » — sur le substrat recherche de chemin, avec les trois témoins exigés par la table :

1. La garantie transportée : coût LPA* = coût A* from scratch à chaque étape d’une séquence de 8 changements (8/8 concordances) ;
2. La localité payée juste : 12 expansions pour le repair contre 273 pour le ré-apprentissage complet (23×), budget cumulé minoré sur la séquence (9 contre 2258) ;
3. Les contre-témoins : le repair naïf perd la garantie (dette mesurée, chemin valide non optimal) ; l’absence de propagation rend l’état interne faux (plan traversant un mur, coût affirmé sans chemin réel).

La première attestation est le binôme GT-13b/13c (Safe Subgame Solving) : réparer la stratégie dans un sous-jeu en préservant la non-exploitabilité. Deux substrats indépendants, même patron — l’opération 6 reste en table avec deux attestations.

Position dans la série : ce carnet approfondit Search-03 (A*) — il suppose la file de priorité, l’heuristique admissible et la garantie d’optimalité d’A* acquis. Il fait suite aux approfondissements Search-11d (descente sous budget), Search-12a (composer des regards) et Search-13a (traverser des murs certifiés), seconds témoins des opérations 11, 12 et 13 de la table des opérations (EPIC #12204).

Référence : Sven Koenig & Maxim Likhachev, D* Lite, AAAI 2002 — la version déplacement (but fixe, départ mobile) de LPA*, citée ici comme prolongement naturel pour l’observation partielle.

Ce que la section « recoller » ajoute

La garantie de LPA* portait sur un plan ; la section « recoller » la transporte sur un objet — la colle de tables locales. Elle vérifie la loi de l’opération 5 dans les deux sens : violée avec preuve d’inexistence du recollement (énumération exhaustive des étiquetages : 0/24 cohérent), puis réparée avec exhibition de l’objet global (24/24). Le témoin est celui qu’exige la Tombée 3 — exploitable, pas le résidu : une marche de méidentification exécutée pas à pas sur la grille, qui traverse son but et le dépasse en croyant arriver. Le contrat faible (chaque table est une bijection, la couverture est complète) est satisfait dans les deux cas : c’est la composition sur les triples qui tranche, et c’est précisément ce que personne n’écrit.

Navigation : << Search-03e — optimalité de A* | Index | retour au parent Search-03 (A*) ↑