Intelligence artificielle : planification

Grégory Bonnet

Université de Caen Normandie - GREYC

[Link]
Plan du cours

Problèmes de planification
Contexte
Représentation des actions
Graphe, recherche et planification

Recherche non informée

Recherche en profondeur
Recherche en largeur

Recherche heuristique
Algorithme de Dijkstra
Information et heuristiques
Algorithme A∗

Recherche heuristique avancée

Recherche en faiseau
Recherche multi-crtière
Algorithme B ∗
Problèmes de planification
Rappel du contexte

Domaine
I variables d’état (ex. : ONB , FIXEDB , FREEP )
I domaines de variable booléennes (ex. : TRUE, FALSE)
I domaines de variables multi-valuées (ex. : RED, BLUE, GREEN)
I contraintes (ex. : (ONA = B) =⇒ ¬(ONB = A) ∧ FIXEDB )

Problème de satisfaction de contraintes

À partir de la description des contraintes, trouver une affectation de valeurs aux
variables (instance) telles que toutes les contraintes soient satisfaites.

Problème de satisfaction de contraintes

À partir d’une collection d’instances, trouver les règles communes d’affectation de
valeurs aux variables (ex. des contraintes).

Problème de planification
Disposant de connaissances sur des actions, d’un état de départ et d’un état à
atteindre (des instances particulières), trouver la séquence d’actions qui le permet.
Représentation des actions

Schéma d’action
Une action (ACT) est spécifiée en termes de préconditions (PRE) qui doivent être vraies
pour qu’elle puisse être exécutée et en terme d’effets (EFF) qui s’ensuivent quand elle
est exécutée.

Exemple
ACT(PUTA,B,C )
I PRE := ¬FIXEDA ∧ (ONA = B) ∧ ¬FIXEDC
I EFF := ¬(ONA = B) ∧ (ONA = C ) ∧ ¬FIXEDB ∧ FIXEDC

Exemple
ACT(TRANSLATEP,P 0 )
I PRE := ¬FREEP ∧ FREEP 0
I EFF := FREEP ∧ ¬FREEP 0 ∧ (∀A t.q.(ONA = P) : (ONA = P 0 ))

Exécuter une action

Exécuter une action A dans l’état E conduit à un état E 0 identique exceptées les
modifications provoquées par EFF(A).
Hypothèses sur les actions

Redondance des effets

Un effet ne modifie pas une variable si elle est déjà bien instanciée.

Problème du cadre
Que faire des variables qui ne sont pas spécifiées par l’action ?
I Les variables qui ne sont pas dans PRE sont ignorées : leur valeur importe peu,
I Les variables qui ne sont pas dans EFF sont ignorées : leur valeur reste inchangée.

Problème de l’applicabilité
I Une action est applicable à chaque état qui satisfait les préconditions,
I Sinon l’action n’a pas d’effet.

Problème de qualification
L’exécution d’une action réussit toujours : il ne peut pas y avoir d’échec.
Qu’est-ce qu’un problème de planification ?

Étant donné :
I une description du monde
I un état initial du monde (une instanciation complète)
I une description du but (une instanciation partielle)
I un ensemble d’actions disponibles pour changer le monde

Planification
La planification consiste à calculer une séquence d’actions permettant de passer de
l’état initial à un état qui satisfait le but.

Planification progressive ou chaînage avant

Partir de l’état initial et chercher à atteindre un état qui satisfait le but.

Planification régressive ou chaînage arrière

Part d’une spécification partielle du but et chercher à atteindre l’état initial.
Planification et graphes

Un problème de planification peut se représenter par un graphe

I Un nœud est un état du monde
I Un arc est l’application d’une action
I Un chemin entre l’état initial et un état satisfaisant le but est un plan d’actions

F ∧ B ∧ ¬A

{∅, ¬F} {¬A, ¬B}

∅
∅ ¬F ∧ B ∧ ¬A F ∧ ¬B ∧ ¬A ∅
∅

{¬A, ¬B} {∅, ¬F}

¬F ∧ ¬B ∧ ¬A
Que faut-il coder ?

satisfies(instantiation, goals)
1: return goals ⊂ instanciation

is_applicable(action, instantiation)
1: return [Link] ⊂ instanciation

apply(action, instantiation)
1: if is_applicable(action, instantation) then
2: next = new Instantiation(instantiation)
3: next = next + [Link]
4: return next
5: else
6: return new Instantiation(instantiation)
7: end if
Application à d’autres domaines

Rubik’s Cube Taquin

Recherche non informée
Recherche en profondeur

dfs(problem, instantiation, plan, closed)

Require: instantiation ← initial_state
Require: plan ← STACK<Action>({})
Require: closed ← SET<State>({initial_state})
1: if satisfies(instantiation, [Link]) then
2: return plan
3: else
4: for all action ∈ [Link] do
5: if is_applicable(action, instantiation) then
6: next ← apply(action, instantiation)
7: if not next ∈ closed then
8: push(plan, action)
9: closed ← closed ∪ next
10: subplan ← DFS(problem, next, plan, closed)
11: if not subplan = ∅ then
12: return subplan
13: else
14: pop(plan)
15: end if
16: end if
17: end if
18: end for
19: return ∅ {Can be implemented as a null object}
20: end if
Exercice : appliquez DFS

Hypothèses
I l’état initial est a et l’état but est h
I les arêtes sortantes indiquent l’action applicable dans un état
I les arêtes entrantes indiquent l’état résultant de l’application de l’action
I ex. (a, d) est l’action dans a qui conduit à d
I l’ordre des enfants d’un nœud est l’ordre alphabétique

d f h

a c

b e g
Problèmes liés à la recherche en profondeur

Problème des solutions sous-optimales

I Une branche de l’arbre peut mener au but
I Rien ne dit qu’il existe une branche plus courte
I =⇒ il existe donc un plan plus parcimonieux !

Problème des arbres de grande profondeur

L’algorithme risque de développer une branche stérile sans que le mécanisme de retour
en arrière puisse se déclencher.

Améliorations possibles : la recherche en profondeur itérative

I Profondeur maximale de récursion
I Pour X de 1 à N faire un DFS à profondeur X
I Complexité en temps : 1 + b + b 2 + . . . + b d = O(b d )
I Complexité en espace : O(b × d)
Recherche en largeur
bfs(problem)
1: father ← MAP<State, State>
2: plan ← MAP<State, Action>
3: closed ← SET<State>({problem.initial_state})
4: open ← QUEUE<State>({problem.initial_state})
5: father [problem.initial_state] ← ∅
6: if satisfies(problem.initial_state, [Link]) then
7: return {}
8: end if
9: while open 6= {} do
10: instantiation ← dequeue(open)
11: closed ← closed ∪ instantiation
12: for all action ∈ [Link] do
13: if is_applicable(action, instantiation) then
14: next ← apply(action, instantiation)
15: if not next ∈ closed and not next ∈ open then
16: father [next] ← instantiation
17: plan[next] ← action
18: if satisfies(next, [Link]) then
19: return get-bfs-plan(father , plan, next)
20: else
21: enqueue(open, next)
22: end if
23: end if
24: end if
25: end for
26: end while
27: return ∅ {Can be implemented as a null object}
Recherche en largeur

Reconstruction du plan
get-bfs-plan(father, plan, goal)
Require: father ≡ MAP<State, State>
Require: plan ≡ MAP<State, Action>
Require: goal ≡ State
1: BFS_plan ← QUEUE({})
2: while goal 6= ∅ do
3: enqueue(BFS_plan, plan[goal])
4: goal ← father [goal]
5: end while
6: return reverse(BFS_plan)

Propriétés
I L’algorithme trouve toujours le plan le plus court en premier
I Toutefois, il peut explorer inutilement des nœuds
Exercice : appliquez BFS

Hypothèses
I l’état initial est a et l’état but est h
I les arêtes sortantes indiquent l’action applicable dans un état
I les arêtes entrantes indiquent l’état résultant de l’application de l’action
I ex. (a, d) est l’action dans a qui conduit à d
I l’ordre des enfants d’un nœud est l’ordre alphabétique

d f h

a c

b e g
Recherche heuristique
Introduction du problème des coûts

Le coût d’un plan n’est pas le nombre d’action

I Une action a un coût
I le coût d’un plan est la somme du coût des actions
I =⇒ algorithme de Dijkstra

Exemples de coûts pour le Block World

I le simple fait d’agir (i.e minimiser le nombre d’actions)
I la distance entre deux piles
I la hauteur de déplacement d’un bloc

Complexité de la recherche aveugle

I O(b d )
I pouvons-nous éviter d’explorer les états inutiles ?
I =⇒ algorithme A∗
Dijkstra(problem)
Require: plan ← MAP<State, Action>
Require: distance ← MAP<State, REAL>
Require: father ← MAP<State, State>
1: goals ← ∅
2: father [problem.initial_state] ← ∅
3: distance[problem.initial_state] ← 0
4: open ← SET<State>({problem.initial_state})
5: while open 6= ∅ do
6: instantiation ← choose({x ∈ open|∀x 0 ∈ open, distance[x] ≤ distance[x 0 ]}) {fonction argmin}
7: open ← open \ {instantiation}
8: if satisfies(instantiation, [Link]) then
9: goals ← goals ∪ {instantiation}
10: end if
11: for all action ∈ [Link] do
12: if is_applicable(action, instantiation) then
13: next ← apply(action, instantiation)
14: if not next ∈ distance then
15: distance[next] ← +∞
16: end if
17: if distance[next] > distance[instantiation] + cost(action) then
18: distance[next] ← distance[instantiation] + cost(action)
19: father [next] ← instantiation
20: plan[next] ← action
21: open ← open ∪ {next}
22: end if
23: end if
24: end for
25: end while
26: if goal = ∅ then
27: return ∅ {Can be implemented as a null object}
28: else
29: return get-dijkstra-plan(father , plan, goals, distance)
30: end if
Reconstruction du plan pour l’algorithme de Dijkstra

get-dijkstra-plan(father, plan, goals, distance)

Require: father ≡ MAP<State, State>
Require: plan ≡ MAP<State, Action>
Require: goal ≡ State
Require: distance ≡ MAP<State, REAL>
1: DIJ_plan ← QUEUE({})
0 0
2: goal ← choose({x ∈ goals|∀x ∈ goals, distance[x] ≤ distance[x ]}) {fonction argmin}
3: while father [goal] 6= ∅ do
4: enqueue(DIJ_plan, plan[goal])
5: goal ← father [goal]
6: end while
7: return reverse(DIJ_plan)

Hypothèses derrière l’algorithme de Dijkstra

I Les coûts sont non négatifs
I Un sous-ensemble du plan de coût minimal est aussi de coût minimal

Propriétés
I L’algorithme retourne le plan de coût minimal
I Toutefois, il peut toujours explorer inutilement des nœuds
Exercice : appliquez l’algorithme de Dijkstra

Hypothèses
I l’état initial est a et l’état but est g ; les actions sont toujours notées (x, y )
I les arêtes sont non orientées et le coût des actions y est indiqué

8
5 b c

7
9 5

15
d e

6 9
8

11
f g
One more time with feeling !

Calculez
Le plan menant de a à c !

a b
2

5
4 5

e 5 f 9

4
4 4

d c
2
Est-ce toujours une bonne idée d’explorer les effets de certaines
actions ?

Une action qui nous éloigne du but

Une action qui est très coûteuse
Un algorithme de recherche en « meilleur d’abord »

Objectif
Rechercher une solution dans un graphe d’états à partir d’un état initial et en
explorant uniquement que les « meilleurs » chemins vers cette solution.

Meilleur = Heuristique
Soit ei un état quelconque, pour un l’état initial e0 et un but eg fixés, f (ei ) est la
valeur de cet état telle que :

f (ei ) = c(ei ) + h(ei )

I c(ei ) : coût pour aller de e0 (initial) à ei (courant)
I h(ei ) : estimation (heuristique) du coût pour aller de ei (courant) à eg (but)

Équivalence avec l’algorithme de Dijkstra

Si ∀ei ∈ V : h(ei ) = 0 alors f (ei ) = c(ei ) et A∗ fait une recherche en largeur

Équivalence avec la descente de gradient

Si ∀ei ∈ V : f (ei ) = h(ei ) alors A∗ fait une recherche en profondeur
Propriétés de l’heuristique

Admissibilité
∀e ∈ V : h(e) ≤ h∗ (e) où h∗ est l’heuristique optimale
I l’heuristique h est dite admissible si elle minore le coût réel (inconnu) du chemin
I si h est admissible alors l’algorithme retourne le meilleur chemin

Monotonie
∀ei , ej ∈ V , ej ∈ successeurs(ei ) : h(ei ) ≤ h(ej ) + c(ei , ej )
I si l’heuristique h est monotone alors elle est admissible
I et l’algorithme A∗ est de complexité linéaire

Information
∀e ∈ V : 0 ≤ h1 (e) ≤ h2 (e)
I l’heuristique h2 est dite mieux informée que h1
I plus une heuristique est informée, moins le nombre d’états explorés sera grand
Principes de l’algorithme A∗

Principes de l’algorithme A∗
I sélectionner un nœud ej dont la valeur f est minimale
I ajouter à l’espace de recherche les successeurs de ej
I conserver pour chaque nœud le meilleur chemin à partir de ei .
I l’algorithme termine dès que l’on a atteint l’un des nœuds solutions

Utilisation de files d’attente prioritaires

liste ouverte : contient tous les nœuds qui restent à évaluer
liste fermée : contient tous les nœuds qui ont été évalués

Propriété
Si l’heuristique est monotone alors il est inutile d’utiliser des listes.
Astar(problem)
Require: plan ← MAP<State, Action>
Require: father ← MAP<State, State>
Require: distance ← MAP<State, REAL>
Require: value ← MAP<State, REAL>
1: open ← SET<State>({problem.initial_state})
2: father [problem.initial_state] ← ∅
3: distance[problem.initial_state] ← 0
4: value[problem.initial_state] ← heuristic(problem.initial_state)
5: while open 6= ∅ do
6: instantiation ← choose({x ∈ open|∀x 0 ∈ open, value[x] ≤ value[x 0 ]}) {fonction argmin}
7: if satisfies(instantiation, [Link]) then
8: return get-bfs-plan(father , plan, instantiation)
9: else
10: open ← open \ {instantiation}
11: for all action ∈ [Link] do
12: if is_applicable(action, instantiation) then
13: next ← apply(action, instantiation)
14: if not next ∈ distance then
15: distance[next] ← +∞
16: end if
17: if distance[next] > distance[instantiation] + cost(action) then
18: distance[next] ← distance[instantiation] + cost(action)
19: value[next] ← distance[next] + heuristic(next)
20: father [next] ← instantiation
21: plan[next] ← action
22: open ← open ∪ {next}
23: end if
24: end if
25: end for
26: end if
27: end while
28: return ∅ {Can be implemented as a null object}
Exercice : heuristiques admissibles

Une heuristique possible

Soit l’heuristique h1 qui associe à chaque état le nombre de blocs mal placés, i.e. qui
ne se trouvent pas sur le bon bloc ou la bonne pile (ONB est incorrect).

Questions
1. Démontrez que h1 est admissible,
2. Trouver une heuristique admissible h2 plus informée que h1 .
Exercice : appliquez A*

Considérez le problème suivant

I soit des états décrits par un ensemble V de 4 variables booléennes : a, b, c, d
¯ l’état initial
I soit {ā, b̄, c̄, d}
I soit {a, b, c, d} l’état but
I soit l’heuristique h qui associe à chaque état le nombre de variables à faux

Actions
I ∀v ∈ V : Sv : (PRE = >, EFF = {v }) coûtant 1
I D1 : (PRE = >, EFF = {a, b}) coûtant 1,5
I D2 : (PRE = >, EFF = {c, d}) coûtant 1,5
I T1 : (PRE = >, EFF = {a, b, c}) coûtant 4
I T2 : (PRE = >, EFF = {b, c, d}) coûtant 4
One more time with feeling !

Calculez
I Le plan menant de a à c !
I La valeur heuristique est indiquée à coté de l’identifiant du nœud

(a, 3) (b, 2)
2

5
4 5

(e, 4) 5 (f , 1) 9

4
4 4

(d, 2) (c, 0)
2
Recherche heuristique avancée
Algorithme de recherche en faiseau (ou beam search)

Problème
Si A∗ ne développe pas systématiquement l’arbre de résolution, le nombre de nœuds
ouverts peut devenir prohibitif.

Solution
Ne conserver dans les ouverts que les k meilleurs nœuds

Propriétés
I perte de la complétude et de l’optimalité
I si k → ∞ alors la recherche en faiseau se comporte comme A∗

Variante avec approfondissement itératif

I initaliser k avec une petite valeur
I en cas d’échec, recommencer avec k = k + ∆
Algorithme A∗ multi-critère

Fonction d’évaluation
f : V 7−→ Rk (idem pour c et h)
f =g ⊕h

Exemple d’opérateur de comparaison entre deux états ei et ej

I minoration

ei  ej si, et seulement si, min f n (ei ) < min f n (ej )

n∈[1,k] n∈[1,k]

I somme pondérée
X X
ei  ej si, et seulement si, ωn f n (ei ) < ωk f n (ej )
n∈[1,k] n∈[1,k]

I ordre lexicographique

ei  ej si, et seulement si, ∃n ∈ [0, k] : f 1..n (ei ) = f 1..n (ej ) ∧ f n+1 (ei ) < f n+1 (ej )
Algorithme B ∗

Principe
Les nœuds sont évalués par des intervales plutôt que par des valeurs singletons.

Fonction d’évaluation
f : V → R2 (aussi noté (f− , f+ ) )

Règles d’évaluation
1. évaluer les successeurs d’un nœud dans un ordre arbitraire
2. f− (successeurs(ei )) > f− (ei ) =⇒ f− (ei ) ← f− (successeurs(ei ))
3. f+ (ei ) > f+ (successeurs(ei )) =⇒ f+ (ei ) ← f+ (successeurs(ei ))

Condition d’arrêt
Un successeur a une valeur pessimiste supérieure aux valeurs optimistes des autres
successeurs
Conclusion
Conclusion

Les problèmes de planification peuvent être modélisés par des graphes

Problème de planification
canonique : graphe entièrement connu (connaissance parfaite)
coûts fixes (statique)
exploration : graphe découvert au fur et à mesure (connaissance imparfaite)
coûts variables (dynamique)

Algorithme A∗
I généralisation de l’algorithme de Dijkstra
I recherche en « meilleur d’abord » selon une fonction heuristique
I de nombreuses variantes (recherche en faiseau, recherche frontalière, etc.)
Bibliographie

Jean-Marc Aliot, Thomas Schiex, Pascal Brisset et Frédérick Garcia

Intelligence artificielle et informatique théorique
Cépaduès, 2007.
Stuart Russell et Peter Norvig
Intelligence artificielle
Pearson, 2010.
Amit Patel
Red Blob Games
[Link]
2017.