View
1
Download
0
Category
Preview:
Citation preview
Algorithmique pour QBF
Florian LETOMBECRIL, CNRS FRE 2499
Plan
• Introduction• Présentation des QBFs• Prouveurs QBF et méthodes existantes
– État de l’art des prouveurs– Méthodes générales d’élagage/évaluation– Méthodes spécifiques à certains prouveurs
• Expérimentations• Conclusion
QBF : définition formelle
• Une QBF a la forme :
!nn XQXQ K11
• X1…Xn ensembles de variables propositionnelles• Φ formule propositionnelle construite sur ces
variables• Qi (1 ≤ i ≤ n) un quantificateur existentiel (∃) ou
universel (∀)
Validité de QBF( )
!"
#$%
&
''¬
(')*)
)( cba
bacba
Existenced’unestratégiegagnantedans un jeucontre lanature
⊥
a
c
b b
T
T ⊥
T
Intérêts théoriques et pratiques• Connaître la validité d’une QBF est un
problème PSPACE-complet• Réduction depuis de nombreux problèmes
d’intelligence artificielle– Planification– Raisonnements non monotones– Abduction– Etc ...
QBF = langage pivot
Problèmed’inférence,
prise dedécision
QBF SolutionRéduction Test de
validité
Interprétation
État de l’art des prouveurs QBF
• QKN : H. Kleine-Büning, M. Karpinski etA. Flögel (1995)
• Evaluate : M. Cadoli, A. Giovanardi, et M.Schaerf (1998)
• Decide : J. Rintanen (1999)• Qsolve : R. Feldmann, B. Monien et S.
Schamberger (2000)
État de l’art des prouveurs QBF(Suite)
• QuBE : E. Giunchiglia, M. Narizzano et A.Tacchella (2001)
• Semprop : R. Letz (2001)• Quaffle : L. Zhang et S. Malik (2002)
Méthodes généralesd’élagage/évaluation
• DPLL• Élimination des ∀-variables internes• Fausseté triviale (sur des ensembles de
variables)• Vérité triviale
Séparation des ensembles devariables
• Σ : union de tous les ensembles de ∃-variables
• Π : union de tous les ensembles de ∀-variables
Exemple
!!!
"
#
$$$
%
&
'¬(¬'¬'(¬(
'¬'(('¬'
)*)*
=
)]()()(
)()()[(
121122
1211111
zyxwyx
zwwyzyx
XYWZ
F
{ }{ }2121
211
,,,
,,
xxwwXW
yyzYZ
=!="
=!=#
Séparation des ensembles declauses
• H(Σ) : clauses dans lesquelles seules lesvariables de Σ (existentielles) apparaissent
• G(Π) : clauses dans lesquelles seules lesvariables de Π (universelles) apparaissent
• L(Σ,Π) : toutes les autres clauses
Exemple (suite)
Toute formule QBF F peut s’écrire :
!!"
#$$%
&
'()')(=
),()()(
11
LGH
XQXQF
nnK
Exemple (suite et fin)
)()()( 121 zyyH !¬"=#
!!!
"
#
$$$
%
&
¬'¬'(
'¬'(
'¬'
=)*
)(
)(
)(
),(
112
121
111
xwy
zww
zyx
L
)()( 2xG ¬=!
DPLL [DLL62]• DPLL(F) :
Simplifier(F)Si F est trivialement SAT alors
Retourner VraiSi F est trivialement UNSAT alors
Retourner Fauxl <- choix de littéralSi DPLL(Fl) alors
Retourner VraiRetourner DPLL(F ¬l)
DPLL (suite)
!"
#$%
&
'¬((
(('¬=
)()(
)()()(
121
2111
0zyy
yzzyF
Branchement sur z1,F devient : !
"
#$%
&
'=
)(
)(
1
2
0y
yF
Pour que F0 soit vraie, il faut que y2 et y1 soientvérifiés
Élimination des ∀-variablesles plus internes
!!!
"
#
$$$
%
&
'¬(¬'¬'(¬(
'¬'(('¬'
)*)*
=
)]()()(
)()()[(
121122
12111111
zyxwyx
zwwyzyx
XYWZ
F
!!!
"
#
$$$
%
&
'¬(¬'()(
'¬'(('¬
*+*
,
)]()(
)()()[(
1212
1211111
zywy
zwwyzy
YWZ
F
Fausseté triviale sur Π• Une QBF F est fausse si G’(Π)≠∅,
où G’(Π) est obtenu à partir de G(Π) auquelon retire les clauses tautologiques
!!"
#$$%
&
'()(=
),()(
11
LH
XQXQF
nnKDonc F peut s’écrire :
• La QBF F1 est trivialement fausse sur Π dansnotre exemple
Fausseté triviale sur Σ
• La QBF F2 n’est pas trivialement fausse surΣ dans notre exemple
• Une QBF F est fausse si H(Σ) n’est pas satisfiable
!!!
"
#
$$$
%
&
'¬(¬'(
'¬'(('¬
)*)
=
)]()(
)()()[(
1212
1211112
zywy
zwwyzy
YWZ
F
Vérité triviale
• Une QBF F est valide si H(Σ)∧L’(Σ) estsatisfiable, où L’(Σ) est obtenu à partir deL(Σ, Π) auquel on retire toutes les variablesde Π.
• La QBF F2 est trivialement vraie sur Σ dansnotre exemple
Méthodes spécifiques à certainsprouveurs
• Q-résolution par saturation (QKN)• Backtracking (Evaluate, Decide, Qsolve,
QuBE, Quaffle)• Backjumping (QuBE, Semprop)• Apprentissage (QuBE, Semprop, Quaffle)• Inversion de quantificateurs (Decide,
Qsolve)• Échantillonnage (Decide)
Q-résolution
En deux étapes :• Simplification de la formule clause par
clause• « Confrontation » de deux clauses ayant un
littéral existentiel positif pour l’une etnégatif pour l’autre
Q-résolution (suite et fin)
!!!
"
#
$$$
%
&
'(¬'¬(¬(
¬'¬'('
)*)
=
)]()()(
)()[(
21112
121113
xzxwx
zwwzx
XZW
F
!!!
"
#
$$$
%
&
'(¬'¬(
¬(¬'('
)*)
+
)]()(
)()()[(
2111
221113
xzxw
xwwzx
XZW
F
!"""" #""" #"¬$% trivialeFaussetéresQ
zxxz 1221 )(),(
a)
b)
Backtracking
1. Simplifier la QBF F2. Si la simplification ne donne rien alors
Choisir un littéralSinon Retourner en arrière
3. Si un littéral choisi alorsEmpiler le littéral
4. Répéter étapes 1 à 3 jusqu’à une solution
Backtracking (suite)
!!!
"
#
$$$
%
&
''¬(¬'¬'(
¬(¬'¬'('¬'
)*)*
=
)]()(
)()()[(
212112
21211113
xzyxwy
xzwwzyx
YXZW
F
Backtracking (suite)Étape 1 :
!!!
"
#
$$$
%
&
'(¬'¬(¬(
¬'¬'('
)*)
=
)]()()(
)()[(
21112
12111
)1(
3
xzxwx
zwwzx
XZW
F
{ }!!!
"
#
$$$
%
&
'(¬'¬(
¬('
)*)
=+¬
)]()(
)()[(,
2111
211
)2(
3
)1(
32
xzxw
xzx
XZW
FFw
Simplification :
Choix de variable : ¬w2Empilement :
Backtracking (suite)Étape 2 :
Simplification :
Choix de variable : ¬w1
Empilement :{ }
!!!
"
#
$$$
%
&
'
¬('
)*
=+¬
)](
)()[(,
21
211
)3(
3
)2(
31
xz
xzx
XZ
FFw
!!!
"
#
$$$
%
&
'(¬'¬(
¬('
)*)
=
)]()(
)()[(
2111
211
)2(
3
xzxw
xzx
XZW
F
Backtracking (suite)Étape 3 :
Simplification :
Choix de variable : z1
Empilement :{ } !
"
#$%
&
¬
'=(
)][(,
2
2)4(
3
)3(
31x
xFFz
!!!
"
#
$$$
%
&
'
¬('
)*
=
)](
)()[(
21
211
)3(
3
xz
xzx
XZ
F
Backtracking (suite et fin)
On dépile :
Or, pour l’exploration de z1, le résultat de lasimplification de F(4) est Vrai et z1 est ∀
De plus, le résultat avec ¬z1 est contradictoire
{ })3(31,Fz
On obtient donc ⊥ pour résultat
!"
#$%
&
¬
'=
)][( 2
2)4(
3x
xF
Étape 4 :est valide
Backjumping
• Initialiser les raisons en fonction d’unrésultat (QBF valide ou non pour unecombinaison de variables)
• Si la variable dépilée est dans ces raisons Alors Retourner en arrièreSinon Continuer à dépiler (la variable
n’a pas d’importance)
Backjumping (suite)• Les trois premières étapes du backtracking
sont les même pour le backjumping
Étape 4 :{ }wr w w z! ¬ ¬
1 2 1, ,
z reason wr1. !
Empilement :{ }¬ !z
1,
Backjumping (suite et fin)Étape 5 :
{ }wr w w z! ¬ ¬ ¬1 2 1, ,
{ }¬ !z1,
On dépile :
Or backjump retourne NULL et res vaut ⊥
On obtient donc ⊥ pour résultat
Apprentissage• Une affectation L=l1;…;lm est prefix-closed
si, pour chaque li, toutes les variables plusexternes sont dans L
• « Nogoods » : L=l1;…;lm prefix-closed, lesous-ensemble de L, raison pour l’invaliditéde FL, est un Nogood
• « Goods » : L=l1;…;lm prefix-closed, lesous-ensemble de L, raison pour la validitéde FL, est un Good
Apprentissage (« Nogoods »)
!!!
"
#
$$$
%
&
¬'(¬'¬('¬
('¬'¬('
)*))
=
)()()(
)()(4
sysyzx
szyzy
syzx
F
Affectation prefix-closed : x;y;z
F4 simplifié par x;y;z est invalide
Raison pour cette invalidité : {y,z}
Donc on peut ajouter la clause (¬y ∨ ¬z) enconjonction à F4
Apprentissage (« Goods »)
!!!
"
#
$$$
%
&
'(¬''(¬'¬
(¬'¬'('¬'¬
)*))
=
)()()(
)()(5
szszyzy
syxzyx
syzx
F
Affectation prefix-closed : ¬x;¬y;z
F5 simplifiée par ¬x;¬y;z est valide
Raison pour cette validité : {¬y,z}
Donc on peut ajouter le terme (¬y ∧ z) endisjonction à F5
Inversion de quantificateurs
• Pour les formules de la forme :
• Principe : inverser les quantificateurs de Xet de Y et donner aléatoirement des valeursde vérité aux littéraux de Y
• But : obtenir des valeurs de vérité pourcertains littéraux de X par propagationunitaire
! "X Y#
Inversion de quantificateurs(suite)
!!!
"
#
$$$
%
&
'(¬'¬(¬(
¬'¬'('
)*)
=
)]()()(
)()[(
21112
12111
xzxwx
zwwzx
XZW
F
On inverse ∃W et ∀Z
Inversion de quantificateurs(suite et fin)
Posons :z1
0!
Cela force les valeurs de x1, puis w1, et enfincelle de w2 ;
Ce qui nous mène à une contradiction
On obtient donc ⊥ pour résultat
Échantillonnage
• Pour les formules de la forme :
• Principe : donner aléatoirement des valeursde vérité aux littéraux de Y
• But : détecter les littéraux erronés de X parpropagation unitaire
! "X Y#
Échantillonnage (suite)
!!!
"
#
$$$
%
&
'(¬'¬(¬(
¬'¬'('
)*)
=
)]()()(
)()[(
21112
12111
xzxwx
zwwzx
XZW
F
On choisit aléatoirement des valeurs devérité pour les variables de Z
Échantillonnage (suite et fin)
Prenons :z1
0!
Cela force les valeurs de x1, puis w1, et enfincelle de w2
Ce sont ces valeurs qui seront gardées pour cesvariables
x vrai w faux w faux1 1 2! ! !, ,
Expérimentations
• Cadre des expérimentations
• Résultats expérimentaux
• Analyse expérimentale
Cadre des expérimentations
Machine :• CPU : Pentium III (Katmai) à 450 MHz• Mémoire vive : 1GoInstances de J. Rintanen :• Bolcks world, Chain, Logn, Toilet :
planification• Logn : chaine d’implications• R3cnf : instances aléatoires (∃∀∃)
Cadre des expérimentations (suite)
Prouveurs :• Decide (Backtracking, Inversion de
quantificateurs, Échantillonnage)• Quaffle (Backtracking, Apprentissage)• QuBE (Backjumping, Apprentissage)Sur 75 instances de 6 types différents• 65 résolues par Decide, 55 par Quaffle et 52
par QuBE
Résultats expérimentaux
O0.010.04-13066Impl16
O0.000.030.08375150R3CNF_150_3_15_2.50_0.T
O778.38-39.4898921820CHAIN17v.18
N--12.7615047915BLOCKS4ii.7.2
N-227.687.7215872779BLOCKS4i.6.4
ValQuBEQuaffleDecideCLSVRSInstance
Analyse expérimentale
• QuBE plus rapide sur presque toutes lesinstances aléatoires
• Decide résout le plus grand nombred’instances
• Decide plus rapide sur la plupart desinstances (proposées par J. Rintanen)
Conclusion
• A ce jour :– 7 prouveurs QBF (plus ceux qui ne font pas
encore l’objet d’un papier)– méthodes générales d’élagage utilisables dans
tout prouveur– méthodes spécifiques à évaluer et comparer
• A venir :– un prouveur performant– de nouvelles méthodes propres à ce prouveur
Recommended