On Preferring and Inspecting Abductive Models LuísMonizPereira1 PierangeloDell’Acqua2 GonçaloLopes1 1CENTRIA-CentrodeInteligênciaArtificial UniversidadeNovadeLisboa,Portugal 2ITN-DepartmentofScienceandTechnology LinköpingUniversity,Sweden PADL’09–Savannah,Georgia-January19-20,2009 Pereira&Dell’Acqua&Lopes PADL’09 1/87 Outline Outline • Abductiveframework • Declarativesemantics • Pragmatics • Proceduralsemantics • Aposterioripreferences • Medicaldiagnosis • Moraldecisionmaking • Implementation • Conclusions Pereira&Dell’Acqua&Lopes PADL’09 2/87 AbductiveFramework Declarative Abduction and Preferences Framework (cid:4) Abductionisapowerfulmechanismtoaccountfordefeasiblereasoning andincompleteknowledge (cid:4) AbductiveLogicProgramsallowforincompletelydefinedliterals • eachabductiveliteral(abducible)canbeassumedeithertrueorfalseina 2-valuedsemantics • AbductiveLogicProgramstypicallyhaveseveralmodelsthatarederived fromtheabducedliterals (cid:4) PreferencesinLogicProgramminghavemostlybeenfocusedon: • preferencesamongrulesofatheory • preferencesovertheoryliterals Pereira&Dell’Acqua&Lopes PADL’09 3/87 AbductiveFramework Enabling Pre and Post Preferences (cid:4) Ourapproachisbasedonhandlingpreferencerelationsbetween abducibles (cid:4) Preferencesoverabduciblesareenactedbothapriorioraposterioriwrt. themodelgeneration: • apriori: toenactpreferencesduringthecomputationofthemodelsofa theory • aposteriori: toenactpreferencesonthecomputedmodelsofatheory (cid:4) Abduciblescanbeemployedasnamingdevices(cf. Poole)of,sayrules, onwhichpreferencesarethenenacted Pereira&Dell’Acqua&Lopes PADL’09 4/87 AbductiveFramework Basic Abductive Framework (cid:4) LetLbeafirstorderpropositionallanguagedefinedasfollows (cid:4) AliteralcanbeeitheranatomAoritsdefaultnegationnotA (cid:4) Aruletakestheform: A ← L ,...,L 1 t whereAisanatomandL ,...,L (t ≥ 0)areliterals 1 t (cid:4) Anintegrityconstraintisarulewhoseheadis⊥: ⊥ ← L ,...,L 1 t Pereira&Dell’Acqua&Lopes PADL’09 5/87 AbductiveFramework (cid:4) Eachprogramisassociatedwithasetofabducibles: literalswhichdonotoccurinanyrulehead (cid:4) Totestwhetheracertainabduciblehasbeenabduced,weexploitthe reservedabducible abduced(a) foreveryabduciblea (cid:54)(cid:54)= abduced(.) (cid:4) abduced(a)actsasaconstraintthatissatisfiedinthesolutionifthe abducibleaisindeedassumed (cid:4) Itcanbeconstruedasmeta-abductionintheformofabducingtocheck (orpassivelyverify)thatacertainabductionisadopted (cid:4) abduced(a)permitstocheckforside-effectsofabductionsmade Pereira&Dell’Acqua&Lopes PADL’09 6/87 AbductiveFramework Example LetPbe: p←abduced(a),a q←abduced(b) withsetofabduciblesA = {a,b,abduced(a),abduced(b)} P Phasfourintendedmodels: • M ={} 1 • M ={p,a,abduced(a)} 2 • M ={q,b,abduced(b)} 3 • M ={p,q,a,b,abduced(a),abduced(b)} 4 ∗ Theset{q,abduced(b)}isnotanintendedmodelsincetheassumption ofabduced(b)requirestheassumptionofb Pereira&Dell’Acqua&Lopes PADL’09 7/87 AbductiveFramework Hypotheses Generation (cid:4) Abduciblesextendatheoryandcanbeusedtoprovidealternative explanationsforagivenquery (cid:4) Generatingallalternativeexplanationsforaqueryisacentralproblemin abductionbecauseofthecombinatorialexplosion (cid:4) So,generateonlythoseexplanationswhicharepreferredandrelevantfor thequery Pereira&Dell’Acqua&Lopes PADL’09 8/87 AbductiveFramework Enabling the Assumption of Abducibles (cid:4) Thenotionofexpectationisemployedtoexpresspreconditionsfor enablingtheassumptionofabducibles (cid:4) Aconsideredabduciblecanbeassumedonlyifthereisanexpectation foritand,furthermore,thereisnoexpectationtothecontrary: expect(a) ← L ,...,L 1 t expect_not(a) ← L ,...,L 1 t foreveryabduciblea (cid:54)(cid:54)= abduced(.) (cid:4) Thatis,assumedabduciblesarethosewhoseconsiderationisexpected andnotdefeated Pereira&Dell’Acqua&Lopes PADL’09 9/87 AbductiveFramework ExampleLetPbe: p←a q←b expect(a) expect(b) expect_not(a)←q withA = {a,b,abduced(a),abduced(b)} P Phasthreeintendedmodels,forwheneverAbd isabduced abduced(Abd)isintendedaswell: • M ={expect(a),expect(b)} 1 • M ={p,a,abduced(a),expect(a),expect(b)} 2 • M ={q,b,abduced(b),expect(a),expect(b)} 3 ∗ Itisnotpossibletoassumebothaandbbecausetheassumptionofb makesqtruewhichinturnmakesexpect_not(a)truepreventingatobe assumed;i.e. theconsiderationofaisdefeated Pereira&Dell’Acqua&Lopes PADL’09 10/87