Une classe traitable de problèmes dePlanification temporelle

Martin Cooper, Florian Franc, Frédéric Maris, Pierre Régnier

IRIT, Université Paul Sabatier, Toulouse

1

� Planification en IA

� Planification temporelle

� Complexité de la planification

� Une classe traitable pour la planification temporelle

� Définitions

� Détection de la monotonie

� Conclusion/Perspectives

2

Représentation de l’état initial

Représentation du but

Représentation des actions

Plan-solution

(Ensemble organisé d’actions)

3

� Cadre classique de la planification :◦ Monde totalement observable, pas d’incertitude

◦ Actions instantanées, discrètes, déterministes

A

P1

P2

< Conditions > < Effets >

E1

E2

¬E3

4

� Cadre temporel (PDDL 2.1) :� Actions avec durée (duration)

� Conditions

� at start

� at end

� over all

� Effets

� at start

� at end

A [durée]

P1

P3

P2

E1 E2

5

� Cas général : non soluble en temps polynomial

� Planification propositionnelle : PSPACE-complète

� Planification temporelle PDDL 2.1 :

� test de l’existence d’un plan valide EXPSPACE-complet

� PSPACE-complète lorsque différentes instances d’une même action ne peuvent se chevaucher

6

� Soluble en temps O(n3) et en espace O(n2), où n est le nombre total d’événements des actions de A

� Un plan temporel optimal en nombre d’actions peut être trouvé avec la même complexité

7

Ensemble des sousEnsemble des sousEnsemble des sousEnsemble des sous----butsbutsbutsbuts

Etant donné un problème de planification temporelle <I,A,G>, l’ensemble l’ensemble l’ensemble l’ensemble SgSgSgSg des sousdes sousdes sousdes sous----buts buts buts buts est le sous-ensemble minimal de Cond(A) ∪ G qui satisfait :

� G ⊆ Sg et

� pour toute action a ∈ A, si Add(a) ∩ (Sg\I) ≠ ∅,

alors Cond(a) ⊆ Sg.

Ensemble d’actions réduitEnsemble d’actions réduitEnsemble d’actions réduitEnsemble d’actions réduit

L’ensemble d’actions réduit L’ensemble d’actions réduit L’ensemble d’actions réduit L’ensemble d’actions réduit est ArArArAr = {a ∈ A | Add(a) ∩ (Sg\I) ≠ ∅}

8

EtablisseurEtablisseurEtablisseurEtablisseur----uniqueuniqueuniqueunique

Un ensemble d’actions A={a1,...,an}

est etablisseuretablisseuretablisseuretablisseur----uniqueuniqueuniqueunique relativement

à un ensemble de fluents S si aucun

fluent de S ne peut être établi par

deux actions distinctes de A

9

AAAA

CCCC

DDDD

w

y

BBBB

EEEE

z

FFFF

x

Monotonie d’un fluent fMonotonie d’un fluent fMonotonie d’un fluent fMonotonie d’un fluent f

� f est –monotone pour un problème de planification <I,A,G> si, après avoir été détruit, f n’est jamais ré-établi dans aucun plan temporel

� f est +monotone si, après avoir été établi, il n’est jamais détruit dans aucun plan temporel pour <I,A,G>

10

Monotonie d’un fluent fMonotonie d’un fluent fMonotonie d’un fluent fMonotonie d’un fluent f

� Exemples de – monotonie

� vivante (une personne)

� jamais-utilisée (une allumette)

� Exemples de + monotonie

� diplômée (une personne)

� explosé (un ballon)

� mangé (un plat)

11

Planification Temporelle

Ar EtablisseurUnique

+Monotonie de Sg

Ar Etablisseur Unique+

Monotonie de Sgdétectable par nos

règles

12

� Soit Π la classe des problèmes de planification temporelle <I,A,G> dans lesquels : � Ar est établisseur-unique relativement à Sg

� tous les fluents dans Sg sont monotones

� tous les fluents dans I ∩ Sg sont −monotones

� la monotonie des fluents peut être détectée en appliquant les règles suivantes règles suivantes règles suivantes règles suivantes jusqu’à convergence

Alors Π est traitable

13

Règle 1Règle 1Règle 1Règle 1

� S’il n’existe pas d’actions a, a′ ∈ Ar telles que f ∈ Del(a) ∩ Add(a′) alors f est à la fois +monotone et −monotone

14

af

p

f

a

¬f ¬p

Règle 2Règle 2Règle 2Règle 2

=> f est - monotone

15

Soit af l’unique action qui établit le fluent f ∈ Sg. Si pour toute a ∈ Ar telle que f ∈ Del(a) :

1) ∃ un fluent −monotone p ∈ Del(a) ∩ Cond(af) tel queτ(a → ¬p) − τ(a → ¬f) ≤ τ(p →| af) − τ(af → f) ou

2) …3) …4) …

Règle 3Règle 3Règle 3Règle 3

a

p

¬f

af

f ¬p

=> f est + monotone

16

Soit af l’unique action qui établit le fluent f ∈ Sg. Si pour toute a ∈ Ar telle que f ∈ Del(a) :

1) ∃ un fluent −monotone p ∈ Cond(a) ∩ Del(af) tel que τ(af → ¬p) − τ(af → f) ≤ τ(p →| a) − τ(a → ¬f) ou

2) …3) …4) …

� Pour trouver un plan (optimal) il faut résoudre un ensemble de contrainte de la forme :

� a ≤ Xi – Xj ≤ b

� Xi – Xj ≠ c

� Donc STP≠ : résolution en temps O(n3) et espace O(n2) [Gerevini & Cristani, 2007]

17

18

Available(s)

Available(water)

Mixed(p1,p2)

ACTIVATE(s)[22]

CATALYZE(p1,s,c1)[8]

MIX(p1,p2)[5]

SYNTHESIZE(p1,c1)[6]REACT(p1,p2,s)[5]

Catalyzing(p1,c1) ¬Catalyzing(p1,c1)End-Catalyze(p1)

Reacting(s)

Reacting(s)

Catalyzing(p1,c1)

Synthesized(p1)

CATALYZE(p2,s,c2)[8]

SYNTHESIZE(p2,c2)[6]

Catalyzing(p2,c2) ¬Catalyzing(p2,c2)

End-Catalyze(p2)

Reacting(s)

Synthesized(p2)

Catalyzing(p2,c2)

End-Catalyze(p1)

End-Catalyze(p2)

Synthesized(p1)

Synthesized(p2)

Mixed(p1,p2)

Reacted(p1,p2)

Reacting(s)

¬Available(s)

¬Reacting(s)

¬Available(c1)

Available(c2)

¬Available(c2)

Available(c1)

19

ACT-S ACT-E

CA1-S CA1-E

CA2-S CA2-E

SY1-S SY1-E

SY2-S SY2-E

MIX-S MIX-E REA-E

[8,8]

[8,8]

[6,6]

[22,22]

[6,6]

REA-S

[0,+∞[

[0,+∞[

[0,+∞[

[0,+∞[

[0,+∞[

[5,5]

[5,5]

[0,+∞[[0,+∞[

[0,+∞[

[0,+∞[[0,+∞[

[0,+∞[

[0,+∞[

[0,+∞[

[0,+∞[[0,+∞[

� Obtention d’une première classe traitable pour la planification temporelle

� Des problèmes courants rentrent dans cette classe

� Différentes applications

20

Planification Temporelle

Ar Etablisseur Unique+

Monotonie de Sg

Ar Etablisseur Unique+

Monotonie de Sgdétectable par nos

règles

21