Comprendre Graphe de planification
Un graphe de planification alterne niveaux d’états et niveaux d’actions. Le premier niveau d’états contient les littéraux de l’état initial ainsi que la négation de chaque atome mentionné par le domaine et omis par l’état initial. Chaque niveau d’actions contient toute action dont les préconditions sont toutes présentes et deux à deux compatibles au niveau d’états précédent, plus une action de persistance pour chaque littéral, qui se borne à le reporter. Le niveau d’états suivant contient tout littéral produit par une action de ce niveau d’actions. La construction est polynomiale en la taille du problème et ne comporte aucune recherche, et c’est ce qui rend la structure abordable comme source d’heuristiques.
Un niveau n’affirme pas que tout ce qu’il contient puisse tenir simultanément, et les liens d’exclusion mutuelle consignent là où ce n’est pas le cas. Deux actions sont mutuellement exclusives si elles ont des effets incompatibles, c’est-à-dire si l’une retire ce que l’autre ajoute ; si elles interfèrent, c’est-à-dire si l’une retire une précondition de l’autre ; ou si elles ont des besoins concurrents, c’est-à-dire des préconditions mutuellement exclusives au niveau précédent. Deux littéraux sont mutuellement exclusifs si l’un est la négation de l’autre, ou si toute paire d’actions les produisant est elle-même mutuellement exclusive. Ces conditions sont locales et peu coûteuses, et c’est précisément pourquoi l’approximation qui en résulte est unilatérale.
En faisant croître le graphe, on finit par produire un niveau identique à son prédécesseur, tant par ses littéraux que par ses exclusions mutuelles ; le graphe s’est alors stabilisé et aucun niveau supplémentaire ne peut ajouter d’information. Le coût de niveau d’un littéral est l’indice du premier niveau où il apparaît, et comme un littéral absent au niveau i est véritablement inatteignable en i étapes, les coûts de niveau sont des bornes inférieures. Cela donne trois heuristiques pour un but conjonctif : le coût de niveau maximal parmi les littéraux du but, leur somme, et le niveau d’ensemble, c’est-à-dire le premier niveau où ils apparaissent tous sans qu’aucune de leurs paires y soit mutuellement exclusive.
Max-niveau et niveau d’ensemble sont admissibles, et le niveau d’ensemble domine max-niveau parce qu’il exige de surcroît que les buts soient conjointement compatibles. Somme-des-niveaux additionne les coûts de niveau comme si les sous-buts étaient indépendants et peut donc surestimer, ce qui la rend inadmissible en général, bien qu’elle soit fréquemment la plus informative des trois en pratique. Le graphe soutient également GraphPlan, qui parcourt les niveaux à rebours pour en extraire directement un plan, au lieu de n’user de la structure que pour noter des états.
Comment calculer
levelcost(l) = min{ i : l ∈ S_i }; setlevel(g) = min{ i : g ⊆ S_i, no pair of g mutex at S_i }
où
- S_i
- les littéraux du i-ème niveau d’états du graphe
- l
- un littéral isolé dont on mesure la première apparition possible
- g
- le but conjonctif, traité comme un ensemble de littéraux
- mutex
- une paire consignée dont on prouve qu’elle ne peut tenir ensemble à ce niveau
Exemple : Graphe de planification
Dans le problème « avoir le gâteau et le manger aussi », S0 contient Have(Cake) et ¬Eaten(Cake) sans aucune exclusion mutuelle. Bake ne peut figurer au premier niveau d’actions parce que sa précondition ¬Have(Cake) n’y est pas encore présente.
En S1, les quatre littéraux sont présents avec quatre paires mutuellement exclusives. Have(Cake) et Eaten(Cake) sont mutuellement exclusifs parce que leurs seuls producteurs sont l’action de persistance de Have et Eat(Cake), et qu’Eat retire Have, ce qui est une interférence.
L’exclusion mutuelle disparaît en S2, où le graphe se stabilise. Max-niveau et somme-des-niveaux renvoient toutes deux 1, le niveau d’ensemble renvoie 2, et le plan optimal - manger le gâteau, puis en cuire un autre - est bien de longueur 2 : seul le niveau d’ensemble est ici exact.
Avantages et inconvénients
Avantages
- Construit en temps polynomial et sans recherche, si bien que le coût de l’heuristique reste très en deçà du coût de la planification.
- Le raisonnement par exclusion mutuelle saisit entre sous-buts des interactions que les heuristiques littéral par littéral manquent systématiquement.
- Fournit toute une famille d’heuristiques à partir d’une seule structure, avec un ordre d’admissibilité clair entre elles.
Inconvénients
- Défini pour des problèmes propositionnels : un domaine décrit par schémas doit d’abord être instancié, ce qui peut coûter cher.
- L’approximation est unilatérale : l’absence prouve l’inatteignabilité, mais la présence ne prouve rien.
- Seules les exclusions mutuelles par paires sont calculées, si bien que les incompatibilités plus larges, entre trois littéraux ou davantage, passent inaperçues.
Questions fréquentes
Pourquoi le graphe inclut-il des actions de persistance ?
Sans elles, un littéral vrai à un niveau pourrait disparaître au suivant simplement parce qu’aucune action ne se trouve le reproduire. Une action de persistance, parfois appelée no-op, prend le littéral à la fois comme précondition et comme effet, ce qui le reporte et permet au raisonnement par exclusion mutuelle de traiter ce report comme un choix en concurrence avec les autres actions.
Que veut dire se stabiliser, et pourquoi cela arrive-t-il ?
Les niveaux sont monotones : les littéraux s’accumulent et les exclusions mutuelles ne font que disparaître. Les deux étant bornés, le processus doit atteindre un niveau identique à son prédécesseur en littéraux comme en exclusions mutuelles, après quoi tout niveau ultérieur lui est identique également. C’est le point où plus aucune information ne peut être tirée du graphe.
Si somme-des-niveaux est inadmissible, pourquoi s’en servir ?
L’admissibilité garantit l’optimalité mais ne dit rien de la vitesse, et max-niveau est souvent si faible que la recherche en devient impraticable. Somme-des-niveaux est d’ordinaire bien plus proche du coût véritable, si bien qu’un planificateur prêt à renoncer à la garantie d’optimalité résout fréquemment des problèmes hors de portée des heuristiques admissibles.
En résumé
Un graphe de planification achète de l’information sur un problème difficile en résolvant exhaustivement, plutôt qu’approximativement, une relaxation bon marché de ce problème. Les liens d’exclusion mutuelle en sont la substance : ils transforment un décompte naïf d’atteignabilité en une structure qui remarque quand deux buts se gênent l’un l’autre, ce qui est exactement le mode de défaillance qui coule les heuristiques de planification plus simples.